X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=moebius2.git;a=blobdiff_plain;f=mgraph.h;h=e98fa850a53658bacf17ff452d03d2341c89afa9;hp=9f02e88c418438c682321d6d30ea916c0ac0ca9e;hb=97ef96dd318b684d829ac950403582788df427d8;hpb=96318dec79e12d23d718139bca74f5d33cd52253

diff --git a/mgraph.h b/mgraph.h
index 9f02e88..e98fa85 100644
--- a/mgraph.h
+++ b/mgraph.h
@@ -1,100 +1,128 @@
+/*
+ * Graph topology
+ */
 /*
  * Vertices in strip are numbered as follows:
  *
- *     ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3   ___ 4   __
- *         Y-1     Y-1      0       0       0       0       0
- *        /  \    /  \    /  \    /  \    /  \    /  \    /  \
- *       /    \  /    \  /    \  /    \  /    \  /    \  /    \
- *     X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___  3  ___ 4
- *     Y-2     Y-2     Y-2      1       1       1       1       1
- *       \    /  \    /  \    /  \    /  \    /  \    /  \    /
- *        \  /    \  /    \  /    \  /    \  /    \  /    \  /
- *     ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3   __
- *         Y-3     Y-3     Y-3      2       2       2       2
- *
- *       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
- *
- *      X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3
- *       1       1       1       1      Y-2     Y-2     Y-2     Y-2
- *        \    /  \    /  \    /  \    /  \    /  \    /  \    /
- *         \  /    \  /    \  /    \  /    \  /    \  /    \  /
- *      ___ X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   __
- *           0       0       0       0      Y-1     Y-1     Y-1
+ *                          :axis of symmetry
+ *			  | :
+ *			  | :
+ *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4  __
+ *         Y-1     Y-1    |0:      0       0       0       0
+ *        /  \    /  \    / :\    /  \    /  \    /  \    /  \
+ *       /    \  /    \  /| : \  /    \  /    \  /    \  /    \
+ *     X-3 ___ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  4
+ *     Y-2     Y-2     Y-2| :  1       1       1       1       1
+ *       \    /  \    /  \| : /  \    /  \    /  \    /  \    /
+ *        \  /    \  /    \ :/    \  /    \  /    \  /    \  /
+ *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  __   4 ___
+ *         Y-3     Y-3    |2:      2       2       2 	   2
+ *        /  \    /  \    / :\    /  \    /  \    /  \    /  \
+ *       /    \  /    \  /| : \  /    \  /    \  /    \  /    \
+ *     X-3 ___ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  4
+ *     Y-4     Y-4     Y-4| :  3       3       3       3       3
+ *			  | :
+ *       .   .   .   .   .| :.   .   .   .   .   .   .   .   .   .
+ *			  | :
+ *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4 ___
+ *         2       2      |Y-3     Y-3     Y-3     Y-3     Y-3
+ *        /  \    /  \    / :\    /  \    /  \    /  \    /  \
+ *       /    \  /    \  /| : \  /    \  /    \  /    \  /    \
+ *          __ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  3  ___  4
+ *             1       1  | :  Y-2     Y-2     Y-2     Y-2     Y-2     Y-2
+ *    /  \    /  \    /  \| : /  \    /  \    /	 \    /  \    /
+ *   /    \  /    \  /    \ :/    \  /    \  /	  \  /    \  /
+ *  -3 ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4 ___
+ *  0      0       0      |Y-1     Y-1     Y-1     Y-1     Y-1
+ *			  | :
+ *			  | :
+ *			  |
+ *                        ^ join, where there is
+ *                           a discontinuity in numbering
  *
  * Node x,y for
- *   0 <= x < X     x = distance along
- *   0 <= y < Y     y = distance across
+ *   0 <= x < X = 2^XBITS     x = distance along
+ *   0 <= y < Y = 2^YBITS-1   y = distance across
  *
  * Vertices are in reading order from diagram above ie x varies fastest.
  *
- * Y must be even.  The actual location opposite (0,0) is (X-(Y-1)/2,0),
- * and likewise opposite (0,Y-1) is ((Y-1)/2,0).
+ * Note that though presentation above is equilateral triangles, this
+ * is not the case.  It's actually a square lattice with half of the
+ * diagonals added.  We can't straighten it out because at the join
+ * the diagonals point the other way!
  *
  * We label edges as follows:
  *
- *			    \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 numbering 2..5 or 0..3.)
+ *		    \2   /1
+ *		     \  /
+ *		  ___ 0   __
+ *		  3    1   0
+ *		     /  \
+ *		   4/   5\
  *
- * When we iterate over edges, we iterate first over vertices and then
- * over edges 0 to 2, disregarding edges 3 to 5.
+ * vertex number:   0000 | y     | x
+ *                        YBITS   XBITS
  */
 
 #ifndef MGRAPH_H
 #define MGRAPH_H
 
