doublelinkedlist.h

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

// method: remove
//
// arguments:
//  TObject*& item: (output) the item in the current node
//  
// return: a boolean value indicating status
//
// this method removes the current node and outputs the item inside
// it. if the allocation mode is USER then the pointer returned will
// be the original item. if in SYSTEM, the user must pass in an
// allocated object and we will copy the internal data to this
// pointer, since we have to delete the internal pointer.
//
template<class TObject>
boolean DoubleLinkedList<TObject>::remove(TObject*& item_a) {

  // check curr_d
  //
  if (curr_d == (NODE*)NULL) {
    return false;
  }
  
  // make sure memory is allocated if we are SYSTEM-allocated
  //
  if ((alloc_d == SYSTEM) && (item_a == (TObject*)NULL)) {
    return (Error::handle(name(), L"remove", Error::NULL_ARG,
			  __FILE__, __LINE__));
  }

  // else initialize the output argument
  //
  else if (alloc_d == USER) {
    item_a = (TObject*)NULL;
  }

  // unlink the current node and handle special cases
  //
  // if the marked node just got deleted then set it to NULL
  //
  if (curr_d == mark_d) {
    mark_d = (NODE*)NULL;
  }  
  if (curr_d == first_d) {
    return removeFirst(item_a);
  }
  else if (curr_d == last_d) {
    return removeLast(item_a);
  }
  
  // this will either save the pointer (for USER mode) or make a copy
  // (for SYSTEM mode).
  //
  item_a = curr_d->accessByMode(item_a, alloc_d);
  
  // if allocation mode is SYSTEM, delete the pointer
  //
  if (alloc_d == SYSTEM) {
    delete curr_d->getItem();
  }
  
  // handle the general case. if curr_d is not the first or the last
  // then its link pointers can not be NULL
  //
  curr_d->getPrev()->setNext(curr_d->getNext());
  curr_d->getNext()->setPrev(curr_d->getPrev());
  
  // decrement the length of the list
  //
  length_d -= 1;

  // delete the node and set the current pointer to the next node
  //
  NODE* ptr = curr_d->getNext();
  delete curr_d;
  curr_d = ptr;
  
  // exit gracefully
  //
  return true;
}

// method: remove
//
// arguments: none
//  
// return: a boolean value indicating status
//
// this method removes the current node
//
template<class TObject>
boolean DoubleLinkedList<TObject>::remove() {
  
  // check curr_d
  //
  if (curr_d == (NODE*)NULL) {
    return false;
  }
  
  // if the marked node just got deleted then set it to NULL
  //
  if (curr_d == mark_d) {
    mark_d = (NODE*)NULL;
  }  
  if (curr_d == first_d) {
    return removeFirst();
  }
  else if (curr_d == last_d) {
    return removeLast();
  }
  
  // if allocation mode is SYSTEM, delete the pointer
  //
  if (alloc_d == SYSTEM) {
    delete curr_d->getItem();
  }
  
  // handle the general case. if curr_d is not the first or the last
  // then its link pointers can not be NULL
  //
  curr_d->getPrev()->setNext(curr_d->getNext());
  curr_d->getNext()->setPrev(curr_d->getPrev());
  
  // decrement the length of the list
  //
  length_d -= 1;

  // delete the node and set the current pointer to the next node
  //
  NODE* ptr = curr_d->getNext();
  delete curr_d;
  curr_d = ptr;
  
  // exit gracefully
  //
  return true;
}

