Ticket #1796: sfPropelActAsNestedSetBehavior.class.php

<?php
/*
 * This file is part of the sfPropelActAsNestedSetBehavior package.
 * 
 * (c) 2006-2007 Tristan Rivoallan <tristan@rivoallan.net>
 * 
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

/**
 * This behavior adds necessary logic for a propel model to behave as a nested set.
 * 
 * To enable this behavior add this after Propel stub class declaration :
 * 
 * <code>
 *   $columns_map = array('left'   => MyClassPeer::TREE_LEFT,
 *                        'right'  => MyClassPeer::TREE_RIGHT,
 *                        'parent' => MyClassPeer::TREE_PARENT,
 *                        'scope'  => MyClassPeer::TOPIC_ID);
 * 
 *   sfPropelBehavior::add('MyClass', array('actasnestedset' => array('columns' => $columns_map)));
 * </code>
 * 
 * Column map values signification :
 * 
 *  - left : Model column holding nested set left value for a row
 *  - right : Model column holding nested set right value for a row
 *  - parent : Model column holding row's parent id 
 * (this is necessary because we use adjacency list tree traversal for some methods)
 *  - scope : Model column holding row's scope id. The scope is used to differenciate trees stored in
 * the same table
 *  
 * @author   Tristan Rivoallan   <tristan@rivoallan.net>
 * @author   Heltem              (http://propel.phpdb.org/trac/ticket/312)
 * @author   Joe Simms           (http://www.symfony-project.com/forum/index.php/m/20657/)
 * 
 * @see      http://www.symfony-project.com/trac/wiki/sfPropelActAsNestedSetBehaviorPlugin
 */
class sfPropelActAsNestedSetBehavior
{

# -- PROPERTIES

  /**
   * Nested set related columns.
   * 
   * @var array
   */
  private static $columns = array();
  
  /**
   * Holds SQL queries propel objects that need to be processed before a node is saved.
   * It acts as a FIFO stack.
   * 
   * @var array
   */
  private $presave_stack = array();
  
  /**
   * Holds SQL queries propel objects that need to be processed before a node is deleted.
   * It acts as a FIFO stack.
   * 
   * @var array
   */
  private $predelete_stack = array();  
  
  /**
    * Store infos required to update the tree after a node deletion
    * @var array  
    */
  private $node_infos = array() ;
  

# -- HOOKS

  /**
   * Runs necessary queries before node is saved.
   * 
   * @param      BaseObject  $node
   */
  public function preSave(BaseObject $node)
  {
    $this->processPreSaveStack();
  }

  /**
    * Runs queries to update tree after a node is deleted
    */
  public function postDelete ()
  {
    $peer_name = $this->node_infos['peer_name'] ;
    $stub_name = $this->node_infos['stub_name'] ;
    $scope_id_value = $this->node_infos['scope_id_value'] ;
    $right_value = $this->node_infos['right_value'] ;
    if (isset($this->node_infos['delta']))
    {
      $delta = $this->node_infos['delta'] ;
    }
    else 
    {
      /* no child nodes */ 
        $delta = 2 ;
    }
    $con = Propel::getConnection();
    
    /* Update the left value of nodes which have a left value greater than node 
       right's value */
    $query = sprintf('UPDATE %s SET %s = %s - 2 WHERE %s = %d AND %s > (%d - %d)',
                       constant("$peer_name::TABLE_NAME"),
                       self::getColumnConstant($stub_name, 'left'),
                       self::getColumnConstant($stub_name, 'left'),
                       self::getColumnConstant($stub_name, 'scope'), 
                       $scope_id_value,
                       self::getColumnConstant($stub_name, 'left'),
                       $right_value,
                       $delta);
    $statement = $con->createStatement();
    $statement->execute($query);
    
    /* Update the right value of nodes which have a right value greater than node 
       right's value */
    $query = sprintf('UPDATE %s SET %s = %s - 2 WHERE %s = %d AND %s > (%d - %d + 1)',
                       constant("$peer_name::TABLE_NAME"),
                       self::getColumnConstant($stub_name, 'right'),
                       self::getColumnConstant($stub_name, 'right'),
                       self::getColumnConstant($stub_name, 'scope'), 
                       $scope_id_value,
                       self::getColumnConstant($stub_name, 'right'),
                       $right_value,
                       $delta);
    $con = Propel::getConnection();
    $statement = $con->createStatement();
    $statement->execute($query);
  } // postDelete

