chiark / gitweb /
actually do precomputations!
[moebius2.git] / mgraph.h
1 /*
2  * Graph topology
3  */
4 /*
5  * Vertices in strip are numbered as follows:
6  *
7  *                          :axis of symmetry
8  *                        | :
9  *                        | :
10  *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4  __
11  *         Y-1     Y-1    |0:      0       0       0       0
12  *        /  \    /  \    / :\    /  \    /  \    /  \    /  \
13  *       /    \  /    \  /| : \  /    \  /    \  /    \  /    \
14  *     X-3 ___ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  4
15  *     Y-2     Y-2     Y-2| :  1       1       1       1       1
16  *       \    /  \    /  \| : /  \    /  \    /  \    /  \    /
17  *        \  /    \  /    \ :/    \  /    \  /    \  /    \  /
18  *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  __   4 ___
19  *         Y-3     Y-3    |2:      2       2       2       2
20  *        /  \    /  \    / :\    /  \    /  \    /  \    /  \
21  *       /    \  /    \  /| : \  /    \  /    \  /    \  /    \
22  *     X-3 ___ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  4
23  *     Y-4     Y-4     Y-4| :  3       3       3       3       3
24  *                        | :
25  *       .   .   .   .   .| :.   .   .   .   .   .   .   .   .   .
26  *                        | :
27  *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4 ___
28  *         2       2      |Y-3     Y-3     Y-3     Y-3     Y-3
29  *        /  \    /  \    / :\    /  \    /  \    /  \    /  \
30  *       /    \  /    \  /| : \  /    \  /    \  /    \  /    \
31  *          __ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  3  ___  4
32  *             1       1  | :  Y-2     Y-2     Y-2     Y-2     Y-2     Y-2
33  *    /  \    /  \    /  \| : /  \    /  \    /  \    /  \    /
34  *   /    \  /    \  /    \ :/    \  /    \  /    \  /    \  /
35  *  -3 ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4 ___
36  *  0      0       0      |Y-1     Y-1     Y-1     Y-1     Y-1
37  *                        | :
38  *                        | :
39  *                        |
40  *                        ^ join, where there is
41  *                           a discontinuity in numbering
42  *
43  * Node x,y for
44  *   0 <= x < X = 2^XBITS     x = distance along
45  *   0 <= y < Y = 2^YBITS-1   y = distance across
46  *
47  * Vertices are in reading order from diagram above ie x varies fastest.
48  *
49  * Note that though presentation above is equilateral triangles, this
50  * is not the case.  It's actually a square lattice with half of the
51  * diagonals added.  We can't straighten it out because at the join
52  * the diagonals point the other way!
53  *
54  * We label edges as follows:
55  *
56  *                  \2   /1
57  *                   \  /
58  *                ___ 0   __
59  *                3    1   0
60  *                   /  \
61  *                 4/   5\
62  *
63  * vertex number:   0000 | y      | x
64  *                        (YBITS)   XBITS
65  */
66
67 #ifndef MGRAPH_H
68 #define MGRAPH_H
69
70 #include "common.h"
71
72 #ifndef DEFSZ /* DEFSZ may be (Y/2-1)*10 + XBITS ie Y is 2*<tens>+1 */
73 #define XBITS 3
74 #define YBITS 3
75 #define Y ((1<<YBITS) - 1)
76 #define YMASK (Y << YSHIFT)
77 #else
78 #define XBITS  (DEFSZ % 10)
79 #define Y      ((DEFSZ / 10)*2+1)
80 #endif
81
82 #define X (1<<XBITS)
83
84 #define N (X*Y)
85 #define XMASK (X-1)
86 #define YSHIFT XBITS
87 #define Y1 (1 << YSHIFT)
88
89 #define V6 6
90 #define V3 3
91
92
93 /* Loop constructors are macros of the form
94  *    LOOP(v,zero,n, precomp)
95  * which work much like this one:
96  */
97 #define INNER(v,zero,n, precomp)  \
98   for ((v)=(zero); precomp, (v)<(n); (v)++)
99
100 #define FOR_VERTEX(v,loop) \
101   loop ((v), 0, N, NOTHING)
102
103 #define FOR_VPEDGE(e) \
104   for ((e)=0; (e)<V6; (e)++)
105
106 int edge_end2(unsigned v1, int e);
107 #define EDGE_END2 edge_end2
108
109 /* given    v1,e     s.t.  v2==EDGE_END2(v1,e) >= 0,
110  * returns  eprime   s.t.  v1==EDGE_END2(v2,eprime) */
111 int edge_reverse(int v1, int e);
112
113 #define EDGE_OPPOSITE(e) (((e)+V3) % V6)
114
115 #define RIM_VERTEX_P(v) (((v) & ~XMASK) == 0 || ((v) & ~XMASK) == (Y-1)*Y1)
116
117 #define FOR_VEDGE_X(v1,e,v2,init,otherwise)     \
118   FOR_VPEDGE((e))                               \
119     if (((v2)= EDGE_END2((v1),(e)),             \
120          (init),                                \
121          (v2)) < 0) { otherwise; } else
122
123 #define NOTHING ((void)0)
124
125 #define FOR_VEDGE(v1,e,v2)                      \
126   FOR_VEDGE_X(v1,e,v2,NOTHING,NOTHING)
127
128 #define FOR_EDGE(v1,e,v2, loop)                 \
129   FOR_VERTEX((v1), loop)                        \
130     FOR_VEDGE((v1),(e),(v2))
131
132 #define FOR_RIM_VERTEX(vy,vx,v, loop)           \
133   for ((vy)=0; (vy)<Y; (vy)+=Y-1)               \
134     loop ((vx), 0, X, (v)= (vy)<<YSHIFT | (vx))
135
136 int vertices_span_join_p(int v0, int v1);
137
138 typedef double Vertices[N][D3];
139 struct Vertices { Vertices a; };
140
141 #endif /*MGRAPH_H*/