<?php

/**
 * THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 * @package fusionLib
 * @copyright Copyright (c) 2008 - 2016 fusionLib. All rights reserved.
 * @link http://fusionlib.com
 */

/**
 * flDbNestedSet Class
 *
 * Class to implement nested set within the database.
 *
 * @package fusionLib
 */
class flDbNestedSet {

	/**#@+
	 * Locations.
	 */
	const BEFORE = 0;
	const AFTER = 1;
	const UNDER = 2;
	/**#@-*/

	/**
	 * The database object to use.
	 *
	 * @var flDb
	 */
	protected $db;

	/**
	 * The database table name.
	 *
	 * @var string
	 */
	protected $table;

	/**
	 * The lock count.
	 *
	 * @var int
	 */
	protected $lockCount = 0;

	/**
	 * The name of the ID field.
	 *
	 * @var string
	 */
	protected $idField;

	/**
	 * Construct the object.
	 *
	 * @param flDb $db The database object.
	 * @param string $table The name of the table.
	 * @param string $idField The name of the ID field.
	 */
	function __construct($db, $table, $idField = 'id') {
		$this->db = $db;
		$this->table = $table;
		$this->idField = $idField;
	}

	/**
	 * Lock the table.
	 */
	function lock() {
		if(!$this->lockCount++)
			$this->db->query("LOCK TABLE $this->table WRITE");
	}

	/**
	 * Unlock the table.
	 */
	function unlock() {
		if(!--$this->lockCount)
			$this->db->query('UNLOCK TABLES');
	}

	/**
	 * Insert a new child node before or after the given node.
	 *
	 * @param int $id The node to insert the child before or after.
	 * @param enum $where One of BEFORE, AFTER or UNDER.
	 * @param array $data Array of name => value pairs of the field data to set.
	 * @return int ID of the new node or false if not added.
	 */
	function insertNode($id, $where, $data = array()) {
		$r = false;
		$lft = null;

		$this->lock();

		if($where == self::UNDER && !$id) {
			if(!($lft = $this->db->fetchOne("SELECT MAX(rgt) FROM $this->table")))
				$lft = 1;
			else
				$lft++;
			$parentid = $id;
		}
		else if(($node = $this->db->fetchRow("SELECT parentid,lft,rgt FROM $this->table WHERE $this->idField=?", $id)) !== null) {
			$lft = $where == self::BEFORE ? $node['lft'] : $node['rgt'] + ($where == self::AFTER ? 1 : 0);
			$parentid = $where == self::UNDER ? $id : $node['parentid'];
		}

		if($lft) {
			$this->db->query("UPDATE $this->table SET lft=IF(lft>=?, lft+2, lft), rgt=IF(rgt>=?, rgt+2, rgt) WHERE rgt >= ?", $lft, $lft, $lft);
			$rgt = $lft + 1;
			$data = array_merge($data, array('lft' => $lft, 'rgt' => $rgt, 'parentid' => $parentid));
			if($this->db->query("INSERT INTO $this->table (" . join(',', array_keys($data)) . ',lftrgtset) VALUES (' . substr(str_repeat('?,', count($data)), 0, -1) . ",LineString(Point(-1, $lft), Point(1, $rgt)))", $data)) {
				$r = $this->db->insertID();
				$this->db->query("UPDATE $this->table SET lftrgtset=LineString(Point(-1,lft), Point(1, rgt))");
			}
		}

		$this->unlock();

		return $r;
	}

	/**
	 * Delete the node and all child nodes.
	 *
	 * @param int $id The ID of the node to delete.
	 */
	function deleteNode($id) {
		$this->lock();

		if(($node = $this->db->fetchRow("SELECT lft,rgt FROM $this->table WHERE $this->idField=?", $id)) !== null) {
			$this->db->delete($this->table, 'lft BETWEEN ? AND ?', $node['lft'], $node['rgt']);
			$d = ($node['rgt'] - $node['lft']) + 1;
			$this->db->query("UPDATE $this->table SET lft=IF(lft>?,lft-$d,lft), rgt=IF(rgt>?,rgt-$d,rgt) WHERE rgt>?", $node['lft'], $node['lft'], $node['rgt']);
			$this->db->query("UPDATE $this->table SET lftrgtset=LineString(Point(-1,lft), Point(1, rgt))");
		}

		$this->unlock();
	}

