base_lis.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,366 行 · 第 1/4 页

//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MJF 03/27/89 -- Initial design and implementation.
// Updated: MJF 04/15/89 -- Implemented Base list class.
// Updated: JCB 06/05/89 -- Fixed merge and sort.
// Updated: JCB 06/20/89 -- Implemented next_union, next_intersection,
//                          next_difference, next_xor.
// Updated: JCB 06/21/89 -- Modified next() and prev() to check for a current
//                          position not in THIS list, i.e. !traversal
// Updated: MJF 08/03/89 -- Improved operator== by checking for identical nodes
// Updated: MJF 08/10/89 -- Changed return values of operator+=, etc to List ref
// Updated: MJF 08/11/89 -- Changed methods which return new list references:
//                          tail, last, but_last, member, sublist and copy
// Updated: LGO 09/07/89 -- Made next, reference and dereference inline
// Updated: LGO 09/07/89 -- Moved the guts of find to the template classes.
// Updated: LGO 09/08/89 -- use do_find instead of compare_data in most places.
// Updated: LGO 09/08/89 -- Move push to the template classes.
// Updated: MBN 09/20/89 -- Added conditional exception handling
// Updated: LGO 10/05/89 -- Don't sort lists with less than 2 elements
// Updated: MBN 10/11/89 -- Change "current_position" to "curpos" and also
//                          "previous_position" to "prevpos"
// Updated: LGO 12/04/89 -- Make binary set operators not inline
// Updated: LGO 12/05/89 -- Make sort/merge predicate ANSI compatable
// Updated: MJF 03/12/90 -- Added group names to RAISE
// Updated: MJF 05/22/90 -- Fixed remove_duplicates
// Updated:  VDN 02/21/92 -- new lite version and fix memory leaks
// Updated: JAM 08/14/92 -- removed DOS specifics, stdized #includes
// Updated: JAM 08/14/92 -- modernized template syntax, remove macro hacks
//
// This  file contains member and friend  function implementation code for  the
// CoolList class defined in the  Base_List.h header  file.  Where appropriate  and
// possible, interfaces  to, and  us of,  existing system   functions has  been
// incorporated.  An overview of the structure of the CoolList class, along  with a
// synopsis of each member and friend function, can be found in the Base_List.h
// header file.

#ifndef BASE_LISTH                              // If CoolBase_List class not defined,
#include <cool/Base_List.h>                     // include header file
#endif

CoolBase_List NIL = CoolBase_List();                    // NIL -- Global NIL CoolBase_List

// CoolBase_List_Node() -- Constructor
// Input:         None
// Output:        None

CoolBase_List_Node::CoolBase_List_Node() {}             // Constructor


// ~CoolBase_List_Node -- Destructor (not inline because it's virtual)
//                   Virtual is needed to call ~CoolList_Node<Type>.
// Input:         None
// Output:        None

CoolBase_List_Node::~CoolBase_List_Node() {;}


// get_data()  -- Gets data of node. There is no data for CoolBase_List class.
// Input:         None.
// Output:        A void* pointer.

const void* CoolBase_List_Node::get_data() {
  cout << "\nWarning:  CoolBase_List_Node::get_data() has been called.\n";
  return NULL;
}


// set_data()  -- Sets data of node to specified value. There is not data
//                to set for CoolBase_List class.
// Input:         A void* pointer.
// Output:        None.

void CoolBase_List_Node::set_data(const void*) {
#if ERROR_CHECKING
  //RAISE (Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  printf ("CoolBase_List_Node::set_data(): Method called is redundant.\n");
#endif
}


// ~CoolBase_List -- Destructor (not inline because it's virtual)
// Input:         None
// Output:        None

CoolBase_List::~CoolBase_List () {;}

// Prev() -- decrement current position. If NULL, set it to last.
// Input:    None.
// Output:   TRUE or FALSE.

