cutil/oldlist.cpp File Reference

#include "oldlist.h"
#include "structures.h"
#include <stdio.h>
#include "freelist.h"

Go to the source code of this file.

Defines

• #define add_on(l, x)   l = push (l,first (x))
• #define next_one(l)   l = rest (l)

Functions

• int count (LIST var_list)

  Recursively count the elements in a list.
  

• LIST delete_d (LIST list, void *key, int_compare is_equal)

  Delete all the elements out of the current list that match the key.
  

• LIST destroy (LIST list)

  Return the space taken by a list to the heap.
  

• void destroy_nodes (LIST list, void_dest destructor)

  Return the space taken by the LISTs of a list to the heap.
  

• void insert (LIST list, void *node)

  Create a list element and rearange the pointers so that the first element in the list is the second aurgment.
  

• int is_same (void *item1, void *item2)

  Compare the list node with the key value return TRUE (non-zero) if they are equivalent strings. (Return FALSE if not).
  

• int is_same_node (void *item1, void *item2)

  Compare the list node with the key value return TRUE (non-zero) if they are equivalent strings. (Return FALSE if not).
  

• LIST join (LIST list1, LIST list2)

  Join the two lists together.
  

• LIST last (LIST var_list)

  Return the last list item (this is list type).
  

• void * nth_cell (LIST var_list, int item_num)

  Return nth list cell in the list.
  

• LIST pop (LIST list)

  Return the list with the first element removed & destroys the space that it occupied in the list.
  

• LIST push (LIST list, void *element)

  Create a list element.
  

• LIST push_last (LIST list, void *item)

  Create a list element.
  

• LIST reverse (LIST list)

  Create a new list with the elements reversed.
  

• LIST reverse_d (LIST list)

  Create a new list with the elements reversed.
  

• LIST s_adjoin (LIST var_list, void *variable, int_compare compare)

  Adjoin an element to an assorted list.
  

• LIST search (LIST list, void *key, int_compare is_equal)

  Search list, return NIL if not found.
  

---

Define Documentation

#define add_on	(	l,
		x		)	l = push (l,first (x))

Note:

File: oldlist.cpp
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'. All of these routines check for the NIL condition before dereferencing pointers.

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     To access the head               name = (char *) first (l);

To implement a QUEUE use:

push_last To add to the Queue              l = push_last (l, (LIST) "jim");
pop       Remove items from the Queue      l = pop (l);
first     To access the head               name = (char *) first (l);

To implement LISP like functions use:

first     CAR                              x = (int) first (l);
rest      CDR                              l = 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, NULL))

To implement SETS use:

adjoin                                     l  = adjoin (l, x);
set_union                                  l = set_union (r, s);
intersection                               l = intersection (r, s);
set_difference                             l = set_difference (r, s);
delete                                     l = delete (s, x, NULL);
search                                     if (search (l, x, NULL))

To Implement Associated LISTS use:

lpush                                      l = lpush (l, p);
assoc                                      s = assoc (l, x);
adelete                                    l = adelete (l, x);

The following rules of closure exist for the functions provided.

a = first (push (a, b))
b = rest (push (a, b))
a = push (pop (a), a))        For all a <> NIL
a = reverse (reverse (a))

Author:

Mark Seaman, Software Productivity

Date:

Jul 23 13:24:09 1987 Dec 22 10:59:52 1988 (Mark Seaman) marks Feb 26 1990 Revision 1.12 marks (Mark Seaman); Added pop_off and join_on Mar 6 1990 Revision 1.13 marks (Mark Seaman); Look for correct file of <malloc.h> or <stdlib.h>

# (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.

Note:

File: oldlist.cpp

Definition at line 91 of file oldlist.cpp.

#define next_one

(

l

)

l = rest (l)

Definition at line 92 of file oldlist.cpp.

---

Function Documentation

int count

(

LIST

var_list

)

Recursively count the elements in a list.

Return the count.

Definition at line 102 of file oldlist.cpp.

References iterate.

Referenced by REJMAP::accept_count(), AdaptiveClassifier(), apply_box_testing(), apply_box_training(), STATS::cluster(), POLY_BLOCK::contains(), count_alphanums(), count_alphas(), edgesteps_to_edgepts(), ExtractMicros(), find_modal_font(), fix_rep_char(), font_recognition_pass(), ELIST2::internal_de_dump(), ELIST::internal_de_dump(), CLIST::internal_de_dump(), ELIST2::length(), ELIST::length(), CLIST::length(), LogNewWordChoice(), POLY_BLOCK::overlap(), ELIST2::prep_serialise(), ELIST::prep_serialise(), CLIST::prep_serialise(), PrintAdaptedTemplates(), read_next_box(), ELIST2::sort(), ELIST::sort(), CLIST::sort(), POLY_BLOCK::winding_number(), and WriteAdaptedClass().

                         {
  int temp = 0;

  iterate (var_list) temp += 1;
  return (temp);
}

