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