Boolean CoolBase_List::prev() {
  register CoolBase_List_Node* cp = this->curpos;
  CoolBase_List_Node* prev = this->prevpos;
  // if cp invalid (i.e. NULL) the following test will fail
  if (prev != NULL && prev->next == cp) {
    // already have the previous position
    cp = prev;
    this->prevpos = NULL; // this isn't needed, but why not...
  } else {
    // find previous node of current position
    // When cp is invalid, this finds the last node.
    register CoolBase_List_Node* np = this->node_ptr;
    prev = NULL;
    if (np != NULL) {
      while(np->next != cp)
        prev = np, np = np->next;
      cp = np;
      this->prevpos = prev;    
    }
  }
  // current position not found in CoolBase_List
  return (this->curpos = cp) != NULL;
}

// operator== -- Returns TRUE if similar data in THIS and the specified CoolBase_List.
//               Uses the static CoolBase_List comparer function on elements.
// Input:        A CoolBase_List reference.
// Output:       TRUE or FALSE.

Boolean CoolBase_List::operator==(const CoolBase_List& l) const {
  if (this == &l) return TRUE;  // same CoolBase_Lists
  CoolBase_List_Node *np, *np_l;
  for (np = this->node_ptr, np_l = l.node_ptr;
      np != NULL && np_l != NULL; 
      np = np->next, np_l = np_l->next) {
    if (np == np_l)
      return TRUE;   // same node pointers
    else if (!this->compare_data(np->get_data(), np_l->get_data()))
      return FALSE;
  }
  if (np == NULL && np_l == NULL) return TRUE;
  else return FALSE;
}


// tail() -- Sets CoolBase_List passed to the the nth tail of this CoolBase_List. With no 2nd
//           argument, tail() sets CoolBase_List passed to the 1st tail of this CoolBase_List.
// Input:    A CoolBase_List reference to store the nth tail elements of THIS and
//           the positive integer, n. (default 1)
// Output:   None.

void CoolBase_List::tail(CoolBase_List& l, int n) {
  this->dereference(l.node_ptr);
  int count = n;
  CoolBase_List_Node* np;
  for (np = this->node_ptr; np != NULL && count > 0; np = np->next, count--);
  // if n < length, return nth tail
  if (np != NULL && count == 0) {
    this->curpos = np;
    this->reference(np);
    l.node_ptr = np;
  }
  else l.node_ptr = NULL;
}


// last() -- Sets CoolBase_List passed to the n last elements of this CoolBase_List. With no
//           2nd argument, sets CoolBase_List passed to the last element of thie CoolBase_List.
// Input:    A CoolBase_List reference to store the n last elements of THIS and
//           the positive interger, n (default 1).
// Output:   None.

void CoolBase_List::last(CoolBase_List& l, int n) {
  // last n elements = (size-n)th tail
  int nth = this->length() - n;   
  if (nth >= 0)
    tail(l, nth);
  else {
    this->dereference(l.node_ptr);
    l.node_ptr = NULL;
  }
}


// but_last() -- Sets CoolBase_List passed to all but the last n elements of THIS List. 
//               With no 2nd argument, sets CoolBase_List passed to all but the last
//               element
// Input:        A positive integer (default 1).
// Output:       An altered THIS with all but the n last elements.

void CoolBase_List::but_last(CoolBase_List& l, int n) {
  this->reset();                                // Current position invalid
  CoolBase_List_Node* np = this->node_ptr;
  this->dereference(l.node_ptr);                // Delete nodes in l
  if (n == 0) {
    this->reference(np);                        
    l.node_ptr = np;                            // Points at all nodes of THIS
  }
  else {
    // get the number of nodes in this CoolBase_List and copy into CoolBase_List l
    int no_nodes = this->length() - n; 
    if (no_nodes > 0 && np != NULL)  {
      CoolBase_List_Node* first_np = this->insert_after_node(np->get_data(), NULL);
      CoolBase_List_Node* rest_np = first_np;   
      no_nodes--;
      for(np = np->next; 
          np != NULL && no_nodes > 0; 
          np = np->next, no_nodes--) {
        rest_np = this->insert_after_node(np->get_data(), rest_np);
      }
      l.node_ptr = first_np;                    // Create totally new nodes
    } else
      l.node_ptr = NULL;
  }
}


// clear() -- Removes all nodes of THIS CoolBase_List.
// Input:     None.
// Output:    None.