  /**
    * Store informations required to update the tree after a node deletion
    *
    */
  public function preDelete (BaseObject $node)
  {
    $this->node_infos['peer_name'] = get_class($node->getPeer());
    $this->node_infos['stub_name'] = get_class($node);
    $this->node_infos['scope_id_value'] = $node->getScopeIdValue() ;
    $this->node_infos['right_value'] = $node->getRightValue() ;
  } // 

# -- GETTERS AND SETTERS

  /**
   * Proxy method used to access column holding nested set's left value getter.
   * 
   * @param      BaseObject  $node
   */
  public function getLeftValue(BaseObject $node)
  {
    $getter = self::forgeMethodName($node, 'get', 'left'); 
    return $node->$getter();
  }

  /**
   * Proxy method used to access column holding nested set's left value setter.
   * 
   * @param      BaseObject  $node
   * @param      integer     $value
   */
  public function setLeftValue(BaseObject $node, $value)
  {
    $setter = self::forgeMethodName($node, 'set', 'left'); 
    return $node->$setter($value);    
  }

  /**
   * Proxy method used to access column holding nested set's right value setter.
   * 
   * @param      BaseObject  $node
   * @param      integer     $value
   */
  public function setRightValue(BaseObject $node, $value)
  {
    $setter = self::forgeMethodName($node, 'set', 'right'); 
    return $node->$setter($value);    
  }

  /**
   * Proxy method used to access column holding nested set's right value getter.
   * 
   * @param      BaseObject  $node
   */
  public function getRightValue(BaseObject $node)
  {
    $getter = self::forgeMethodName($node, 'get', 'right'); 
    return $node->$getter();    
  }
  
  /**
   * Proxy method used to access column holding nested set's scope value setter.
   * 
   * @param      BaseObject  $node
   * @param      integer     $value
   */
  public function setScopeIdValue(BaseObject $node, $value)
  {
    $setter = self::forgeMethodName($node, 'set', 'scope'); 
    return $node->$setter($value);    
  }
  
  /**
   * Proxy method used to access column holding nested set's scope value getter.
   * 
   * @param      BaseObject  $node
   */
  public function getScopeIdValue(BaseObject $node)
  {
    $getter = self::forgeMethodName($node, 'get', 'scope'); 
    return $node->$getter();    
  }  

  /**
   * Proxy method used to access column holding nested set's parent value setter.
   * 
   * @param      BaseObject  $node
   * @param      integer     $value
   */
  public function setParentIdValue(BaseObject $node, $value)
  {
    $setter = self::forgeMethodName($node, 'set', 'parent'); 
    return $node->$setter($value);
  }
  
  /**
   * Proxy method used to access column holding nested set's parent value getter.
   * 
   * @param      BaseObject  $node
   */
  public function getParentIdValue(BaseObject $node)
  {
    $getter = self::forgeMethodName($node, 'get', 'parent'); 
    return $node->$getter();    
  }  

# -- NESTED SETS PUBLIC API

  /**
   * Sets node properties to make it a root node.
   * 
   * @param      BaseObject  $node
   * @throws     Exception   When trying to turn an existing non-root node into a root node
   */
  public function makeRoot(BaseObject $node)
  {
    if ((bool)$node->getLeftValue())
    {
      throw new Exception('Cannot turn an existing node into a root node.');
    }
    
    $node->setLeftValue(1);
    $node->setRightValue(2);
  }

# ---- INSERTION METHODS
  
  /**
   * Inserts node as first child of given node.
   * 
   * @param      BaseObject     $node
   * @param      BaseObject     $dest_node
   */
  public function insertAsFirstChildOf(BaseObject $node, BaseObject $dest_node)
  {
    $node->setLeftValue($dest_node->getLeftValue() + 1);
    $node->setRightValue($dest_node->getLeftValue() + 2);
    $node->setScopeIdValue($dest_node->getScopeIdValue());
    $node->setParentIdValue($dest_node->getPrimaryKey());
    $this->addPreSaveStackEntries($this->shiftRLValues(get_class($node->getPeer()), 
                                                       $node->getLeftValue(), 
                                                       2, 
                                                       $dest_node->getScopeIdValue()));
    
    $dest_node->setRightValue($dest_node->getRightValue() + 2);
    $this->addPreSaveStackEntries(array($dest_node));
  }