	/**
	 * Move a node before/after another node.
	 *
	 * @param int $id The ID of the node to move.
	 * @param int $nodeId The ID of the node to move before/after or make the parent of $id.
	 * @param enum $where One of BEFORE, AFTER or UNDER.
	 * @return bool true of the node was moved; else false.
	 */
	function moveNode($id, $nodeId, $where) {
		$r = false;
		$this->lock();

		$ns = $this->db->fetchRow("SELECT lft,rgt FROM $this->table WHERE $this->idField=?", $id);
		if($where == self::UNDER && !$nodeId)
			$np['lft'] = $this->db->fetchOne("SELECT MAX(rgt) FROM $this->table");
		else
			$np = $this->db->fetchRow("SELECT parentid,lft,rgt FROM $this->table WHERE $this->idField=?", $nodeId);

		if($ns !== null && $np !== null && ($np['lft'] < $ns['lft'] || $np['lft'] > $ns['rgt'])) {
			if($where == self::UNDER) {
				$parentid = $nodeId;
				$t = $np['lft'] + 1;
			}
			else {
				$parentid = $np['parentid'];
				$t = $where == self::AFTER ? $np['rgt'] + 1 : $np['lft'];
			}

			// Calc size of block being moved
			$ms = ($ns['rgt'] - $ns['lft']) + 1;

			// Calc delta to move source by & move
			if(($d = $t - $ns['lft']) < 0) {
				$d -= $ms;
				$ns['lft'] += $ms;
				$ns['rgt'] += $ms;
			}

			// Make space, move node to new location, close gap, update parent
			$this->db->query("UPDATE $this->table SET lft=IF(lft>=?, lft+$ms, lft), rgt=IF(rgt>=?, rgt+$ms, rgt) WHERE rgt >= ?", $t, $t, $t);
			$this->db->query("UPDATE $this->table SET lft=lft+$d,rgt=rgt+$d WHERE lft BETWEEN ? AND ?", $ns['lft'], $ns['rgt']);
			$this->db->query("UPDATE $this->table SET lft=IF(lft>?,lft-$ms,lft),rgt=IF(rgt>?,rgt-$ms,rgt) WHERE rgt>?", $ns['lft'], $ns['lft'], $ns['lft']);
			$this->db->query("UPDATE $this->table SET parentid=? WHERE $this->idField=?", $parentid, $id);
			$this->db->query("UPDATE $this->table SET lftrgtset=LineString(Point(-1,lft), Point(1, rgt))");

			$r = true;
		}

		$this->unlock();
		return $r;
	}

	/**
	 * Update the node data.
	 *
	 * @param int $id The ID of the node to update.
	 * @param array $data The name => value pairs of the data to update
	 * @return bool true of the data was updated; else false.
	 */
	function updateNodeData($id, $data) {
		return $this->db->update($this->table, $data, "$this->idField=?", $id);
	}

	/**
	 * Get the node data.
	 *
	 * @param int $id The ID of the node to get.
	 * @param array $fields Fields to get.
	 * @return array The fields fetched from the node.
	 */
	function getNodeData($id, $fields = array('id')) {
		$fields = join(',', $fields);
		return $this->db->fetchRow("SELECT $fields FROM $this->table WHERE $this->idField=?", $id);
	}

	/**
	 * Get the parent node.
	 *
	 * @param int $id ID of the node to get the parent of.
	 * @return int The parent ID or false if the node doesn't exist.
	 */
	function getParent($id) {
		return $this->db->fetchOne("SELECT parentid FROM $this->table WHERE $this->idField=?", $id);
	}

	/**
	 * Get direct child nodes of the given node.
	 *
	 * @param int $id The ID of the node to get the children of.
	 * @param array $fields Fields to get.
	 * @param int $num The number of children to get or 0 for all.
	 * @param bool $leftToRight true to order nodes left to right or false to order right to left.
	 * @param int $depth The maximum depth to descend to, 0 for unlimited.
   * @param string $sortBy The field to sort by.
	 * @return array The fields fetched from the child nodes.
	 */
	function getChildren($id, $fields = array('id'), $num = 0, $leftToRight = true, $depth = 1, $sortBy = 'lft') {
		if($depth == 1) {
			$fields = join(',', $fields);
			return $this->db->fetchAll("SELECT $fields FROM $this->table WHERE parentid=? ORDER BY $sortBy " .
				($leftToRight ? 'ASC' : 'DESC') .
				($num ? " LIMIT $num" : ''), $id);
		}
		else {
			$fields = 'c.' . join(',c.', $fields);
			$params = array($id, $id);
			if($depth > 1)
				$params[] = $id;
			return $this->db->fetchAll("SELECT $fields FROM $this->table AS c, $this->table AS p WHERE p." . ($id ? $this->idField : 'parentid') . "=? && c.$this->idField!=? && MBRINTERSECTS(Point(0, c.lft), p.lftrgtset)" .
				($depth > 1 ? " && (SELECT COUNT(*) FROM $this->table AS c2, $this->table AS x WHERE MBRINTERSECTS(Point(0, c2.lft), x.lftrgtset) && c2.$this->idField=c.$this->idField) <= ?" : '') .
				" ORDER BY c.$sortBy " . ($leftToRight ? 'ASC' : 'DESC') . ($num ? " LIMIT $num" : ''), $params);
		}
	}