void CoolBase_List::clear() {
  this->reset();                                // make current position invalid   
  this->dereference(this->node_ptr);            // Delete nodes in this.
  this->node_ptr = NULL;
}


// length() -- Returns the number of elements in THIS CoolBase_List.
// Input:      None.
// Output:     An interger representing the number of elements in THIS.

int CoolBase_List::length() {
  int count = 0;
  for (CoolBase_List_Node* np = this->node_ptr; np != NULL; np = np->next, count++);
  return count;
}


// position -- Returns current position.
// Input:      THIS.
// Output:     An integer representing current position.

int CoolBase_List::position() {
  if (this->curpos == NULL) return -1;
  int index = 0;
  for (CoolBase_List_Node* np = this->node_ptr;  np != NULL; np = np->next, index++)
    if (np == this->curpos) return index;
  return -1;
}

// search() -- Returns TRUE if the specified CoolBase_List is a subset of this CoolBase_List
// Input:      A reference to subList to be searched.
// Output:     TRUE or FALSE.

Boolean CoolBase_List::search(const CoolBase_List& l) {
  CoolBase_List_Node* tnode = this->node_ptr;
  CoolBase_List_Node* lnode = l.node_ptr;
  if (tnode == lnode) {
    // this CoolBase_List and subList l have same head node pointers
    this->curpos = tnode;
    this->prevpos = NULL;
    return TRUE;  
  }
  if (lnode == NULL) return FALSE;      // subList l is nil
  while(tnode != NULL &&
        this->do_find(tnode, lnode->get_data(), this->curpos, this->prevpos)) {
    tnode = this->curpos;
    if (tnode == lnode) {
      // a node in this CoolBase_List and head node of CoolBase_List l are same
      return TRUE;
    }
    // data of node in this CoolBase_List is also in node of CoolBase_List l
    // continue searching rest of data
    CoolBase_List_Node *np2, *lnp;
    for (np2 = tnode->next, lnp = lnode->next; 
         np2 != NULL && lnp != NULL;
         np2 = np2->next, lnp = lnp->next) {
      if (np2 == lnp) {
        // node in this CoolBase_List and node in CoolBase_List l are same
        return TRUE;
      }
      if  (!this->compare_data(np2->get_data(), lnp->get_data()))
        break;
    }
    if (lnp == NULL) {
      // found data of CoolBase_List l in this CoolBase_List
      return TRUE;
    }
    tnode = tnode->next;
  } 
  return FALSE;
}


// sublist() -- Returns TRUE if THIS CoolBase_List contains second argument and sets
//              first argument to a sublist in THIS CoolBase_List starting at the 1st
//              occurence of second argument.
// Input:       A reference to the CoolBase_List which will be set to a sublist within
//              THIS CoolBase_List; and a reference to the CoolBase_List in search of.
// Output:      TRUE or FALSE.

Boolean CoolBase_List::sublist(CoolBase_List& l, const CoolBase_List& subl) {
  this->dereference(l.node_ptr);
  if (this->search(subl)) {
    this->reference(this->curpos);
    l.node_ptr = this->curpos;  
    return TRUE;
  } else {
    l.node_ptr = NULL;
    return FALSE;
  }
}


// copy() -- Mutates *this to store a copy of elements in specified List
// Input:    List containing elements to be copied from
// Output:   None.

void CoolBase_List::copy (const CoolBase_List& l) {
  cout << "****warning: copy from argument into *this****" << endl;
  this->reset();                                // make current position invalid
  this->dereference(this->node_ptr);            // free current nodes of *this
  CoolBase_List_Node* np = l.copy_nodes();              // make new list of nodes of l
  this->node_ptr = np;                          // all with ref_count = 1
}

// reverse() -- Reverses the order of the elements of THIS CoolBase_List.
// Input:       None.
// Output:      None.

void CoolBase_List::reverse() {
  this->reset();                                // Current position invalid
  CoolBase_List_Node *np, *np2, *rev_head;
  rev_head = NULL;
  for (np = this->node_ptr; np != NULL; np = np2) {
    np2 = np->next;
    np->next = rev_head;
    rev_head = np;
  }
  this->node_ptr = rev_head;
}