00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_UTIL_BINTREE_H__
00020 #define __CS_UTIL_BINTREE_H__
00021
00022 #include "csutil/blockallocator.h"
00023
00027 template <class T> class csTree
00028 {
00029 private:
00030 struct Element
00031 {
00032 uint32 key;
00033 T value;
00034 Element *left, *right;
00035
00036 inline Element () {}
00037 inline Element (uint32 key0, const T &value0,
00038 Element *left0 = 0, Element *right0 = 0)
00039 : key (key0), value (value0), left (left0), right (right0) {}
00040 inline Element (const Element &o)
00041 : key (o.key), value (o.value), left (o.left), right (o.right) {}
00042 };
00043 Element *Root;
00044 csBlockAllocator<Element> Pool;
00045 int BS;
00046 int Size;
00047
00048 inline Element* New (uint32 key,
00049 Element *left = 0, Element *right = 0)
00050 {
00051 Element *e = Pool.Alloc ();
00052 e->key = key;
00053 e->left = left;
00054 e->right = right;
00055 return e;
00056 }
00057
00058 inline Element* New (uint32 key, const T &value,
00059 Element *left = 0, Element *right = 0)
00060 {
00061 Element *e = Pool.Alloc ();
00062 e->key = key;
00063 e->value = value;
00064 e->left = left;
00065 e->right = right;
00066 return e;
00067 }
00068
00069 void Copy (Element *dest, const Element *src)
00070 {
00071 dest->key = src->key;
00072 dest->value = src->value;
00073 if (src->left) Copy (dest->left = Pool.Alloc (), src->left);
00074 else dest->left = 0;
00075 if (src->right) Copy (dest->right = Pool.Alloc (), src->right);
00076 else dest->right = 0;
00077 }
00078
00079 void DeleteTree (Element *e)
00080 {
00081 if (e->left) DeleteTree (e->left);
00082 if (e->right) DeleteTree (e->right);
00083 Pool.Free (e);
00084 }
00085
00086 Element* Populate (const csArray<uint32> &keys, const csArray<T> &values)
00087 {
00088 int len = keys.Length ();
00089 if (! len) return 0;
00090 int mid = len / 2;
00091 return New (keys[mid], values[mid],
00092 Populate (keys.Section (0, mid-1), values.Section (0, mid-1)),
00093 Populate (keys.Section (mid+1, len-1), values.Section (mid+1, len-1)));
00094 }
00095
00097 typedef void TraverseFunc (uint32 key, const T &value, void *some);
00098
00099 void Traverse (const Element *e, TraverseFunc *func, void *some) const
00100 {
00101 func (e->key, e->value, some);
00102 if (e->left) Traverse (e->left, func, some);
00103 if (e->right) Traverse (e->right, func, some);
00104 }
00105
00106 public:
00111 csTree (int blocksize = 15)
00112 : Pool (blocksize), BS (blocksize), Size (0), Root (0) {}
00113
00115 csTree (const csTree<T> &other)
00116 : Pool (other.BS), BS (other.BS), Size (other.Size)
00117 {
00118 if (other.Root) Copy (Root = Pool.Alloc (), other.Root);
00119 else Root = 0;
00120 }
00121
00123 void PopulateWith (const csArray<uint32> &keys, const csArray<T> &values)
00124 {
00125 CS_ASSERT (! Root);
00126 CS_ASSERT (totallen == values.Length ());
00127 Root = Populate (keys, values);
00128 }
00129
00131 void Traverse (TraverseFunc *func, void *some) const
00132 {
00133 if (Root) Traverse (Root, func, some);
00134 }
00135
00137 void Put (uint32 key, const T &value)
00138 {
00139 if (! Root)
00140 {
00141 Root = New (key, value);
00142 Size++;
00143 return;
00144 }
00145 Element *e = Root;
00146 while (true)
00147 if (key < e->key)
00148 {
00149 if (e->left) e = e->left;
00150 else
00151 {
00152 e->left = New (key, value);
00153 Size++;
00154 return;
00155 }
00156 }
00157 else if (e->key < key)
00158 {
00159 if (e->right) e = e->right;
00160 else
00161 {
00162 e->right = New (key, value);
00163 Size++;
00164 return;
00165 }
00166 }
00167 else
00168 {
00169 e->value = value;
00170 return;
00171 }
00172 }
00173
00175 T& Find (uint32 key)
00176 {
00177 if (! Root)
00178 {
00179 Root = New (key);
00180 Size++;
00181 return Root->value;
00182 }
00183 Element *e = Root;
00184 while (true)
00185 if (key < e->key)
00186 {
00187 if (e->left) e = e->left;
00188 else
00189 {
00190 e->left = New (key);
00191 Size++;
00192 return e->left->value;
00193 }
00194 }
00195 else if (e->key < key)
00196 {
00197 if (e->right) e = e->right;
00198 else
00199 {
00200 e->right = New (key);
00201 Size++;
00202 return e->right->value;
00203 }
00204 }
00205 else return e->value;
00206 }
00207
00209 const T& Find (uint32 key) const
00210 {
00211 static const T zero (0);
00212 if (! Root) return zero;
00213 Element *e = Root;
00214 while (true)
00215 if (key < e->key)
00216 {
00217 if (e->left) e = e->left;
00218 else return zero;
00219 }
00220 else if (e->key < key)
00221 {
00222 if (e->right) e = e->right;
00223 else return zero;
00224 }
00225 else return e->value;
00226 }
00227
00229 bool Delete (uint32 key)
00230 {
00231 if (! Root) return false;
00232 if (Root->key == key)
00233 {
00234 Pool.Free (Root);
00235 Root = 0;
00236 return true;
00237 }
00238
00239 bool left;
00240 Element *old, *e = Root;
00241 while (true)
00242 if (key < e->key)
00243 {
00244 if (e->left) e = e->left;
00245 else return false;
00246 left = true;
00247 old = e;
00248 }
00249 else if (e->key < key)
00250 {
00251 if (e->right) e = e->right;
00252 else return false;
00253 left = false;
00254 old = e;
00255 }
00256 else
00257 {
00258 if (e->left)
00259 {
00260 if (e->right)
00261 {
00262 Element *promoteold = e, *promote = e->right;
00263 while (promote->left)
00264 {
00265 promoteold = promote;
00266 promote = promote->left;
00267 }
00268 promoteold->left = 0;
00269 e->key = promote->key;
00270 e->value = promote->value;
00271 Pool.Free (promote);
00272 }
00273 else
00274 {
00275 if (left) old->left = e->left;
00276 else old->right = e->left;
00277 Pool.Free (e);
00278 }
00279 }
00280 else
00281 {
00282 if (e->right)
00283 {
00284 if (left) old->left = e->right;
00285 else old->right = e->right;
00286 }
00287 else
00288 {
00289 if (left) old->left = 0;
00290 else old->right = 0;
00291 }
00292 Pool.Free (e);
00293 }
00294 Size--;
00295 return true;
00296 }
00297 }
00298
00300 bool DeleteAll ()
00301 {
00302 if (! Root) return false;
00303 DeleteTree (Root);
00304 return true;
00305 }
00306
00308 int GetSize () const
00309 {
00310 return Size;
00311 }
00312 };
00313
00314 #endif