tree.php

Cake Framwork , Excellent

		$verify = false;
		extract($this->settings[$model->alias]);
		$fields = array($model->primaryKey, $field, $left, $right);
		$sort = $field . ' ' . $order;
		$nodes = $model->children($id, true, $fields, $sort, null, null, $recursive);
		if ($nodes) {
			foreach ($nodes as $node) {
				$id = $node[$model->alias][$model->primaryKey];
				$model->moveDown($id, true);
				if ($node[$model->alias][$left] != $node[$model->alias][$right] - 1) {
					$this->reorder($model, compact('id', 'field', 'order', 'verify'));
				}
			}
		}
		return true;
	}
/**
 * Remove the current node from the tree, and reparent all children up one level.
 *
 * If the parameter delete is false, the node will become a new top level node. Otherwise the node will be deleted
 * after the children are reparented.
 *
 * @param AppModel $model
 * @param mixed $id The ID of the record to remove
 * @param boolean $delete whether to delete the node after reparenting children (if any)
 * @return boolean true on success, false on failure
 * @access public
 */
	function removefromtree(&$model, $id = null, $delete = false) {
		if (is_array($id)) {
			extract (array_merge(array('id' => null), $id));
		}
		extract($this->settings[$model->alias]);

		list($node) = array_values($model->find('first', array(
			'conditions' => array($scope, $model->escapeField() => $id),
			'fields' => array($model->primaryKey, $left, $right, $parent),
			'recursive' => $recursive
		)));

		if ($node[$right] == $node[$left] + 1) {
			if ($delete) {
				$model->delete();
			} else {
				return false;
			}
		} elseif ($node[$parent]) {
			list($parentNode) = array_values($model->find('first', array(
				'conditions' => array($scope, $model->escapeField() => $node[$parent]),
				'fields' => array($model->primaryKey, $left, $right),
				'recursive' => $recursive
			)));
		} else {
			$parentNode[$right] = $node[$right] + 1;
		}

		$model->updateAll(array($parent => $node[$parent]), array($parent => $node[$model->primaryKey]));
		$this->__sync($model, 1, '-', 'BETWEEN ' . ($node[$left] + 1) . ' AND ' . ($node[$right] - 1));
		$this->__sync($model, 2, '-', '> ' . ($node[$right]));
		$model->id = $id;

		if ($delete) {
			$model->updateAll(
				array(
					$model->escapeField($left) => 0,
					$model->escapeField($right) => 0,
					$model->escapeField($parent) => null
				),
				array($model->escapeField() => $id)
			);
			return $model->delete($id);
		} else {
			$edge = $this->__getMax($model, $scope, $right, $recursive);
			if ($node[$right] == $edge) {
				$edge = $edge - 2;
			}
			$model->id = $id;
			return $model->save(array($left => $edge + 1, $right => $edge + 2, $parent => null));
		}
	}
/**
 * Backward compatible method
 *
 * Returns true if the change is successful.
 *
 * @param AppModel $model
 * @param mixed $parentId The ID to set as the parent of the current node.
 * @return true on success
 * @access public
 */
	function setparent(&$model, $parentId = null , $created = null) {
		extract($this->settings[$model->alias]);
		if ($created === false && $parentId == $model->field($parent)) {
			return true;
		}
		return $model->saveField($parent, $parentId);
	}
