# HG changeset patch
# User alpar
# Date 1078688014 0
# Node ID ee17030e5f47afbe8ce660783a6b98abf8737458
# Parent  a34e5a909e970d9e64ae600689ee77102abbb4fe
One more step toward the standars interface.

diff -r a34e5a909e97 -r ee17030e5f47 src/work/alpar/emptygraph.h
--- a/src/work/alpar/emptygraph.h	Thu Mar 04 19:45:06 2004 +0000
+++ b/src/work/alpar/emptygraph.h	Sun Mar 07 19:33:34 2004 +0000
@@ -38,7 +38,7 @@
   //  class SymEdgeIt : public EdgeIt {};
   class EachEdgeIt : public EdgeIt {
     EachEdgeIt() {}
-    EachEdgeIt(const EmptyGraph &, NodeIt) {}
+    EachEdgeIt(const EmptyGraph &) {}
   };
 
   EachNodeIt &getFirst(EachNodeIt &) const {}
diff -r a34e5a909e97 -r ee17030e5f47 src/work/alpar/smart_graph.h
--- a/src/work/alpar/smart_graph.h	Thu Mar 04 19:45:06 2004 +0000
+++ b/src/work/alpar/smart_graph.h	Sun Mar 07 19:33:34 2004 +0000
@@ -3,27 +3,28 @@
 #ifndef SMART_GRAPH_H
 #define SMART_GRAPH_H
 
-#include <iostream>
 #include <vector>
 #include <limits.h>
 
+struct _Invalid {} Invalid;
+
 namespace hugo {
 
   class SmartGraph {
 
-    static const int INVALID_EDGE=-1;
-    static const int INVALID_NODE=INT_MAX;
+//     static const int INVALID=-1;
+//     static const int INVALID_NODE=INT_MAX;
 
     struct NodeT 
     {
       int first_in,first_out;      
-      NodeT() : first_in(INVALID_EDGE), first_out(INVALID_EDGE) {}
+      NodeT() : first_in(-1), first_out(-1) {}
     };
     struct EdgeT 
     {
       int head, tail, next_in, next_out;      
       //FIXME: is this necessary?
-      EdgeT() : next_in(INVALID_EDGE), next_out(INVALID_EDGE) {}  
+      EdgeT() : next_in(-1), next_out(-1) {}  
     };
 
     std::vector<NodeT> nodes;
@@ -37,11 +38,10 @@
     public:
       virtual void add(const Key k) = NULL;
       virtual void erase(const Key k) = NULL;
-      DynMapBase(SmartGraph &_G) : G(&_G) {}
+      DynMapBase(const SmartGraph &_G) : G(&_G) {}
       virtual ~DynMapBase() {}
       friend class SmartGraph;
     };
-
   public:
     template <typename T> class DynEdgeMap;
     template <typename T> class DynEdgeMap;
@@ -50,8 +50,8 @@
     class EdgeIt;
 
   protected:
-    std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
-    std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
+    mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
+    mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
     
   public:
 
@@ -60,13 +60,13 @@
     class OutEdgeIt;
     class InEdgeIt;
     
-    //      class NodeIt { int n; };
+    //     class NodeIt { int n; };
     //     class EachNodeIt : public NodeIt { };
     //     class EdgeIt { int n; };
     //     class EachEdgeIt : public EdgeIt {};
     //     class OutEdgeIt : public EdgeIt {};
     //     class InEdgeIt : public EdgeIt {};
-    //    class SymEdgeIt;
+    //     class SymEdgeIt;
     
     template <typename T> class NodeMap;
     template <typename T> class EdgeMap;
@@ -96,13 +96,13 @@
     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
     NodeIt head(EdgeIt e) const { return edges[e.n].head; }
 
-    NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
-    NodeIt aNode(const InEdgeIt& e) const { return head(e); }
-    //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
+//     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
+//     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
+//     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
 
-    NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
-    NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
-    //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
+//     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
+//     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
+//     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
 
     EachNodeIt& getFirst(EachNodeIt& v) const { 
       v=EachNodeIt(*this); return v; }
@@ -127,23 +127,23 @@
       return e; 
     }
 
-    bool valid(EdgeIt e) const { return e.n!=INVALID_EDGE; }
-    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
-    bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
+    bool valid(EdgeIt e) const { return e.n!=-1; }
+    //    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
+    bool valid(NodeIt n) const { return n.n!=-1; }
     
-    void setInvalid(EdgeIt &e) { e.n=INVALID_EDGE; }
-    void setInvalid(NodeIt &n) { n.n=INVALID_NODE; }
+    void setInvalid(EdgeIt &e) { e.n=-1; }
+    void setInvalid(NodeIt &n) { n.n=-1; }
     
-    template <typename It> It next(It it) const
-      //    { It tmp(it); return goNext(tmp); }
-    { It tmp; tmp.n=it.n+1; return tmp; }
+    template <typename It> It getNext(It it) const
+    { It tmp(it); return next(tmp); }
+    //{ It tmp; tmp.n=it.n+1; return tmp; }
 
-    NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
-    OutEdgeIt& goNext(OutEdgeIt& it) const
+    NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
+    OutEdgeIt& next(OutEdgeIt& it) const
     { it.n=edges[it.n].next_out; return it; }
