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
}
mnt
data
src
tesseract-ocr
cutil
oldlist.cpp
Generated on Thu Nov 1 2012 20:19:48 for Tesseract by
1.8.1