<?php
/**
 * The Strangecode Codebase - a general application development framework for PHP
 * For details visit the project site: <http://trac.strangecode.com/codebase/>
 * Copyright 2001-2012 Strangecode, LLC
 *
 * This file is part of The Strangecode Codebase.
 *
 * The Strangecode Codebase is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your option)
 * any later version.
 *
 * The Strangecode Codebase is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * The Strangecode Codebase. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * Hierarchy.inc.php
 *
 * Objective: This class provides the tools to organize pieces of data into a
 * hierarchy of nodes. Any form of data (article, product, image) can be
 * represented as a node in this hierarchy. This class does not manipulate the
 * data, nor is it involved in storing or retrieving the data. In fact it does
 * not access the tables where data exists and cannot find out info about the
 * data. You must provide identification of a piece of data (type and ID) to
 * insert it into the hierarchy. The node hierarchy is completely
 * separate from data storage and retrieval. You must separately store the data
 * using whatever logic is specific to the data then also call these functions.
 * Nodes are not the data. The nodes are mere singularities in virtual space
 * that represent a piece of data's relationship with another. The hierarchy
 * is an inverted tree structure. Each node can have virtually infinite
 * children. Each child can have multiple parents.
 *
 * @author    Quinn Comendant <quinn@strangecode.com>
 * @version   1.1 (07 Apr 2006 20:16:59)
 */

class Hierarchy
{

    /**
     * Array containing object parameters.
     * @var array $params
     *
     *  $params['child_type'] = 'article'
     *  $params['child_id'] = 23
     *
     */
    public $params = array();


    /**
     * The active node type.
     * @var string $child_type
     */
    public $child_type;

    /**
     * The active node id.
     * @var string $child_id
     */
    public $child_id;

    /**
     * Boolean indicating whether or not we've set
     * the 'active' node type and id.
     * @var bool $node_init
     */
    public $node_init = false;

    /**
     * Constructor
     * @param resource  $dbh    A database handler if we are already connected.
     * @param array     $params A hash containing any additional
     *                          configuration or connection parameters.
     */
    public function __construct($params=array())
    {
        $this->params = $params;
    }

    /**
     * Defines the default child_type and child_id for this object.
     * @child_type string   this node's type
     * @child_id string     this node's id
     * @return string       the previous node identifier, or the current one
     *                      if no new ones are specified.
     */
    public function currentNode($child_type=null, $child_id=null)
    {
        $old_type = isset($this->child_type) ? $this->child_type : $child_type;
        $old_id = isset($this->child_id) ? $this->child_id : $child_id;
        if (isset($child_type) && isset($child_id)) {
            $this->child_type = $child_type;
            $this->child_id = $child_id;
            $this->node_init = true;
        }
        return $this->toStringID($old_type, $old_id);
    }

