tesseract  5.0.0
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 
59 #include "errcode.h" // for ASSERT_HOST
60 
61 #include <cstdio>
62 #include <cstring> // for strcmp
63 
64 namespace tesseract {
65 
66 /*----------------------------------------------------------------------
67  F u n c t i o n s
68 ----------------------------------------------------------------------*/
69 
70 /**********************************************************************
71  * i s s a m e
72  *
73  * Compare the list node with the key value return true (non-zero)
74  * if they are equivalent strings. (Return false if not)
75  **********************************************************************/
76 static int is_same(void *item1, void *item2) {
77  return strcmp(static_cast<char *>(item1), static_cast<char *>(item2)) == 0;
78 }
79 
80 /**********************************************************************
81  * d e l e t e d
82  *
83  * Delete all the elements out of the current list that match the key.
84  * This operation destroys the original list. The caller will supply a
85  * routine that will compare each node to the
86  * key, and return a non-zero value when they match.
87  **********************************************************************/
88 LIST delete_d(LIST list, void *key, int_compare is_equal) {
89  LIST result = NIL_LIST;
90  LIST last_one = NIL_LIST;
91 
92  if (is_equal == nullptr) {
93  is_equal = is_same;
94  }
95 
96  while (list != NIL_LIST) {
97  if (!(*is_equal)(list->first_node(), key)) {
98  if (last_one == NIL_LIST) {
99  last_one = list;
100  list = list->list_rest();
101  result = last_one;
102  set_rest(last_one, NIL_LIST);
103  } else {
104  set_rest(last_one, list);
105  last_one = list;
106  list = list->list_rest();
107  set_rest(last_one, NIL_LIST);
108  }
109  } else {
110  list = pop(list);
111  }
112  }
113  return (result);
114 }
115 
116 /**********************************************************************
117  * d e s t r o y
118  *
119  * Return the space taken by a list to the heap.
120  **********************************************************************/
122  LIST next;
123 
124  while (list != NIL_LIST) {
125  next = list->list_rest();
126  delete list;
127  list = next;
128  }
129  return (NIL_LIST);
130 }
131 
132 /**********************************************************************
133  * d e s t r o y n o d e s
134  *
135  * Return the space taken by the LISTs of a list to the heap.
136  **********************************************************************/
137 void destroy_nodes(LIST list, void_dest destructor) {
138  ASSERT_HOST(destructor != nullptr);
139 
140  while (list != NIL_LIST) {
141  if (list->first_node() != nullptr) {
142  (*destructor)(list->first_node());
143  }
144  list = pop(list);
145  }
146 }
147 
148 /**********************************************************************
149  * l a s t
150  *
151  * Return the last list item (this is list type).
152  **********************************************************************/
153 LIST last(LIST var_list) {
154  while (var_list->list_rest() != NIL_LIST) {
155  var_list = var_list->list_rest();
156  }
157  return var_list;
158 }
159 
160 /**********************************************************************
161  * p o p
162  *
163  * Return the list with the first element removed. Destroy the space
164  * that it occupied in the list.
165  **********************************************************************/
166 LIST pop(LIST list) {
167  LIST temp = list->list_rest();
168  delete list;
169  return temp;
170 }
171 
172 /**********************************************************************
173  * p u s h
174  *
175  * Create a list element. Push the second parameter (the node) onto
176  * the first parameter (the list). Return the new list to the caller.
177  **********************************************************************/
178 LIST push(LIST list, void *element) {
179  LIST t;
180 
181  t = new list_rec;
182  t->node = static_cast<LIST>(element);
183  set_rest(t, list);
184  return (t);
185 }
186 
187 /**********************************************************************
188  * p u s h l a s t
189  *
190  * Create a list element. Add the element onto the end of the list.
191  **********************************************************************/
192 LIST push_last(LIST list, void *item) {
193  LIST t;
194 
195  if (list != NIL_LIST) {
196  t = last(list);
197  t->next = push(NIL_LIST, item);
198  return (list);
199  } else {
200  return (push(NIL_LIST, item));
201  }
202 }
203 
204 /**********************************************************************
205  * s e a r c h
206  *
207  * Search list, return NIL_LIST if not found. Return the list starting from
208  * the item if found. The compare routine "is_equal" is passed in as
209  * the third parameter to this routine.
210  **********************************************************************/
211 LIST search(LIST list, void *key, int_compare is_equal) {
212  if (is_equal == nullptr) {
213  is_equal = is_same;
214  }
215 
216  iterate(list) if ((*is_equal)(list->first_node(), key)) return list;
217  return (NIL_LIST);
218 }
219 
220 } // namespace tesseract
#define ASSERT_HOST(x)
Definition: errcode.h:59
#define iterate(l)
Definition: oldlist.h:91
#define set_rest(l, cell)
Definition: oldlist.h:101
#define NIL_LIST
Definition: oldlist.h:75
#define is_equal(p1, p2)
Definition: outlines.h:93
LIST last(LIST var_list)
Definition: oldlist.cpp:153
LIST destroy(LIST list)
Definition: oldlist.cpp:121
LIST delete_d(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:88
LIST push_last(LIST list, void *item)
Definition: oldlist.cpp:192
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:211
LIST pop(LIST list)
Definition: oldlist.cpp:166
LIST push(LIST list, void *element)
Definition: oldlist.cpp:178
void destroy_nodes(LIST list, void_dest destructor)
Definition: oldlist.cpp:137
void(*)(void *) void_dest
Definition: oldlist.h:78
int(*)(void *, void *) int_compare
Definition: oldlist.h:77
list_rec * next
Definition: oldlist.h:105
list_rec * first_node()
Definition: oldlist.h:107
list_rec * list_rest()
Definition: oldlist.h:111
list_rec * node
Definition: oldlist.h:104