<?php

/*
** Fishlib - a collection of utilities for db-driven applications in PHP
** Copyright (C) 2002  LTWD, LLC DBA The Madfish Group
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library 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
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

// default depth for searches
if (!defined('TREE_DEPTH'))
    define('TREE_DEPTH', 3);
class FishTree
{

    var $parents = NULL;
    var $children = NULL;
    var $all_ids = array();
    var $all_data = array();
    // fields from node - store the stuff that's not likely to change
    var $node = NULL;
    var $node_class = NULL;
    var $idfield = NULL;
    var $table = NULL;

    function &all_ids($k=NULL,&$v)
    {
        if ($k === NULL)
        {
            return $this->all_ids;
        }
        if ($v !== NULL)
        {
            $this->all_ids[$k] =& $v;
        }
        elseif (!array_key_exists($k,$this->all_ids))
        {
            return FALSE;
        }
        return $this->all_ids[$k];
    }

    function all_data($k=NULL,$v=NULL)
    {
        if ($k === NULL)
        {
            return $this->all_data;
        }
        if ($v !== NULL)
        {
            if (isset($this->all_data[$k]))
            {
                $o = $this->all_data[$k];
                if ($o !== $v)
                {
                    trace("merge all_data[$k]=$o with props($v)");
                    $o->build(get_object_vars($v));
                }
                else
                {
                    trace("all_data[$k]=$o is same as v=($v)");
                }
            }
            else
            {
                trace("set all_data[$k] to $v");
                $this->all_data[$k] = $v;
            }
        }
        elseif (!array_key_exists($k,$this->all_data))
        {
            return FALSE;
        }
        return $this->all_data[$k];
    }

    function node($o=NULL)
    {
        if ($o !== NULL)
        {
            if (is_object($o) && is_a($o, 'base'))
            {
                $class = get_class($o);
                if ($this->node !== NULL 
                    && $o !== $this->node 
                    && $class == $this->node_class
                )
                {
                    $props = array_merge(
                        get_object_vars($this->node)
                        , get_object_vars($o)
                    );
                    foreach ($props as $k => $v)
                    {
                        $o->$k = $v;
                    }
                }
                $this->node = $o;
                $this->node_class = get_class($o);
                $this->idfield = $o->idfield;
                $this->table = $o->table;
            }
            else
            {
                return FALSE;
            }
        }
        elseif ($this->node === NULL)
        {
            return FALSE;
        }
        return $this->node;
    }

    function predict_children($id=NULL, $maxdepth=NULL, $depth=NULL)
    {
        if (!($o = $this->node())) { return FALSE; }
        if ($id === NULL)
        {
            $id = $o->id;
        }
        elseif (is_array($id))
        {
            $id = implode(',',$id);
        }
        if (!$id)
        {
            $id = 0;
        }
        $fields = array("g0.{$this->idfield} as g0_id");
        $joins = '';
        if ($depth === NULL)
        {
            $depth = TREE_DEPTH;
        }
        if ($maxdepth !== NULL && $maxdepth < $depth)
        {
            $depth = $maxdepth;
        }
        for ($p = 0, $i = 1; $i <= $depth; $p++, $i++)
        {
            $fields[] = "g{$i}.{$this->idfield} as g{$i}_id";
            $joins .= " left join {$this->table} g{$i} on g{$p}.{$this->idfield} = g{$i}.parent_id ";
        }
        if ($id == 0)
        {
            $where = " g0.parent_id = 0 ";
        }
        else
        {
            $where = " g0.{$this->idfield} in ($id) ";
        }
        $query = 'select '
            . implode(', ', $fields)
            . " from {$this->table} g0 $joins where "
            . $where
        ;
        trace('query=', $query);
        $rows = $o->dbh->getAll($query, array(), DB_FETCHMODE_ORDERED);
        $next = array();
        foreach ($rows as $r)
        {
            $rid = array_shift($r);
            if ($rid === NULL)
            {
                continue;
            }
            if ($this->all_ids($rid) === FALSE)
            {
                $this->children[$rid] = array();
                $this->all_ids($rid, $this->children[$rid]);
            }
            elseif (count($r) == 0 || $r[0] === NULL)
            {
                continue;
            }
            $c =& $this->all_ids($rid);
            foreach ($r as $k)
            {
                if ($k === NULL)
                {
                    continue;
                }
                if (!array_key_exists($k,$c))
                {
                    $c[$k] = array();
                }
                $this->all_ids($k, $c[$k]);
                $c =& $c[$k];
                if (!is_array($c))
                {
                    die;
                }
            }
            $l = array_pop($r);
            if ($l !== NULL)
            {
                $next[] = $l;
            }
        }
        if (!empty($next) && $depth != $maxdepth)
        {
            // last column should always be empty, unless
            // a maximum depth has been supplied - if not,
            // we need to go again with another generation
            $this->predict_children($next,$maxdepth,$depth);
        }
        return TRUE;
    }

    function add_children($o=NULL, $maxdepth=NULL, $depth=NULL)
    {
        $n = $this->node();
        if ($o === NULL)
        {
            $o = $this->node();
        }
        elseif (!$n)
        {
            $o = $this->node($o);
        }
        if (!$o) { return FALSE; }
        if (!$this->predict_children($o->id,$maxdepth,$depth))
        {
            return FALSE;
        }
        $ids = array_diff(
            array_keys($this->all_ids())
            , array_keys($this->all_data())
        );
        trace(' ids:', implode(',',$ids));
        if (count($ids) == 0)
        {
            return $this->children();
        }
        $query = 'select * from '
            . $this->table
            . ' where '
            . $this->idfield
            . ' in ( '
            . implode(',',$ids)
            . ') '
        ;
        $rows = $o->dbh->getAll($query);
        $class = $this->node_class;
        foreach ($rows as $row)
        {
            $rid = $row[$this->idfield];
            if ($rid == $o->id)
            {
                $o->build($row);
                $this->all_data($rid, $o);
            }
            else
            {
                $c = new $class($row);
                $this->all_data($rid, $c);
            }
        }
        return $this->children;
    }

    function children($o=NULL,$maxdepth=NULL,$depth=NULL)
    {
        if ($this->children === NULL)
        {
            $this->children = array();
            $o = $this->node($o);
        }
        if ($o)
        {
            return $this->add_children($o,$maxdepth,$depth);
        }
        return $this->children;
    }

    function parents($o=NULL)
    {
        if ($this->parents === NULL)
        {
            $this->parents = array();
            $o = $this->node($o);
        }
        if ($o)
        {
            $this->get_parent($o);
        }
        return $this->parents;
    }
    function get_parent($o)
    {
        if ($o->parent_id == 0)
        {
            return;
        }
        $row = $o->fetch_record($o->table,$o->idfield,$o->parent_id);
        $class = get_class($o);
        $c = new $class;
        $c->build($row);
        $this->get_parent($c);
        $this->parents[$c->id] = $c;
    }
    function depth_list($a,&$output,$depth=0)
    {
        if (is_array($a))
        {
            foreach ($a as $k => $v)
            {
                $output[$k] = $depth;
                FishTree::depth_list($v,$output,$depth+1);
            }
        }
    }
}
?>