ComtreeTable.cpp

#include "ComtreeTable.h"

namespace forest {

ComtreeTable::ComtreeTable(int maxLnk1, int maxCtx1)
                : maxLnk(maxLnk1), maxCtx(maxCtx1) {
                comtMap = new HashMap<comt_t,Entry,Hash::u32>(maxCtx,false);
                comtList = new Dlist[maxLnk];
                for (int i = 1; i <= maxLnk; i++) comtList[i].resize(maxCtx);
}
                
ComtreeTable::~ComtreeTable() {
                delete comtMap; delete [] comtList;
}

bool ComtreeTable::addLink(int ctx, int lnk, bool rflg, bool cflg) {
        if (!validCtx(ctx)) return false;
                Entry& e = getEntry(ctx);
                ClnkInfo cli;
                int cLnk = e.clMap->put(lnk,cli);
                if (cLnk == 0) return false;

        if (rflg) e.rtrLinks->addLast(cLnk);
        if (cflg) e.coreLinks->addLast(cLnk);
                comtList[lnk].addLast(ctx);

        return true;
}

bool ComtreeTable::removeLink(int ctx, int cLnk) {
        if (!validCtx(ctx)) return false;
                Entry& e = getEntry(ctx);
                if (!e.clMap->valid(cLnk)) return false;

        int lnk = e.clMap->getKey(cLnk);
                if (lnk == e.pLnk) {
                                return removeEntry(ctx);
                }
        e.clMap->remove(lnk);
        e.rtrLinks->remove(cLnk);
        e.coreLinks->remove(cLnk);
                comtList[lnk].remove(ctx);
                return true;
}

int ComtreeTable::addEntry(comt_t comt) {
                Entry e;
                int ctx = comtMap->put(comt,e);
                return ctx;
}

bool ComtreeTable::removeEntry(int ctx) {
                if (!validCtx(ctx)) return true;
                Entry& e = getEntry(ctx);

                // first remove ctx from comtList[lnk] for all links in comtree
                for (int clx = e.clMap->first(); clx != 0; clx = e.clMap->next(clx)) {
                                int lnk = e.clMap->getKey(clx);
                                comtList[lnk].remove(ctx);
                }

                // now clear the map and lists, then drop comt from comtree mapping
                e.clMap->clear(); e.rtrLinks->clear(); e.coreLinks->clear();
                
                int comt = comtMap->getKey(ctx);
                comtMap->remove(comt);
                return true;
}

void ComtreeTable::purgeLink(int lnk) {
                int ctx = comtList[lnk].first();
                while (ctx != 0 ) {
                                Entry& e = getEntry(ctx);
                                if (lnk == e.pLnk) { // skip for now
                                                ctx = comtList[lnk].next(ctx);
                                } else {
                                                int cLnk = e.clMap->find(lnk);
                                                e.clMap->remove(lnk);
                                                e.rtrLinks->remove(cLnk);
                                                e.coreLinks->remove(cLnk);
                                                // now, carefully remove ctx from comtList[lnk]
                                                int x = ctx;
                                                ctx = comtList[lnk].next(ctx);
                                                comtList[lnk].remove(x);
                                }
                }
                // now remove comtrees for which lnk==pLnk
                // note that removeEntry updates comtList[lnk]
                while (!comtList[lnk].empty()) {
                                removeEntry(comtList[lnk].first());
                }
}

bool ComtreeTable::checkEntry(int ctx) const {
                if (!validCtx(ctx)) return false;
                Entry& e = getEntry(ctx);

                for (int cLnk = firstRtrLink(ctx); cLnk != 0;
                                 cLnk = nextRtrLink(ctx,cLnk)) {
                                if (!e.clMap->valid(cLnk)) return false;
                }

                for (int cLnk = firstCoreLink(ctx); cLnk != 0;
                                 cLnk = nextCoreLink(ctx,cLnk)) {
                                if (!e.rtrLinks->member(cLnk)) return false;
                }

                // parent must be a router
                int plnk = getPlink(ctx);
                if (plnk != 0 && !isRtrLink(ctx,plnk)) return false;

                if (inCore(ctx)) {
                                // parent of a core router must be a core router
                                if (plnk != 0 && !isCoreLink(ctx,plnk)) return false;
                } else {
                                // and a non-core router has at most one core link
                                int n = e.coreLinks->length();
                                if (n > 1) return false;
                                // and if it has a core link, it must be the parent link
                                if (n == 1 && !isCoreLink(ctx,plnk)) return false;
                }
                return true;
}

bool ComtreeTable::readEntry(istream& in) {
                int comt, plnk;
                Entry e;

        Util::skipBlank(in);
        if (!Util::readInt(in, comt) || comt < 1) return false;
                if (Util::verify(in,'*')) e.coreFlag = true;
                if (!Util::readInt(in,plnk)) return false;

                if (!Util::verify(in,'{')) return false;
                ClnkInfo cli;
                cli.rates.set(Forest::MINBITRATE,Forest::MINBITRATE,
                                      Forest::MINPKTRATE,Forest::MINPKTRATE);
                while (true) {
                                if (Util::verify(in,'}')) break;
                                int lnk;
                                if (!Util::readInt(in,lnk)) return false;
                                int cLnk = e.clMap->put(lnk,cli);
                                if (Util::verify(in,'+')) {
                                                e.rtrLinks->addLast(cLnk);
                                } else if (Util::verify(in,'*')) {
                                                e.rtrLinks->addLast(cLnk);
                                                e.coreLinks->addLast(cLnk);
                                }
                }
                Util::nextLine(in);

                int ctx = comtMap->put(comt,e);
                if (ctx == 0) return false;

                setPlink(ctx,plnk); // must be done after links are defined

                if (!checkEntry(ctx)) { removeEntry(ctx); return false; }
                
        return true;
}

bool ComtreeTable::read(istream& in) {
                int num;
                Util::skipBlank(in);
                if (!Util::readInt(in,num)) return false;
                Util::nextLine(in);
                for (int i = 1; i <= num; i++) {
                                if (!readEntry(in)) {
                                                cerr << "ComtreeTable::read: could not read "
                                                     << i << "-th comtree\n";
                                                return false;
                                }
                }
        return true;
}

string ComtreeTable::entry2string(int ctx) const {
                stringstream ss;
                if (!validCtx(ctx)) return "";
                Entry& e = getEntry(ctx);
                int comt = comtMap->getKey(ctx);

                ss << comt << e.toString() << endl; 
                return ss.str();
}

string ComtreeTable::toString() const {
                stringstream ss;
                ss << comtMap->size() << endl;
                ss << "# comtree  coreFlag  pLink  links" << endl;
                for (int ctx = firstComt(); ctx != 0; ctx = nextComt(ctx))
                ss << entry2string(ctx);
                return ss.str();
}

} // ends namespace