1 /*
2 ---------------------------------------------------------------------------
3 BOUND.H
4   Declarations of public routines found in bound.c
5   Macros dealing with weave boundaries
6   Public Domain
7 ---------------------------------------------------------------------------
8 */
9 
10 #ifndef BOUND
11 #define BOUND
12 
13 #include "standard.h"
14 #include "poly.h"
15 
16 #define MAXSTRING 12
17 #define BIGWEAVE (2*MAXSTRING+2)
18 
19 /*
20 ---------------------------------------------------------------------------
21   This algorithm models the solved region of a link by a set of simple
22   weaves and their associated polynomials, which are called tags.  Due to a
23   nice result, any simple weave is uniquely defined by how its inputs are
24   matched to its outputs.  A list of the outputs the inputs are matched to,
25   in the order of the inputs, is enough to define a simple weave.
26   Unfortunatly, there is no similar result about the associated tags.  Since
27   I've never seen a workstation capable of storing 9! polynomials, it
28   is reasonable to assume no weave of more than 8 inputs ever needs to be
29   dealt with.  Weaves of 8 inputs have 16 boundary crossings, so any reduced
30   weave with 8 inputs or less can be stored in (8 copies of 4 bits =32 bits).
31   The size of an integer nowadays is, you guessed it, 32 bits.  Something of
32   type WEAVE is just a simple weave and its tag.  BODY is a compressed
33   representation of the simple weave itself.  TAG is the polynomial
34   associated with that simple weave.
35 ---------------------------------------------------------------------------
36 */
37 
38 struct weave
39 {
40   ub4    boundary[2];       /* Representation of the weave, heavily encoded. */
41   Poly   tag;        /* Polynomial associated with link represented by weave */
42 };
43 typedef struct weave weave;
44 
45 /*
46 ---------------------------------------------------------------------------
47   Global Variables -- located in bound.c
48 ---------------------------------------------------------------------------
49 */
50 extern word       list[];                 /* description of first new weave */
51 extern word       list2[];              /* description of second, if needed */
52 extern word       old_going_in[];   /* Was *i* an input? *old_going_in[i]*. */
53 extern word       going_in[];       /* Will *i* be an input? *going_in[i]*. */
54 extern word       map[];      /* i of old weave becomes map[i] of new weave */
55 extern word       first;                       /* first boundary crossing to remove */
56 extern word       second;                     /* second boundary crossing to remove */
57 extern word       right;                /* Is the crossing being added righthanded? */
58 extern word       oldcross;        /* number of boundary crossings in the old weave */
59 extern word       newcross;       /* number of boundary crossings in each new weave */
60 extern word       oldin;                       /* number of inputs to the old weave */
61 extern word       newin;                       /* number of inputs to the new weave */
62 
63 /*
64 ---------------------------------------------------------------------------
65   Procedures defined in bound.c
66 ---------------------------------------------------------------------------
67 */
68 
69 /* Manipulate those variables whose values are universal to all weaves at a
70    given step.  (These are the global variables declared above).  */
71 void   b_manip(weave *oldweaves);
72 
73 /* Add a crossing to a single weave without removing any pair of boundary
74    crossings.  Compute list, and perhaps list2, describing the new simple
75    weaves.  */
76 void   b_no_pairs(word *list, word *list2, word *one, word *two);
77 
78 /* Add a crossing to a simple weave and remove one pair of boundary crossings.
79    If the result is one or two simple weaves, well and good.  If the result
80    is more complicated than that, b_one_pair is essentially a no-op. */
81 void   b_one_pair(word *list, word *list2, word *one, word *two);
82 
83 
84 /*
85 ---------------------------------------------------------------------------
86 There are three representations of weave boundaries.
87 1) *list* is an array of words of size oldcross saying which crossing
88    is attached to which other crossing.  If list[i]==j, list[j]==i.
89 2) The medium-size representation (two ub4's) stores the values of
90    *list* for only the inputs (the output can be deduced).  Further, each
91    value is stored in 5 bits, with 6 values per ub4.
92 3) The tiny representation recognizes that the medium-size representation
93    is a permutation of the outputs, and permutations can be enumerated.
94    The tiny representation is the number for that permutation.
95 ---------------------------------------------------------------------------
96 */
97 
98 /*
99 ---------------------------------------------------------------------------
100   The macro b_cross determines if two strings cross in a simple weave in
101   standard form.  This formula has been proven to be correct
102   (via a large truth table).
103 ---------------------------------------------------------------------------
104 */
105 #define b_cross( inp1, inp2, outp1, outp2) \
106  (((inp1)<(inp2))==((inp2)<(outp1))==((outp1)<(outp2))==((inp1)<(outp2)))
107 
108 
109 /*
110 ---------------------------------------------------------------------------
111   Switch the positions of *first* and *second* in the boundary *list*.
112 ---------------------------------------------------------------------------
113 */
114 #define b_switch( list, first, second, temp ) \
115 if (1) \
116 { \
117   list[list[first]] = second; \
118   list[list[second]] = first; \
119   temp = list[first]; \
120   list[first] = list[second]; \
121   list[second] = temp; \
122 } else
123 
124 
125 /*
126 ---------------------------------------------------------------------------
127   Should the crossing of *first* and *second* in *list* be righthanded? *i*.
128   Boundary crossings are numbered counterclockwise.  Inside a simple weave,
129   the string with the lowest input should be an overpass.
130 ---------------------------------------------------------------------------
131 */
132 #define b_right( list, going_in, first, second, i ) \
133 if (1) \
134 { \
135   word x = first < list[first] ? first : list[first]; \
136   word y = second < list[second] ? second : list[second]; \
137   if (x > y) {i = x; x = y; y = i;} \
138   i = !(going_in[x] && !going_in[y]); \
139 } else
140 
141 #endif  /* BOUND */
142