doublelinkedlist.h

这是一个从音频信号里提取特征参量的程序

  // for system mode delete the item memory
  //
  else {
    item_a->assign(*(tmp_node->getItem()));
    delete tmp_node->getItem();
  }

  // cleanup the node
  //
  delete tmp_node;
  length_d -= 1;

  // exit gracefully
  //
  return true;
}

// method: removeLast
//
// arguments: none
//  
// return: a boolean value indicating status
//
// this method removes the last node. it is used only if the memory is
// SYSTEM-allocated. it cleans up all the memories in the last node. 
//
template<class TObject>
boolean DoubleLinkedList<TObject>::removeLast() {
  
  // make sure the last node is valid
  //
  if (last_d == (NODE*)NULL) {
    
    // return an error
    //
    return false;
  }

  // keep the position of the last node
  //
  NODE* tmp_node = last_d;
  
  // unlink the last node and set the new last node
  //  if the first node is not equal to the last node then there must be
  //  nodes in between. otherwise, the new list will be empty
  //
  if (last_d != first_d) {
    
    last_d->getPrev()->setNext((NODE*)NULL);
    last_d = last_d->getPrev();
  }
  else {
    first_d = (NODE*)NULL;
    last_d = (NODE*)NULL;
    curr_d = (NODE*)NULL;
  }
  
  // if the current node just got deleted then set the new current to be
  // the new last node
  //
  if (curr_d == tmp_node) {
    curr_d = last_d;
  }

  // if the marked node just got deleted then set it to NULL
  //
  if (mark_d == tmp_node) {
    mark_d = (NODE*)NULL;
  }

  // for SYSTEM mode delete the item memory
  //
  if (alloc_d == SYSTEM) {
    delete tmp_node->getItem();
  }
  
  // cleanup the old node
  //
  delete tmp_node;
  length_d -= 1;
  
  // exit gracefully
  //
  return true;
}

//---------------------------------------------------------------------------
//
// class-specific public methods:
//  property methods
//
//---------------------------------------------------------------------------

// method: contains
//
// arguments:
//  TObject* item: (input) the item to be found
//
// return: a boolean value indicating status
//
// this method determines if an item is contained in this list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::contains(const TObject* item_a) const {

  // check if the input item is NULL
  //
  if (item_a == (TObject*)NULL) {
    return Error::handle(name(), L"contains", Error::NULL_ARG,
			 __FILE__, __LINE__);
  }

  // save the current position
  //
  NODE* temp_curr = curr_d;

  // call the find method
  //
  boolean item_found =
    const_cast<DoubleLinkedList<TObject>*>(this)->find(item_a);

  // revert the current pointer so as to leave the list unchanged
  //
  const_cast<DoubleLinkedList<TObject>*>(this)->curr_d = temp_curr;
  
  // return whether or not the item was found
  //
  return item_found;
}

// method: find
//
// arguments:
//  TObject* item: (input) the item to be found
//
// return: a boolean value indicating status
//
// this method finds the first item in the list which is equivalent to the
// item passed in. if no equivalent item is found, false is returned. if an
// item is found, the list is positioned to that point, otherwise the state
// of the list is unchanged. 
//
template<class TObject>
boolean DoubleLinkedList<TObject>::find(const TObject* item_a) {
  
  // check if the input item is NULL
  //
  if (item_a == (TObject*)NULL) {
    return Error::handle(name(), L"find", Error::NULL_ARG,
			 __FILE__, __LINE__);
  }

  // save the current position
  //
  NODE* temp_curr = curr_d;

  // temporary variables
  //
  boolean item_found = false;
  boolean more_nodes = gotoFirst();
  
  // search from the beginning for the item
  //
  while (!item_found && more_nodes) {
    if (!(item_found = item_a->eq(*getCurr()))) {
      more_nodes = gotoNext();
    }
  }

  if (!item_found) {
    curr_d = temp_curr;
  }
  
  // return whether or not the item was found
  //
  return item_found;
}

