1 | // list.h |
---|
2 | |
---|
3 | |
---|
4 | // The classes "list" and "list_iterator" are designed for the special needs |
---|
5 | // of Buchberger's algorithm; it is not recommendable to use them for |
---|
6 | // more general purposes. |
---|
7 | // "list" implements a simply linked list of binomials (or, more exactly, |
---|
8 | // pointers on binomials). |
---|
9 | // A list_iterator is not much more than a pointer to a list element, but using |
---|
10 | // iterators instead of pointers makes the code of Buchberger's algorithm much |
---|
11 | // easier to read. |
---|
12 | |
---|
13 | // The delegation of tasks to this classes and the realization of some |
---|
14 | // functions are quite special. |
---|
15 | // So is the insertion of list elements the task of the class list, while the |
---|
16 | // deletion is delegated to the iterator class. The reason is the simple: |
---|
17 | // Elements are almost always inserted at the beginning of a list (except |
---|
18 | // from the case of an ordered list), but can be deleted from an arbitrary |
---|
19 | // place (this is necessary e.g. if a binomial is reduced to zero during |
---|
20 | // Buchberger's algorithm). |
---|
21 | |
---|
22 | // For efficiency reasons, the iterator operations are not secure. They do |
---|
23 | // not check if the iterator really references a list element or if it has |
---|
24 | // reached the end of the list. To assert this, use the is_at_end()-test. |
---|
25 | |
---|
26 | // I have designed an own iterator class instead of taking pointers for |
---|
27 | // iteration as lists members for flexibility reasons: |
---|
28 | // Buchberger's algorithm requires to form pairs of binomials (or, for |
---|
29 | // testing criteria to discard S-Pairs, even triples). So we need up to |
---|
30 | // three pointers to iterate over the generator lists. The advantage of the |
---|
31 | // iterator class is simply that the programmer does not have to keep |
---|
32 | // in mind the lists over which he is actually iterating. |
---|
33 | // This was very helpful for me during the implementation of Buchberger's |
---|
34 | // algorithm (especially for the implementation of |
---|
35 | // SUPPORT_DRIVEN_METHODS_EXTENDED where many lists have to be considered). |
---|
36 | |
---|
37 | |
---|
38 | // There are two different implementations of the class list: |
---|
39 | // - If SL_LIST is set, we use a simply linked list. |
---|
40 | // The insert operations are very efficient because we have to set very |
---|
41 | // few pointers. But the deletion of an element is a dangerous operation |
---|
42 | // because it moves the following element (not the binomial, but the struct) |
---|
43 | // to another storage place. |
---|
44 | // - If DL_LIST is set, we use a doubly linked list. |
---|
45 | // This shows to be considerably slower, but it is easier to use |
---|
46 | |
---|
47 | |
---|
48 | |
---|
49 | #ifndef LIST_H |
---|
50 | #define LIST_H |
---|
51 | |
---|
52 | |
---|
53 | |
---|
54 | #define DL_LIST |
---|
55 | // possibilities: |
---|
56 | // SL_LIST |
---|
57 | // DL_LIST |
---|
58 | |
---|
59 | |
---|
60 | |
---|
61 | #include "binomial__term_ordering.h" |
---|
62 | |
---|
63 | |
---|
64 | |
---|
65 | |
---|
66 | ////////////////////////////// struct element /////////////////////////////// |
---|
67 | |
---|
68 | |
---|
69 | |
---|
70 | |
---|
71 | typedef struct Element |
---|
72 | { |
---|
73 | binomial *entry; |
---|
74 | struct Element *next; |
---|
75 | |
---|
76 | |
---|
77 | #ifdef DL_LIST |
---|
78 | |
---|
79 | struct Element *previous; |
---|
80 | |
---|
81 | #endif // DL_LIST |
---|
82 | |
---|
83 | |
---|
84 | // flags needed by the ideal implementation to speed up Buchberger's |
---|
85 | // algorithm |
---|
86 | BOOLEAN done; |
---|
87 | BOOLEAN head_reduced; |
---|
88 | |
---|
89 | } element; |
---|
90 | |
---|
91 | |
---|
92 | |
---|
93 | |
---|
94 | /////////////////////////// class list //////////////////////////////////// |
---|
95 | |
---|
96 | |
---|
97 | |
---|
98 | |
---|
99 | class list |
---|
100 | { |
---|
101 | |
---|
102 | |
---|
103 | |
---|
104 | private: |
---|
105 | |
---|
106 | |
---|
107 | element *start; |
---|
108 | // pointer to the beginning |
---|
109 | |
---|
110 | |
---|
111 | |
---|
112 | public: |
---|
113 | |
---|
114 | |
---|
115 | // constructors and destructor |
---|
116 | |
---|
117 | list(); |
---|
118 | // Creates an "empty" list (with a dummy element for a user friendly |
---|
119 | // iterator class, see the comments in list.cc). |
---|
120 | |
---|
121 | list(const list&); |
---|
122 | // copy-constructor |
---|
123 | |
---|
124 | ~list(); |
---|
125 | // destructor |
---|
126 | |
---|
127 | |
---|
128 | |
---|
129 | // inserting |
---|
130 | |
---|
131 | list& insert(binomial&); |
---|
132 | list& copy_insert(const binomial&); |
---|
133 | // These operations insert a binomial at the beginning of the list: |
---|
134 | // insert does this by placing pointers on it, copy_insert by copying the |
---|
135 | // binomial. |
---|
136 | // The first operation is dangerous; but the consequent use of the |
---|
137 | // combination insert - extract_element (cf. class list_iterator) instead of |
---|
138 | // copy_insert - delete_element is very important for the performance of |
---|
139 | // Buchberger's algorithm. |
---|
140 | |
---|
141 | list& _insert(binomial&); |
---|
142 | list& _copy_insert(const binomial&); |
---|
143 | // A little more efficient insert function for list that do not use |
---|
144 | // the 3 flags - these are not set. |
---|
145 | // It is not more efficient to implement these simpler lists as an own class. |
---|
146 | |
---|
147 | list& ordered_insert(binomial&, const term_ordering&); |
---|
148 | list& ordered_copy_insert(const binomial&, const term_ordering&); |
---|
149 | // These operations insert a binomial according to the given term ordering |
---|
150 | // into a list. (The list should be ordered by the same term ordering.) |
---|
151 | // To insert elements, we use a simple linear search. |
---|
152 | |
---|
153 | list& _ordered_insert(binomial&, const term_ordering&); |
---|
154 | list& _ordered_copy_insert(const binomial&, const term_ordering&); |
---|
155 | // A little more efficient ordered_insert function for list that do not use |
---|
156 | // the 3 flags - these are not set. |
---|
157 | |
---|
158 | |
---|
159 | |
---|
160 | // output |
---|
161 | |
---|
162 | void print() const; |
---|
163 | void ordered_print(const term_ordering&) const; |
---|
164 | // Writes the list to the standard output medium. |
---|
165 | // The first routine writes the list elements as they are oredred in |
---|
166 | // the list. |
---|
167 | // The second one writes them in increasing order with respect to the |
---|
168 | // argument term ordering; the list has not to be ordered before and |
---|
169 | // will not be ordered after. This routine is essentially written to |
---|
170 | // compare Gröbner bases. |
---|
171 | |
---|
172 | void print(FILE* output) const; |
---|
173 | void ordered_print(FILE* output, const term_ordering&) const; |
---|
174 | // Writes the list to the referenced file which has to be opened for |
---|
175 | // writing before. |
---|
176 | |
---|
177 | void print(ofstream&) const; |
---|
178 | void ordered_print(ofstream&, const term_ordering&) const; |
---|
179 | // Writes the list to the given ofstream. |
---|
180 | |
---|
181 | void format_print(ofstream&) const; |
---|
182 | void ordered_format_print(ofstream&, const term_ordering&) const; |
---|
183 | // Writes the list to the given ofstream in the format needed by the |
---|
184 | // IP-algorithms. |
---|
185 | |
---|
186 | friend class list_iterator; |
---|
187 | |
---|
188 | }; |
---|
189 | |
---|
190 | |
---|
191 | |
---|
192 | |
---|
193 | ///////////////////// class list_iterator //////////////////////////////// |
---|
194 | |
---|
195 | |
---|
196 | |
---|
197 | |
---|
198 | class list_iterator |
---|
199 | { |
---|
200 | |
---|
201 | |
---|
202 | |
---|
203 | private: |
---|
204 | |
---|
205 | element* actual; |
---|
206 | |
---|
207 | |
---|
208 | |
---|
209 | public: |
---|
210 | |
---|
211 | |
---|
212 | |
---|
213 | // constructors and destructor |
---|
214 | |
---|
215 | list_iterator(); |
---|
216 | // Sets actual to NULL. |
---|
217 | |
---|
218 | list_iterator(list& l); |
---|
219 | // Sets a list_iterator to the beginning of l. |
---|
220 | |
---|
221 | list_iterator(list_iterator& iter); |
---|
222 | // Sets a list iterator to the same position as iter. |
---|
223 | |
---|
224 | ~list_iterator(); |
---|
225 | // destructor |
---|
226 | |
---|
227 | |
---|
228 | |
---|
229 | // object information |
---|
230 | |
---|
231 | BOOLEAN element_is_marked_done() const; |
---|
232 | // Returns the "done"-component of the referenced element. |
---|
233 | |
---|
234 | BOOLEAN element_is_marked_head_reduced() const; |
---|
235 | // Returns the "head_reduced"-component of the referenced element. |
---|
236 | |
---|
237 | BOOLEAN is_at_end() const; |
---|
238 | // Returns TRUE iff the iterator is at the end of "its" list |
---|
239 | // (especially if the iterator references no list). |
---|
240 | |
---|
241 | |
---|
242 | |
---|
243 | // assignment |
---|
244 | |
---|
245 | list_iterator& set_to_list(const list& l); |
---|
246 | // Sets the iterator to the beginning of l. |
---|
247 | |
---|
248 | list_iterator& operator=(const list_iterator& iter); |
---|
249 | // Sets the iterator to the same element as iter. |
---|
250 | |
---|
251 | list_iterator& next(); |
---|
252 | // Sets the iterator to the next entry. |
---|
253 | |
---|
254 | |
---|
255 | |
---|
256 | // comparison |
---|
257 | |
---|
258 | int operator==(const list_iterator& iter) const; |
---|
259 | int operator!=(const list_iterator& iter) const; |
---|
260 | // These operators verifie if actual references the same element |
---|
261 | // as iter.actual. |
---|
262 | |
---|
263 | int next_is(const list_iterator& iter) const; |
---|
264 | // Checks if actual->next references the same element as iter.actual. |
---|
265 | // This check is needed in very special situations (two iterators reference |
---|
266 | // subsequent elements of a list, and the first is deleted; then the |
---|
267 | // iterator referencing the second before deletion references freed memory |
---|
268 | // after deletion, cf. the implementation of delete and extract). |
---|
269 | |
---|
270 | |
---|
271 | |
---|
272 | // manipulation of list elements |
---|
273 | |
---|
274 | // All this operations could be declared as const because they do not |
---|
275 | // change the "actual" pointer. For suggestive reasons, this is not done |
---|
276 | // because they change the referenced list element. |
---|
277 | |
---|
278 | binomial& get_element(); |
---|
279 | // Returns the referenced binomial. |
---|
280 | |
---|
281 | list_iterator& delete_element(); |
---|
282 | // Deletes the referenced binomial. |
---|
283 | |
---|
284 | list_iterator& extract_element(); |
---|
285 | // Only resets pointers so that the refenced binomial is no longer found |
---|
286 | // when iterating over the list. |
---|
287 | |
---|
288 | list_iterator& mark_element_done(); |
---|
289 | // Sets the "done"-component of the referenced element to TRUE. |
---|
290 | |
---|
291 | list_iterator& mark_element_undone(); |
---|
292 | // Sets the "done"-component of the referenced element to FALSE. |
---|
293 | |
---|
294 | list_iterator& mark_element_head_reduced(); |
---|
295 | // Sets the "head_reduced"-component of the referenced element to TRUE. |
---|
296 | |
---|
297 | list_iterator& mark_element_head_unreduced(); |
---|
298 | // Sets the "head_reduced"-component of the referenced element to FALSE. |
---|
299 | |
---|
300 | }; |
---|
301 | |
---|
302 | |
---|
303 | #endif // list.h |
---|