    /**
     * Takes a node type and id and returns them as a serialized identifier like
     * article__24 or category__84. If the first argument is an array, and the
     * second is -1, we loop through the array and serialize the identifiers inside.
     * @param  mixed    $child_type
     * @param  string   $child_id
     * @return mixed    If a single type and id are provided, a single vector identifier is returned,
     *                  otherwise if an array is provided, an array of identifiers is returned.
     */
    public function toStringID($child_type=null, $child_id=null)
    {
            $app =& App::getInstance();

            if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('toStringID failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }
        if (is_array($child_type) && $child_id === -1) {
            // We take an array in the first argument. It really has nothing
            // to do with $child_type.
            if (!isset($child_type[0]['child_type'])) {
                // It's not a properly configured array.
                return false;
            }
            foreach ($child_type as $node) {
                $serialized_arr[] = $node['child_type'] . '__' . $node['child_id'];
            }
            return $serialized_arr;
        } else {
            return $child_type . '__' . $child_id;
        }
    }

    /**
     * Takes a singular node identifier and returns it as components of an array.
     * @param string    $node
     * @return mixed    Array of node type and id on success, false on failure.
     */
    public function toArrayID(&$node)
    {
            $app =& App::getInstance();

            if (preg_match('/^([[:alnum:]]+)__-?([[:digit:]]+)$/', $node, $node_parts)) {
            return array('node_type' => $node_parts[1], 'node_id' => $node_parts[2]);
        } else {
            $app->logMsg('Cannot parse node identifier, not formated correctly.', LOG_ERR, __FILE__, __LINE__);
            return false;
        }
    }

    /**
     * Adds a single node. Tests if it already exists first.
     * @param string    $child_type
     * @param string    $child_id
     * @param string    $parents    A serialized array of serialized parent identifiers
     * @param string    $relationship_type
     * @return bool     true on success, false on error.
     */
    public function insertNode($parents, $child_type=null, $child_id=null, $relationship_type=null, $title='')
    {
        $app =& App::getInstance();
        $db =& DB::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('insertNode failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        // Make sure this is not empty and an array, even if it has only one value.
        if ('' == $parents) {
            $app->raiseMsg(sprintf(_("Cannot add node <em>%s %s</em>, no parent was specified."), $child_type, $child_id), MSG_ERR, __FILE__, __LINE__);
            $app->logMsg(sprintf('Cannot add node %s %s, no parent was specified.', $child_type, $child_id), LOG_ERR, __FILE__, __LINE__);
            return false;
        } else if (!is_array($parents)) {
            $parents = array($parents);
        }

        // Remove duplicates.
        $parents = array_unique($parents);

        // Test that this node does not already exist and that the new parents
        // do exist before we continue.
        foreach ($parents as $parent_string) {
            $parent = $this->toArrayID($parent_string);
            if ($this->nodeExists($child_type, $child_id, $parent['node_type'], $parent['node_id'], $relationship_type)) {
                $app->raiseMsg(sprintf(_("Cannot add node <em>%s %s</em> to parent <em>%s %s</em>. It already exists there"), $child_type, $child_id, $parent['node_type'], $parent['node_id']), MSG_ERR, __FILE__, __LINE__);
                $app->logMsg(sprintf('Cannot add node %s %s to parent %s %s. It already exists there', $child_type, $child_id, $parent['node_type'], $parent['node_id']), LOG_ERR, __FILE__, __LINE__);
                return false;
            }
            if (!$this->nodeExists($parent['node_type'], $parent['node_id'])) {
                $app->raiseMsg(sprintf(_("Cannot add node <em>%s %s</em> to nonexistent parent <em>%s %s</em>."), $child_type, $child_id, $parent['node_type'], $parent['node_id']), MSG_ERR, __FILE__, __LINE__);
                $app->logMsg(sprintf('Cannot add node %s %s to nonexistent parent %s %s.', $child_type, $child_id, $parent['node_type'], $parent['node_id']), LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        // Insert new nodes with the new parents.
        foreach ($parents as $parent_string) {
            $parent = $this->toArrayID($parent_string);
            $db->query("
                INSERT INTO node_tbl (
                    parent_type,
                    parent_id,
                    child_type,
                    child_id,
                    relationship_type,
                    title
                ) VALUES (
                    '" . $db->escapeString($parent['node_type']) . "',
                    '" . $db->escapeString($parent['node_id']) . "',
                    '" . $db->escapeString($child_type) . "',
                    '" . $db->escapeString($child_id) . "',
                    " . (is_null($relationship_type) ? "NULL" : "'" . $db->escapeString($relationship_type) . "'") . ",
                    '" . $db->escapeString($title) . "'
                )
            ");
            $app->logMsg(sprintf('insertNode: Added node %s %s with parent %s %s.', $child_type, $child_id, $parent['node_type'], $parent['node_id']), LOG_INFO, __FILE__, __LINE__);
        }
        return true;
    }

    /**
     * Deletes a node using the following algorithm:
     * (1) Find each of this node's parents. Place serialized identifiers in array.
     * (2) Find all children of this node, and move each to all the parents of this node.
     * (3) Delete this node.
     *
     * @param  string    $child_type
     * @param  string    $child_id
     *
     * @return bool      false on error, true otherwise.
     */
    public function deleteNode($child_type=null, $child_id=null)
    {
        $app =& App::getInstance();
        $db =& DB::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('deleteNode failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        // Move children to parents of node being deleted.
        $new_parents = $this->getParents($child_type, $child_id);
        $children = $this->getChildren($child_type, $child_id);

        if ($children && $new_parents) {
            foreach ($children as $child) {
                $this->moveNode($new_parents, $child['child_type'], $child['child_id']);
            }
        }

        $db->query("
            DELETE FROM node_tbl
            WHERE child_type = '" . $db->escapeString($child_type) . "'
            AND child_id = '" . $db->escapeString($child_id) . "'
        ");
        $app->logMsg(sprintf('deleteNode: Deleted node %s %s.', $child_type, $child_id), LOG_INFO, __FILE__, __LINE__);

        return true;
    }

    /**
     * Moves a node using the following algorithm:
     * (1) Ensure the newly assigned parents exist.
     * (2) Delete old nodes with the specified type and id.
     * (3) Add the node with new parents.
     *
     * @param  string    $child_type
     * @param  string    $child_id
     * @param  array     $new_parents  An array of serialized node identifiers
     *                                 that the node will belong to. Example:
     *                                 $new_parents[0] = 'category__23';
     * @param  string    $relationship_type
     *
     * @return bool      false on error, true otherwise.
     */
    public function moveNode($new_parents=null, $child_type=null, $child_id=null, $relationship_type=null, $title='')
    {
            $app =& App::getInstance();
            $db =& DB::getInstance();

            if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('moveNode failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        // Make sure this is not empty and an array, even if it has only one value.
        if (empty($new_parents)) {
            $app->raiseMsg(sprintf(_("Cannot move node <em>%s %s</em>, no parent was specified."), $child_type, $child_id), MSG_ERR, __FILE__, __LINE__);
            $app->logMsg(sprintf('Cannot move node %s %s, no parent was specified.', $child_type, $child_id), LOG_ERR, __FILE__, __LINE__);
            return false;
        } else if (!is_array($new_parents)) {
            $new_parents = array($new_parents);
        }

        // Remove duplicates.
        $new_parents = array_unique($new_parents);

        // Test that the new parents exist before we delete the old ones.
        foreach ($new_parents as $parent_string) {
            $parent = $this->toArrayID($parent_string);
            if (!$this->nodeExists($parent['node_type'], $parent['node_id'])) {
                $app->raiseMsg(sprintf(_("Cannot move node <em>%s %s</em> to nonexistent parent <em>%s %s</em>."), $child_type, $child_id, $parent['node_type'], $parent['node_id']), MSG_ERR, __FILE__, __LINE__);
                $app->logMsg(sprintf('Cannot move node %s %s to nonexistent parent %s %s.', $child_type, $child_id, $parent['node_type'], $parent['node_id']), LOG_ERR, __FILE__, __LINE__);
                return false;
            }
            if ($this->isAncestor($child_type, $child_id, $parent['node_type'], $parent['node_id'])) {
                $app->raiseMsg(sprintf(_("Cannot move node <em>%s %s</em> to parent <em>%s %s</em> because a node cannot have itself as a parent."), $child_type, $child_id, $parent['node_type'], $parent['node_id']), MSG_ERR, __FILE__, __LINE__);
                $app->logMsg(sprintf('Cannot move node %s %s to parent %s %s because a node cannot have itself as a parent.', $child_type, $child_id, $parent['node_type'], $parent['node_id']), LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        if (empty($title)) {
            // Select the title of the node we are moving, so we can add it again with the same info.
            $qid = $db->query("
                SELECT title FROM node_tbl
                WHERE child_type = '" . $db->escapeString($child_type) . "'
                AND child_id = '" . $db->escapeString($child_id) . "'
                AND relationship_type " . (is_null($relationship_type) ? "IS NULL" : "= '" . $db->escapeString($relationship_type) . "'") . "
            ");
            list($title) = mysql_fetch_row($qid);
        }

        // Delete the nodes with the old parents.
        $db->query("
            DELETE FROM node_tbl
            WHERE child_type = '" . $db->escapeString($child_type) . "'
            AND child_id = '" . $db->escapeString($child_id) . "'
            AND relationship_type " . (is_null($relationship_type) ? "IS NULL" : "= '" . $db->escapeString($relationship_type) . "'") . "
        ");
        $app->logMsg(sprintf('moveNode: Deleted node %s %s.', $child_type, $child_id), LOG_INFO, __FILE__, __LINE__);

        // Insert new nodes with the new parents.
        $this->insertNode($new_parents, $child_type, $child_id, $relationship_type, $title);

        return true;
    }

    /**
     * Returns an array of all the parents of the current node (just the ones
     * immediately above this node). You may need to call array_unique if you
     * don't want duplicate nodes returned.
     *
     * @param  string   $child_type
     * @param  string   $child_id
     * @return string   The parents as an array of serialized node identifiers.
     */
    public function getParents($child_type=null, $child_id=null, $type_constraint=null, $order='')
    {
        $app =& App::getInstance();
        $db =& DB::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('getParents failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        $in_clause = '';
        if (isset($type_constraint)) {
            if (!is_array($type_constraint)) {
                $type_constraint = array($type_constraint);
            }
            $in_clause = "AND parent_type IN ('" . join("','", array_map(array($db, 'escapeString'), $type_constraint)) . "')";
        }

        $qid = $db->query("
            SELECT parent_type, parent_id
            FROM node_tbl
            WHERE child_type = '" . $db->escapeString($child_type) . "'
            AND child_id = '" . $db->escapeString($child_id) . "'
            $in_clause
            " . $db->escapeString($order) . "
        ");

        $parents = array();
        while ($row = mysql_fetch_assoc($qid)) {
            $parents[] = $this->toStringID($row['parent_type'], $row['parent_id']);
        }

        if (sizeof($parents) > 0) {
            return $parents;
        } else {
            return false;
        }
    }

    /**
     * Returns details of specified node.
     *
     * @param  string  $child_type
     * @param  string  $child_id
     * @return array   type, id, title, subnode_quantity.
     */
    public function getNode($child_type=null, $child_id=null)
    {
        $app =& App::getInstance();
        $db =& DB::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('getNode failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        $qid = $db->query("
            SELECT child_type, child_id, title, subnode_quantity
            FROM node_tbl
            WHERE child_type = '" . $db->escapeString($child_type) . "'
            AND child_id = '" . $db->escapeString($child_id) . "'
        ");

        $children = array();
        while ($row = mysql_fetch_assoc($qid)) {
            $children[] = $row;
        }
        if (sizeof($children) > 0) {
            return $children;
        } else {
            return false;
        }
    }

    /**
     * Returns an array of all the children of the current node (just the ones
     * immediately below this node). You may need to call array_unique if you
     * don't want duplicate nodes returned.
     *
     * @param  string  $child_type
     * @param  string  $child_id
     * @param  string  $type_constraint  An array of node types to restrict the search to.
     *
     * @return string  The children as an array of serialized node identifiers.
     */
    public function getChildren($child_type=null, $child_id=null, $type_constraint=null, $order='')
    {
        $app =& App::getInstance();
        $db =& DB::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('getChildren failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        $in_clause = '';
        if (isset($type_constraint)) {
            if (!is_array($type_constraint)) {
                $type_constraint = array($type_constraint);
            }
            $in_clause = "AND child_type IN ('" . join("','", array_map(array($db, 'escapeString'), $type_constraint)) . "')";
        }

        $qid = $db->query("
            SELECT *
            FROM node_tbl
            WHERE parent_type = '" . $db->escapeString($child_type) . "'
            AND parent_id = '" . $db->escapeString($child_id) . "'
            $in_clause
            " . $db->escapeString($order) . "
        ");

        $children = array();
        while ($row = mysql_fetch_assoc($qid)) {
            $children[] = $row;
        }
        if (sizeof($children) > 0) {
            return $children;
        } else {
            return false;
        }
    }

    /**
     * Give the number of children a category has. We are talking about the
     * direct children, on the next level.
     *
     * @param string optional $parent The name of the parent from where we begin.
     * @param string $type_constraint  An array of node types to restrict the search to.
     *
     * @return integer
     */
    public function getNumberChildren($child_type=null, $child_id=null, $type_constraint=null)
    {
        $app =& App::getInstance();
        $db =& DB::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('getNumberChildren failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        $in_clause = '';
        if (isset($type_constraint)) {
            if (!is_array($type_constraint)) {
                $type_constraint = array($type_constraint);
            }
            $in_clause = "AND child_type IN ('" . join("','", array_map(array($db, 'escapeString'), $type_constraint)) . "')";
        }

        $qid = $db->query("
            SELECT COUNT(*)
            FROM node_tbl
            WHERE parent_type = '" . $db->escapeString($child_type) . "'
            AND parent_id = '" . $db->escapeString($child_id) . "'
            $in_clause
        ");
        list($num_children) = mysql_fetch_row($qid);

        return $num_children;
    }

    /**
     * Tests of the specified node is a leaf (i.e. it has no children).
     * @param  string    $child_type
     * @param  string    $child_id
     * @return bool      true if a leaf, or false if not or an error
     */
    public function isLeaf($child_type=null, $child_id=null)
    {
        $app =& App::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('isLeaf failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        if ($this->getNumberChildren($child_type, $child_id) <= 0) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * This function will tell you if a specified node (the child) is actually
     * an ancestor to another node that perhaps is considered to be a parent. If
     * the specified node IS an ancestor of a node made into it's parent, we would
     * have a circular reference that would cause an infinite loop with any
     * recursive queries of the hierarchy.
     * @param  string    $child_type
     * @param  string    $child_id
     * @param  string    $considered_parent_type
     * @param  string    $considered_parent_id
     * @return bool      true if the child is an ancestor to the considered
     *                   parent, or false otherwise, or in case of failure.
     */
    public function isAncestor($child_type, $child_id, $considered_parent_type, $considered_parent_id)
    {
        $family_tree = $this->getAllAncestors($considered_parent_type, $considered_parent_id);
        $family_tree = $this->toStringID($family_tree, -1);

        if (in_array($this->toStringID($child_type, $child_id), $family_tree)) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * This function builds an array of all the parents starting from a
     * specified node, up to the root of the tree. It will follow paths for
     * nodes with multiple parents, branching off and filling the array with
     * ALL ancestors to the specified node. I'm not sure what the order will be
     * but that probably isn't useful anyways. I use this to prevent circular
     * references in the hierarchy.
     * @param  string    $child_type
     * @param  string    $child_id
     * @param  bool      $go_linear  ?
     * @param  int       $_return_flag  An internal value that counts up as
     *                                  recursion progresses. When the value
     *                                  drops back to 0, we return the output.
     * @return array     Array of serialized node identifiers.
     */
    public function getAllAncestors($child_type, $child_id, $go_linear=false, $_return_flag=true)
    {
        $db =& DB::getInstance();

        static $output = array();
        static $return_flag;

        $qid = $db->query("
            SELECT parent_type, parent_id, child_type, child_id, title, subnode_quantity
            FROM node_tbl
            WHERE child_type = '" . $db->escapeString($child_type) . "'
            AND child_id = '" . $db->escapeString($child_id) . "'
        ");
        while ($row = mysql_fetch_assoc($qid)) {
            // Preventing circular references.
            if ($row['parent_type'] == $child_type && $row['parent_id'] == $child_id) {
                continue;
            }

            // Build a linear path to root...no wormholes.
            if ($enough_already && $go_linear) {
                continue;
            }
            $enough_already = true;

            // To prevent duplicates, only add the new found node
            // if not already in the array of ancestors.
            $curr_items = sizeof($output) > 0 ? $this->toStringID($output, -1) : array();
            if (!in_array($this->toStringID($row['child_type'], $row['child_id']), $curr_items)) {
                $output[] = $row;
            }

            $this->getAllAncestors($row['parent_type'], $row['parent_id'], $go_linear, false);
        }
        if ($_return_flag) {
            // We must reset the static $output variable so that it does
            // not fill up during subsequent function calls.
            $ret = $output;
            $output = array();
            return $ret;
        }
    }

    /**
     * Tests if the specified node exists. If only the child type and id is
     * specified, check if any node exists like that. If the parent type and id
     * is also provided, test for an exact node match.
     * @param  string    $child_type
     * @param  string    $child_id
     * @param  string    $parent_type
     * @param  string    $parent_id
     * @param  string    $relationship_type
     * @return bool      true if a leaf, or false if not or an error
     */
    public function nodeExists($child_type=null, $child_id=null, $parent_type=null, $parent_id=null, $relationship_type=null)
    {
        $app =& App::getInstance();
        $db =& DB::getInstance();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('nodeExists failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        if (isset($parent_type) && isset($parent_id)) {
            $qid = $db->query("
                SELECT 1 FROM node_tbl
                WHERE parent_type = '" . $db->escapeString($parent_type) . "'
                AND parent_id = '" . $db->escapeString($parent_id) . "'
                AND child_type = '" . $db->escapeString($child_type) . "'
                AND child_id = '" . $db->escapeString($child_id) . "'
                AND relationship_type " . (is_null($relationship_type) ? "IS NULL" : "= '" . $db->escapeString($relationship_type) . "'") . "
            ");
        } else {
            $qid = $db->query("
                SELECT 1 FROM node_tbl
                WHERE child_type = '" . $db->escapeString($child_type) . "'
                AND child_id = '" . $db->escapeString($child_id) . "'
            ");
        }
        if (mysql_num_rows($qid) > 0) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Recursively go through the node tree, starting at a specified node, and
     * drill down, filling an array with info about the nodes:
     *
     * @param  array   $preselected
     * @param  string  $child_type
     * @param  string  $child_id
     * @param  string  $type_constraint  An array of node types to restrict the search to.
     * @param  bool    $include_curr     Do we include the specified node in the list?
     * @param  string  $order            SQL to append to the query of the getChildren
     *                                   call. Ex: 'ORDER BY child_id DESC'
     * @return array  Details of from the node table of all nodes below the
     *                specified node: (type, id, title, indent level, selected status)
     */
    public function &getNodeList($preselected=null, $child_type=null, $child_id=null, $type_constraint=null, $include_curr=false, $order='', $_indent=0, $_return_flag=true)
    {
        $app =& App::getInstance();

        static $output = array();
        static $is_a_leaf = array();

        if (!isset($child_type) || !isset($child_id)) {
            if ($this->node_init) {
                $child_type =& $this->child_type;
                $child_id =& $this->child_id;
            } else {
                $app->logMsg('getNodeList failed. Arguments not specified properly.', LOG_ERR, __FILE__, __LINE__);
                return false;
            }
        }

        if (!is_array($preselected)) {
            $preselected = array($preselected);
        }

        if ($_return_flag && $include_curr) {
            $my_children = $this->getNode($child_type, $child_id);
        } else {
            $my_children = $this->getChildren($child_type, $child_id, $type_constraint, $order);
        }

        if ($my_children) {
            $num_children = sizeof($my_children);
            for ($i=0; $i<$num_children; $i++) {

                // Preventing circular references.
                if ($my_children[$i]['child_type'] == $child_type && $my_children[$i]['child_id'] == $child_id && !($_return_flag && $include_curr)) {
                    $app->logMsg(sprintf('Circular reference detected: %s has itself as a parent.', $this->toStringID($my_children[$i]['child_type'], $my_children[$i]['child_id'])), LOG_ERR, __FILE__, __LINE__);
                    continue;
                }

                $my_children[$i]['indent'] = $_indent;
                if (in_array($this->toStringID($my_children[$i]['child_type'], $my_children[$i]['child_id']), $preselected)) {
                    $my_children[$i]['selected'] = true;
                }
                $output[] = $my_children[$i];

                // Test if each node is a string only once. Store the result in the is_a_leaf array statically.
                if (!isset($is_a_leaf[$this->toStringID($my_children[$i]['child_type'], $my_children[$i]['child_id'])])) {
                    $is_a_leaf[$this->toStringID($my_children[$i]['child_type'], $my_children[$i]['child_id'])] = $this->isLeaf($my_children[$i]['child_type'], $my_children[$i]['child_id']);
                }
                if (!$is_a_leaf[$this->toStringID($my_children[$i]['child_type'], $my_children[$i]['child_id'])]) {
                    // If this node is not a leaf, we dive into it recursively.
                    $this->getNodeList($preselected, $my_children[$i]['child_type'], $my_children[$i]['child_id'], $type_constraint, $include_curr, $order, $_indent+1, false);
                }
            }
        }

        if ($_return_flag) {
            // We must reset the static variables so that they do
            // not fill up during subsequent function calls.
            $ret = $output;
            $output = array();
            $is_a_leaf = array();
            return $ret;
        }

    }


    /**
     * Counts the number of items linked to each parent node
     * putting the result in the relevant category counters. This function is
     * called each time a product, article, etc. is inserted, updated, or deleted.
     *
     * @param  string  $type_constraint  An array of node types to restrict the search to.
     */
    public function rebuildSubnodeQty($type_constraint=null)
    {
        $db =& DB::getInstance();

        // Reset all the category counters to zero.
        $db->query("UPDATE node_tbl SET subnode_quantity = 0");

        // Get all the nodes.
        $qid = $db->query("SELECT DISTINCT child_type, child_id FROM node_tbl");

        // For each node count the number of children...
        while (list($child_type, $child_id) = mysql_fetch_row($qid)) {
            $num_children = $this->getNumberChildren($child_type, $child_id, $type_constraint);
            // ...and add that number to the node counter for that object and all parents.
            if ($num_children > 0) {
                $this->setSubnodeQtyToParents($child_type, $child_id, $num_children);
            }
        }
    }

    /**
     * Used internally by setSubnodeQty to add the quantity of subnodes to
     * all parents recursively.
     */
    public function setSubnodeQtyToParents($child_type, $child_id, $num_children)
    {
        $db =& DB::getInstance();

        $db->query("
            UPDATE node_tbl
            SET subnode_quantity = subnode_quantity + '" . $db->escapeString($num_children) . "'
            WHERE child_type = '" . $db->escapeString($child_type) . "'
            AND child_id = '" . $db->escapeString($child_id) . "'
        ",false);
        $qid = $db->query("
            SELECT parent_type, parent_id
            FROM node_tbl
            WHERE child_type = '" . $db->escapeString($child_type) . "'
            AND child_id = '" . $db->escapeString($child_id) . "'
        ",false);
        while ((list($parent_type, $parent_id) = mysql_fetch_row($qid)) && $parent_id > 0) {
            $this->setSubnodeQtyToParents($parent_type, $parent_id, $num_children);
        }
    }

// THE END
}