-    InEdgeIt& goNext(InEdgeIt& it) const
+    InEdgeIt& next(InEdgeIt& it) const
     { it.n=edges[it.n].next_in; return it; }
-    EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
+    EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
 
     int id(NodeIt v) const { return v.n; }
     int id(EdgeIt e) const { return e.n; }
@@ -166,7 +166,7 @@
       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
 
       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
-	  i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
+	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
 
       return e;
     }
@@ -186,17 +186,19 @@
     protected:
       int n;
       friend int SmartGraph::id(NodeIt v) const; 
+      NodeIt(int nn) {n=nn;}
     public:
       NodeIt() {}
-      NodeIt(int nn) {n=nn;}
+      NodeIt (_Invalid i) { n=-1; }
       bool operator==(const NodeIt i) const {return n==i.n;}
       bool operator!=(const NodeIt i) const {return n!=i.n;}
+      bool operator<(const NodeIt i) const {return n<i.n;}
     };
     
     class EachNodeIt : public NodeIt {
       friend class SmartGraph;
     public:
-      EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
+      EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
       EachNodeIt() : NodeIt() { }
     };
 
@@ -210,17 +212,21 @@
     protected:
       int n;
       friend int SmartGraph::id(EdgeIt e) const;
+
+      EdgeIt(int nn) {n=nn;}
     public:
       EdgeIt() { }
-      EdgeIt(int nn) {n=nn;}
+      EdgeIt (_Invalid i) { n=-1; }
       bool operator==(const EdgeIt i) const {return n==i.n;}
       bool operator!=(const EdgeIt i) const {return n!=i.n;}
+      bool operator<(const EdgeIt i) const {return n<i.n;}
     };
     
     class EachEdgeIt : public EdgeIt {
       friend class SmartGraph;
     public:
-      EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
+      EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
+      EachEdgeIt (_Invalid i) : EdgeIt(i) { }
       EachEdgeIt() : EdgeIt() { }
     };
     
@@ -228,6 +234,8 @@
       friend class SmartGraph;
     public: 
       OutEdgeIt() : EdgeIt() { }
+      OutEdgeIt (_Invalid i) : EdgeIt(i) { }
+
       OutEdgeIt(const SmartGraph& G,const NodeIt v)
 	: EdgeIt(G.nodes[v.n].first_out) {}
     };
@@ -236,6 +244,7 @@
       friend class SmartGraph;
     public: 
       InEdgeIt() : EdgeIt() { }
+      InEdgeIt (_Invalid i) : EdgeIt(i) { }
       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
     };
 
@@ -285,7 +294,7 @@
       typedef T ValueType;
       typedef NodeIt KeyType;
 
-      DynNodeMap(SmartGraph &_G) :
+      DynNodeMap(const SmartGraph &_G) :
 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
       {
 	//FIXME: What if there are empty Id's?
@@ -311,10 +320,14 @@
       {
 	if(k.n>=container.size()) container.resize(k.n+1);
       }
-      void erase(const NodeIt k)
-      {
-	//FIXME: Please implement me.
-      }
+//       void erase(const NodeIt k)
+//       {
+// 	//FIXME: Please implement me.
+//       }
+//       void erase(const EdgeIt k)
+//       {
+// 	//FIXME: Please implement me.
+//       }
       
       void set(NodeIt n, T a) { container[n.n]=a; }
       T get(NodeIt n) const { return container[n.n]; }
@@ -333,7 +346,7 @@
       typedef T ValueType;
       typedef EdgeIt KeyType;
 
-      DynEdgeMap(SmartGraph &_G) :
+      DynEdgeMap(const SmartGraph &_G) :
 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
       {
 	//FIXME: What if there are empty Id's?
@@ -376,4 +389,7 @@
   };
 } //namespace hugo
 
+
+
+
 #endif //SMART_GRAPH_H
diff -r a34e5a909e97 -r ee17030e5f47 src/work/alpar/smart_graph_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/alpar/smart_graph_demo.cc	Sun Mar 07 19:33:34 2004 +0000
@@ -0,0 +1,36 @@
+#include<smart_graph.h>
+
+#include <iostream>
+
+using namespace hugo;
+
+SmartGraph::OutEdgeIt safeFirstOut(const SmartGraph &G, SmartGraph::NodeIt n)
+{
+  return G.valid(n) ? SmartGraph::OutEdgeIt(G,n):Invalid;
+}
+
+int main()
+{
+
+  typedef SmartGraph::EdgeIt EdgeIt;
+  typedef SmartGraph::InEdgeIt InEdgeIt;
+  typedef SmartGraph::OutEdgeIt OutEdgeIt;
+  typedef SmartGraph::EachEdgeIt EachEdgeIt;
+  typedef SmartGraph::NodeIt NodeIt;
+  typedef SmartGraph::EachNodeIt EachNodeIt;
+  
+  SmartGraph G;
+  EachNodeIt n;
+
+
+  //  std::cout.form("%s: %d\n","Sztring",15);
+
+  for(int i=0;i<10;i++) G.addNode();
+  for(G.getFirst(n);G.valid(n);G.next(n)) 
+    for(EachNodeIt m(G);m!=Invalid;G.next(m)) 
+      if(n!=m) G.addEdge(n,m);
+
+  OutEdgeIt e = safeFirstOut(G,n);
+  OutEdgeIt f = safeFirstOut(G,EachNodeIt(G));
+  
+}