00001
00002
00003
00004
00005
00006
00007 #include "unihashtree.h"
00008 #include "assert.h"
00009
00010
00011 UniHashTreeBase::UniHashTreeBase(UniHashTreeBase *parent,
00012 const UniConfKey &key) :
00013 xkey(key)
00014 {
00015 xparent = parent;
00016 xchildren = NULL;
00017
00018 if (xparent)
00019 xparent->link(this);
00020 }
00021
00022
00023 UniHashTreeBase::~UniHashTreeBase()
00024 {
00025 if (xchildren)
00026 {
00027 Container *oldchildren = xchildren;
00028 xchildren = NULL;
00029
00030 delete oldchildren;
00031 }
00032
00033
00034
00035
00036
00037 if (xparent)
00038 xparent->unlink(this);
00039 }
00040
00041
00042 void UniHashTreeBase::_setparent(UniHashTreeBase *parent)
00043 {
00044 if (xparent == parent)
00045 return;
00046 if (xparent)
00047 xparent->unlink(this);
00048 xparent = parent;
00049 if (xparent)
00050 xparent->link(this);
00051 }
00052
00053
00054 UniHashTreeBase *UniHashTreeBase::_root() const
00055 {
00056 const UniHashTreeBase *node = this;
00057 while (node->xparent)
00058 node = node->xparent;
00059 return const_cast<UniHashTreeBase*>(node);
00060 }
00061
00062
00063 UniConfKey UniHashTreeBase::_fullkey(const UniHashTreeBase *ancestor) const
00064 {
00065 UniConfKey result;
00066 if (ancestor)
00067 {
00068 const UniHashTreeBase *node = this;
00069 while (node != ancestor)
00070 {
00071 result.prepend(node->key());
00072 node = node->xparent;
00073 assert(node != NULL ||
00074 ! "ancestor was not a node in the tree");
00075 }
00076 }
00077 else
00078 {
00079 const UniHashTreeBase *node = this;
00080 while (node->xparent)
00081 {
00082 result.prepend(node->key());
00083 node = node->xparent;
00084 }
00085 }
00086 return result;
00087 }
00088
00089
00090 UniHashTreeBase *UniHashTreeBase::_find(const UniConfKey &key) const
00091 {
00092 const UniHashTreeBase *node = this;
00093 UniConfKey::Iter it(key);
00094 it.rewind();
00095 while (it.next())
00096 {
00097 node = node->_findchild(it());
00098 if (!node)
00099 break;
00100 }
00101 return const_cast<UniHashTreeBase*>(node);
00102 }
00103
00104
00105 UniHashTreeBase *UniHashTreeBase::_findchild(const UniConfKey &key) const
00106 {
00107 if (key.isempty())
00108 return const_cast<UniHashTreeBase*>(this);
00109
00110 return xchildren ? (*xchildren)[key] : NULL;
00111 }
00112
00113
00114 bool UniHashTreeBase::haschildren() const
00115 {
00116 return xchildren && !xchildren->isempty();
00117 }
00118
00119
00120 void UniHashTreeBase::link(UniHashTreeBase *node)
00121 {
00122 if (!xchildren)
00123 xchildren = new Container();
00124
00125 xchildren->add(node);
00126 }
00127
00128
00129 void UniHashTreeBase::unlink(UniHashTreeBase *node)
00130 {
00131 if (!xchildren)
00132 return;
00133
00134 xchildren->remove(node);
00135 if (xchildren->count() == 0)
00136 {
00137 delete xchildren;
00138 xchildren = NULL;
00139 }
00140 }
00141
00142
00143 static int keysorter(const UniHashTreeBase *a, const UniHashTreeBase *b)
00144 {
00145 return a->key().compareto(b->key());
00146 }
00147
00148 void UniHashTreeBase::_recursive_unsorted_visit(
00149 const UniHashTreeBase *a,
00150 const UniHashTreeBaseVisitor &visitor, void *userdata,
00151 bool preorder, bool postorder)
00152 {
00153 if (preorder)
00154 visitor(a, userdata);
00155 Container::Iter i(*const_cast<Container*>(a->xchildren));
00156 for (i.rewind(); i.next();)
00157 _recursive_unsorted_visit(i.ptr(), visitor, userdata,
00158 preorder, postorder);
00159 if (postorder)
00160 visitor(a, userdata);
00161 }
00162
00163 bool UniHashTreeBase::_recursivecompare(
00164 const UniHashTreeBase *a, const UniHashTreeBase *b,
00165 const UniHashTreeBaseComparator &comparator, void *userdata)
00166 {
00167 bool equal = true;
00168
00169
00170
00171
00172
00173
00174 if (!comparator(a, b, userdata))
00175 equal = false;
00176
00177
00178 Container::Sorter *ait = NULL, *bit = NULL;
00179 if (a != NULL)
00180 {
00181 ait = new Container::Sorter(*const_cast<Container*>(a->xchildren),
00182 keysorter);
00183 ait->rewind();
00184 a = ait->next() ? ait->ptr() : NULL;
00185 }
00186 if (b != NULL)
00187 {
00188 bit = new Container::Sorter(*const_cast<Container*>(b->xchildren),
00189 keysorter);
00190 bit->rewind();
00191 b = bit->next() ? bit->ptr() : NULL;
00192 }
00193
00194
00195 while (a != NULL && b != NULL)
00196 {
00197 int order = a->key().compareto(b->key());
00198 if (order < 0)
00199 {
00200 equal = false;
00201 _recursivecompare(a, NULL, comparator, userdata);
00202 a = ait->next() ? ait->ptr() : NULL;
00203 }
00204 else if (order > 0)
00205 {
00206 equal = false;
00207 _recursivecompare(NULL, b, comparator, userdata);
00208 b = bit->next() ? bit->ptr() : NULL;
00209 }
00210 else
00211 {
00212 if (!_recursivecompare(a, b, comparator, userdata))
00213 equal = false;
00214 a = ait->next() ? ait->ptr() : NULL;
00215 b = bit->next() ? bit->ptr() : NULL;
00216 }
00217 }
00218
00219
00220 while (a != NULL)
00221 {
00222 equal = false;
00223 _recursivecompare(a, NULL, comparator, userdata);
00224 a = ait->next() ? ait->ptr() : NULL;
00225 }
00226 while (b != NULL)
00227 {
00228 equal = false;
00229 _recursivecompare(NULL, b, comparator, userdata);
00230 b = bit->next() ? bit->ptr() : NULL;
00231 }
00232
00233 delete ait;
00234 delete bit;
00235
00236 return equal;
00237 }