-#define XBITS 4
-#define X (1<<XBITS)
-#define YBITS 4
-#define Y (1<<YBITS)
+#include "common.h"
 
-/* vertex number:   0000 | y     | x
- *                        YBITS   XBITS
- */
+#ifndef DEFBITS
+#define XBITS 3
+#define YBITS 3
+#else
+#define XBITS (DEFBITS / 10)
+#define YBITS (DEFBITS % 10)
+#endif
+
+#define X (1<<XBITS)
+#define Y ((1<<YBITS) - 1)
 
 #define N (X*Y)
 #define XMASK (X-1)
 #define YSHIFT XBITS
 #define Y1 (1 << YSHIFT)
-#define YMASK (Y-1 << YSHIFT)
+#define YMASK (Y << YSHIFT)
 
 #define V6 6
 
-#define D3 3
-
 #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);
+int edge_end2(unsigned v1, int e);
 #define EDGE_END2 edge_end2
 
-#define FOR_VEDGE(v1,e) \
-  FOR_VPEDGE((v1),(e))
-    if (((v2)= EDGE_END2((v1),(e))) < 0) ; else
+/* given v1,e  s.t.  v2==EDGE_END2(v1,e) >= 0,
+ * returns  eprime s.t. v1==EDGE_END2(v2,eprime) */
+int edge_reverse(int v1, int e);
 
-#define FOR_EDGE(v1,e,v2) \
-  FOR_VERTEX((v1)) \
-    FOR_VEDGE((v1),(e),(v2))
+#define RIM_VERTEX_P(v) (((v) & YMASK) == 0 || ((v) & YMASK) == (Y-1)*Y1)
 
-#define FOR_COORD(k) \
-  for ((k)=0; (k)<D3; (k)++)
+#define FOR_VEDGE_X(v1,e,v2,init,otherwise)	\
+  FOR_VPEDGE((v1),(e))				\
+    if (((v2)= EDGE_END2((v1),(e)),		\
+	 (init),				\
+	 (v2)) < 0) { otherwise; } else
+
+#define NOTHING ((void)0)
+
+#define FOR_VEDGE(v1,e,v2)			\
+  FOR_VEDGE_X(v1,e,v2,NOTHING,NOTHING)
+
+#define FOR_EDGE(v1,e,v2)			\
+  FOR_VERTEX((v1))				\
+    FOR_VEDGE((v1),(e),(v2))
 
-#define K FOR_COORD(k)
+#define FOR_RIM_VERTEX(vy,vx,v)					\
+  for ((vy)=0; (vy)<Y; (vy)+=Y-1)				\
+    for ((vx)=0; (v)= (vy)<<YSHIFT | (vx), (vx)<X; (vx)++)
 
-typedef struct {
-  double v[N][D3];
-} Layout;
+typedef double Vertices[N][D3];
+struct Vertices { Vertices a; };
 
 #endif /*MGRAPH_H*/