CTBmap.cxx Source File

00001 
00006 /*----------------------------------------------------------------------------*/
00007 /* C Tool Box: Designed and implemented by:                                   */
00008 /*    Walter F.J. Mueller   Gesellschaft fuer Schwerionenforschung (GSI)      */
00009 /*                          Planckstrasse 1, D-64291 Darmstadt, Germany       */
00010 /*                  Email:  W.F.J.Mueller@gsi.de                              */
00011 /*                  WWW:    http://www-kp3.gsi.de/www/kp3/people/mueller.html */
00012 /*------------------------------------------+---------------------------------*/
00013 
00014 #include <assert.h>
00015 
00016 #include "CTB.hxx"
00017 #include "CTB_Trace.hxx"
00018 #include "CTBmap.hxx"
00019 
00025 //------------------------------------------+-----------------------------------
00027 
00028 template <class K, class V, class C>
00029 bool CTBmap<K,V,C>::Insert(const CTBpair<const K,V>& pair)
00030 {
00031   CTB_Trace("CTBmap::Insert(const CTBpair&)");
00032   int   i_mtype;
00033   Node* p_parent = LocateMatchOrBound(pair.Key(),i_mtype);
00034 
00035   if (p_parent && i_mtype == 0) return false; // key already present
00036   InsertNode(new Node(pair),p_parent,i_mtype); // create node and insert
00037   return true;
00038 }
00039 
00040 //------------------------------------------+-----------------------------------
00042 
00043 template <class K, class V, class C>
00044 bool CTBmap<K,V,C>::Insert(const K& key, const V& value)
00045 {
00046   CTB_Trace("CTBmap::Insert(const K&,const V&)");
00047   int   i_mtype;
00048   Node* p_parent = LocateMatchOrBound(key,i_mtype);
00049 
00050   if (p_parent && i_mtype == 0) return false; // key already present
00051   InsertNode(new Node(key,value),p_parent,i_mtype); // create node and insert
00052   return true;
00053 }
00054 
00055 //------------------------------------------+-----------------------------------
00057 
00058 template <class K, class V, class C>
00059 bool CTBmap<K,V,C>::Insert(const K& key)
00060 {
00061   CTB_Trace("CTBmap::Insert(const K&)");
00062   int   i_mtype;
00063   Node* p_parent = LocateMatchOrBound(key,i_mtype);
00064 
00065   if (p_parent && i_mtype == 0) return false; // key already present
00066   InsertNode(new Node(key),p_parent,i_mtype); // create node and insert
00067   return true;
00068 }
00069 
00070 //------------------------------------------+-----------------------------------
00072 
00073 template <class K, class V, class C>
00074 CTBmapIterator<K,V,C> CTBmap<K,V,C>::Find(const K& key)
00075 {
00076   CTB_Trace("CTBmap::Find(const K&)");
00077   int   i_mtype;
00078   Node* p_node = LocateMatchOrBound(key,i_mtype);
00079   
00080   if (p_node && i_mtype == 0) return Iterator((Map*) this,p_node);
00081   return Iterator();
00082 }
00083 
00084 //------------------------------------------+-----------------------------------
00086 
00087 template <class K, class V, class C>
00088 CTBmapBrowser<K,V,C> CTBmap<K,V,C>::Find(const K& key) const
00089 {
00090   CTB_Trace("CTBmap::Find(const K&) const");
00091   int   i_mtype;
00092   Node* p_node = LocateMatchOrBound(key,i_mtype);
00093   
00094   if (p_node && i_mtype == 0) return Browser((Map*) this,p_node);
00095   return Browser();
00096 }
00097 
00098 //------------------------------------------+-----------------------------------
00100 
00101 template <class K, class V, class C>
00102 CTBmapIterator<K,V,C> CTBmap<K,V,C>::FindOrCreate(const K& key, bool& b_found)
00103 {
00104   CTB_Trace("CTBmap::FindOrCreate(const K&,bool)");
00105   int   i_mtype;
00106   Node* p_node = LocateMatchOrBound(key,i_mtype);
00107 
00108   b_found = p_node && i_mtype == 0;
00109   if (!b_found) {                           // create if not found
00110     Node* p_new = new Node(key);            // node with key and default value
00111     InsertNode(p_new,p_node,i_mtype);
00112     p_node = p_new;
00113   }
00114   
00115   return Iterator(this,p_node);
00116 }
00117 
00118 //------------------------------------------+-----------------------------------
00120 
00125 template <class K, class V, class C>
00126 bool CTBmap<K,V,C>::Rename(const K& keyold, const K& keynew)
00127 {
00128   CTB_Trace("CTBmap::Rename(const K&,const K&)");
00129   return Rename(Find(keyold),keynew);
00130 }
00131 
00132 //------------------------------------------+-----------------------------------
00134 
00139 template <class K, class V, class C>
00140 bool CTBmap<K,V,C>::Rename(const CTBmapIterator<K,V,C>& p, const K& keynew)
00141 {
00142   // The rename function is genuine hackery ! The key member of Pair is in
00143   // all other circumstances strickly read-only, and to enforce this, the
00144   // Pair is intentionally defined as CTBpair<const K, V>.
00145   // Rename is designed to rename the key of a map entry and leave all
00146   // iterators valid, especially those pointing to the entry being renamed.
00147   // Therefore, we can't simply allocate a new Node with the new key, but
00148   // rather have to change the key of the existing Node.
00149   // The consequence is, that in this and only this function the const of K
00150   // is `cast away' to make the modification possible.
00151   //
00152 
00153   CTB_Trace("CTBmap::Rename(const CTBmapIterator&,const K&)");
00154   int   i_mtype;
00155   Node* p_old  = p;                         // convert iterator to Node*
00156   Node* p_node = LocateMatchOrBound(keynew,i_mtype);
00157   K*    p_key;
00158 
00159   if (!p_old) return false;                 // iterator not valid
00160   if (p_node && i_mtype == 0) return false; // new key already exists
00161   
00162   RemoveNode(p_old);                        // unlink
00163 
00164   p_key  = (K*) &(p_old->Key());            // cast away the const of K !!!
00165   *p_key = keynew;                          // rename key field
00166   
00167   p_node = LocateMatchOrBound(keynew,i_mtype); // reinsert
00168   InsertNode(p_old,p_node,i_mtype);
00169 
00170   return true;
00171 }
00172 
00173 //------------------------------------------+-----------------------------------
00175 
00179 template <class K, class V, class C>
00180 bool CTBmap<K,V,C>::Delete(const K& key)
00181 {
00182   CTB_Trace("CTBmap::Delete(const K&)");
00183   int   i_mtype;
00184   Node* p_node = LocateMatchOrBound(key,i_mtype);
00185 
00186   if (!p_node || i_mtype != 0) return false; // quit if key not found
00187   delete p_node;                            // destruct will do proper unlink
00188   return true;
00189 }
00190 
00191 //------------------------------------------+-----------------------------------
00193 
00197 template <class K, class V, class C>
00198 bool CTBmap<K,V,C>::Delete(const CTBmapIterator<K,V,C>& p)
00199 {
00200   CTB_Trace("CTBmap::Delete(const CTBmapIterator&)");
00201   Node* p_node = p;
00202 
00203   delete p_node;
00204   return p_node;                            // return true if iterator valid
00205 }
00206 
00207 //------------------------------------------+-----------------------------------
00209 
00210 template <class K, class V, class C>
00211 void CTBmap<K,V,C>::Clear()
00212 {
00213   CTB_Trace("CTBmap::Clear()");
00214   CTBbtree::Clear();
00215   return;
00216 }
00217 
00218 //------------------------------------------+-----------------------------------
00220 
00227 template <class K, class V, class C>
00228 CTBmapNode<K,V,C>* CTBmap<K,V,C>::LocateMatchOrBound(const K& key,
00229                                                      int& i_mtype) const
00230 {
00231   CTB_Trace("CTBmap::LocateMatchOrBound(const K&,int&)");
00232   C      compare;                           // compare function object
00233   Node*  p_cur = (Node*) RNode();
00234 
00235   i_mtype = 0;
00236   
00237   if (p_cur) {
00238     for (;;) {
00239       int    i_cmp = compare(key,p_cur->Key());
00240       Node*  p_next;
00241       
00242       if (i_cmp == 0) return p_cur;         // match found
00243 
00244       if (i_cmp < 0) {                      // key < current
00245         p_next = p_cur->Left();             // try to follow left tree
00246         if (!p_next) {                      // if none found quit
00247           i_mtype = -1;                     // new node will be left child
00248           return p_cur;
00249         }
00250 
00251       } else {                              // key > current
00252         p_next = p_cur->Right();            // try to follow right tree
00253         if (!p_next) {                      // if none found quit
00254           i_mtype = 1;                      // new node will be right child
00255           return p_cur;
00256         }
00257       }
00258 
00259       p_cur = p_next;
00260     }
00261   }
00262   return 0;
00263 }
00264 
00265 //------------------------------------------+-----------------------------------
00267 
00268 template <class K, class V, class C>
00269 CTBmapNode<K,V,C>* CTBmap<K,V,C>::LocateMatchOrPrev(const K& key,
00270                                                     bool& b_found) const
00271 {
00272   CTB_Trace("CTBmap::LocateMatchOrPrev(const K&,bool&)");
00273   int   i_mtype;
00274   Node* p_node = LocateMatchOrBound(key,i_mtype);
00275   
00276   b_found = p_node && i_mtype == 0;
00277   if (p_node && i_mtype < 0) {              // if key < node
00278     p_node = p_node->Prev();                // take previous node
00279   }
00280   return p_node;
00281 }
00282 
00283 //------------------------------------------+-----------------------------------
00285 
00286 template <class K, class V, class C>
00287 CTBmapNode<K,V,C>* CTBmap<K,V,C>::LocateMatchOrNext(const K& key,
00288                                                     bool& b_found) const
00289 {
00290   CTB_Trace("CTBmap::LocateMatchOrNext(const K&,bool&)");
00291   int   i_mtype;
00292   Node* p_node = LocateMatchOrBound(key,i_mtype);
00293   
00294   b_found = p_node && i_mtype == 0;
00295   if (p_node && i_mtype > 0) {              // if key > node
00296     p_node = p_node->Next();                // take next node
00297   }
00298   return p_node;
00299 }
00300