diff -r 571003783202 -r 9aca797b87e8 src/work/jacint/j_graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/j_graph.h	Thu Feb 26 11:38:51 2004 +0000
@@ -0,0 +1,363 @@
+// -*- mode:C++ -*-
+
+#ifndef J_GRAPH_H
+#define J_GRAPH_H
+
+#include <iostream>
+#include <vector>
+
+namespace hugo {
+
+  class JGraph {
+
+    struct NodeT 
+    {
+      int in, out;      
+      NodeT() : in(), out() {}
+    };
+   
+    struct EdgeT 
+    {
+      int head, tail, in, out;      
+    };
+
+
+    std::vector<NodeT> nodes;
+    std::vector<EdgeT> edges;
+    
+
+    /*    template <typename Key> class DynMapBase
+    {
+    protected:
+      SmartGraph* G; 
+    public:
+      virtual void add(const Key k) = NULL;
+      virtual void erase(const Key k) = NULL;
+      DynMapBase(SmartGraph &_G) : G(&_G) {}
+      virtual ~DynMapBase() {}
+      friend class SmartGraph;
+      };
+
+    template <typename T> class DynEdgeMap;
+    template <typename T> class DynEdgeMap;
+    */
+
+  public:
+  
+    class TrivNodeIt;
+    class TrivEdgeIt;
+    class NodeIt;
+    class EdgeIt;
+    class OutEdgeIt;
+    class InEdgeIt;
+    
+    /*  protected:
+    std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
+    std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
+    */
+
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+    
+  public:
+
+    JGraph() : nodes(1), edges(1) {
+      edges[0].head=0; 
+      edges[0].tail=0; 
+      edges[0].in=0; //numEdges (numNodes is maintained in nodes[0].in)
+      edges[0].out=0; 
+    }    
+
+
+    /*    ~SmartGraph()
+    {
+      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
+	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
+      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
+	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
+	  }*/
+
+    int numNodes() const { return nodes[0].in; }
+    int numEdges() const { return edges[0].in; } 
+
+    TrivNodeIt tail(TrivEdgeIt e) const { return edges[e.n].tail; }
+    TrivNodeIt head(TrivEdgeIt e) const { return edges[e.n].head; }
+
+    /*    EachNodeIt& getFirst(EachNodeIt& v) const { 
+      v=EachNodeIt(*this); return v; }
+    EachEdgeIt& getFirst(EachEdgeIt& e) const { 
+      e=EachEdgeIt(*this); return e; }
+    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 
+      e=OutEdgeIt(*this,v); return e; }
+    InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 
+      e=InEdgeIt(*this,v); return e; }
+    */
+
+    NodeIt firstNode() const { 
+      return NodeIt( numNodes() );
+    }
+    EdgeIt firstEdge() const { 
+      return EdgeIt( numEdges() );
+    }
+    InEdgeIt firstIn(TrivNodeIt v) const { 
+      return InEdgeIt(nodes[v.n].in);
+    }
+    OutEdgeIt firstOut(TrivNodeIt v) const { 
+      return OutEdgeIt(nodes[v.n].out);
+    }
+
+
+   
+    void next(NodeIt& it) const {--it.n;}
+    void next(OutEdgeIt& it) const { it.n=edges[it.n].out; }
+    void next(InEdgeIt& it) const { it.n=edges[it.n].in; }
+    void next(EdgeIt& it) const {--it.n;}
+    
+    int id(TrivNodeIt v) const { return v.n; }
+    int id(TrivEdgeIt e) const { return e.n; }
+
+    TrivNodeIt addNode() {
+      TrivNodeIt n; 
+      n.n=++nodes[0].in;
+      nodes.push_back(NodeT()); //FIXME
+
+      /*      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
+	      i!=dyn_node_maps.end(); ++i) (**i).add(n.n);*/
+
+      return n;
+    }
+    
+
+    TrivEdgeIt addEdge(TrivNodeIt u, TrivNodeIt v) {
+      if ( u && v ) {
+      TrivEdgeIt e; 
+      e.n=++edges[0].in;
+      edges.push_back(EdgeT()); //FIXME: Hmmm...
+      edges[e.n].tail=u.n;   edges[e.n].head=v.n;
+      edges[e.n].out=nodes[u.n].out;
+      edges[e.n].in=nodes[v.n].in;
+      nodes[u.n].out=nodes[v.n].in=e.n;
+      return e;
+      } 
+      else return TrivEdgeIt();
+
+	       /*      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
+		       i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);*/
+
+      
+    }
+
+
+    void clear() {
+      nodes.resize(1);
+      edges.resize(1); edges[0].in=0;
+    }
+
+
+    class TrivNodeIt {
+      friend class JGraph;
+      template <typename T> friend class NodeMap;
+      
+      friend class TrivEdgeIt;
+      friend class OutEdgeIt;
+      friend class InEdgeIt;
+
+    protected:
+      int n;
+    public:
+      TrivNodeIt() : n() {}
+      TrivNodeIt(int number) {n=number;}
+      bool operator==(const TrivNodeIt i) const {return n==i.n;}
+      bool operator!=(const TrivNodeIt i) const {return n!=i.n;}
+   
+      operator bool() const  { return n!=0; }
+   
+ };
+    
+
+    class NodeIt : public TrivNodeIt {
+      friend class JGraph;
+    public:
+      NodeIt() : TrivNodeIt() { }
+      NodeIt(int i) : TrivNodeIt(i) { }
+      operator bool() const  { return n!=0; }
+    };
+
+
+    class TrivEdgeIt {
+      friend class JGraph;
+      template <typename T> friend class EdgeMap;
+      
+      friend class TrivNodeIt;
+      friend class NodeIt;
+    protected:
+      int n;
+    public:
+      TrivEdgeIt() : n() { }
+      TrivEdgeIt(int number) {n=number;}
+      bool operator==(const TrivEdgeIt i) const {return n==i.n;}
+      bool operator!=(const TrivEdgeIt i) const {return n!=i.n;}
+      operator bool() const { return n!=0; }
+    
+ };
+    
+
+    class EdgeIt : public TrivEdgeIt {
+      friend class JGraph;
+    public:
+      EdgeIt() : TrivEdgeIt() { }
+      EdgeIt(int i) : TrivEdgeIt(i) { }
+      operator bool() const { return n!=0; } 
+ };
+    
+
+    class OutEdgeIt : public TrivEdgeIt {
+      friend class JGraph;
+    public: 
+      OutEdgeIt() : TrivEdgeIt() { }
+      OutEdgeIt(int i) : TrivEdgeIt(i) { }
+    };
+    
+
+    class InEdgeIt : public TrivEdgeIt {
+      friend class JGraph;
+    public: 
+      InEdgeIt() : TrivEdgeIt() { }
+      InEdgeIt(int i) : TrivEdgeIt(i) { }
+    };
+
+
+    // Map types
+    
+    template <typename T>
+    class NodeMap {
+      const JGraph& G; 
+      std::vector<T> container;
+    public:
+      NodeMap(const JGraph& _G) : G(_G), container( G.numNodes()+1  ) { }
+      NodeMap(const JGraph& _G, T a) : 
+	G(_G), container(G.numNodes()+1, a) { }
+      void set(TrivNodeIt n, T a) { container[n.n]=a; }
+      T get(TrivNodeIt n) const { return container[n.n]; }
+      /*T& operator[](NodeIt n) { return container[n.n]; }
+	const T& operator[](NodeIt n) const { return container[n.n]; }*/
+      void update() { container.resize(G.numNodes()+1); }
+      void update(T a) { container.resize(G.numNodes()+1, a); }
+    };
+
+    template <typename T>
+    class EdgeMap {
+      const JGraph& G; 
+      std::vector<T> container;
+    public:
+      EdgeMap(const JGraph& _G) : G(_G), container(G.numEdges()+1) { }
+      EdgeMap(const JGraph& _G, T a) : 
+	G(_G), container(G.numEdges()+1, a) { }
+      void set(TrivEdgeIt e, T a) { container[e.n]=a; }
+      T get(TrivEdgeIt e) const { return container[e.n]; }
+      /*T& operator[](EdgeIt e) { return container[e.n]; } 
+	const T& operator[](EdgeIt e) const { return container[e.n]; } */
+      void update() { container.resize(G.numEdges()+1); }
+      void update(T a) { container.resize(G.numEdges()+1, a); }
+    };
+
+    /*template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
+    {
+      std::vector<T> container;
+
+    public:
+      typedef T ValueType;
+      typedef NodeIt KeyType;
+
+      DynNodeMap(JGraph &_G) :
+	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
+      {
+	//FIXME: What if there are empty Id's?
+	//FIXME: Can I use 'this' in a constructor?
+	G->dyn_node_maps.push_back(this);
+      }
+      ~DynNodeMap()
+      {
+	if(G) {
+	  std::vector<DynMapBase<NodeIt>* >::iterator i;
+	  for(i=G->dyn_node_maps.begin();
+	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
+	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
+	  //A better way to do that: (Is this really important?)
+	  if(*i==this) {
+	    *i=G->dyn_node_maps.back();
+	    G->dyn_node_maps.pop_back();
+	  }
+	}
+      }
+
+      void add(const NodeIt k) 
+      {
+	if(k.n>=container.size()) container.resize(k.n+1);
+      }
+      void erase(const NodeIt k)
+      {
+	//FIXME: Please implement me.
+      }
+      
+      void set(NodeIt n, T a) { container[n.n]=a; }
+      T get(NodeIt n) const { return container[n.n]; }
+      T& operator[](NodeIt n) { return container[n.n]; }
+      const T& operator[](NodeIt n) const { return container[n.n]; }
+
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+    };
+    
+    template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
+    {
+      std::vector<T> container;
+
+    public:
+      typedef T ValueType;
+      typedef EdgeIt KeyType;
+
+      DynEdgeMap(JGraph &_G) :
+	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
+      {
+	//FIXME: What if there are empty Id's?
+	//FIXME: Can I use 'this' in a constructor?
+	G->dyn_edge_maps.push_back(this);
+      }
+      ~DynEdgeMap()
+      {
+	if(G) {
+	  std::vector<DynMapBase<EdgeIt>* >::iterator i;
+	  for(i=G->dyn_edge_maps.begin();
+	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
+	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
+	  //A better way to do that: (Is this really important?)
+	  if(*i==this) {
+	    *i=G->dyn_edge_maps.back();
+	    G->dyn_edge_maps.pop_back();
+	  }
+	}
+      }
+      
+      void add(const EdgeIt k) 
+      {
+	if(k.n>=int(container.size())) container.resize(k.n+1);
+      }
+      void erase(const EdgeIt k)
+      {
+	//FIXME: Please implement me.
+      }
+      
+      void set(EdgeIt n, T a) { container[n.n]=a; }
+      T get(EdgeIt n) const { return container[n.n]; }
+      T& operator[](EdgeIt n) { return container[n.n]; }
+      const T& operator[](EdgeIt n) const { return container[n.n]; }
+
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+      };*/
+        
+  };
+} //namespace hugo
+
+#endif //J_GRAPH_H