/**
 * Check if the current tree is valid.
 *
 * Returns true if the tree is valid otherwise an array of (type, incorrect left/right index, message)
 *
 * @param AppModel $model
 * @return mixed true if the tree is valid or empty, otherwise an array of (error type [index, node],
 *  [incorrect left/right index,node id], message)
 * @access public
 */
	function verify(&$model) {
		extract($this->settings[$model->alias]);
		if (!$model->find('count', array('conditions' => $scope))) {
			return true;
		}
		$min = $this->__getMin($model, $scope, $left, $recursive);
		$edge = $this->__getMax($model, $scope, $right, $recursive);
		$errors =  array();

		for ($i = $min; $i <= $edge; $i++) {
			$count = $model->find('count', array('conditions' => array(
				$scope, 'OR' => array($model->escapeField($left) => $i, $model->escapeField($right) => $i)
			)));
			if ($count != 1) {
				if ($count == 0) {
					$errors[] = array('index', $i, 'missing');
				} else {
					$errors[] = array('index', $i, 'duplicate');
				}
			}
		}
		$node = $model->find('first', array('conditions' => array($scope, $model->escapeField($right) . '< ' . $model->escapeField($left)), 'recursive' => 0));
		if ($node) {
			$errors[] = array('node', $node[$model->alias][$model->primaryKey], 'left greater than right.');
		}

		$model->bindModel(array('belongsTo' => array('VerifyParent' => array(
			'className' => $model->alias,
			'foreignKey' => $parent,
			'fields' => array($model->primaryKey, $left, $right, $parent)
		))));

		foreach ($model->find('all', array('conditions' => $scope, 'recursive' => 0)) as $instance) {
			if (is_null($instance[$model->alias][$left]) || is_null($instance[$model->alias][$right])) {
				$errors[] = array('node', $instance[$model->alias][$model->primaryKey],
					'has invalid left or right values');
			} elseif ($instance[$model->alias][$parent]) {
				if (!$instance['VerifyParent'][$model->primaryKey]) {
					$errors[] = array('node', $instance[$model->alias][$model->primaryKey],
						'The parent node ' . $instance[$model->alias][$parent] . ' doesn\'t exist');
				} elseif ($instance[$model->alias][$left] < $instance['VerifyParent'][$left]) {
					$errors[] = array('node', $instance[$model->alias][$model->primaryKey],
						'left less than parent (node ' . $instance['VerifyParent'][$model->primaryKey] . ').');
				} elseif ($instance[$model->alias][$right] > $instance['VerifyParent'][$right]) {
					$errors[] = array('node', $instance[$model->alias][$model->primaryKey],
						'right greater than parent (node ' . $instance['VerifyParent'][$model->primaryKey] . ').');
				}
			} elseif ($model->find('count', array('conditions' => array($scope, $left . '< ' . $instance[$model->alias][$left], $right . '> ' . $instance[$model->alias][$right]), 'recursive' => 0))) {
				$errors[] = array('node', $instance[$model->alias][$model->primaryKey], 'The parent field is blank, but has a parent');
			}
		}

		if ($errors) {
			return $errors;
		} else {
			return true;
		}
	}
/**
 * Sets the parent of the given node
 *
 * The force parameter is used to override the "don't change the parent to the current parent" logic in the event
 * of recovering a corrupted table, or creating new nodes. Otherwise it should always be false. In reality this
 * method could be private, since calling save with parent_id set also calls setParent
 *
 * @param AppModel $model
 * @param mixed $parentId
 * @return boolean true on success, false on failure
 * @access protected
 */
	function _setParent(&$model, $parentId = null, $created = false) {
		extract($this->settings[$model->alias]);
		list($node) = array_values($model->find('first', array('conditions' => array($scope, $model->escapeField() => $model->id),
									'fields' => array($model->primaryKey, $parent, $left, $right), 'recursive' => $recursive)));
		$edge = $this->__getMax($model, $scope, $right, $recursive, $created);

		if (empty ($parentId)) {
			$this->__sync($model, $edge - $node[$left] + 1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right], $created);
			$this->__sync($model, $node[$right] - $node[$left] + 1, '-', '> ' . $node[$left], $created);
		} else {
			$parentNode = array_values($model->find('first', array('conditions' => array($scope, $model->escapeField() => $parentId),
										'fields' => array($model->primaryKey, $left, $right), 'recursive' => $recursive)));

			if (empty($parentNode) || empty($parentNode[0])) {
				return false;
			} 
			$parentNode = $parentNode[0];

			if (($model->id == $parentId)) {
				return false;

			} elseif (($node[$left] < $parentNode[$left]) && ($parentNode[$right] < $node[$right])) {
				return false;
			}
			if (empty ($node[$left]) && empty ($node[$right])) {
				$this->__sync($model, 2, '+', '>= ' . $parentNode[$right], $created);
				$model->save(array($left => $parentNode[$right], $right => $parentNode[$right] + 1, $parent => $parentId), false);
			} else {
				$this->__sync($model, $edge - $node[$left] +1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right], $created);
				$diff = $node[$right] - $node[$left] + 1;

				if ($node[$left] > $parentNode[$left]) {
					if ($node[$right] < $parentNode[$right]) {
						$this->__sync($model, $diff, '-', 'BETWEEN ' . $node[$right] . ' AND ' . ($parentNode[$right] - 1), $created);
						$this->__sync($model, $edge - $parentNode[$right] + $diff + 1, '-', '> ' . $edge, $created);
					} else {
						$this->__sync($model, $diff, '+', 'BETWEEN ' . $parentNode[$right] . ' AND ' . $node[$right], $created);
						$this->__sync($model, $edge - $parentNode[$right] + 1, '-', '> ' . $edge, $created);
					}
				} else {
					$this->__sync($model, $diff, '-', 'BETWEEN ' . $node[$right] . ' AND ' . ($parentNode[$right] - 1), $created);
					$this->__sync($model, $edge - $parentNode[$right] + $diff + 1, '-', '> ' . $edge, $created);
				}
			}
		}
		return true;
	}