LIST delete_d	(	LIST	list,
		void *	key,
		int_compare	is_equal
	)

Delete all the elements out of the current list that match the key.

Parameters:

	list	The list
	key	Key
	is_equal	Routine that will compare each node to the key

Returns:

last value deleted ??

This operation destroys the original list. is_equal compares each node to the key, and returns a non-zero value when they match. If the value NULL is supplied for is_equal, the is_key routine will be used.

Definition at line 123 of file oldlist.cpp.

References first, is_same(), NIL, NULL, pop(), rest, and set_rest.

Referenced by FilterWordChoices(), GetBuckets(), LogNewWordChoice(), and MakePermanent().

                                                          {
  LIST result = NIL;
  LIST last_one = NIL;

  if (is_equal == NULL)
    is_equal = is_same;

  while (list != NIL) {
    if (!(*is_equal) (first (list), key)) {
      if (last_one == NIL) {
        last_one = list;
        list = rest (list);
        result = last_one;
        set_rest(last_one, NIL);
      }
      else {
        set_rest(last_one, list);
        last_one = list;
        list = rest (list);
        set_rest(last_one, NIL);
      }
    }
    else {
      list = pop (list);
    }
  }
  return (result);
}

LIST destroy

(

LIST

list

)

Return the space taken by a list to the heap.

Definition at line 156 of file oldlist.cpp.

References free_cell(), NIL, and rest.

Referenced by draw_blob_edges(), FreeLabeledClassList(), FreeLabeledList(), FreeNormProtoList(), FreeTrainingSamples(), reverse_d(), and IMAGE::~IMAGE().

                        {
  LIST next;

  while (list != NIL) {
    next = rest (list);
    free_cell(list);
    list = next;
  }
  return (NIL);
}

void destroy_nodes	(	LIST	list,
		void_dest	destructor
	)

Return the space taken by the LISTs of a list to the heap.

Definition at line 171 of file oldlist.cpp.

References first, memfree(), NIL, NULL, and pop().

Referenced by convert_choice_list(), EndDangerousAmbigs(), free_adapted_class(), free_variables(), FreeMicroFeatures(), FreeOutlines(), FreeProtoList(), FreeTempConfig(), init_match_table(), InitChoiceAccum(), and LogNewWordChoice().

                                                    {
  if (destructor == NULL)
    destructor = memfree;

  while (list != NIL) {
    (*destructor) (first (list));
    list = pop (list);
  }
}

void insert	(	LIST	list,
		void *	node
	)

Create a list element and rearange the pointers so that the first element in the list is the second aurgment.

Definition at line 186 of file oldlist.cpp.

References first, NIL, push(), rest, and set_rest.

Referenced by s_adjoin().

                                   {
  LIST element;

  if (list != NIL) {
    element = push (NIL, node);
    set_rest (element, rest (list));
    set_rest(list, element);
    node = first (list);
    list->node = first (rest (list));
    list->next->node = (LIST) node;
  }
}

int is_same	(	void *	item1,
		void *	item2
	)

Compare the list node with the key value return TRUE (non-zero) if they are equivalent strings. (Return FALSE if not).

Definition at line 213 of file oldlist.cpp.

Referenced by delete_d(), and search().

                                      {
  return (!strcmp ((char *) item1, (char *) item2));
}

int is_same_node	(	void *	item1,
		void *	item2
	)

Compare the list node with the key value return TRUE (non-zero) if they are equivalent strings. (Return FALSE if not).

Definition at line 204 of file oldlist.cpp.

Referenced by LogNewWordChoice().

                                           {
  return (item1 == item2);
}

LIST join	(	LIST	list1,
		LIST	list2
	)

Join the two lists together.

This function is similar to concat except that concat creates a new list. This function returns the first list updated.

Definition at line 224 of file oldlist.cpp.

References last(), NIL, and set_rest.

Referenced by h_edge(), and v_edge().

                                  {
  if (list1 == NIL)
    return (list2);
  set_rest (last (list1), list2);
  return (list1);
}

LIST last

(

LIST

var_list

)

Return the last list item (this is list type).

Definition at line 235 of file oldlist.cpp.

References NIL, and rest.