  /**
   * Inserts node as last child of given node.
   * 
   * @param      BaseObject    $node
   * @param      BaseObject    $dest_node
   */
  public function insertAsLastChildOf(BaseObject $node, BaseObject $dest_node)
  {
    $node->setLeftValue($dest_node->getRightValue());
    $node->setRightValue($dest_node->getRightValue() + 1);
    $node->setScopeIdValue($dest_node->getScopeIdValue());
    $node->setParentIdValue($dest_node->getPrimaryKey());
    $this->addPreSaveStackEntries($this->shiftRLValues(get_class($node->getPeer()), 
                                  $node->getLeftValue(), 
                                  2, 
                                  $dest_node->getScopeIdValue()));
    
    $dest_node->setRightValue($dest_node->getRightValue() + 2);
    $this->addPreSaveStackEntries(array($dest_node));
  }
  
  /**
   * Inserts node as next sibling of given node.
   * 
   * @param      BaseObject  $node
   * @param      BaseObject  $dest_node
   * @throws     Exception   When trying to create a sibling to a root node
   */
  public function insertAsNextSiblingOf(BaseObject $node, BaseObject $dest_node)
  {
    if ($dest_node->isRoot())
    {
      $msg = 'Root nodes cannot have siblings';
      throw new Exception($msg);
    }

    $node->setLeftValue($dest_node->getRightValue() + 1);
    $node->setRightValue($dest_node->getRightValue() + 2);
    $node->setScopeIdValue($dest_node->getScopeIdValue());
    $node->setParentIdValue($dest_node->getParentIdValue());
    
    $this->addPreSaveStackEntries($this->shiftRLValues(get_class($node->getPeer()), 
                                  $node->getLeftValue(),
                                  2,
                                  $dest_node->getScopeIdValue()));
  }

  /**
   * Inserts node as previous sibling of given node.
   * 
   * @param      BaseObject     $node
   * @param      BaseObject     $dest_node
   * @throws     Exception      When trying to create a sibling to a root node
   */

  public function insertAsPrevSiblingOf(BaseObject $node, BaseObject $dest_node)
  {
    if ($dest_node->isRoot())
    {
      $msg = 'Root nodes cannot have siblings';
      throw new Exception($msg);
    }

    $node->setLeftValue($dest_node->getLeftValue());
    $node->setRightValue($dest_node->getLeftValue() + 1);
    $node->setScopeIdValue($dest_node->getScopeIdValue());
    $node->setParentIdValue($dest_node->getParentIdValue());
    
    $this->addPreSaveStackEntries($this->shiftRLValues(get_class($node->getPeer()), 
                                  $node->getLeftValue(),
                                  2,
                                  $dest_node->getScopeIdValue()));

    $dest_node->setLeftValue($dest_node->getLeftValue() + 2);
    $dest_node->setRightValue($dest_node->getRightValue() + 2);
    $this->addPreSaveStackEntries(array($dest_node));
  }

  /**
   * Inserts node as parent of given node.
   * 
   * @param      BaseObject     $node
   * @param      BaseObject     $dest_node
   * @throws     Exception      When trying to insert node as parent of a root node
   */
  public function insertAsParentOf(BaseObject $node, BaseObject $dest_node)
  {
    if ($dest_node->isRoot())
    {
      $msg = 'Impossible to insert a node as parent of a root node';
      throw new Exception($msg);
    }

    $peer_name = get_class($node->getPeer());

    $this->addPreSaveStackEntries(self::shiftRLValues($peer_name, $dest_node->getLeftValue(), 1, $dest_node->getScopeIdValue()));
    $this->addPreSaveStackEntries(self::shiftRLValues($peer_name, $dest_node->getRightValue() + 2, -1, $dest_node->getScopeIdValue()));
    
    $node->setLeftValue($dest_node->getLeftValue());
    $node->setRightValue($dest_node->getRightValue() + 2);

    $previous_parent = $dest_node->getParentIdValue();
    $node->setParentIdValue($previous_parent);
    $dest_node->setParentIdValue($node->getPrimaryKey());

    $this->addPreSaveStackEntries(array($dest_node));
    
  }

# ---- INFORMATIONAL METHODS

  /**
   * Returns true if given node as one or several children.
   * 
   * @param      BaseObject  $node
   * @return     bool
   */
  public function hasChildren(BaseObject $node)
  {
    return $node->getRightValue() - $node->getLeftValue() > 1;
  }

  /**
   * Returns true if given node is a root node.
   * 
   * @param      BaseObject      $node
   * @return     bool
   */
  public function isRoot(BaseObject $node)
  {
    return $node->getLeftValue() == 1;
  }