/**
 * get the maximum index value in the table.
 *
 * @param AppModel $model
 * @param string $scope
 * @param string $right
 * @return int
 * @access private
 */
	function __getMax($model, $scope, $right, $recursive = -1, $created = false) {
		$db =& ConnectionManager::getDataSource($model->useDbConfig);
		if ($created) {
			if (is_string($scope)) {
				$scope .= " AND {$model->alias}.{$model->primaryKey} <> ";
				$scope .= $db->value($model->id, $model->getColumnType($model->primaryKey));
			} else {
				$scope['NOT'][$model->alias . '.' . $model->primaryKey] = $model->id;
			}
		}
		list($edge) = array_values($model->find('first', array(
			'conditions' => $scope,
			'fields' => $db->calculate($model, 'max', array($right)),
			'recursive' => $recursive
		)));
		return ife(empty ($edge[$right]), 0, $edge[$right]);
	}
/**
 * get the minimum index value in the table.
 *
 * @param AppModel $model
 * @param string $scope
 * @param string $right
 * @return int
 * @access private
 */
	function __getMin($model, $scope, $left, $recursive = -1) {
		$db =& ConnectionManager::getDataSource($model->useDbConfig);
		list($edge) = array_values($model->find('first', array(
		    'conditions' => $scope,
		    'fields' => $db->calculate($model, 'min', array($left)),
		    'recursive' => $recursive
		)));
		return ife(empty($edge[$left]), 0, $edge[$left]);
    }
/**
 * Table sync method.
 *
 * Handles table sync operations, Taking account of the behavior scope.
 *
 * @param AppModel $model
 * @param integer $shift
 * @param string $direction
 * @param array $conditions
 * @param string $field
 * @access private
 */
	function __sync(&$model, $shift, $dir = '+', $conditions = array(), $created = false, $field = 'both') {
		$modelRecursive = $model->recursive;
		extract($this->settings[$model->alias]);
		$model->recursive = $recursive;

		if ($field == 'both') {
			$this->__sync($model, $shift, $dir, $conditions, $created, $left);
			$field = $right;
		}
		if (is_string($conditions)) {
			$conditions = array("{$model->alias}.{$field} {$conditions}");
		}
		if (($scope != '1 = 1' && $scope !== true) && $scope) {
			$conditions[] = $scope;
		}
		if ($created) {
			$conditions['NOT'][$model->alias . '.' . $model->primaryKey] = $model->id;
		}
		$model->updateAll(array($model->alias . '.' . $field => $model->alias . '.' . $field . ' ' . $dir . ' ' . $shift), $conditions);
		$model->recursive = $modelRecursive;
	}
}

?>