tesseract 4.1.1
Loading...
Searching...
No Matches
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 **********************************************************************/
86static 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 **********************************************************************/
95int 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 **********************************************************************/
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 **********************************************************************/
157void 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 **********************************************************************/
172void 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 **********************************************************************/
190LIST 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 **********************************************************************/
201LIST 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 **********************************************************************/
213LIST 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 **********************************************************************/
227LIST 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 **********************************************************************/
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}
#define ASSERT_HOST(x)
Definition: errcode.h:88
LIST push_last(LIST list, void *item)
Definition: oldlist.cpp:227
void destroy_nodes(LIST list, void_dest destructor)
Definition: oldlist.cpp:157
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:258
LIST delete_d(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:110
#define copy_first(l1, l2)
Definition: oldlist.cpp:71
void insert(LIST list, void *node)
Definition: oldlist.cpp:172
LIST destroy(LIST list)
Definition: oldlist.cpp:141
LIST pop(LIST list)
Definition: oldlist.cpp:201
LIST push(LIST list, void *element)
Definition: oldlist.cpp:213
int count(LIST var_list)
Definition: oldlist.cpp:95
LIST last(LIST var_list)
Definition: oldlist.cpp:190
LIST reverse(LIST list)
Definition: oldlist.cpp:244
void(*)(void *) void_dest
Definition: oldlist.h:79
#define iterate(l)
Definition: oldlist.h:101
#define set_rest(l, cell)
Definition: oldlist.h:111
list_rec * LIST
Definition: oldlist.h:85
#define first_node(l)
Definition: oldlist.h:92
int(*)(void *, void *) int_compare
Definition: oldlist.h:78
#define list_rest(l)
Definition: oldlist.h:91
#define NIL_LIST
Definition: oldlist.h:76
#define is_equal(p1, p2)
Definition: outlines.h:105
list_rec * node
Definition: oldlist.h:82
list_rec * next
Definition: oldlist.h:83