/src/tesseract/src/cutil/oldlist.cpp

Source
/******************************************************************************
#
# File:         oldlist.cpp
# Description:  List processing procedures.
# Author:       Mark Seaman, Software Productivity
#
# (c) Copyright 1987, Hewlett-Packard Company.
** Licensed under the Apache License, Version 2.0 (the "License");
** you may not use this file except in compliance with the License.
** You may obtain a copy of the License at
** http://www.apache.org/licenses/LICENSE-2.0
** Unless required by applicable law or agreed to in writing, software
** distributed under the License is distributed on an "AS IS" BASIS,
** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
** See the License for the specific language governing permissions and
** limitations under the License.
#
###############################################################################

  This file contains a set of general purpose list manipulation routines.
  These routines can be used in a wide variety of ways to provide several
  different popular data structures. A new list can be created by declaring
  a variable of type 'LIST', and can be initialized with the value 'NIL_LIST'.
  All of these routines check for the NIL_LIST condition before dereferencing
  pointers.  NOTE:  There is a users' manual available in printed form from
  Mark Seaman at (303) 350-4492 at Greeley Hard Copy.

  To implement a STACK use:

  push         to add to the Stack             l = push(l, (LIST)"jim");
  pop          to remove items from the Stack  l = pop(l);
  first_node   to access the head              name = (char *)first_node(l);

  To implement a QUEUE use:

  push_last    to add to the Queue              l = push_last(l, (LIST)"x");
  pop          remove items from the Queue      l = pop(l);
  first_node   to access the head               name = (char *)first_node (l);

  To implement LISP like functions use:

  first_node   CAR                              x = (int)first_node(l);
  rest         CDR                              l = list_rest (l);
  push         CONS                             l = push(l, (LIST)this);
  last         LAST                             x = last(l);
  concat       APPEND                           l = concat(r, s);
  count        LENGTH                           x = count(l);
  search       MEMBER                           if (search(l, x, nullptr))

  The following rules of closure exist for the functions provided.
  a = first_node (push (a, b))
  b = list_rest (push (a, b))
  a = push (pop (a), a))        For all a <> NIL_LIST
  a = reverse (reverse (a))

******************************************************************************/
#include "oldlist.h"

#include "errcode.h" // for ASSERT_HOST

#include <cstdio>
#include <cstring> // for strcmp

namespace tesseract {

/*----------------------------------------------------------------------
              F u n c t i o n s
----------------------------------------------------------------------*/

/**********************************************************************
 *  i s   s a m e
 *
 *  Compare the list node with the key value return true (non-zero)
 *  if they are equivalent strings.  (Return false if not)
 **********************************************************************/
static int is_same(void *item1, void *item2) {
  return strcmp(static_cast<char *>(item1), static_cast<char *>(item2)) == 0;
}

/**********************************************************************
 *  d e l e t e    d
 *
 *  Delete all the elements out of the current list that match the key.
 *  This operation destroys the original list.  The caller will supply a
 *  routine that will compare each node to the
 *  key, and return a non-zero value when they match.
 **********************************************************************/
LIST delete_d(LIST list, void *key, int_compare is_equal) {
  LIST result = NIL_LIST;
  LIST last_one = NIL_LIST;

  if (is_equal == nullptr) {
    is_equal = is_same;
  }

  while (list != NIL_LIST) {
    if (!(*is_equal)(list->first_node(), key)) {
      if (last_one == NIL_LIST) {
        last_one = list;
        list = list->list_rest();
        result = last_one;
        set_rest(last_one, NIL_LIST);
      } else {
        set_rest(last_one, list);
        last_one = list;
        list = list->list_rest();
        set_rest(last_one, NIL_LIST);
      }
    } else {
      list = pop(list);
    }
  }
  return (result);
}

/**********************************************************************
 *  d e s t r o y
 *
 *  Return the space taken by a list to the heap.
 **********************************************************************/
LIST destroy(LIST list) {
  LIST next;

  while (list != NIL_LIST) {
    next = list->list_rest();
    delete list;
    list = next;
  }
  return (NIL_LIST);
}

/**********************************************************************
 *  d e s t r o y   n o d e s
 *
 *  Return the space taken by the LISTs of a list to the heap.
 **********************************************************************/
void destroy_nodes(LIST list, void_dest destructor) {
  ASSERT_HOST(destructor != nullptr);

  while (list != NIL_LIST) {
    if (list->first_node() != nullptr) {
      (*destructor)(list->first_node());
    }
    list = pop(list);
  }
}

/**********************************************************************
 *  l a s t
 *
 *  Return the last list item (this is list type).
 **********************************************************************/
LIST last(LIST var_list) {
  while (var_list->list_rest() != NIL_LIST) {
    var_list = var_list->list_rest();
  }
  return var_list;
}

/**********************************************************************
 *  p o p
 *
 *  Return the list with the first element removed.  Destroy the space
 *  that it occupied in the list.
 **********************************************************************/
LIST pop(LIST list) {
  LIST temp = list->list_rest();
  delete list;
  return temp;
}

/**********************************************************************
 *  p u s h
 *
 *  Create a list element.  Push the second parameter (the node) onto
 *  the first parameter (the list). Return the new list to the caller.
 **********************************************************************/
LIST push(LIST list, void *element) {
  LIST t;

  t = new list_rec;
  t->node = static_cast<LIST>(element);
  set_rest(t, list);
  return (t);
}

/**********************************************************************
 *  p u s h   l a s t
 *
 *  Create a list element. Add the element onto the end of the list.
 **********************************************************************/
LIST push_last(LIST list, void *item) {
  LIST t;

  if (list != NIL_LIST) {
    t = last(list);
    t->next = push(NIL_LIST, item);
    return (list);
  } else {
    return (push(NIL_LIST, item));
  }
}

/**********************************************************************
 *   s e a r c h
 *
 *  Search list, return NIL_LIST if not found. Return the list starting from
 *  the item if found.  The compare routine "is_equal" is passed in as
 *  the third parameter to this routine.
 **********************************************************************/
LIST search(LIST list, void *key, int_compare is_equal) {
  if (is_equal == nullptr) {
    is_equal = is_same;
  }

  iterate(list) if ((*is_equal)(list->first_node(), key)) return list;
  return (NIL_LIST);
}

} // namespace tesseract

