/** @file
* Special DAG structure template declarations.
* Copyright (C) ArkM, 2008. All rights reserved.
* Alpha version 2008-09-25/2.
* Free for non-commercial use.
*/
#ifndef DAGSTUFF_H
#define DAGSTUFF_H
/// Misc class predeclaration.
class DagLoaderImpl;
/// Helper to load DAG file with double values
/** It's impossible to declare it explicitly. */
class DagLoader {
public:
virtual ~DagLoader() { close(); }
static DagLoader* create();
void Delete();
bool open(const char* fname);
int countLines();
bool getLine();
bool getNext(double& x);
void close();
private:
DagLoader():pImpl(0) {}
DagLoaderImpl* pImpl;
};
/// Special DAG structure based on the two-way tree.
/** It's possible to include any user data in verticies.
* By default it's an int var == 0.
* Weight type: any number type.
* Not copiable.
*/
template<typename Weight = int, class UserData = typename Weight>
class DagBase {
public:
DagBase(): pool(0), rows(0), loader(*DagLoader::create()), pRow(0)
{}
virtual ~DagBase() {
delete pool;
delete pRow;
}
/// The DAG root has level index zero.
/** columns index started from zero. */
Weight weight(int level, int column) const {
return (pRow[level]+column)->weight;
}
UserData& data(int level, int column) {
return (pRow[level]+column)->data;
}
const UserData& data(int level, int column) const {
return (pRow[level]+column)->data;
}
UserData* dataPtr(int level, int column = 0) {
return &(pRow[level]+column)->data;
}
const UserData* dataPtr(int level, int column = 0) const {
return &(pRow[level]+column)->data;
}
int levels() const { return rows; }
/// Load DAG file.
bool load(const char* fname) {
bool res = loader.open(fname);
if (!res)
return false;
int n = loader.countLines();
if (n <= 0)
return false;
int i;
int level = 0;
Weight w;
double x;
int cells = n *(n+1)/2;
delete [] pool;
delete [] pRow;
DagNode* p;
pool = p = new DagNode[cells];
pRow = new DagNode*[n];
// Avoid STL dependencies in the header...
//pRow.reserve(n);
while (loader.getLine()) {
//pRow.push_back(p);
pRow[level] = p;
n = ++level;
for (i = 0; i < level && loader.getNext(x); ++i) {
w = static_cast<Weight>(x);
p++ ->weight = w;
}
if (i < level) {
loader.close();
res = false;
break;
}
}
if (res)
rows = n;
return res;
}
/// Probe DAG cursor class (DAG navigation).
/** @todo Add indicies check up... */
class cursor {
public:
typedef DagBase<Weight,UserData> Dag;
/// Must be attached before using!
cursor():i(0), j(0), n(0), pdag(0)
{}
explicit cursor(Dag& dag):
i(0), j(0), n(dag.levels()), pdag(&dag)
{}
void attachDag(Dag& dag) {
i = j = 0;
pdag = &dag;
}
int getLevel() const { return i; }
int getColumn() const { return j; }
bool toRoot() {
i = j = 0;
return n > 0;
}
bool move(int level, int column) {
if (level >= 0 && level < n &&
column >= 0 && n - column >= 1) {
i = level; j = column;
return true;
}
return false;
}
bool toBottomLeft() {
return move(n-1,0);
}
bool mightDown() const { return n - i >= 1; }
bool mightUp() const { return i > 0; }
bool mightLeft() const { return j > 0; }
bool mightRight()const { return i - j >= 1; }
bool downLeft() {
if (n - i > 1) {
++i;
return true;
}
return false;
}
bool operator++() { return downLeft(); } // ++c
bool downRight() {
if (n - i >= 1) {
++i, ++j;
return true;
}
return false;
}
bool operator++(int) { return downRight(); } // c++
bool upLeft() {
if (i > 0 && j > 0) {
--i, --j;
return true;
}
return false;
}
bool operator --() { return upLeft(); } // --c
bool upRight() {
if (i > 0 && i - j >= 1) {
--i;
return true;
}
return false;
}
bool operator --(int) { return upRight(); } // c--
Weight weight() const {
return pdag?pdag->weight(i,j):Weight(0);
}
UserData& data() { return pdag->data(); }
operator bool() const { return i < n; }
protected:
int i, j, n;
Dag* pdag;
}; // end of cursor definition.
protected:
struct DagNode {
DagNode():weight(0), data(0)
{}
Weight weight;
UserData data;
/// dag[i][j] gets vertex weight.
Weight operator[](int j) const {
return this[j].weight;
}
};
DagNode* pool;
// No std::vector dependency now...
//std::vector<DagNode*> pRow;
DagNode** pRow;
private:
DagLoader& loader;
int rows;
DagBase(const DagBase&);
DagBase& operator =(const DagBase&);
};
#endif
... 
I was clearly making my own problem bigger than it needed to be, but it allowed me to learn rather important principles!