memory.php

来自「视频监控网络部分的协议ddns,的模块的实现代码,请大家大胆指正.」· PHP 代码 · 共 1,354 行 · 第 1/4 页

<?php
//
// +----------------------------------------------------------------------+
// | PHP Version 4                                                        |
// +----------------------------------------------------------------------+
// | Copyright (c) 1997-2003 The PHP Group                                |
// +----------------------------------------------------------------------+
// | This source file is subject to version 2.02 of the PHP license,      |
// | that is bundled with this package in the file LICENSE, and is        |
// | available at through the world-wide-web at                           |
// | http://www.php.net/license/2_02.txt.                                 |
// | If you did not receive a copy of the PHP license and are unable to   |
// | obtain it through the world-wide-web, please send a note to          |
// | [e-mail] so we can mail you a copy immediately.               |
// +----------------------------------------------------------------------+
// | Authors: Wolfram Kriesing <[e-mail]>                      |
// +----------------------------------------------------------------------+
//
//  $Id: Memory.php,v 1.20 2003/02/26 18:46:31 cain Exp $

require_once 'Tree/Common.php';
require_once 'Tree/Error.php';

/**
*   this class can be used to step through a tree using ['parent'], ['child'], etc.
*   the tree is saved as flat data in a db, where at least the parent
*   needs to be given if a previous member is given too then the order
*   on a level can be determined too
*   actually this class was used for a navigation tree
*   now it is extended to serve any kind of tree
*   you can unambigiously refer to any element by using the following
*   syntax
*   tree->data[currentId][<where>]...[<where>]
*   <where> can be either "parent", "child", "next" or "previous", this way
*   you can "walk" from any point to any other point in the tree
*   by using <where> in any order you want
*   example (in parentheses the id):
*   root
*    +---level 1_1 (1)
*    |      +----level 2_1 (2)
*    |      +----level 2_2 (3)
*    |              +-----level 3_1 (4)
*    +---level 1_2 (5)
*
*    the database table to this structure (without defined order)
*    id     parentId        name
*    1         0         level 1_1
*    2         1         level 2_1
*    3         1         level 2_1
*    4         3         level 3_1
*    5         0         level 1_2
*
*   now you can refer to elements for example like this (all examples assume you know the structure):
*   to go from "level 3_1" to "level 1_1": $tree->data[4]['parent']['parent']
*   to go from "level 3_1" to "level 1_2": $tree->data[4]['parent']['parent']['next']
*   to go from "level 2_1" to "level 3_1": $tree->data[2]['next']['child']
*   to go from "level 2_2" to "level 2_1": $tree->data[3]['previous']
*   to go from "level 1_2" to "level 3_1": $tree->data[5]['previous']['child']['next']['child']
*

on a pentium 1.9 GHz 512 MB RAM, Linux 2.4, Apache 1.3.19, PHP 4.0.6
performance statistics for version 1.26, using examples/Tree/Tree.php
    reading from DB and preparing took: 0.14958894252777
    building took: 0.074488043785095
    buildStructure took: 0.05151903629303
    setting up the tree time: 0.29579293727875
    number of elements: 1564
    deepest level: 17
so you can use it for tiny-big trees too :-)
but watch the db traffic, which might be considerable, depending on your setup

FIXXXME there is one really bad thing about the entire class, at some points there are references to
$this->data returned, or the programmer can even access this->data, which means he can change the
structure, since this->data can not be set to read-only, therefore this->data has to be handled with great care
!!! never do something like this: $x = &$tree->data[<some-id>]; $x = $y; this overwrites the element in the structure !!!

*
*
*   @access   public
*   @author   Wolfram Kriesing <[e-mail]>
*   @version  2001/06/27
*   @package  Tree
*/
class Tree_Memory extends Tree_Common
{
    /**
    *   this array contains the pure data from the DB
    *   which are always kept, since all other structures will
    *   only make references on any element
    *   and those data are extended by the elements 'parent' 'children' etc...
    *   @var    array $data
    */
    var $data = array();