Coverage Report

Created: 2026-09-14 06:59

Line	Count	Source
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	0	static int is_same(void item1, void item2) {
77	0	return strcmp(static_cast<char >(item1), static_cast<char >(item2)) == 0;
78	0	}
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	107	LIST delete_d(LIST list, void *key, int_compare is_equal) {
89	107	LIST result = NIL_LIST;
90	107	LIST last_one = NIL_LIST;
91
92	107	if (is_equal == nullptr) {
93	0	is_equal = is_same;
94	0	}
95
96	4.26k	while (list != NIL_LIST) {
97	4.16k	if (!(*is_equal)(list->first_node(), key)) {
98	3.37k	if (last_one == NIL_LIST) {
99	45	last_one = list;
100	45	list = list->list_rest();
101	45	result = last_one;
102	45	set_rest(last_one, NIL_LIST);
103	3.32k	} else {
104	3.32k	set_rest(last_one, list);
105	3.32k	last_one = list;
106	3.32k	list = list->list_rest();
107	3.32k	set_rest(last_one, NIL_LIST);
108	3.32k	}
109	3.37k	} else {
110	790	list = pop(list);
111	790	}
112	4.16k	}
113	107	return (result);
114	107	}
115
116		/**********************************************************************
117		* d e s t r o y
118		*
119		* Return the space taken by a list to the heap.
120		**********************************************************************/
121	0	LIST destroy(LIST list) {
122	0	LIST next;
123
124	0	while (list != NIL_LIST) {
125	0	next = list->list_rest();
126	0	delete list;
127	0	list = next;
128	0	}
129	0	return (NIL_LIST);
130	0	}
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	2.77k	void destroy_nodes(LIST list, void_dest destructor) {
138	2.77k	ASSERT_HOST(destructor != nullptr);
139
140	7.97k	while (list != NIL_LIST) {
141	5.19k	if (list->first_node() != nullptr) {
142	5.19k	(*destructor)(list->first_node());
143	5.19k	}
144	5.19k	list = pop(list);
145	5.19k	}
146	2.77k	}
147
148		/**********************************************************************
149		* l a s t
150		*
151		* Return the last list item (this is list type).
152		**********************************************************************/
153	5.19k	LIST last(LIST var_list) {
154	27.8k	while (var_list->list_rest() != NIL_LIST) {
155	22.6k	var_list = var_list->list_rest();
156	22.6k	}
157	5.19k	return var_list;
158	5.19k	}
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	45.2k	LIST pop(LIST list) {
167	45.2k	LIST temp = list->list_rest();
168	45.2k	delete list;
169	45.2k	return temp;
170	45.2k	}
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	46.3k	LIST push(LIST list, void *element) {
179	46.3k	LIST t;
180
181	46.3k	t = new list_rec;
182	46.3k	t->node = static_cast<LIST>(element);
183	46.3k	set_rest(t, list);
184	46.3k	return (t);
185	46.3k	}
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	440	LIST push_last(LIST list, void *item) {
193	440	LIST t;
194
195	440	if (list != NIL_LIST) {
196	0	t = last(list);
197	0	t->next = push(NIL_LIST, item);
198	0	return (list);
199	440	} else {
200	440	return (push(NIL_LIST, item));
201	440	}
202	440	}
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	0	LIST search(LIST list, void *key, int_compare is_equal) {
212	0	if (is_equal == nullptr) {
213	0	is_equal = is_same;
214	0	}
215
216	0	iterate(list) if ((*is_equal)(list->first_node(), key)) return list;
217	0	return (NIL_LIST);
218	0	}
219
220		} // namespace tesseract