  /**
   * Returns true if given node has a parent node.
   * 
   * @param      BaseObject      $node
   * @return     bool
   */
  public function hasParent(BaseObject $node)
  {
    return $node->getParentIdValue();
  }

  /**
   * Returns true if given node has a next sibling.
   * 
   * @param      BaseObject      $node
   * @return     bool
   */
  public function hasNextSibling(BaseObject $node)
  {
    return (bool)$node->retrieveNextSibling();
  }

  /**
   * Returns true if given node has a previous sibling.
   * 
   * @param      BaseObject      $node
   * @return     bool
   */
  public function hasPrevSibling(BaseObject $node)
  {
    return (bool)$node->retrievePrevSibling();
  }

  /**
   * Returns true if given node does not have children.
   * 
   * @param      BaseObject      $node
   * @return     bool 
   */
  public function isLeaf(BaseObject $node)
  {
    return $node->getRightValue() - $node->getLeftValue() == 1;
  }

  /**
   * Returns true if given node is identical to node.
   * 
   * @param      BaseObject      $node
   * @param      BaseObject      $compared_node
   * @return     bool
   */
  public function isEqualTo(BaseObject $node, BaseObject $compared_node)
  {
    return ($node->getLeftValue()        === $compared_node->getLeftValue()
            && $node->getRightValue()    === $compared_node->getRightValue()
            && $node->getScopeIdValue()  === $compared_node->getScopeIdValue()
            && $node->getParentIdValue() === $compared_node->getParentIdValue());
  }

  /**
   * Returns true if given node is parent of node.
   * 
   * @param      BaseObject      $node
   * @param      BaseObject      $parent_node
   */
  public function isChildOf(BaseObject $node, BaseObject $parent_node)
  {
    return ($node->getParentIdValue() === $parent_node->getPrimaryKey()
            && $node->getScopeIdValue() === $parent_node->getScopeIdValue());
  }

  /**
   * Returns given node number of direct children.
   * 
   * @param      BaseObject  $node
   * @return     integer
   */
  public function getNumberOfChildren(BaseObject $node)
  {
    $peer_name = get_class($node->getPeer());
    $con = Propel::getConnection();
    $scope_sql = '';
    if (!is_null($node->getScopeIdValue()))
    {
      $scope_sql = sprintf(' AND %s = %d',
                           self::getColumnConstant(get_class($node), 'scope'), 
                           $node->getScopeIdValue());
    }
    
    $sql = sprintf('SELECT COUNT(*) AS num_children FROM %s WHERE %s = %s %s',
      constant("$peer_name::TABLE_NAME"),
      self::getColumnConstant(get_class($node), 'parent'),
      $node->getPrimaryKey(),
      $scope_sql
    );

    $stmt = $con->createStatement();
    $rs = $stmt->executeQuery($sql);
    $rs->next();
    
    return $rs->getInt('num_children');
  }

  /**
   * Returns given node number of descendants (n level).
   * 
   * @param      BaseObject  $node
   * @return     integer
   */
  public function getNumberOfDescendants(BaseObject $node)
  {
    $right = $node->getRightValue();
    $left = $node->getLeftValue();
    $num = ($right - $left - 1) / 2;
    
    return $num;
  }

  /**
   * Returns given node level.
   * 
   * @param      BaseObject     $node
   * @return     integer
   */
  public function getLevel(BaseObject $node)
  {
    if (!isset($node->level))
    {
      $peer_name = get_class($node->getPeer());
  
      $con = Propel::getConnection();
      $stmt = $con->createStatement();
      
      $scope_sql = '';
      if (!is_null($node->getScopeIdValue())) {
        $scope_sql = sprintf(' AND %s = %d', self::getColumnConstant(get_class($node), 'scope'), $node->getScopeIdValue());
      }
      
      $sql = sprintf('SELECT COUNT(*) AS level FROM %s WHERE (%s < %d AND %s > %d) %s',
        constant("$peer_name::TABLE_NAME"),
        self::getColumnConstant(get_class($node), 'left'),
        $node->getLeftValue(),
        self::getColumnConstant(get_class($node), 'right'),
        $node->getRightValue(),
        $scope_sql
      );
      
      $rs = $stmt->executeQuery($sql);
      $rs->next();
      
      $level = $rs->getInt('level');
      $this->level = $level;
    }
    else
    {
      $level = $node->level;
    }
    
    return $level;
  }
  
  /**
   * Sets node level.
   * 
   * @param    BaseObject    $node