    /**
    *   this array contains references to this->data but it
    *   additionally represents the directory structure
    *   that means the array has as many dimensions as the
    *   tree structure has levels
    *   but this array is only used internally from outside you can do everything using
    *   the node-id's
    *
    *   @var    array $structure
    *   @access private
    */
    var $structure = array();

    /**
    *   it contains all the parents and their children, where the parentId is the
    *   key and all the children are the values, this is for speeding up the tree-building process
    *
    *   @var    array   $children
    */
    var $children = array();

    /**
    *   @access private
    *   @var    boolean saves if tree nodes shall be removed recursively
    *   @see    setRemoveRecursively()
    */
    var $removeRecursively = false;


    /**
    *   @access public
    *   @var    integer $debug  the debug mode, if > 0 then debug info are shown,
    *                           actually those messages only show performance times
    */
    var $debug = 0;

    /**
    *   @see    &getNode()
    *   @see    &_getNode()
    *   @access private
    *   @var    integer $_getNodeMaxLevel   variable only used in the method getNode and _getNode
    */
    var $_getNodeMaxLevel;

    /**
    *   @see    &getNode()
    *   @see    &_getNode()
    *   @access private
    *   @var    integer $_getNodeCurParent  variable only used in the method getNode and _getNode
    */
    var $_getNodeCurParent;

    /**
    *   the maximum depth of the tree
    *   @access private
    *   @var    int     the maximum depth of the tree
    */
    var $_treeDepth = 0;
    
    /**
    *   set up this object
    *
    *   @version    2001/06/27
    *   @access     public
    *   @author     Wolfram Kriesing <[e-mail]>
    *   @param      mixed   $dsn        this is a DSN for the PEAR::DB, can be either an object/string
    *   @param      array   $options    additional options you can set
    */
    function Tree_Memory( $type , $dsn='' , $options=array() )
    {
        $this->Tree_Options($options); // set the options for $this

        require_once("Tree/Memory/$type.php");

        $className = 'Tree_Memory_'.$type;
        $this->dataSourceClass =& new $className( $dsn , $options );
        // copy the options to be able to get them via getOption(s)
//FIXXME this is not really cool, maybe overwrite the *Option* methods!!!
        if( isset($this->dataSourceClass->options) )
            $this->options = $this->dataSourceClass->options;

    } // end of function

    /**
    *   use this to switch data sources on the run
    *   i.e. if you are reading the data from a db-tree and want to save it
    *   as xml data (which will work one day too)
    *   or reading the data from an xml file and writing it in the db
    *   which should already work
    *
    *   @version    2002/01/17
    *   @access     public
    *   @author     Wolfram Kriesing <[e-mail]>
    *   @param      string  $dsn    this is a DSN of the for that PEAR::DB uses it
    *                               only that additionally you can add parameters like ...?table=test_table
    *                               to define the table it shall work on
    *   @param      array   $options  additional options you can set
    *   @return     boolean     true on success
    */
    function switchDataSource( $type , $dsn='' , $options=array() )
    {
        $data = $this->getNode();
        //$this->Tree( $dsn , $options );
        $this->Tree_Memory( $type , $GLOBALS['dummy'] , $options );

        // this method prepares data retreived using getNode to be used
        // in this type of tree
        $this->dataSourceClass->setData($data);
        $this->setup();
    }

    /**
    *
    *
    *   @version    2002/01/19
    *   @access     public
    *   @author     Wolfram Kriesing <[e-mail]>
    *   @return
    */
    function setupByRawData( $string )
    {
//  expects
//   for XML an XML-String,
//   for DB-a result set, may be or an array, dont know here - not implemented yet
        $res = $this->dataSourceClass->setupByRawData( $string );
        return $this->_setup( $res );
    }

