oldlist.cpp

Go to the documentation of this file.

/* -*-C-*-
###############################################################################
#
# File:         oldlist.cpp
# Description:  List processing procedures.
# Author:       Mark Seaman, Software Productivity
# Created:      Thu Jul 23 13:24:09 1987
# Modified:     Thu Dec 22 10:59:52 1988 (Mark Seaman) marks@hpgrlt
# Language:     C
# Package:      N/A
# Status:       Reusable Software Component
#
# (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))

  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, nullptr);
  search                                        if (search(l, x, nullptr))

  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_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 <cstdio>
#include <cstring>      // for strcmp
#include "errcode.h"    // for ASSERT_HOST
#include "structures.h"

/*----------------------------------------------------------------------
              M a c r o s
----------------------------------------------------------------------*/
#define add_on(l, x) l = push(l, first_node(x))
#define next_one(l) l = list_rest(l)

/*----------------------------------------------------------------------
              F u n c t i o n s
----------------------------------------------------------------------*/
/**********************************************************************
 *  c o u n t
 *
 *  Recursively count the elements in  a list.  Return the count.
 **********************************************************************/
int count(LIST var_list) {
  int temp = 0;

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

/**********************************************************************
 *  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.  If the value
 *  nullptr is supplied for is_equal, the is_key routine will be used.
 **********************************************************************/
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)(first_node(list), key)) {
      if (last_one == NIL_LIST) {
        last_one = list;
        list = list_rest(list);
        result = last_one;
        set_rest(last_one, NIL_LIST);
      } else {
        set_rest(last_one, list);
        last_one = list;
        list = list_rest(list);
        set_rest(last_one, NIL_LIST);
      }
    } else {
      list = pop(list);
    }
  }
  return (result);
}

LIST delete_d(LIST list, void *key,
              TessResultCallback2<int, void *, void *> *is_equal) {
  LIST result = NIL_LIST;
  LIST last_one = NIL_LIST;

  while (list != NIL_LIST) {
    if (!(*is_equal).Run(first_node(list), key)) {
      if (last_one == NIL_LIST) {
        last_one = list;
        list = list_rest(list);
        result = last_one;
        set_rest(last_one, NIL_LIST);
      } else {
        set_rest(last_one, list);
        last_one = list;
        list = list_rest(list);
        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_rest(list);
    free_cell(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 (first_node(list) != nullptr) (*destructor)(first_node(list));
    list = pop(list);
  }
}

/**********************************************************************
 *  i n s e r t
 *
 *  Create a list element and rearange the pointers so that the first
 *  element in the list is the second aurgment.
 **********************************************************************/
void insert(LIST list, void *node) {
  LIST element;

  if (list != NIL_LIST) {
    element = push(NIL_LIST, node);
    set_rest(element, list_rest(list));
    set_rest(list, element);
    node = first_node(list);
    list->node = first_node(list_rest(list));
    list->next->node = (LIST)node;
  }
}

/**********************************************************************
 *  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)
 **********************************************************************/
int is_same(void *item1, void *item2) {
  return strcmp((char *)item1, (char *)item2) == 0 ? 1 : 0;
}

/**********************************************************************
 *  j o i n
 *
 *  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.
 **********************************************************************/
LIST join(LIST list1, LIST list2) {
  if (list1 == NIL_LIST) return (list2);
  set_rest(last(list1), list2);
  return (list1);
}

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

/**********************************************************************
 *  n t h   c e l l
 *
 *  Return nth list cell in the list.
 **********************************************************************/
void *nth_cell(LIST var_list, int item_num) {
  int x = 0;
  iterate(var_list) {
    if (x++ == item_num) return (var_list);
  }
  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;

  temp = list_rest(list);

  if (list != NIL_LIST) {
    free_cell(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_cell();
  t->node = (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));
}

/**********************************************************************
 *  r e v e r s e
 *
 *  Create a new list with the elements reversed. The old list is not
 *  destroyed.
 **********************************************************************/
LIST reverse(LIST list) {
  LIST newlist = NIL_LIST;

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

/**********************************************************************
 *  r e v e r s e   d
 *
 *  Create a new list with the elements reversed. The old list is
 *  destroyed.
 **********************************************************************/
LIST reverse_d(LIST list) {
  LIST result = reverse(list);
  destroy(list);
  return (result);
}

/**********************************************************************
 *  s   a d j o i n
 *
 *  Adjoin an element to an assorted list.  The original list is
 *  modified.  Returns the modified list.
 **********************************************************************/
LIST s_adjoin(LIST var_list, void *variable, int_compare compare) {
  LIST l;
  int result;

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

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

/**********************************************************************
 *   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.   If the value nullptr is supplied
 *  for is_equal, the is_key routine will be used.
 **********************************************************************/
LIST search(LIST list, void *key, int_compare is_equal) {
  if (is_equal == nullptr) is_equal = is_same;

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

LIST search(LIST list, void *key,
            TessResultCallback2<int, void *, void *> *is_equal) {
  iterate(list) if ((*is_equal).Run(first_node(list), key)) return (list);
  return (NIL_LIST);
}