base_lis.c

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

}


// remove() -- Removes the first occurence of the specified item in this CoolBase_List
// Input:      A refernce to data item to be removed.
// Output:     TRUE if item found and removed, FALSE otherwise.

Boolean CoolBase_List::remove(const void* x) {
  // find node for x
  if (this->do_find(this->node_ptr, x, this->curpos, this->prevpos)) {
    this->dereference(this->remove());          // throw node to trash, since 
    return TRUE;                                // it is not returned
  }
  return FALSE;
}


// replace() -- Replaces the first occurence of specified data item in THIS
//              CoolBase_List with a new value
// Input:       Two void* pointers.
// Output:      TRUE if item found and replaced, FALSE otherwise.

Boolean CoolBase_List::replace(const void* old_data, const void* new_data) {
  // find node of old_data in this CoolBase_List
  if(this->do_find(this->node_ptr, old_data, this->curpos, this->prevpos)) {
    // replace old_data in node with new_data
    this->curpos->set_data(new_data);
    return TRUE;
  }
  return FALSE;
}


// replace_all() -- Replaces all occurences of the specified data item in THIS
//                  CoolBase_List with a new value.
// Input:           Two void* pointers.
// Output:          TRUE if at least one item found and replaced, else FALSE

Boolean CoolBase_List::replace_all(const void* old_data, const void* new_data) {
  this->reset();        // make current position invalid
  Boolean success = FALSE; // return value
  CoolBase_List_Node* pp;
  CoolBase_List_Node* np = this->node_ptr;
  while (np != NULL && this->do_find(np, old_data, np, pp)) {
    np->set_data(new_data);
    success = TRUE;
    np = np->next;
  }
  return success;
}


// sort() -- Sorts the elements of THIS using the specified predicate function.
//           The predicate function returns TRUE if and only if the first
//           element preceeds the second. The sort routine uses the Sort
//           algorithm as given in "Numerical Recipes in C" p247.
// Input:    A predicate function pointer.
// Output:   None.

void CoolBase_List::sort(Predicate f) {
  this->reset();        // make current position invalid
  CoolBase_List_Node* np;
  int l, j, ir, i;
  int n = this->length();
  if (n < 2) return;    // No sense sorting if less than two elements
  CoolBase_List_Node** node_array = new CoolBase_List_Node*[n+1];
  // put the nodes of THIS into an array which will be used by the
  // heap sort algorithm
  for (np = this->node_ptr, i = 1; np != NULL; np = np->next, i++)
     node_array[i] = np;
  // the heap sort algorithm
  CoolBase_List_Node* temp;
  l = (n >> 1) + 1;
  ir = n;
  while (TRUE) {
    if (l > 1)
      temp = node_array[--l];
    else {
      temp = node_array[ir];
      node_array[ir] = node_array[1];
      if (--ir == 1) {
        node_array[1] = temp;
        break;
      }
    }
    i = l;
    j = i << 1;
    while (j <= ir) {
      if (j < ir && (*f) ((node_array[j])->get_data(),
                          (node_array[j+1])->get_data()) < 0)
        ++j;
      if ((*f) (temp->get_data(), (node_array[j])->get_data()) < 0) {
        node_array[i] = node_array[j];
        j += (i = j);
      }
      else
        j = ir + 1;
    }
    node_array[i] = temp;
  }

  // put the sorted nodes of the array back into THIS
  this->node_ptr = node_array[1];
  for (i = 1; i < n; i++) {
     (node_array[i])->next = node_array[i+1];
   }
  (node_array[n])->next = NULL;

  delete [] node_array;
}


// merge() -- Merges the elements of THIS CoolBase_List with the elements of the
//            specified CoolBase_List sorted with the specified predicate function.
//            If THIS is sorted already, then the result of the merge will be
//            sorted. Otherwise there are no guarantees for the sortedness of
//            the result.
// Input:     A reference to a CoolBase_List to be merged and a predicate function 
//            pointer.
// Output:    None.

void CoolBase_List::merge(const CoolBase_List& l, Predicate f) {
  this->reset();        // make current position invalid
  CoolBase_List_Node* tnode = this->node_ptr;
  if (tnode == NULL)
    // if this CoolBase_List is NULL, just assign this CoolBase_List to CoolBase_List l
    this->operator=(l);
  else {
    // begin merging CoolBase_List l into this CoolBase_List
    CoolBase_List_Node *lnode;

    // first merge nodes of CoolBase_List l in front of first node of this CoolBase_List
    // until a node in this CoolBase_List is less than a node in CoolBase_List l
    for (lnode = l.node_ptr;
         lnode != NULL &&
         (*f) (tnode->get_data(), lnode->get_data()) >= 0;
         lnode = lnode->next) {
      tnode = this->insert_before_node(lnode->get_data(), tnode);
      this->node_ptr = tnode;
    }
      
    // merge rest of nodes in CoolBase_List l into this CoolBase_List
    CoolBase_List_Node* tnode_prev = tnode;
    tnode = tnode->next;
    while (lnode != NULL) {
      if (tnode == NULL) {
        // if the end of THIS is reached, 
        // add the CoolBase_List l nodes to the end of this CoolBase_List
        for (; lnode !=NULL; lnode = lnode->next)
          tnode_prev = this->insert_after_node(lnode->get_data(), tnode_prev);
      }
      else if ((*f)(tnode->get_data(), lnode->get_data()) < 0) {
        // if node in this CoolBase_List is less than node in CoolBase_List l
        // just go to next node in this CoolBase_List
        tnode_prev = tnode;
        tnode = tnode->next;      
      } else {
        // if node in CoolBase_List l is less than node in this CoolBase_List
        // insert the CoolBase_List l node into THIS
        // and goto next node in CoolBase_List l
        tnode_prev->next = this->insert_before_node(lnode->get_data(), tnode);
        tnode_prev = tnode_prev->next;
        lnode = lnode->next;
      }
    }
  }
}


