Grafalgo
Library of useful data structures and algorithms
|
00001 00009 #include "SaTreeMap.h" 00010 00011 namespace grafalgo { 00012 00016 SaTreeMap::SaTreeMap(int size) : Adt(size) { 00017 makeSpace(size); 00018 } 00019 00021 SaTreeMap::~SaTreeMap() { freeSpace(); } 00022 00026 void SaTreeMap::makeSpace(int size) { 00027 try { 00028 st = new SaBstSet(size); 00029 values = new uint32_t[size+1]; 00030 nodes = new SetPair(size); 00031 } catch (std::bad_alloc e) { 00032 stringstream ss; 00033 ss << "makeSpace:: insufficient space for " 00034 << size << "index values"; 00035 string s = ss.str(); 00036 throw OutOfSpaceException(s); 00037 } 00038 root = 0; nn = size; clear(); 00039 } 00040 00042 void SaTreeMap::freeSpace() { 00043 delete st; delete [] values; delete nodes; 00044 } 00045 00047 void SaTreeMap::clear() { 00048 while (root != 0) remove(st->key(root)); 00049 } 00050 00054 void SaTreeMap::resize(int size) { 00055 freeSpace(); 00056 try { makeSpace(size); } catch(OutOfSpaceException e) { 00057 string s; s = "SaTreeMap::resize::" + e.toString(s); 00058 throw OutOfSpaceException(s); 00059 } 00060 } 00061 00066 void SaTreeMap::expand(int size) { 00067 if (size <= n()) return; 00068 SaTreeMap old(this->n()); old.copyFrom(*this); 00069 resize(size); this->copyFrom(old); 00070 } 00074 void SaTreeMap::copyFrom(const SaTreeMap& source) { 00075 if (&source == this) return; 00076 if (source.n() > n()) resize(source.n()); 00077 else clear(); 00078 00079 for (index x = source.nodes->firstIn(); x != 0; 00080 x = source.nodes->nextIn(x)) { 00081 put(source.st->key(x),source.values[x]); 00082 } 00083 } 00084 00089 int SaTreeMap::get(keytyp key) { 00090 if (root == 0) return UNDEF_VAL; 00091 index x = st->access(key,root); 00092 if (x == 0) return UNDEF_VAL; 00093 return values[x]; 00094 } 00095 00103 bool SaTreeMap::put(uint64_t key, uint32_t val) { 00104 index x; 00105 if (root == 0 || (x = st->access(key,root)) == 0) { 00106 x = nodes->firstOut(); 00107 if (x == 0) return false; 00108 nodes->swap(x); 00109 st->setkey(x,key); 00110 if (root == 0) root = x; 00111 else st->insert(x,root); 00112 } 00113 values[x] = val; 00114 return true; 00115 } 00116 00120 void SaTreeMap::remove(uint64_t key) { 00121 index x; 00122 if (root != 0 && (x = st->access(key,root)) != 0) { 00123 st->remove(x,root); nodes->swap(x); 00124 } 00125 return; 00126 } 00127 00132 string& SaTreeMap::toString(string& s) const { 00133 stringstream ss; 00134 for (index u = nodes->firstIn(); u != 0; u = nodes->nextIn(u)) { 00135 ss << " " << st->key(u) << "," << values[u]; 00136 } 00137 s = ss.str(); 00138 return s; 00139 } 00140 00141 } // ends namespace