/Users/jst/src/grafalgo/cpp/include/PathSet.h

Go to the documentation of this file.

// Header file for path set data structure used to implement
// dynamic trees. Maintains a set of paths on nodes numbered
// {1,...,n}.

#ifndef PATHSET_H
#define PATHSET_H

#include "stdinc.h"
#include "Adt.h"
#include "Util.h"

namespace grafalgo {

typedef int path;               // path
typedef int cost;

class PathSet : public Adt {
public:         PathSet(int);
                ~PathSet();

        struct PathCostPair {
                index x; cost c;
                PathCostPair(index xx, cost cc) : x(xx), c(cc) {}
        }; 
        struct PathPair {
                path p1, p2;
                PathPair(path pp1, path pp2) : p1(pp2), p2(pp2) {}
        }; 

        // common methods
        void    clear();
        void    resize(int);
        void    expand(int);
        void    copyFrom(const PathSet&);

        path    findpath(index);                
        index   findtail(path); 
        PathCostPair findpathcost(path); 
        index   findtreeroot(index);    
        cost    nodeCost(index) const;

        void    addpathcost(path,cost);
        path    join(path,index,path);
        PathPair split(index);  

        string& path2string(path, string&) const;
        string& pathTree2string(path, string&) const;
        string& toString(string&) const;
protected:
        struct PathNode {
        index   left, right, p;         // /<left child, right child, parent
        cost    dcost, dmin;            // /<delta cost and delta min
        };
        PathNode *pnode;                

        index   splay(index);
        void    splaystep(index);
        void    rotate(index);

        void    makeSpace(int);
        void    freeSpace();
};

} // ends namespace

#endif