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