tesseract  4.1.1
oldlist.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2 ###############################################################################
3 #
4 # File: oldlist.cpp
5 # Description: List processing procedures.
6 # Author: Mark Seaman, Software Productivity
7 #
8 # (c) Copyright 1987, Hewlett-Packard Company.
9 ** Licensed under the Apache License, Version 2.0 (the "License");
10 ** you may not use this file except in compliance with the License.
11 ** You may obtain a copy of the License at
12 ** http://www.apache.org/licenses/LICENSE-2.0
13 ** Unless required by applicable law or agreed to in writing, software
14 ** distributed under the License is distributed on an "AS IS" BASIS,
15 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 ** See the License for the specific language governing permissions and
17 ** limitations under the License.
18 #
19 ###############################################################################
20 
21  This file contains a set of general purpose list manipulation routines.
22  These routines can be used in a wide variety of ways to provide several
23  different popular data structures. A new list can be created by declaring
24  a variable of type 'LIST', and can be initialized with the value 'NIL_LIST'.
25  All of these routines check for the NIL_LIST condition before dereferencing
26  pointers. NOTE: There is a users' manual available in printed form from
27  Mark Seaman at (303) 350-4492 at Greeley Hard Copy.
28 
29  To implement a STACK use:
30 
31  push to add to the Stack l = push(l, (LIST)"jim");
32  pop to remove items from the Stack l = pop(l);
33  first_node to access the head name = (char *)first_node(l);
34 
35  To implement a QUEUE use:
36 
37  push_last to add to the Queue l = push_last(l, (LIST)"x");
38  pop remove items from the Queue l = pop(l);
39  first_node to access the head name = (char *)first_node (l);
40 
41  To implement LISP like functions use:
42 
43  first_node CAR x = (int)first_node(l);
44  rest CDR l = list_rest (l);
45  push CONS l = push(l, (LIST)this);
46  last LAST x = last(l);
47  concat APPEND l = concat(r, s);
48  count LENGTH x = count(l);
49  search MEMBER if (search(l, x, nullptr))
50 
51  The following rules of closure exist for the functions provided.
52  a = first_node (push (a, b))
53  b = list_rest (push (a, b))
54  a = push (pop (a), a)) For all a <> NIL_LIST
55  a = reverse (reverse (a))
56 
57 ******************************************************************************/
58 #include "oldlist.h"
59 #include <cstdio>
60 #include <cstring> // for strcmp
61 #include "errcode.h" // for ASSERT_HOST
62 
63 /**********************************************************************
64  * c o p y f i r s t
65  *
66  * Do the appropriate kind a push operation to copy the first node from
67  * one list to another.
68  *
69  **********************************************************************/
70 
71 #define copy_first(l1,l2) \
72 (l2=push(l2, first_node(l1)))
73 
74 
75 
76 /*----------------------------------------------------------------------
77  F u n c t i o n s
78 ----------------------------------------------------------------------*/
79 
80 /**********************************************************************
81  * i s s a m e
82  *
83  * Compare the list node with the key value return true (non-zero)
84  * if they are equivalent strings. (Return false if not)
85  **********************************************************************/
86 static int is_same(void *item1, void *item2) {
87  return strcmp(static_cast<char *>(item1), static_cast<char *>(item2)) == 0;
88 }
89 
90 /**********************************************************************
91  * c o u n t
92  *
93  * Recursively count the elements in a list. Return the count.
94  **********************************************************************/
95 int count(LIST var_list) {
96  int temp = 0;
97 
98  iterate(var_list) temp += 1;
99  return (temp);
100 }
101 
102 /**********************************************************************
103  * d e l e t e d
104  *
105  * Delete all the elements out of the current list that match the key.
106  * This operation destroys the original list. The caller will supply a
107  * routine that will compare each node to the
108  * key, and return a non-zero value when they match.
109  **********************************************************************/
110 LIST delete_d(LIST list, void *key, int_compare is_equal) {
111  LIST result = NIL_LIST;
112  LIST last_one = NIL_LIST;
113 
114  if (is_equal == nullptr) is_equal = is_same;
115 
116  while (list != NIL_LIST) {
117  if (!(*is_equal)(first_node(list), key)) {
118  if (last_one == NIL_LIST) {
119  last_one = list;
120  list = list_rest(list);
121  result = last_one;
122  set_rest(last_one, NIL_LIST);
123  } else {
124  set_rest(last_one, list);
125  last_one = list;
126  list = list_rest(list);
127  set_rest(last_one, NIL_LIST);
128  }
129  } else {
130  list = pop(list);
131  }
132  }
133  return (result);
134 }
135 
136 /**********************************************************************
137  * d e s t r o y
138  *
139  * Return the space taken by a list to the heap.
140  **********************************************************************/
142  LIST next;
143 
144  while (list != NIL_LIST) {
145  next = list_rest(list);
146  delete list;
147  list = next;
148  }
149  return (NIL_LIST);
150 }
151 
152 /**********************************************************************
153  * d e s t r o y n o d e s
154  *
155  * Return the space taken by the LISTs of a list to the heap.
156  **********************************************************************/
157 void destroy_nodes(LIST list, void_dest destructor) {
158  ASSERT_HOST(destructor != nullptr);
159 
160  while (list != NIL_LIST) {
161  if (first_node(list) != nullptr) (*destructor)(first_node(list));
162  list = pop(list);
163  }
164 }
165 
166 /**********************************************************************
167  * i n s e r t
168  *
169  * Create a list element and rearrange the pointers so that the first
170  * element in the list is the second argument.
171  **********************************************************************/
172 void insert(LIST list, void *node) {
173  LIST element;
174 
175  if (list != NIL_LIST) {
176  element = push(NIL_LIST, node);
177  set_rest(element, list_rest(list));
178  set_rest(list, element);
179  node = first_node(list);
180  list->node = first_node(list_rest(list));
181  list->next->node = (LIST)node;
182  }
183 }
184 
185 /**********************************************************************
186  * l a s t
187  *
188  * Return the last list item (this is list type).
189  **********************************************************************/
190 LIST last(LIST var_list) {
191  while (list_rest(var_list) != NIL_LIST) var_list = list_rest(var_list);
192  return (var_list);
193 }
194 
195 /**********************************************************************
196  * p o p
197  *
198  * Return the list with the first element removed. Destroy the space
199  * that it occupied in the list.
200  **********************************************************************/
201 LIST pop(LIST list) {
202  LIST temp = list_rest(list);
203  delete list;
204  return (temp);
205 }
206 
207 /**********************************************************************
208  * p u s h
209  *
210  * Create a list element. Push the second parameter (the node) onto
211  * the first parameter (the list). Return the new list to the caller.
212  **********************************************************************/
213 LIST push(LIST list, void *element) {
214  LIST t;
215 
216  t = new list_rec;
217  t->node = static_cast<LIST>(element);
218  set_rest(t, list);
219  return (t);
220 }
221 
222 /**********************************************************************
223  * p u s h l a s t
224  *
225  * Create a list element. Add the element onto the end of the list.
226  **********************************************************************/
227 LIST push_last(LIST list, void *item) {
228  LIST t;
229 
230  if (list != NIL_LIST) {
231  t = last(list);
232  t->next = push(NIL_LIST, item);
233  return (list);
234  } else
235  return (push(NIL_LIST, item));
236 }
237 
238 /**********************************************************************
239  * r e v e r s e
240  *
241  * Create a new list with the elements reversed. The old list is not
242  * destroyed.
243  **********************************************************************/
245  LIST newlist = NIL_LIST;
246 
247  iterate(list) copy_first(list, newlist);
248  return (newlist);
249 }
250 
251 /**********************************************************************
252  * s e a r c h
253  *
254  * Search list, return NIL_LIST if not found. Return the list starting from
255  * the item if found. The compare routine "is_equal" is passed in as
256  * the third parameter to this routine.
257  **********************************************************************/
258 LIST search(LIST list, void *key, int_compare is_equal) {
259  if (is_equal == nullptr) is_equal = is_same;
260 
261  iterate(list) if ((*is_equal)(first_node(list), key)) return (list);
262  return (NIL_LIST);
263 }
pop
LIST pop(LIST list)
Definition: oldlist.cpp:201
list_rec::next
list_rec * next
Definition: oldlist.h:83
NIL_LIST
#define NIL_LIST
Definition: oldlist.h:76
iterate
#define iterate(l)
Definition: oldlist.h:101
set_rest
#define set_rest(l, cell)
Definition: oldlist.h:111
LIST
list_rec * LIST
Definition: oldlist.h:85
push
LIST push(LIST list, void *element)
Definition: oldlist.cpp:213
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:88
insert
void insert(LIST list, void *node)
Definition: oldlist.cpp:172
last
LIST last(LIST var_list)
Definition: oldlist.cpp:190
reverse
LIST reverse(LIST list)
Definition: oldlist.cpp:244
delete_d
LIST delete_d(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:110
void_dest
void(*)(void *) void_dest
Definition: oldlist.h:79
list_rec::node
list_rec * node
Definition: oldlist.h:82
push_last
LIST push_last(LIST list, void *item)
Definition: oldlist.cpp:227
count
int count(LIST var_list)
Definition: oldlist.cpp:95
search
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:258
copy_first
#define copy_first(l1, l2)
Definition: oldlist.cpp:71
first_node
#define first_node(l)
Definition: oldlist.h:92
int_compare
int(*)(void *, void *) int_compare
Definition: oldlist.h:78
destroy
LIST destroy(LIST list)
Definition: oldlist.cpp:141
is_equal
#define is_equal(p1, p2)
Definition: outlines.h:105
errcode.h
list_rec
Definition: oldlist.h:81
oldlist.h
destroy_nodes
void destroy_nodes(LIST list, void_dest destructor)
Definition: oldlist.cpp:157
list_rest
#define list_rest(l)
Definition: oldlist.h:91