// method: getPosition
//
// arguments: none
//
// return: the index position of the current element
//
// this method determines the ordinal index of the current
// element. assuming the list was unchanged a later call to
// gotoNode(pos) will return the current pointer to the current state.
//
template<class TObject>
long DoubleLinkedList<TObject>::getPosition() const {

  // if there are no elements, the position is invalid
  //
  if (isEmpty()) {
    return -1;
  }
  
  // save the current position
  //
  NODE* temp_curr = curr_d;

  // temporary variables
  //
  
  // search from the beginning for the item
  //
  long count = 0;
  for (boolean more=const_cast<DoubleLinkedList<TObject>*>(this)->gotoFirst();
       more && (curr_d != temp_curr);
       more = const_cast<DoubleLinkedList<TObject>*>(this)->gotoNext()) {
    count++;
  }

  // restore the current pointer
  //
  const_cast<DoubleLinkedList<TObject>*>(this)->curr_d = temp_curr;

  // return whether or not the item was found
  //
  return count;
}

//---------------------------------------------------------------------------
//
// class-specific public methods:
//  ordering methods
//
//---------------------------------------------------------------------------  

// method: sort
//
// arguments:
//  Integral::ORDER sort_order: (input) the order to sort
//  SORT_ALGO sort_algo_a: (input) the algorithm to use
// 
// return: a boolean value indicating status
//
// this method sorts the elements in the list according to the given order
//
template<class TObject>
boolean DoubleLinkedList<TObject>::sort(Integral::ORDER sort_order_a,
					SORT_ALGO sort_algo_a) {

  // branch on sort algorithms
  //
  if (sort_algo_a == RAND_QUICK) {
    return randQuickSort(sort_order_a);
  }
  else if (sort_algo_a == INSERTION) {
    return insertionSort(sort_order_a);
  }
  else {
    return Error::handle(name(), L"sort", Error::NOT_IMPLEM,
                         __FILE__, __LINE__, Error::WARNING);
  }
}

// method: reverse
//
// arguments: none
//  
// return: a boolean value indicating status
//
// this method reverse the order of element in the list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::reverse() {

  // if the list is empty then do nothing
  //
  if (isEmpty()) {
    return true;
  }
  
  // create temporary variables to use for exchanging pointers
  //
  NODE* tmp_node = first_d;
  NODE* tmp_next = (NODE*)NULL;
  
  // start from the beginning of the list, loop over each node and
  // reverse the link
  //
  while (tmp_node != (NODE*)NULL) {
    
    // exchange the previous and next pointers
    //
    tmp_next = tmp_node->getNext();
    tmp_node->setNext(tmp_node->getPrev());
    tmp_node->setPrev(tmp_next);

    // move to the next node for reversing
    //
    tmp_node = tmp_node->getPrev();
  }
  
  // exchange the old first and last nodes
  //
  tmp_node = first_d;
  first_d = last_d;
  last_d = tmp_node;
  
  // exit gracefully
  //
  return true;
}

// method: swap
//
// arguments:
//  long i: (input) the node to swap
//  long j: (input) the node to swap
//
// return: a boolean value indicating status
//
// this method swaps the two nodes in the list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::swap(long i_a, long j_a) {
  
  // make sure the indices are in the range of the list
  //
  if (i_a < 0 || (i_a > (long)length_d - 1) ||
      j_a < 0 || (j_a > (long)length_d - 1)) {
    
    return Error::handle(name(), L"swap", Error::BOUNDS,
			 __FILE__, __LINE__);
  }
  
  // the private exchange method works for i < j,
  // so exchange the pointer if j < i
  //
  long i, j;
  if (i_a < j_a) {
    i = i_a;
    j = j_a;
  }
  else if ( j_a < i_a) {
    i = j_a;
    j = i_a;
  }
  else {
    
    // the same node, no need to exchange
    //
    return true;
  }

  // find the i_node and j_node
  //
  NODE* i_node = (NODE*)NULL;
  NODE* j_node = (NODE*)NULL;
  NODE* pp = first_d;
  
  for (long k = 0; k < i; k++) {
    pp = pp->getNext();
  }
  i_node = pp;
  
  for (long k = i; k < j; k++) {
    pp = pp->getNext();
  }
  j_node = pp;
  
  // call the other exchange method
  //
  return swap(i_node, j_node);
}

//---------------------------------------------------------------------------
//
// class-specific public methods:
//  apply methods
//
//---------------------------------------------------------------------------

