base_lis.c

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

// prepend() -- Prepends the specified CoolBase_List to the front of this CoolBase_List and
//              returns TRUE if specified CoolBase_List is not NULL
// Input:       A reference to the CoolBase_List to be prepended.
// Output:      Always TRUE.

Boolean CoolBase_List::prepend(const CoolBase_List& l) {
  // first get copy of nodes in CoolBase_List l 
  CoolBase_List_Node* lnode = l.copy_nodes();
  if (lnode == NULL)
    return FALSE;
  // now prepend copy of l to front of THIS CoolBase_List.  
  this->curpos = lnode;
  this->prevpos = NULL;
  CoolBase_List_Node* last_np = this->curpos;
  if (last_np != NULL) {  
    // find last node of new copy of l
    while(last_np->next != NULL) last_np = last_np->next;
    // insert last node of CoolBase_List l in front of head node of this CoolBase_List
    // and set head node of this CoolBase_List to head node of CoolBase_List l
    last_np->next = this->node_ptr;
    this->node_ptr = this->curpos;
  }
  return TRUE;
}


// append() -- Appends the specified CoolBase_List to the end of this CoolBase_List and returns
//             TRUE if specified CoolBase_List is not NULL.
// Input:      A reference to the CoolBase_List to be appended.
// Output:     TRUE or FALSE.

Boolean CoolBase_List::append(const CoolBase_List& l) {
  CoolBase_List_Node* lnode = l.node_ptr;
  if (lnode == NULL)
    return FALSE;
  this->curpos = lnode;                         // curpos is head node of l
  CoolBase_List_Node* last_np = this->node_ptr;
  if (last_np == NULL) { 
    // there are no nodes in this;
    // just set head node of this CoolBase_List to head node of CoolBase_List l
    this->node_ptr = this->curpos;
    this->prevpos = NULL;
  }
  else {
    // find last node of this
    while(last_np->next != NULL) last_np = last_np->next;
    // add head node of CoolBase_List l after last node of this CoolBase_List
    last_np->next = this->curpos;
    this->prevpos = last_np;
  }
  this->reference(this->curpos);
  return TRUE;
}


// set_tail() -- Sets the nth tail of THIS CoolBase_List to the specified CoolBase_List
// Input:        A CoolBase_List reference, and a count (default 1).
// Output:       TRUE if nth tail exists, FALSE otherwise.

Boolean CoolBase_List::set_tail(const CoolBase_List& l, int n) {
  // find node at start of nth tail
  int count = n;
  CoolBase_List_Node *np, *prev_np;
  for (np = this->node_ptr, prev_np = NULL; 
      np != NULL && count > 0;
      prev_np = np, np = np->next, count--);
  if (np != NULL && count == 0) {
     this->curpos = l.node_ptr; // Current position=head node
     this->prevpos = prev_np;           // Previous position is nth-1
     // replace nth node with head node of CoolBase_List l
     if (prev_np == NULL) this->node_ptr = this->curpos; // when n=0
     else prev_np->next = this->curpos;        // when n>0
     this->reference(this->curpos);
     // removing nth tail
     this->dereference(np);
     return TRUE;
   }
  return FALSE;
}


// remove_duplicates() -- Removes all duplicate elements in THIS CoolBase_List.
// Input:                 None.
// Output:                TRUE if at least one item is removed, FALSE otherwise.

Boolean CoolBase_List::remove_duplicates() {
  Boolean success = FALSE;                      // success flag
  CoolBase_List_Node* np = this->node_ptr;
  CoolBase_List_Node* np_next;
  while ((np != NULL) && ((np_next = np->next) != NULL)) {
    while (this->do_find (np_next, np->get_data(), this->curpos, this->prevpos))
      {
        this->dereference(this->remove());      // duplicate nodes go to trash
        success = TRUE;
        if ((np_next = this->curpos) == NULL) break;
      }
    np = np->next;
  }
  return success;
}


