/*
* 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-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 ___ 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
+ * ___ 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: Or in the square view:
- *
- * \2 /1 2 1
- * \ / | /
- * ___ 0 __ |/
- * 3 1 0 3--*--0
- * / \ /|
- * 4/ 5\ / |
- * 4 5
+ * We label edges as follows:
*
- * (This makes the numbering
- * discontinuity, at the join,
- * vertical and thus tractable.)
+ * \2 /1
+ * \ /
+ * ___ 0 __
+ * 3 1 0
+ * / \
+ * 4/ 5\
*/
#ifndef MGRAPH_H
#include "common.h"
-#define DIMBITS 5
+#define DIMBITS 4
#define XBITS DIMBITS
#define X (1<<XBITS)
#define YBITS DIMBITS
-#define Y (1<<YBITS)
+#define Y ((1<<YBITS) - 1)
/* vertex number: 0000 | y | x
* YBITS XBITS
#define XMASK (X-1)
#define YSHIFT XBITS
#define Y1 (1 << YSHIFT)
-#define YMASK ((Y-1) << YSHIFT)
+#define YMASK (Y << YSHIFT)
#define DIM (N*D3)
extern int edge_end2(unsigned v1, int e);
#define EDGE_END2 edge_end2
+#define RIM_VERTEX_P(v) (((v) & YMASK) == 0 || ((v) & YMASK) == (Y-1)*Y1)
+
#define FOR_VEDGE_X(v1,e,v2,init,otherwise) \
FOR_VPEDGE((v1),(e)) \
if (((v2)= EDGE_END2((v1),(e)), \