// insert_before() -- Inserts the specified item before the current position
// Input:             A void* pointer.
// Output:            TRUE if current position is valid, FALSE otherwise.

Boolean CoolBase_List::insert_before(const void* new_item) {
  CoolBase_List_Node* cp = this->curpos;
  CoolBase_List_Node *np = this->prevpos;
  if (cp == NULL)
    return FALSE;
  if (np == NULL || np->next != cp) {
    np = this->node_ptr;
    // current position is head node    
    if (np == cp)
      return this->push(new_item);
    // find previous node of current position in CoolBase_List
    while (np != NULL && np->next != cp) np = np->next;
    if (np == NULL)
      return FALSE;  // couldn't find current position
    else
      this->prevpos = np;
  }
  // insert new_item before current position and
  // set current position to this new node
  this->curpos = this->insert_before_node(new_item, cp);
  np->next = this->curpos;
  return TRUE;
}


// insert_after() -- Inserts the specified item after the current position
// Input:            A void* pointer.
// Output:           TRUE if current position is valid, FALSE otherwise.

Boolean CoolBase_List::insert_after(const void* new_item) {
  if (this->curpos == NULL)
    return FALSE;
  this->prevpos = this->curpos;
  this->curpos = this->insert_after_node(new_item,
                                                   this->curpos);
  return TRUE;
}


// insert_before() -- Inserts the specified new item before the specified
//                    target item in this CoolBase_List
// Input:             Two data void* pointers.
// Output:            TRUE if target item found, FALSE otherwise.

Boolean CoolBase_List::insert_before(const void* new_item, const void* target_item) {
  // find node with target item
  if (this->do_find(this->node_ptr, target_item, this->curpos, this->prevpos)){
    CoolBase_List_Node *np = this->curpos;
    CoolBase_List_Node *prev_np = this->prevpos;
    // insert new item before target item
    this->curpos = this->insert_before_node(new_item, np);
    if (prev_np == NULL)
      this->node_ptr = this->curpos;     // new item is the head node
    else
      prev_np->next = this->curpos; // new item is a  middle node
    return TRUE;
  }
  return FALSE;
}


// insert_after() -- Inserts the specified new item after the specified target
//                   item in this CoolBase_List
// Input:            Two data void* pointers.
// Output:           TRUE if target item found, FALSE otherwise.

Boolean CoolBase_List::insert_after(const void* new_item, const void* target_item) {
  // find node with target item
  CoolBase_List_Node *np;
  if (this->do_find(this->node_ptr, target_item, np, this->prevpos)) {
    this->curpos = this->insert_after_node(new_item, np);
    this->prevpos = np;
    return TRUE;
  }       
  return FALSE;
}


// value_error -- Raise exception for CoolBase_List::value() method
// Input:         Type string
// Output:        None

void CoolBase_List::value_error (const char* Type) {
  //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  printf ("CoolList<%s>::value(): Invalid current position.\n", Type);
  abort ();
}


// get_error -- Raise exception for CoolBase_List::get() method
// Input:       Type string
// Output:      None

void CoolBase_List::get_error (const char* Type, int n) {
  //RAISE Error, SYM(CoolBase_List), SYM(Negative_Index),
  printf ("CoolList<%s>::get(): Negative index %d.\n", Type, n);
  abort ();
}


// before_error -- Raise exception for CoolBase_List::insert_before() method
// Input:          Type string
// Output:         None

void CoolBase_List::before_error (const char* Type) {
  //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  printf ("CoolList<%s>::insert_before(): Invalid current position.\n", Type);
  abort ();
}


// after_error -- Raise exception for CoolBase_List::insert_after() method
// Input:         Type string
// Output:        None

void CoolBase_List::after_error (const char* Type) {
  //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  printf ("CoolList<%s>::insert_after(): Invalid current position.\n", Type);
  abort ();
}


// bracket_error -- Raise exception for CoolBase_List::operator[]() method
// Input:           Type string
// Output:          None

void CoolBase_List::bracket_error (const char* Type, int n) {
  //RAISE Error, SYM(CoolBase_List), SYM(Negative_Index),
  printf ("CoolList<%s>::operator[](): Negative index %d.\n", Type, n);
  abort ();
}


// pop_error -- Raise exception for CoolBase_List::pop() method
// Input:       Type string
// Output:      None

void CoolBase_List::pop_error (const char* Type) {
  //RAISE Error, SYM(CoolBase_List), SYM(No_Elements),
  printf ("CoolList<%s>::pop(): No elements in CoolBase_List.\n", Type);
  abort ();
}


// remove_error -- Raise exception for CoolBase_List::remove() method
// Input:          Type string
// Output:         None

void CoolBase_List::remove_error (const char* Type) {
  //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  printf ("CoolList<%s>::remove(): Invalid current position.\n", Type);
  abort ();
}

// va_arg_error -- Raise exception for using class objects, or chars in (...)
// Input:          Type string
// Output:         None

void CoolBase_List::va_arg_error (const char* Type, int n) {
  //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Va_Arg),
  printf ("CoolList<%s>::CoolList<%s>(): Invalid type in ... or wrong alignment with %d bytes.\n",
          Type, Type, n);
  abort ();
}