// set_intersection() -- Changes THIS list to contain everything that is an element
//                   of both this and the specified CoolBase_List.
// Input:            A reference to CoolBase_List.
// Output:           None.

void CoolBase_List::set_intersection(const CoolBase_List& l) {
  this->reset();                                // make current position invalid
  if (l.node_ptr == NULL)
    this->clear();
  else {
    CoolBase_List_Node* np = this->node_ptr;
    CoolBase_List_Node* prev_np = NULL;
    CoolBase_List_Node* next_np;
    while(np != NULL) {
      CoolBase_List_Node* cp;
      CoolBase_List_Node* pp;
      if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
        next_np = np->next;
        if (prev_np == NULL) 
          this->node_ptr = np->next;            // next node is at head
        else 
          prev_np->next = np->next;             // next node is in middle
        this->reference(np->next);
        this->dereference(np);                  // delete np from this CoolBase_List.
        np = next_np;                           // set to next node to look at
      }
      else {
        prev_np = np; 
        np = np->next;
      }
    }
  }
}


// set_union() -- Changes THIS list to contain everything that is an element of
//             either THIS or the specified CoolBase_List
// Input:      A reference to CoolBase_List.
// Output:     None.

void CoolBase_List::set_union(const CoolBase_List& l) {
  this->reset();                                // make current position invalid
  CoolBase_List_Node* tnode = this->node_ptr;
  CoolBase_List_Node* lnode = l.node_ptr;
  if (tnode ==  NULL && lnode != NULL) { 
    this->node_ptr = lnode;                     // this is empty, so set head node 
    this->reference(lnode);                     // of this to head node of l
  }
  else
    for (; lnode !=NULL; lnode = lnode->next) {
      CoolBase_List_Node* cp;
      CoolBase_List_Node* pp;
      if (!do_find(this->node_ptr, lnode->get_data(), cp, pp))
        this->push(lnode->get_data());          // push new data of l into this.
    }
}


// set_difference() -- Removes from THIS CoolBase_List the elements which also appears in
//                 the specified CoolBase_List.
// Input:          A reference to CoolBase_List.
// Output:         None.

void CoolBase_List::set_difference(const CoolBase_List& l) {
  this->reset();                                // make current position invalid
  if (l.node_ptr != NULL) {
    CoolBase_List_Node* np = this->node_ptr;
    CoolBase_List_Node* prev_np = NULL;
    CoolBase_List_Node* next_np;
    // if node in this CoolBase_List is found in CoolBase_List l, remove it from this CoolBase_List
    while (np != NULL) {
      CoolBase_List_Node* cp;
      CoolBase_List_Node* pp;
      if (l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
        next_np = np->next;
        if (prev_np == NULL) 
          this->node_ptr = np->next;            // Next node is at head
        else 
          prev_np->next = np->next;             // next node is in middle
        this->reference(np->next);
        this->dereference(np);                  // delete np from this CoolBase_List.
        np = next_np;                           // set to next node to look at
      }
      else {
        prev_np = np; 
        np = np->next;
      }
    }
  }
}


// set_xor() -- Changes CoolBase_List to contain those elements which appear in
//                   exactly one of THIS CoolBase_List and the specified CoolBase_List.
// Input:            A reference to CoolBase_List.
// Output:           None.

void CoolBase_List::set_xor(const CoolBase_List& l) {
  this->reset();        // make current position invalid
  // first get copy of nodes in CoolBase_List l
  CoolBase_List* lcopy = this->new_list((CoolBase_List_Node*)NULL);
  lcopy->copy(l);
  // remove elements in this CoolBase_List from copy of CoolBase_List l
  lcopy->set_difference(*this);
  // remove elements in CoolBase_List l from this CoolBase_List  
  this->set_difference(l);
  // append elements left in lcopy to end of this CoolBase_List
  this->append(*lcopy);
  delete lcopy;                                 // destructor is virtual
}

