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 Tue Oct 5 01:09:19 2004 for WvStreams by doxygen 1.3.7