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 UniHashTreeBase *UniHashTreeBase::_findchild(const UniConfKey &key) const
00105 {
00106 if (key.isempty())
00107 return const_cast<UniHashTreeBase*>(this);
00108
00109 return xchildren ? (*xchildren)[key] : NULL;
00110 }
00111
00112
00113 bool UniHashTreeBase::haschildren() const
00114 {
00115 return xchildren && !xchildren->isempty();
00116 }
00117
00118 void UniHashTreeBase::link(UniHashTreeBase *node)
00119 {
00120 if (!xchildren)
00121 xchildren = new Container();
00122
00123 xchildren->add(node);
00124 }
00125
00126 void UniHashTreeBase::unlink(UniHashTreeBase *node)
00127 {
00128 if (!xchildren)
00129 return;
00130
00131 xchildren->remove(node);
00132 if (xchildren->count() == 0)
00133 {
00134 delete xchildren;
00135 xchildren = NULL;
00136 }
00137 }
00138
00139
00140 void UniHashTreeBase::_recursivecompare(
00141 const UniHashTreeBase *a, const UniHashTreeBase *b,
00142 const UniHashTreeBaseComparator &comparator, void *userdata)
00143 {
00144
00145 if (! comparator(a, b, userdata))
00146 return;
00147
00148
00149 Iter ait(*const_cast<UniHashTreeBase*>(a));
00150 if (a != NULL)
00151 {
00152 ait.rewind();
00153 if (ait.next())
00154 a = ait.ptr();
00155 else
00156 a = NULL;
00157 }
00158 Iter bit(*const_cast<UniHashTreeBase*>(b));
00159 if (b != NULL)
00160 {
00161 bit.rewind();
00162 if (bit.next())
00163 b = bit.ptr();
00164 else
00165 b = NULL;
00166 }
00167
00168
00169 while (a != NULL && b != NULL)
00170 {
00171 int order = a->key().compareto(b->key());
00172 if (order < 0)
00173 {
00174 _recursivecompare(a, NULL, comparator, userdata);
00175 a = ait.next() ? ait.ptr() : NULL;
00176 }
00177 else if (order == 0)
00178 {
00179
00180 _recursivecompare(a, b, comparator, userdata);
00181 a = ait.next() ? ait.ptr() : NULL;
00182 b = bit.next() ? bit.ptr() : NULL;
00183 }
00184 else
00185 {
00186 _recursivecompare(NULL, b, comparator, userdata);
00187 b = bit.next() ? bit.ptr() : NULL;
00188 }
00189 }
00190 while (a != NULL)
00191 {
00192 _recursivecompare(a, NULL, comparator, userdata);
00193 a = ait.next() ? ait.ptr() : NULL;
00194 }
00195 while (b != NULL)
00196 {
00197 _recursivecompare(NULL, b, comparator, userdata);
00198 b = bit.next() ? bit.ptr() : NULL;
00199 }
00200 }
00201