// next_intersection() -- Sets current position to next item in the
//                        intersection of this CoolBase_List and the specified CoolBase_List.
// Input:                 None.
// Output:                TRUE if the next item exists,  FALSE otherwise.

Boolean CoolBase_List::next_intersection(const CoolBase_List& l) {
  CoolBase_List_Node* np = this->curpos;
  if (!this->traversal) {                       // end of intersection
    this->curpos = NULL;
    return FALSE;
  }
  if (np == NULL)                               // starting fresh
    np = this->node_ptr;
  else
    np = np->next;                              // increment position
  for (; np != NULL; np = np->next) {
    CoolBase_List_Node* cp;
    CoolBase_List_Node* pp;
    if (l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }
  }
  this->traversal = FALSE;                      // now traversing second CoolBase_List
  return FALSE;
}


// next_union() -- Sets current position to next item in the union of this
//                  CoolBase_List and the specified CoolBase_List.
// Input:           None.
// Output:          TRUE if the next item exists,  FALSE otherwise.

Boolean CoolBase_List::next_union(const CoolBase_List& l) {
  CoolBase_List_Node* np = this->curpos;
  if (np == NULL && !this->traversal)           // end of both CoolBase_Lists
    return FALSE;
  if (np == NULL && this->traversal)            // starting fresh
    np = this->node_ptr;
  else  
    if (np->next == NULL && this->traversal) {  // end of first CoolBase_List
      this->traversal = FALSE;                  // now traversing second CoolBase_List
      np = l.node_ptr;
    }
  else
    if (!this->traversal)  np = np->next;       // increment position

  if (this->traversal) {                        // still in this CoolBase_List
    if (this->curpos != NULL) 
      this->curpos = np->next;  // increment current position
    else this->curpos = np;
    return TRUE;                        
  }

  for (; np != NULL; np = np->next) {
    CoolBase_List_Node* cp;
    CoolBase_List_Node* pp;
    if (!do_find(this->node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }
  }
  return FALSE;
}


// next_difference() -- Sets current position to next item in the difference
//                      of this CoolBase_List and the specified CoolBase_List
// Input:               None.
// Output:              TRUE if the next item exists,  FALSE otherwise.

Boolean CoolBase_List::next_difference(const CoolBase_List& l) {
  CoolBase_List_Node* np = this->curpos;
  if (np == NULL && !this->traversal) {         // end of this CoolBase_List
    return FALSE;
  }
  if (np == NULL)                               // starting fresh
    np = this->node_ptr;
  else {
    this->traversal = FALSE;                    // now traversing second CoolBase_List
    np = np->next;                              // incrementing position
  }
  for (; np != NULL; np = np->next) {
    CoolBase_List_Node* cp;
    CoolBase_List_Node* pp;
    if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }
  }
  return FALSE;
}


// next_xor() -- Sets current position to next item in exclusive_or
//                        of this CoolBase_List and the specified CoolBase_List.
// Input:                 None.
// Output:                TRUE if the next item exists,  FALSE otherwise.

Boolean CoolBase_List::next_xor(const CoolBase_List& l) {
  CoolBase_List_Node* cp;
  CoolBase_List_Node* pp;
  CoolBase_List_Node* np = this->curpos;
  if (!this->traversal && np == NULL)           // end of both CoolBase_Lists
    return FALSE;
  if (np == NULL && this->traversal)            // starting fresh
    np = this->node_ptr;
  else 
    if (np->next == NULL && this->traversal) {  // end of first CoolBase_List
      this->traversal = FALSE;                  // now traversing second CoolBase_List
      np = l.node_ptr;
    }
  else
    np = np->next;                              // increment position
  if (this->traversal) {                        // still in this CoolBase_List
    for (; np != NULL; np = np->next) 
      if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
        this->curpos = np;
        return TRUE;                    
      } 
    this->traversal = FALSE;                    // now traversing second CoolBase_List
    np = l.node_ptr; 
  }
  for (; np != NULL; np = np->next)
    if (!do_find(this->node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }