singlelinkedlist.h

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

  //
  if (tmp_node != tmp_last_node) {
    curr_d = tmp_node;
  }
  else {
    curr_d = last_d;
  }

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

  // if allocation mode is USER, just return the pointer
  //
  if (alloc_d == USER) {
    item_a = tmp_node->getItem();
  }

  // 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 SingleLinkedList<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;
  NODE* tmp_last_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) {
    gotoLast();
    gotoPrev();
    curr_d->setNext((NODE*)NULL);
    last_d = curr_d;
  }
  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 (tmp_node != tmp_last_node) {
    curr_d = tmp_node;
  }
  else {
    curr_d = last_d;
  }

  // if the marked node just got deleted then set it to NULL
  //
  if (mark_d == tmp_last_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 SingleLinkedList<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<SingleLinkedList<TObject>*>(this)->find(item_a);

  // revert the current pointer so as to leave the list unchanged
  //
  const_cast<SingleLinkedList<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 SingleLinkedList<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 SingleLinkedList<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<SingleLinkedList<TObject>*>(this)->gotoFirst();
       more && (curr_d != temp_curr);
       more = const_cast<SingleLinkedList<TObject>*>(this)->gotoNext()) {
    count++;
  }

  // restore the current pointer
  //
  const_cast<SingleLinkedList<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: (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 SingleLinkedList<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 SingleLinkedList<TObject>::reverse() {

  // if the list is empty then do nothing
  //
  if (isEmpty()) {
    return true;
  }
  
  // keep track of the previous node and the current one
  //
  NODE* tmp_curr = first_d;  
  NODE* tmp_prev = (NODE*)NULL;

  // start from the beginning of the list, loop over each node and
  // reverse the link
  //
  while (tmp_curr != (NODE*)NULL) {

    NODE* tmp_next = tmp_curr->getNext();

    // reverse the next pointer for the current node
    //
    tmp_curr->setNext(tmp_prev);

    // slide the nodes along
    //
    tmp_prev = tmp_curr;
    tmp_curr = tmp_next;
  }
  
  // swap the old first and last nodes
  //
  tmp_curr = first_d;
  first_d = last_d;
  last_d = tmp_curr;
  
  // exit gracefully
  //
  return true;
}

// method: swap
//
// arguments:
//  long i: (input) the index of the first node to swap
//  long j: (input) the index of the second node to swap
//
// return: a boolean value indicating status
//
// this method swaps the two nodes in the list
//
template<class TObject>
boolean SingleLinkedList<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 and their previous nodes
  // since it is expensive for singleLinkedList to get previous node
  // to avoid extra search, we don't call the other swap method
  //
  NODE* i_node = (NODE*)NULL;
  NODE* j_node = (NODE*)NULL;
  NODE* i_prev_node = (NODE*)NULL;
  NODE* j_prev_node = (NODE*)NULL;
  NODE* i_next_node = (NODE*)NULL;
  NODE* j_next_node = (NODE*)NULL;

  NODE* pp = first_d;
  NODE* pp_prev = (NODE*)NULL;
  
  for (long k = 0; k < i; k++) {
    pp_prev = pp;
    pp = pp->getNext();
   
  }
  i_prev_node = pp_prev;
  i_node = pp;
  
  for (long k = i; k < j; k++) {
    pp_prev = pp;
    pp = pp->getNext();
  }
  j_prev_node = pp_prev;
  j_node = pp;
  
  // swap (i < j)
  //
  i_next_node = i_node->getNext();
  j_next_node = j_node->getNext();  
  
  // reconnect i_node and j_node (take care of the case that i_node and
  // j_node are adjacent, and first / last node)
  //
  if (i_next_node == j_node) {
    i_next_node = i_node;
    j_prev_node = j_node;
  }
  
  if (i_prev_node != (NODE*)NULL) {
    i_prev_node->setNext(j_node);
  }
  else {
    first_d = j_node;
  }
  
  j_node->setNext(i_next_node);
  if (i_next_node == (NODE*)NULL) {
    last_d = j_node;
  }
  
  if (j_prev_node != (NODE*)NULL) {
    j_prev_node->setNext(i_node);
  }
  else {
    first_d = i_node;
  }
  
  i_node->setNext(j_next_node);
  if (j_next_node == (NODE*)NULL) {
    last_d = i_node;
  }
	  
  // swap the pointers to i and j nodes, 
  //
  NODE* tmp_node = j_node;
  j_node = i_node;
  i_node = tmp_node;
  
  // exit gracefully
  //
  return true;
}

//---------------------------------------------------------------------------
//
// 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 SingleLinkedList<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
//  SingleLinkedList<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 SingleLinkedList<TObject>::apply(boolean (TObject::*method_a)(),
					 SingleLinkedList<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 SingleLinkedList<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);
  n