chiark / gitweb /
before abolish oee_edgemap in favour of something weirder
authorIan Jackson <ian@davenant.relativity.greenend.org.uk>
Mon, 31 Dec 2007 02:57:15 +0000 (02:57 +0000)
committerIan Jackson <ian@davenant.relativity.greenend.org.uk>
Mon, 31 Dec 2007 02:57:15 +0000 (02:57 +0000)
bgl.cpp
mgraph.c
mgraph.h

diff --git a/bgl.cpp b/bgl.cpp
index ae36ea4..e75918a 100644 (file)
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -28,7 +28,7 @@ extern "C" {
  * e is 0..5.  The edge is edge e out of vertex (x,y).
  *
  * BGL expects an undirected graph's edges to have two descriptors
- * each, one in each direction.
+ * each, one in each direction (otherwise e would be just 0..2).
  */
 
 /*
@@ -50,19 +50,41 @@ class Graph { }; // this is a dummy as our graph has no actual representation
 
 using namespace boost;
 
-struct OutEdgeIterator :
+/*
+ * We use the following alternative numbering for iterating over edges:
+ *
+ *      ix:        \0   /1
+ *                  \  /
+ *               ___ 0   __
+ *               2    1   3
+ *                  /  \
+ *                4/   5\
+ *
+ *
+ * This numbering permits the order-4 nodes at the strip's edge
+ * to have a contiguous edge iterator values 2..5 or 0..3.
+ */
+static const int oee_edgemap[V6]=
+  { 2<<ESHIFT, 1<<ESHIFT, 3<<ESHIFT, 2<<ESHIFT, 4<<ESHIFT, 5<<ESHIFT };
+
+class OutEdgeIterator :
   public iterator_facade<
     OutEdgeIterator,
     int const,
     forward_traversal_tag
 > {
-  int f;
-  void increment() { f += 1<<ESHIFT; }
-  bool equal(OutEdgeIterator const& other) const { return f == other.f; }
+  int v, ix, f;
+  
+  void setf() { f= v | oee_edgemap[ix]; }
+ public:
+  void increment() { ix++; setf(); }
+  bool equal(OutEdgeIterator const& other) const { return ix == other.ix; }
   int const& dereference() const { return f; }
   OutEdgeIterator() { }
-  OutEdgeIterator(int _f) : f(_f) { }
-  OutEdgeIterator(int v, int e) : f(e << ESHIFT | v) { }
+  OutEdgeIterator(int _v, int _ix) : v(_v), ix(_ix) { setf(); }
+
+  static int voe_min(int _v) { return _v & YMASK ? 0 : 2; }
+  static int voe_max(int _v) { return ~_v & YMASK ? V6 : 4; }
 };
  
 typedef counting_iterator<int> VertexIterator;
@@ -103,11 +125,11 @@ namespace boost {
   inline int target(int f, const Graph&) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
   inline std::pair<OutEdgeIterator,OutEdgeIterator>
   out_edges(int v, const Graph&) {
-    return std::make_pair(OutEdgeIterator(v, VE_MIN(v)),
-                         OutEdgeIterator(v, VE_MAX(v)));
+    return std::make_pair(OutEdgeIterator(v, OutEdgeIterator::voe_min(v)),
+                         OutEdgeIterator(v, OutEdgeIterator::voe_max(v)));
   }
   inline unsigned out_degree(int v, const Graph&) {
-    return VE_MAX(v) - VE_MIN(v);
+    return OutEdgeIterator::voe_max(v) - OutEdgeIterator::voe_min(v);
   }
 
   // Concept VertexListGraph:
index 222bd09..19bb4ba 100644 (file)
--- a/mgraph.c
+++ b/mgraph.c
@@ -4,9 +4,8 @@
 
 #include "mgraph.h"
 
-static const unsigned dx[V6]= {   0,  +1,  -1,  +1,  -1,   0  },
-                      dy[V6]= { +Y1, +Y1,   0,   0, -Y1, -Y1  };
-
+static const unsigned dx[V6]= {  +1,  +1,   0,  -1,  -1,   0  },
+                      dy[V6]= {   0, +Y1, +Y1,   0, -Y1, -Y1  };
 
 int edge_end2(unsigned v1, int e) {
   /* The topology is equivalent to that of a square lattice with only
@@ -14,10 +13,10 @@ int edge_end2(unsigned v1, int e) {
    * lattice to make the lines of constant x vertical.  This gives
    * these six directions:
    *
-   *                0  1
+   *                2  1
    *                | /
    *                |/
-   *             2--*--3
+   *             3--*--0
    *              /|
    *             / |
    *            4  5
index a33014b..3995d46 100644 (file)
--- a/mgraph.h
+++ b/mgraph.h
  *
  * We label edges as follows:
  *
- *                         \0   /1
+ *             e:          \2   /1
  *                          \  /
  *                       ___ 0   __
- *                       2    1   3
+ *                       3    1   0
  *                          /  \
  *                        4/   5\
- *
- * (This numbering permits the order-4 nodes at the strip's edge
- *  to have a contiguous edge numbering 2..5 or 0..3.)
- *
- * When we iterate over edges, we iterate first over vertices and then
- * over edges 0 to 2, disregarding edges 3 to 5.
  */
 
 #ifndef MGRAPH_H
 #define FOR_VERTEX(v) \
   for ((v)=0; (v)<N; (v)++)
 
-#define VE_MIN(v) ((v) & YMASK ? 0 : 2)
-#define VE_MAX(v) (~(v) & YMASK ? V6 : 4)
-
 #define FOR_VPEDGE(v,e) \
-  for ((e)=VE_MIN(v); (e)<VE_MAX(v); (e)++)
+  for ((e)=0; (e)<V6; (e)++)
 
 extern int edge_end2(unsigned v1, int e);
 #define EDGE_END2 edge_end2