Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

uniconftree.h

Go to the documentation of this file.
00001 /* -*- Mode: C++ -*-
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * UniConf low-level tree storage abstraction.
00006  */
00007 #ifndef __UNICONFTREE_H
00008 #define __UNICONFTREE_H
00009 
00010 #include "uniconfkey.h"
00011 #include "wvvector.h"
00012 #include "wvcallback.h"
00013 #include "unihashtree.h"
00014 
00015 /**
00016  * A recursively composed dictionary for ordered tree-structured
00017  * data indexed by UniConfKey with logarithmic lookup time for
00018  * each 1-level search, linear insertion and removal.
00019  *
00020  * This container maintains a sorted vector of children which
00021  * greatly facilitates tree comparison and merging.  The
00022  * underlying collection guarantees fast lookups, but insertion
00023  * and removal may be quite slow.  If this becomes a problem,
00024  * then a different (more complex) data structure should be used,
00025  * such as a binary search tree.  However, for the moment, the
00026  * use of a vector keeps down memory footprint.
00027  *
00028  * Someday this could be further abstracted into a generic WvTreeDict.
00029  *
00030  * "Sub" is the name of the concrete subclass of UniConfTree
00031  */
00032 
00033 template<class Sub, class Base = UniHashTreeBase>
00034 class UniConfTree : public Base
00035 {
00036    
00037 public:
00038     typedef WvCallback<bool, const Sub *, const Sub *, void *> Comparator;
00039 
00040     /** Creates a node and links it to a subtree, if parent is non-NULL */
00041     UniConfTree(Sub *parent, const UniConfKey &key) :
00042         Base(parent, key)
00043         { }
00044 
00045     /** Destroy this node's contents and children. */
00046     ~UniConfTree()
00047         { zap(); }
00048 
00049     /** Returns a pointer to the parent node, or NULL if there is none. */
00050     Sub *parent() const
00051         { return static_cast<Sub*>(xparent); }
00052 
00053     /** Reparents this node. */
00054     void setparent(Sub *parent)
00055         { Base::_setparent(parent); }
00056     
00057     /** Returns a pointer to the root node of the tree. */
00058     Sub *root() const
00059         { return static_cast<Sub*>(Base::_root()); }
00060     
00061     /**
00062      * Returns full path of this node relative to an ancestor.
00063      * If ancestor is NULL, returns the root.
00064      */
00065     UniConfKey fullkey(const Sub *ancestor = NULL) const
00066         { return Base::_fullkey(ancestor); }
00067 
00068     /**
00069      * Finds the sub-node with the specified key.
00070      * If key.isempty(), returns this node.
00071      */
00072     Sub *find(const UniConfKey &key) const
00073         { return static_cast<Sub*>(Base::_find(key)); }
00074     
00075     /**
00076      * Finds the direct child node with the specified key.
00077      *
00078      * If key.numsegments() == 1, then performs the same task
00079      * as find(key), but a little faster.  Otherwise returns NULL.
00080      */
00081     Sub *findchild(const UniConfKey &key) const
00082         { return static_cast<Sub*>(Base::_findchild(key)); }
00083 
00084     /**
00085      * Removes the node for the specified key from the tree
00086      * and deletes it along with any of its children.
00087      *
00088      * If the key is UniConfKey::EMPTY, deletes this object.
00089      */
00090     void remove(const UniConfKey &key)
00091         { delete find(key); }
00092     
00093     /** Removes and deletes all children of this node. */
00094     void zap()
00095     {
00096         if (!xchildren)
00097             return;
00098         // set xchildren to NULL first so that the zap() will happen faster
00099         // otherwise, each child will attempt to unlink itself uselessly
00100 
00101         typename Base::Container *oldchildren = xchildren;
00102         xchildren = NULL;
00103 
00104         // delete all children
00105         typename Base::Container::Iter i(*oldchildren);
00106         for (i.rewind(); i.next();)
00107             delete static_cast<Sub*>(i.ptr());
00108 
00109         delete oldchildren;
00110     }
00111 
00112     /**
00113      * Compares this tree with another using the specified comparator
00114      * function.
00115      * Comparison of a subtree ends when the comparator returns false.
00116      * "comparator" is the value compare function
00117      * "userdata" is userdata for the compare function
00118      * Returns: true if the comparison function returned true each time
00119      */
00120     void compare(const Sub *other, const Comparator &comparator,
00121         void *userdata)
00122     {
00123         _recursivecompare(this, other, reinterpret_cast<
00124             const typename Base::BaseComparator&>(comparator), userdata);
00125     }
00126 
00127     /**
00128      * An iterator that walks over all elements on one level of a
00129      * UniConfTree.
00130      */
00131     class Iter : public Base::Iter
00132     {
00133     public:
00134         typedef typename Base::Iter MyBase;
00135 
00136         /** Creates an iterator over the specified tree. */
00137         Iter(Sub &tree) : Base::Iter(tree)
00138             { }
00139 
00140         /** Returns a pointer to the current node. */
00141         Sub *ptr() const
00142             { return static_cast<Sub*>(MyBase::ptr()); }
00143         WvIterStuff(Sub);
00144     };
00145 };
00146 
00147 
00148 /** A plain UniConfTree that holds keys and values. */
00149 class UniConfValueTree : public UniConfTree<UniConfValueTree>
00150 {
00151     WvString xvalue;  /*!< the value of this entry */
00152     
00153 public:
00154     UniConfValueTree(UniConfValueTree *parent,
00155         const UniConfKey &key, WvStringParm value) :
00156         UniConfTree<UniConfValueTree>(parent, key), xvalue(value)
00157     {
00158     }
00159     
00160     /** Returns the value field. */
00161     const WvString &value() const
00162         { return xvalue; }
00163 
00164     /** Sets the value field. */
00165     void setvalue(WvStringParm value)
00166         { xvalue = value; }
00167 };
00168 
00169 
00170 #endif // __UNICONFTREE_H

Generated on Sat Mar 13 14:55:21 2004 for WvStreams by doxygen 1.3.6-20040222