Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
oldlist.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2 ###############################################################################
3 #
4 # File: list.c
5 # Description: List processing procedures.
6 # Author: Mark Seaman, Software Productivity
7 # Created: Thu Jul 23 13:24:09 1987
8 # Modified: Thu Dec 22 10:59:52 1988 (Mark Seaman) marks@hpgrlt
9 # Language: C
10 # Package: N/A
11 # Status: Reusable Software Component
12 #
13 # (c) Copyright 1987, Hewlett-Packard Company.
14 ** Licensed under the Apache License, Version 2.0 (the "License");
15 ** you may not use this file except in compliance with the License.
16 ** You may obtain a copy of the License at
17 ** http://www.apache.org/licenses/LICENSE-2.0
18 ** Unless required by applicable law or agreed to in writing, software
19 ** distributed under the License is distributed on an "AS IS" BASIS,
20 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21 ** See the License for the specific language governing permissions and
22 ** limitations under the License.
23 #
24 ################################################################################
25
26 * Revision 1.13 90/03/06 15:37:54 15:37:54 marks (Mark Seaman)
27 * Look for correct file of <malloc.h> or <stdlib.h>
28 *
29 * Revision 1.12 90/02/26 17:37:36 17:37:36 marks (Mark Seaman)
30 * Added pop_off and join_on
31 *
32
33 This file contains a set of general purpose list manipulation routines.
34 These routines can be used in a wide variety of ways to provide several
35 different popular data structures. A new list can be created by declaring
36 a variable of type 'LIST', and can be initialized with the value 'NIL_LIST'.
37 All of these routines check for the NIL_LIST condition before dereferencing
38 pointers. NOTE: There is a users' manual available in printed form from
39 Mark Seaman at (303) 350-4492 at Greeley Hard Copy.
40
41 To implement a STACK use:
42
43 push to add to the Stack l = push (l, (LIST) "jim");
44 pop to remove items from the Stack l = pop (l);
45 first_node to access the head name = (char *) first_node (l);
46
47 To implement a QUEUE use:
48
49 push_last to add to the Queue l = push_last (l, (LIST) "jim");
50 pop remove items from the Queue l = pop (l);
51 first_node to access the head name = (char *) first_node (l);
52
53 To implement LISP like functions use:
54
55 first_node CAR x = (int) first_node (l);
56 rest CDR l = list_rest (l);
57 push CONS l = push (l, (LIST) this);
58 last LAST x = last (l);
59 concat APPEND l = concat (r, s);
60 count LENGTH x = count (l);
61 search MEMBER if (search (l, x, NULL))
62
63 To implement SETS use:
64
65 adjoin l = adjoin (l, x);
66 set_union l = set_union (r, s);
67 intersection l = intersection (r, s);
68 set_difference l = set_difference (r, s);
69 delete l = delete (s, x, NULL);
70 search if (search (l, x, NULL))
71
72 To Implement Associated LISTS use:
73
74 lpush l = lpush (l, p);
75 assoc s = assoc (l, x);
76 adelete l = adelete (l, x);
77
78 The following rules of closure exist for the functions provided.
79 a = first_node (push (a, b))
80 b = list_rest (push (a, b))
81 a = push (pop (a), a)) For all a <> NIL_LIST
82 a = reverse (reverse (a))
83
84 ******************************************************************************/
85 #include "oldlist.h"
86 #include "structures.h"
87 #include <stdio.h>
88 #if MAC_OR_DOS
89 #include <stdlib.h>
90 #else
91 #include "freelist.h"
92 #endif
93
94 /*----------------------------------------------------------------------
95 M a c r o s
96 ----------------------------------------------------------------------*/
97 #define add_on(l,x) l = push (l,first_node (x))
98 #define next_one(l) l = list_rest (l)
99
100 /*----------------------------------------------------------------------
101 F u n c t i o n s
102 ----------------------------------------------------------------------*/
103 /**********************************************************************
104 * c o u n t
105 *
106 * Recursively count the elements in a list. Return the count.
107 **********************************************************************/
108 int count(LIST var_list) {
109 int temp = 0;
110
111 iterate (var_list) temp += 1;
112 return (temp);
113 }
114
115
116 /**********************************************************************
117 * d e l e t e d
118 *
119 * Delete all the elements out of the current list that match the key.
120 * This operation destroys the original list. The caller will supply a
121 * routine that will compare each node to the
122 * key, and return a non-zero value when they match. If the value
123 * NULL is supplied for is_equal, the is_key routine will be used.
124 **********************************************************************/
125 LIST delete_d(LIST list, void *key, int_compare is_equal) {
126 LIST result = NIL_LIST;
127 LIST last_one = NIL_LIST;
128
129 if (is_equal == NULL)
130 is_equal = is_same;
131
132 while (list != NIL_LIST) {
133 if (!(*is_equal) (first_node (list), key)) {
134 if (last_one == NIL_LIST) {
135 last_one = list;
136 list = list_rest (list);
137 result = last_one;
138 set_rest(last_one, NIL_LIST);
139 }
140 else {
141 set_rest(last_one, list);
142 last_one = list;
143 list = list_rest (list);
144 set_rest(last_one, NIL_LIST);
145 }
146 }
147 else {
148 list = pop (list);
149 }
150 }
151 return (result);
152 }
153
154 LIST delete_d(LIST list, void *key,
155 TessResultCallback2<int, void*, void*>* is_equal) {
156 LIST result = NIL_LIST;
157 LIST last_one = NIL_LIST;
158
159 while (list != NIL_LIST) {
160 if (!(*is_equal).Run (first_node (list), key)) {
161 if (last_one == NIL_LIST) {
162 last_one = list;
163 list = list_rest (list);
164 result = last_one;
165 set_rest(last_one, NIL_LIST);
166 }
167 else {
168 set_rest(last_one, list);
169 last_one = list;
170 list = list_rest (list);
171 set_rest(last_one, NIL_LIST);
172 }
173 }
174 else {
175 list = pop (list);
176 }
177 }
178 return (result);
179 }
180
181
182 /**********************************************************************
183 * d e s t r o y
184 *
185 * Return the space taken by a list to the heap.
186 **********************************************************************/
187 LIST destroy(LIST list) {
188 LIST next;
189
190 while (list != NIL_LIST) {
191 next = list_rest (list);
192 free_cell(list);
193 list = next;
194 }
195 return (NIL_LIST);
196 }
197
198
199 /**********************************************************************
200 * d e s t r o y n o d e s
201 *
202 * Return the space taken by the LISTs of a list to the heap.
203 **********************************************************************/
204 void destroy_nodes(LIST list, void_dest destructor) {
205 if (destructor == NULL)
206 destructor = memfree;
207
208 while (list != NIL_LIST) {
209 (*destructor) (first_node (list));
210 list = pop (list);
211 }
212 }
213
214
215 /**********************************************************************
216 * i n s e r t
217 *
218 * Create a list element and rearange the pointers so that the first
219 * element in the list is the second aurgment.
220 **********************************************************************/
221 void insert(LIST list, void *node) {
222 LIST element;
223
224 if (list != NIL_LIST) {
225 element = push (NIL_LIST, node);
226 set_rest (element, list_rest (list));
227 set_rest(list, element);
228 node = first_node (list);
229 list->node = first_node (list_rest (list));
230 list->next->node = (LIST) node;
231 }
232 }
233
234
235 /**********************************************************************
236 * i s s a m e n o d e
237 *
238 * Compare the list node with the key value return TRUE (non-zero)
239 * if they are equivalent strings. (Return FALSE if not)
240 **********************************************************************/
241 int is_same_node(void *item1, void *item2) {
242 return (item1 == item2);
243 }
244
245
246 /**********************************************************************
247 * i s s a m e
248 *
249 * Compare the list node with the key value return TRUE (non-zero)
250 * if they are equivalent strings. (Return FALSE if not)
251 **********************************************************************/
252 int is_same(void *item1, void *item2) {
253 return (!strcmp ((char *) item1, (char *) item2));
254 }
255
256
257 /**********************************************************************
258 * j o i n
259 *
260 * Join the two lists together. This function is similar to concat
261 * except that concat creates a new list. This function returns the
262 * first list updated.
263 **********************************************************************/
264 LIST join(LIST list1, LIST list2) {
265 if (list1 == NIL_LIST)
266 return (list2);
267 set_rest (last (list1), list2);
268 return (list1);
269 }
270
271
272 /**********************************************************************
273 * l a s t
274 *
275 * Return the last list item (this is list type).
276 **********************************************************************/
277 LIST last(LIST var_list) {
278 while (list_rest (var_list) != NIL_LIST)
279 var_list = list_rest (var_list);
280 return (var_list);
281 }
282
283
284 /**********************************************************************
285 * n t h c e l l
286 *
287 * Return nth list cell in the list.
288 **********************************************************************/
289 void *nth_cell(LIST var_list, int item_num) {
290 int x = 0;
291 iterate(var_list) {
292 if (x++ == item_num)
293 return (var_list);
294 }
295 return (var_list);
296 }
297
298
299 /**********************************************************************
300 * p o p
301 *
302 * Return the list with the first element removed. Destroy the space
303 * that it occupied in the list.
304 **********************************************************************/
305 LIST pop(LIST list) {
306 LIST temp;
307
308 temp = list_rest (list);
309
310 if (list != NIL_LIST) {
311 free_cell(list);
312 }
313 return (temp);
314 }
315
316
317 /**********************************************************************
318 * p u s h
319 *
320 * Create a list element. Push the second parameter (the node) onto
321 * the first parameter (the list). Return the new list to the caller.
322 **********************************************************************/
323 LIST push(LIST list, void *element) {
324 LIST t;
325
326 t = new_cell ();
327 t->node = (LIST) element;
328 set_rest(t, list);
329 return (t);
330 }
331
332
333 /**********************************************************************
334 * p u s h l a s t
335 *
336 * Create a list element. Add the element onto the end of the list.
337 **********************************************************************/
338 LIST push_last(LIST list, void *item) {
339 LIST t;
340
341 if (list != NIL_LIST) {
342 t = last (list);
343 t->next = push (NIL_LIST, item);
344 return (list);
345 }
346 else
347 return (push (NIL_LIST, item));
348 }
349
350
351 /**********************************************************************
352 * r e v e r s e
353 *
354 * Create a new list with the elements reversed. The old list is not
355 * destroyed.
356 **********************************************************************/
357 LIST reverse(LIST list) {
358 LIST newlist = NIL_LIST;
359
360 iterate (list) copy_first (list, newlist);
361 return (newlist);
362 }
363
364
365 /**********************************************************************
366 * r e v e r s e d
367 *
368 * Create a new list with the elements reversed. The old list is
369 * destroyed.
370 **********************************************************************/
371 LIST reverse_d(LIST list) {
372 LIST result = reverse (list);
373 destroy(list);
374 return (result);
375 }
376
377
378 /**********************************************************************
379 * s a d j o i n
380 *
381 * Adjoin an element to an assorted list. The original list is
382 * modified. Returns the modified list.
383 **********************************************************************/
384 LIST s_adjoin(LIST var_list, void *variable, int_compare compare) {
385 LIST l;
386 int result;
387
388 if (compare == NULL)
389 compare = (int_compare) strcmp;
390
391 l = var_list;
392 iterate(l) {
393 result = (*compare) (variable, first_node (l));
394 if (result == 0)
395 return (var_list);
396 else if (result < 0) {
397 insert(l, variable);
398 return (var_list);
399 }
400 }
401 return (push_last (var_list, variable));
402 }
403
404
405 /**********************************************************************
406 * s e a r c h
407 *
408 * Search list, return NIL_LIST if not found. Return the list starting from
409 * the item if found. The compare routine "is_equal" is passed in as
410 * the third paramter to this routine. If the value NULL is supplied
411 * for is_equal, the is_key routine will be used.
412 **********************************************************************/
413 LIST search(LIST list, void *key, int_compare is_equal) {
414 if (is_equal == NULL)
415 is_equal = is_same;
416
417 iterate (list) if ((*is_equal) (first_node (list), key))
418 return (list);
419 return (NIL_LIST);
420 }
421
422 LIST search(LIST list, void *key, TessResultCallback2<int, void*, void*>* is_equal) {
423 iterate (list) if ((*is_equal).Run(first_node (list), key))
424 return (list);
425 return (NIL_LIST);
426 }