// method: apply
//
// arguments:
//  boolean (TObject::*method)(): (input) the method to apply to each element
//                                this method must be a member of the TObject
//                                class
//
// return: a boolean value indicating status
//
// this method applies the input method to each element in the list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::apply(boolean (TObject::*method_a)()) {

  // declare a return value
  //
  boolean return_val = true;

  // create temporary variables
  //
  NODE* tmp_node = first_d;
  TObject* element;

  // loop over each element in the list and apply the method to it
  //
  while (tmp_node != (NODE*)NULL) {

    if ((element = tmp_node->getItem()) != (TObject*)NULL) {
      return_val &= ((tmp_node->getItem())->*method_a)();
    }
    else {
      return (Error::handle(name(), L"apply", Node<TObject>::ERR_NOITEM,
			    __FILE__, __LINE__));
    }

    // move to the next node
    //
    tmp_node = tmp_node->getNext();
  }
  
  // exit gracefully
  //
  return return_val;
}

// method: apply
//
// arguments:
//  boolean (TObject::*method)(): (input) the method to apply to each element
//                                this method must be a member of the TObject
//                                class
//  DoubleLinkedList<TObject>& arg: (input) the list to be applied the
//                                  method on
//
// return: a boolean value indicating status
//
// this method applies the input method to each element in the list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::apply(boolean (TObject::*method_a)(),
					 DoubleLinkedList<TObject>& arg_a) {
  
  // assign the input list to this linked list
  //
  assign(arg_a);
  
  // apply the method to the input list
  //
  return apply(method_a);
}

//---------------------------------------------------------------------------
//
// private methods
//
//---------------------------------------------------------------------------

// method: randQuickSort
//
// arguments:
//  Integral::ORDER sort_order: (input) ascending or descending
//
// return: a boolean value indicating status
//
// "randomized version of quicksort" is taken from:
//
//  T. Cormen, C. Leiserson, R. Rivest,
//  Introduction to Algorithms, MIT Press,
//  Boston, Massachusetts, USA, pp. 153-171, 1998.
//
// this method sorts the linked list using the randomized sort algorithm
//
template<class TObject>
boolean DoubleLinkedList<TObject>::randQuickSort(Integral::ORDER
						 sort_order_a) {

  // declare the sort order to be true if the order is ascending and
  // false if the order is descending - this will help us in deciding
  // that whether we want to go to right or left
  //
  boolean order = true;
  if (sort_order_a == Integral::DESCENDING) {
    order = false;
  }
  
  // declare two pairs of stacks which stores the pointers to nodes and their
  // indices in the linked list 
  //
  Stack<NODE > p_stack(USER);
  Stack<NODE > r_stack(USER);
  Stack<Long> p_ind_stack(SYSTEM);
  Stack<Long> r_ind_stack(SYSTEM);
  
  // store the partition indices in the vectors
  //
  Long num;
  p_stack.push(first_d);
  num = 0;
  p_ind_stack.push(&num);
  
  r_stack.push(last_d);
  num = (long)length_d - 1;
  r_ind_stack.push(&num);
  
  // declare the temporary variables
  //
  Long p;
  Long r;
  NODE* p_node;
  NODE* r_node;
  NODE* i_node;
  NODE* j_node;
  long i, j;

  TObject* tmp_obj;
  TObject pivot;
  
  // keep sorting the partition regions
  //
  while (!p_stack.isEmpty()) {
    
    p_node = (NODE* )NULL;
    r_node = (NODE* )NULL;
 
    p_node = p_stack.pop();
    r_node = r_stack.pop();
    
    p_ind_stack.pop(&p);
    r_ind_stack.pop(&r);
    
    // this is the partition method
    //
    if (p < r) {

      // select a number at random between p and r
      //
      Long rand_pivot = p;
      rand_pivot.rand(p, r);
      
      // error if the value does not lie between p and r
      //
      if ((rand_pivot < p) || (rand_pivot > r)) {
	return Error::handle(name(), L"randQuickSort", Error::ARG,
			     __FILE__, __LINE__);
      }
      
      // find the pivot element
      //
      curr_d = p_node;
      for (long k = p; k < rand_pivot; k++) {
	gotoNext();
      }
      tmp_obj = getCurr();
      pivot.assign(*tmp_obj);                    // pivot element
   
      // starting positions for sort, this is following the algorithm in the
      // reference, but since a linked list can not have indices < 0 or
      // > length_d, special cases of the start and end nodes have to be
      // taken care of
      //
      i = (long)p - 1;
      j = (long)r + 1;

      boolean inode_is_first = false;
      boolean jnode_is_last = false;
      
      if (p_node == first_d) {
	i_node = p_node;
	inode_is_first = true;
      }
      else {
	i_node = p_node->getPrev();
      }

      if (r_node == last_d) {
	j_node = r_node;
	jnode_is_last = true;
      }
      el