// method: insertFirst
//
// arguments:
//  TObject* item: (input) the item to be added into the new first node
//  
// return: a boolean value indicating status
//
// this method adds a new node containing the item into the beginning
// of this list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::insertFirst(TObject* item_a) {
  
  // make sure the item is not NULL
  //
  if (item_a == (TObject*)NULL) {
    return Error::handle(name(), L"insertFirst", Error::NULL_ARG, __FILE__,
                         __LINE__);
  }
  
  // create a new node and put or copy the item into it
  //
  NODE* new_node;

  // SYSTEM mode will store a copy, USER mode stores just the reference
  //
  if (alloc_d == SYSTEM) {
    new_node = new NODE(new TObject(*item_a));
  }
  else {
    new_node = new NODE(item_a);
  }
  
  // set the links for the new node
  //
  new_node->setNext(first_d);
  new_node->setPrev((NODE*)NULL);
  
  // set the links for surrounding nodes
  //
  if (first_d != (NODE*)NULL) {
    new_node->getNext()->setPrev(new_node);
  }
  
  // if the list was previously empty then set first, last, and current
  // to the new node. otherwise, just set the first node to the new node
  //
  if (isEmpty()) {
    last_d = new_node;
  }
  first_d = new_node;
  curr_d = first_d;
  
  // increment the size of the list
  //
  length_d += 1;
  
  // exit gracefully
  //
  return true;
}

// method: insertFirst
//
// arguments:
//  DoubleLinkedList<TObject>& ilist: (input) the list to be added into
//                                    this list
//  
// return: a boolean value indicating status
//
// this method adds a list into the beginning of this list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::insertFirst(DoubleLinkedList<TObject>&
					       ilist_a) {
  
  // if the input list is empty then there is nothing to do
  //
  if (ilist_a.isEmpty()) {
    
    // exit gracefully
    //
    return true;
  }
  
  // start at the back of the input list
  //
  NODE* tmp_node = ilist_a.last_d;
  
  // loop over each element in the input list and add each element to the list
  //
  while (tmp_node != (NODE*)NULL) {
    
    // add the next element to the list
    //
    insertFirst(tmp_node->getItem());

    // move to the previous node
    //
    tmp_node = tmp_node->getPrev();
  }
  
  // exit gracefully
  //
  return true;
}

// method: removeFirst
//
// arguments:
//  TObject*& item: (output) the item in the first node
//  
// return: a boolean value indicating status
//
// this method removes the first node and outputs the item inside it.
//
template<class TObject>
boolean DoubleLinkedList<TObject>::removeFirst(TObject*& item_a) {
  
  // make sure the first node is valid
  //
  if (first_d == (NODE*)NULL) {
    return false;
  }
  
  // make sure the memory is allocated if in SYSTEM mode
  //
  if ((alloc_d == SYSTEM) && (item_a == (TObject*)NULL)) {
    return (Error::handle(name(), L"removeFirst", Error::NULL_ARG,
			  __FILE__, __LINE__));
  }

  // else initialize the output argument
  //
  else if (alloc_d == USER) {
    item_a = (TObject*)NULL;
  }
  
  // if allocation mode is USER, just return the pointer
  //
  if (alloc_d == USER) {
    item_a = first_d->getItem();
  }
  
  // for system mode assign to the output pointer and delete the item
  // memory
  //
  else {
    item_a->assign(*(first_d->getItem()));
    delete first_d->getItem();
  }
  
  // keep the position of the first node
  //
  NODE* tmp_node = first_d;
  
  // unlink the first node and set the new first 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 (first_d != last_d) {
    first_d->getNext()->setPrev((NODE*)NULL);
    first_d = first_d->getNext();
  }
  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 first node
  //
  if (curr_d == tmp_node) {
    curr_d = first_d;
  }
  
  // if the marked node just got deleted then set it to NULL
  //
  if (mark_d == tmp_node) {
    mark_d = (NODE*)NULL;
  }

  // delete the old node and decrement the length of the list
  //
  delete tmp_node;
  length_d -= 1;
  
  // exit gracefully
  //
  return true;
}