	/**
	 * Get the first child node of a parent.
	 *
	 * @param int $id ID of parent to get the 1st child of.
	 * @param array $fields Fields to get.
	 * @return array The fields fetched from the child.
	 */
	function getFirstChild($id, $fields = array('id')) {
		$fields = 'n.' . join(',n.', $fields);
		return $this->db->fetchRow("SELECT $fields FROM $this->table, $this->table AS n WHERE n.lft=$this->table.lft+1 && $this->table.$this->idField=?", $id);
	}

	/**
	 * Get the last child node of a parent.
	 *
	 * @param int $id ID of parent to get the last child of.
	 * @param array $fields Fields to get.
	 * @return array The fields fetched from the child.
	 */
	function getLastChild($id, $fields = array('id')) {
		$fields = 'n.' . join(',n.', $fields);
		return $this->db->fetchRow("SELECT $fields FROM $this->table, $this->table AS n WHERE n.rgt=$this->table.rgt-1 && $this->table.$this->idField=?", $id);
	}

	/**
	 * Get the nth child node.
	 *
	 * @param int $id ID of the node to get the child from.
	 * @param int $idx The zero based index of the child to get.
	 * @param array $fields Fields to get.
	 * @return array The fields fetched from the child or null/false.
	 */
	function getChildAt($id, $idx, $fields = array('id')) {
		$fields = join(',', $fields);
		return $this->db->fetchRow("SELECT $fields FROM $this->table WHERE (SELECT count(*) FROM $this->table AS n WHERE parentid=$this->table.parentid AND n.lft<=$this->table.lft)=? && parentid=? LIMIT 1", $idx + 1, $id);
	}

	/**
	 * Get the nodes previous sibling.
	 *
	 * @param int $id ID of parent to get the previous sibling of.
	 * @param array $fields Fields to get.
	 * @return array The fields fetched from the child or null/false.
	 */
	function getPrevSibling($id, $fields = array('id')) {
		$fields = 'n.' . join(',n.', $fields);
		return $this->db->fetchRow("SELECT $fields FROM $this->table, $this->table AS n WHERE n.rgt=$this->table.lft-1 && $this->table.$this->idField=?", $id);
	}

	/**
	 * Get the nodes next sibling.
	 *
	 * @param int $id ID of parent to get the next sibling of.
	 * @param array $fields Fields to get.
	 * @return array The fields fetched from the child or null/false.
	 */
	function getNextSibling($id, $fields = array('id')) {
		$fields = 'n.' . join(',n.', $fields);
		return $this->db->fetchRow("SELECT $fields FROM $this->table, $this->table AS n WHERE n.lft=$this->table.rgt+1 && $this->table.$this->idField=?", $id);
	}

	/**
	 * Get the number of nodes in the specified nodes subtree.
	 *
	 * @param int $id ID of the node to count from.
	 * @param bool $directOnly true if counting direct decedents.
	 * @return int The number of nodes.
	 */
	function getSize($id, $directOnly = false) {
		if($id && !$directOnly)
			return $this->db->fetchOne("SELECT (rgt-lft) DIV 2 FROM $this->table WHERE $this->idField=?", $id);
		else
			return $this->db->fetchOne("SELECT COUNT(*) FROM $this->table" . ($directOnly ? " WHERE parentid=?" : ''), $id);
	}

	/**
	 * Get the depth of the node within the tree.
	 *
	 * @param int $id ID of the node to get the depth of.
	 * @return int The depth, 1 being the top level.
	 */
	function getDepth($id) {
		return $this->db->fetchOne("SELECT COUNT(*) FROM $this->table AS c, $this->table AS p WHERE MBRINTERSECTS(Point(0, c.lft), p.lftrgtset) && c.$this->idField=?", $id);
	}