    /**
    *
    *
    *   @version    2002/01/19
    *   @access     public
    *   @author     Wolfram Kriesing <[e-mail]>
    *   @param      array   the result of a query which retreives (all) the tree data from a source
    *   @return     true or Tree_Error
    */
    function setup($data=null)
    {
        if( $this->debug )
        {
            $startTime = split(" ",microtime());
            $startTime = $startTime[1]+$startTime[0];
        }

        if(PEAR::isError($res = $this->dataSourceClass->setup($data)) )
            return $res;

        if( $this->debug )
        {
            $endTime = split(" ",microtime());
            $endTime = $endTime[1]+$endTime[0];
            print( " reading and preparing tree data took: ".($endTime - $startTime)." <br>" );
        }

        return $this->_setup( $res );

    }

    /**
    *   retreive all the navigation data from the db and build the
    *   tree in the array data and structure
    *
    *   @version    2001/11/20
    *   @access     private
    *   @author     Wolfram Kriesing <[e-mail]>
    *   @return     boolean     true on success
    */
    function _setup( $setupData )
    {
// TODO sort by prevId (parentId,prevId $addQuery) too if it exists in the table, or the root might be wrong
// TODO  since the prevId of the root should be 0
        if( !$setupData )
            return false;

//FIXXXXXME validate the structure. i.e. a problem occurs, if you give one node, which has a parentId=1 it screws up everything!!!
        // empty the data structures, since we are reading the data from the db (again)
        $this->structure = array();
        $this->data = array();
        $this->children = array();
        // build an array where all the parents have their children as a member
        // this i do to speed up the buildStructure
        foreach( $setupData as $values )
        {
            if( is_array($values) )
            {
                $this->data[$values['id']] = $values;
                $this->children[ $values['parentId'] ][] = $values['id'];
            }
        }

        // walk through all the children on each level and set the next/previous relations
        // of those children, since all children for "children[$id]" are on the same level we can do
        // this here :-)
        foreach( $this->children as $children )
        {
            $lastPrevId = 0;
            if(sizeof($children))
            foreach( $children as $key )
            {
                if( $lastPrevId )
                {
                    $this->data[$lastPrevId]['nextId'] = $key;  // remember the nextId too, so the build process can be sped up
                    $this->data[$lastPrevId]['next'] =   &$this->data[$key];

                    $this->data[$key]['prevId'] = $lastPrevId;
                    $this->data[$key]['previous'] = &$this->data[ $lastPrevId ];
                }
                $lastPrevId = $key;
            }
        }

//print_r($this->children);

        if( $this->debug )
        {
            $startTime = split(" ",microtime());
            $startTime = $startTime[1]+$startTime[0];
        }

        // when NO prevId is given, sort the entries in each level by the given sort order (to be defined)
        // and set the prevId so the build can work properly
        if( !isset($setupData[0]['prevId']) )   // does a prevId exist?
        {
            $lastPrevId = 0;
            $lastParentId = 0;
            $level = 0;
            // build the entire recursive relations, so you have 'parentId', 'childId', 'nextId', 'prevId'
            // and the references 'child', 'parent', 'next', 'previous' set in the property 'data'
            foreach( $this->data as $key=>$value )
            {
                // most if checks in this foreach are for the following reason, if not stated otherwise:
                // dont make an data[''] or data[0] since this was not read from the DB, because id is autoincrement and starts at 1
                // and also in an xml tree there can not be an element </> , i hope :-)
                if( $value['parentId'] )            // see comment above
                {
                    $this->data[$key]['parent']    = &$this->data[ $value['parentId'] ];
                    // the parent has an extra array which contains a reference to all it's children, set it here
                    $this->data[ $value['parentId'] ]['children'][] = &$this->data[$key];
                }

                // was a child saved (in the above 'if')
                if( isset($this->children[$key]) && sizeof( $this->children[$key] ) ) // see comment above
                {
                    // refer to the first child in the [child] and [childId] keys