Referenced by AddLargeSpeckleTo(), CLIST::CLIST(), cutline(), ELIST::ELIST(), ELIST2::ELIST2(), ELIST2::empty(), ELIST::empty(), CLIST::empty(), ELIST2::First(), ELIST::First(), CLIST::First(), join(), push_last(), ELIST2::shallow_copy(), ELIST::shallow_copy(), CLIST::shallow_copy(), ELIST2::singleton(), ELIST::singleton(), and CLIST::singleton().

                         {
  while (rest (var_list) != NIL)
    var_list = rest (var_list);
  return (var_list);
}

void* nth_cell	(	LIST	var_list,
		int	item_num
	)

Return nth list cell in the list.

Definition at line 245 of file oldlist.cpp.

References iterate.

Referenced by LogNewWordChoice().

                                            {
  int x = 0;
  iterate(var_list) {
    if (x++ == item_num)
      return (var_list);
  }
  return (var_list);
}

LIST pop

(

LIST

list

)

Return the list with the first element removed & destroys the space that it occupied in the list.

Definition at line 259 of file oldlist.cpp.

References free_cell(), NIL, and rest.

Referenced by ComputePrototypes(), delete_d(), destroy_nodes(), FreeMFOutline(), and NextSample().

                    {
  LIST temp;

  temp = rest (list);

  if (list != NIL) {
    free_cell(list);
  }
  return (temp);
}

LIST push	(	LIST	list,
		void *	element
	)

Create a list element.

Push the second parameter (the node) onto the first parameter (the list). Return the new list to the caller.

Definition at line 277 of file oldlist.cpp.

References new_cell(), list_rec::node, and set_rest.

Referenced by add_32bit_variable(), add_ptr_variable(), AddToNormProtosList(), ComputeChiSquared(), ComputePrototypes(), ConvertOutline(), ConvertOutlines(), ConvertToMicroFeatures(), copy_choices(), FreeBuckets(), insert(), MakeNewAdaptedClass(), MakeNewTempProtos(), NextSample(), push_last(), read_list(), and ReadTrainingSamples().

                                    {
  LIST t;

  t = new_cell ();
  t->node = (LIST) element;
  set_rest(t, list);
  return (t);
}

LIST push_last	(	LIST	list,
		void *	item
	)

Create a list element.

Add the element onto the end of the list.

Definition at line 292 of file oldlist.cpp.

References last(), list_rec::next, NIL, and push().

Referenced by append_choice(), FillAmbigTable(), ReadAdaptedClass(), ReadNormProtos(), and s_adjoin().

                                      {
  LIST t;

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

LIST reverse

(

LIST

list

)

Create a new list with the elements reversed.

The old list is not destroyed.

Definition at line 310 of file oldlist.cpp.

References copy_first, iterate, and NIL.

Referenced by ELISTIZE_S(), and reverse_d().

                        {
  LIST newlist = NIL;

  iterate (list) copy_first (list, newlist);
  return (newlist);
}

LIST reverse_d

(

LIST

list

)

Create a new list with the elements reversed.

The old list is destroyed.

Definition at line 323 of file oldlist.cpp.

References destroy(), and reverse().

Referenced by copy_choices(), and read_list().

                          {
  LIST result = reverse (list);
  destroy(list);
  return (result);
}

LIST s_adjoin	(	LIST	var_list,
		void *	variable,
		int_compare	compare
	)

Adjoin an element to an assorted list.

The original list is modified. Returns the modified list.

Definition at line 335 of file oldlist.cpp.

References first, insert(), iterate, NULL, and push_last().

Referenced by AddSignalMenuItem(), and LogNewWordChoice().

                                                                  {
  LIST l;
  int result;

  if (compare == NULL)
    compare = (int_compare) strcmp;

  l = var_list;
  iterate(l) {
    result = (*compare) (variable, first (l));
    if (result == 0)
      return (var_list);
    else if (result < 0) {
      insert(l, variable);
      return (var_list);
    }
  }
  return (push_last (var_list, variable));
}

LIST search	(	LIST	list,
		void *	key,
		int_compare	is_equal
	)

Search list, return NIL if not found.

Return the list starting from the item if found. The compare routine "is_equal" is passed in as the third paramter to this routine. If the value NULL is supplied for is_equal, the is_key routine will be used.

Definition at line 364 of file oldlist.cpp.

References first, is_same(), iterate, NIL, and NULL.

Referenced by ComputeChiSquared(), GetBuckets(), and read_variables().

                                                        {
  if (is_equal == NULL)
    is_equal = is_same;

  iterate (list) if ((*is_equal) (first (list), key))
  return (list);
  return (NIL);
}

---