1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/*
* lu_list.h
*
* Copyright (C) 2016-2018 ERGO-Code
*
* Implementation of doubly linked lists (see [1] section 5.5)
*
* Maintain nelem elements in nlist doubly linked lists. Each element can belong
* to zero or one list at a time.
*
* The implementation uses arrays
*
* flink[0..nelem+nlist-1],
* blink[0..nelem+nlist-1].
*
* In each array, the leading nelem entries store links, the trailing nlist
* entries store heads. That is, for 0 <= i < nelem and 0 <= j < nlist:
*
* flink[i] next element in the list containing element i
* blink[i] previous element in the list containing element i
* flink[nelem+j] first element in list j
* blink[nelem+j] last element in list j
*
* The forward link of the last element in a list points to its flink-head. The
* backward link of the first element in a list points to its blink-head. For
* empty lists the heads point to themselves. When an element is not in any list
* its links point to itself.
*
* Optionally the quantity min_list >= 1 can be updated such that lists
* 1..min_list-1 are empty. Notice that list 0 is not covered by min_list.
*
* [1] Istvan Maros, Computational Techniques of the Simplex Method
*
* Methods:
*
* lu_list_init
* lu_list_add
* lu_list_remove
* lu_list_move
* lu_list_swap
*
* The methods are defined in this header file as static inline. This header
* file must be included after lu_def.h so that lu_int is defined.
*
*/
/* ==========================================================================
* lu_list_init
*
* Initialize all lists to empty.
* ========================================================================== */
static inline void
/* ==========================================================================
* lu_list_add
*
* Add element @elem to list @list. @elem must not be in any list already.
* If list > 0 and min_list != NULL, update *min_list = min(*min_list, list).
* ========================================================================== */
static inline void
/* ==========================================================================
* lu_list_remove
*
* Remove element @elem from its list. If @elem was not in a list before,
* then do nothing.
* ========================================================================== */
static inline void
/* ==========================================================================
* lu_list_move
*
* Remove element @elem from its list (if in a list) and add it to list @list.
* ========================================================================== */
static inline void
/* ==========================================================================
* lu_list_swap
*
* Swap elements @e1 and @e2, which both must be in a list. If @e1 and @e2
* are in the same list, then their positions are swapped. If they are in
* different lists, then each is moved to the other's list.
* ========================================================================== */
static inline void