// method: removeFirst
//
// arguments: none
//  
// return: a boolean value indicating status
//
// this method removes the first node
//
template<class TObject>
boolean DoubleLinkedList<TObject>::removeFirst() {
  
  // make sure the first node is valid
  //
  if (first_d == (NODE*)NULL) {
    
    // return an error
    //
    return false;
  }
  
  // keep the position of the first node
  //
  NODE* tmp_node = first_d;
  
  // unlink the first node and set the new first 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 (first_d != last_d) {
    first_d->getNext()->setPrev((NODE*)NULL);
    first_d = first_d->getNext();
  }
  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 first node
  //
  if (curr_d == tmp_node) {
    curr_d = first_d;
  }
  
  // if the marked node just got deleted then set it to NULL
  //
  if (mark_d == tmp_node) {
    mark_d = (NODE*)NULL;
  }
  
  // delete item memory if we are SYSTEM-allocated
  //
  if (alloc_d == SYSTEM) {
    delete tmp_node->getItem();
  }
  
  // delete the old node and decrement the length of the list
  //
  delete tmp_node;
  length_d -= 1;
  
  // exit gracefully
  //
  return true;
}

// method: insertLast
//
// arguments:
//  TObject* item: (input) the item to be added into the last node
//  
// return: a boolean value indicating status
//
// this method adds a new node containing the item into the end of this list
//
template<class TObject>
boolean DoubleLinkedList<TObject>::insertLast(TObject* item_a) {
  
  // make sure the item is not NULL
  //
  if (item_a == (TObject*)NULL) {
    return Error::handle(name(), L"insertLast", Error::NULL_ARG, __FILE__,
                         __LINE__);
  }
  
  // create a new node and put or copy the item into it
  //
  NODE* new_node;

  // SYSTEM mode will store a copy, USER mode stores just the reference
  //
  if (alloc_d == SYSTEM) {
    new_node = new NODE(new TObject(*item_a));
  }
  else {
    new_node = new NODE(item_a);
  }
  
  // set the links for the new node
  //
  new_node->setNext((NODE*)NULL);
  new_node->setPrev(last_d);
  
  // set the links for surrounding nodes
  //
  if (last_d != (NODE*)NULL) {
    new_node->getPrev()->setNext(new_node);
  }
  
  // if the list was previously empty then set first, last, and current
  // to the new node. otherwise, just set the last node to the new node
  //
  if (isEmpty()) {
    first_d = new_node;
  }
  last_d = new_node;
  curr_d = last_d;
  
  // increment the size of the list
  //
  length_d += 1;
  
  // exit gracefully
  //
  return true;
}

// method: insertLast
//
// arguments:
//  DoubleLinkedList<TObject>& ilist: (input) the list to be inserted into
//                                    this list
//  
// return: a boolean value indicating status
//
// this method adds a list into the end of this list
//
template<class TObject>
boolean
DoubleLinkedList<TObject>::insertLast(DoubleLinkedList<TObject>& ilist_a) {
  
  // if the input list is empty then there is nothing to do
  //
  if (ilist_a.isEmpty()) {
    
    // exit gracefully
    //
    return true;
  }

  // start at the front of the input list
  //
  NODE* tmp_node = ilist_a.first_d;
  
  // loop over each element in the input list and add each element to the list
  //
  while (tmp_node != (NODE*)NULL) {
    
    // add the next element to the list
    //
    insertLast(tmp_node->getItem());

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

// method: removeLast
//
// arguments:
//  TObject*& item: (output) the item in the last node
//  
// return: a boolean value indicating status
//
// this method removes the last node and outputs the item inside it. it is
// used only if the memory is USER-allocated. the user is forced to
// accept a pointer to the item so they know the memory is theirs to delete
//
template<class TObject>
boolean DoubleLinkedList<TObject>::removeLast(TObject*& item_a) {

  // make sure the last node is valid
  //
  if (last_d == (NODE*)NULL) {
    return false;
  }

  // make sure memory is allocated if we are SYSTEM-allocated
  //
  if ((alloc_d == SYSTEM) && (item_a == (TObject*)NULL)) {
    return (Error::handle(name(), L"removeLast", Error::NULL_ARG,
			  __FILE__, __LINE__));
  }

  // else initialize the output argument
  //
  else if (alloc_d == USER) {
    item_a = (TObject*)NULL;
  }

  // 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;
  }

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