/Users/jst/src/grafalgo/cpp/dataStructures/searchTrees/TreeMap.cpp

Go to the documentation of this file.

#include "TreeMap.h"

namespace grafalgo {

TreeMap::TreeMap(int size) : Adt(size) {
        makeSpace(size);
}

TreeMap::~TreeMap() { freeSpace(); }

void TreeMap::makeSpace(int size) {
        try {
                st = new BalBstSet(size);
                values = new uint32_t[size+1];
                nodes = new SetPair(size);
        } catch (std::bad_alloc e) {
                stringstream ss;
                ss << "makeSpace:: insufficient space for "
                   << size << "index values";
                string s = ss.str();
                throw OutOfSpaceException(s);
        }
        root = 0;
        nn = size; clear();
}

void TreeMap::freeSpace() {
        delete st; delete [] values; delete nodes;
}

void TreeMap::clear() {
        while (root != 0) { remove(st->key(root)); }
}

void TreeMap::resize(int size) {
        freeSpace();
        try { makeSpace(size); } catch(OutOfSpaceException e) {
                string s; s = "TreeMap::resize::" + e.toString(s);
                throw OutOfSpaceException(s);
        }
}

void TreeMap::expand(int size) {
        if (size <= n()) return;
        TreeMap old(this->n()); old.copyFrom(*this);
        resize(size); this->copyFrom(old);
}
void TreeMap::copyFrom(const TreeMap& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();
        
        for (index x = source.nodes->firstIn(); x != 0;
                   x = source.nodes->nextIn(x)) {
                put(source.st->key(x),source.values[x]); 
        }
}

int TreeMap::get(keytyp key) {
        if (root == 0) return UNDEF_VAL;
        index x = st->access(key,root);
        if (x == 0) return UNDEF_VAL;
        return values[x];
}

bool TreeMap::put(uint64_t key, uint32_t val) {
        index x;
        if (root == 0 || (x = st->access(key,root)) == 0) {
                x = nodes->firstOut();
                if (x == 0) return false;
                nodes->swap(x);
                st->setkey(x,key);
                if (root == 0) root = x;
                else st->insert(x,root);
        }
        values[x] = val;
        return true;
}

void TreeMap::remove(uint64_t key) {
        index x;
        if (root != 0 && (x = st->access(key,root)) != 0) {
                st->remove(x,root); nodes->swap(x);
        }
        return;
}

// Construct string listing the key,value pairs in the map
string& TreeMap::toString(string& s) const {
        stringstream ss;
        for (index u = nodes->firstIn(); u != 0; u = nodes->nextIn(u)) {
                ss << " " << st->key(u) << "," << values[u];
        }
        s = ss.str();
        return s;
}

} // ends namespace