	/**
	 * Get the path from the root to a node.
	 *
	 * @param int $id ID of the node to get the path to.
	 * @param array $fields Fields to get.
	 * @return array The fields for the nodes in the path or false if node not known.
	 */
	function getPath($id, $fields = array('id')) {
		$fields = 'p.' . join(',p.', $fields);
		return $this->db->fetchAll("SELECT $fields FROM $this->table AS c,$this->table AS p WHERE MBRINTERSECTS(Point(0, c.lft), p.lftrgtset) && c.$this->idField=? ORDER BY p.lft", $id);
	}

	/**
	 * Get the short path from the root to a node.
	 *
	 * @param int $id ID of the node to get the path to.
	 * @param string $using The field to return in the short path.
	 * @return array The short path root, node or false if node not known.
	 */
	function getShortPath($id, $using = 'id') {
		return $this->db->fetchRow("SELECT p.$using AS root,IF(c.$this->idField=p.$this->idField, null, c.$using) AS node FROM $this->table AS c LEFT JOIN $this->table AS p ON MBRINTERSECTS(Point(0, c.lft), p.lftrgtset) WHERE c.$this->idField=? && (p.parentid=0 || c.parentid=0)", $id);
	}

	/**
	 * Get a node based on the path from the root.
	 *
	 * @param string|array $path The path to the node either an array or a / seperated string of nodes.
	 * @param string $using The name of the field to use in the search.
	 * @param array $fields Fields to get.
	 * @param bool $useWholePath true if the whole path must be used, false to get deepest matching node.
	 * @param string $pathField Name of the filed to return holding unused path segments.
	 * @return array The fields fetched or null if not found.
	 */
	function getByPath($path, $using, $fields = array('id'), $useWholePath = true, $pathField = 'childpath') {
		if(!is_array($path)) $path = explode('/', $path);

		if(!($pp = count($path)))
			return null;

		// Build the query
		$from = array();
		$id = array();
		$depth = array();
		for($c=0;$c<$pp;$c++) {
			if($c)
				$from[] = "LEFT JOIN $this->table AS n{$c} ON n{$c}.{$using}=" . $this->db->escape($path[$c]) . " && n{$c}.parentid=n" . ($c-1) . ".$this->idField";
			else
				$from[] = "FROM $this->table AS n0";

			if(!$useWholePath) {
				if($r = ($d = ($pp - $c)) - 1) {
					$id[] = "IFNULL(n{$r}.$this->idField, ";
					$depth[] = "IF(n{$r}.$this->idField, $d, ";
				}
				else {
					$id[] = "n0.$this->idField";
					$depth[] = "1";
				}
			}
		}

		// Finalise the SQL and run the query
		$sql = join(' ', $from) . " WHERE n0.{$using}=" . $this->db->escape($path[0]) . ' && n0.parentid=0';

		$c--;
		if($useWholePath) {
			$sql = "SELECT n{$c}." . join(",n$c.", $fields) . ' ' . $sql . " && n{$c}.parentid IS NOT NULL";
			if($d = $this->db->fetchRow($sql))
				$d[$pathField] = array();
		}
		else {
			$sql = 'SELECT ' . join('', $id) . str_repeat(')', $c) . ' AS id, ' . join('', $depth) . str_repeat(')', $c) . ' AS depth ' . $sql;
			if(!($r = $this->db->fetchRow($sql)) || $r['id'] === null)
				return null;

			// Get the data and if segments left store them
			if($d = $this->getNodeData($r['id'], $fields))
				$d[$pathField] = $pp != $r['depth'] ? array_slice($path, $r['depth']) : array();
		}

		return $d;
	}

	/**
	 * Get a node based on it's identifier but under a given root node.
	 *
	 * @param string|array $path The path to the node formatted as root:node, or array(root,node)
	 * @param string $using The name of the field to use in the search.
	 * @param array $fields Fields to get.
	 * @return array The fields fetched or false if not found.
	 */
	function getByShortPath($path, $using, $fields = array('id')) {
		@list($root, $node) = is_string($path) ? explode(':', $path) : $path;
		$fields = 'c.' . join(',c.', $fields);
		if($node === null)
			return $this->db->fetchRow("SELECT $fields FROM $this->table AS c WHERE c.parentid=0 && c.$using=?", $root);
		else
			return $this->db->fetchRow("SELECT $fields FROM $this->table AS c,$this->table AS p WHERE MBRINTERSECTS(Point(0, c.lft), p.lftrgtset) && c.$using=? && p.parentid=0 && p.$using=?", $node, $root);
	}
}
