vislist.h

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

//
//    class list -
//
//

#include "listiterator.h"
#include <cassert>

/*{*/typedef VisibleInteger T; /*}*/

/*{*/ // /*}*/template <class T>
class VisibleList/*{*/: public Visible /*}*/
{
public:
  // type definitions
  typedef T value_type;
  typedef listIterator<T> iterator;

  // constructor and destructor
  VisibleList (): firstLink(0), lastLink(0) /*{*/, Visible(AlgAE::Blue, false), vFirstLink(0,"firstLink"), vLastLink(0,"lastLink") /*}*/{ }
  ~VisibleList ();

  // operations
  bool empty () const { return firstLink == 0; }
  int size() const ;
  T & back () { return lastLink->value; }
  T & front () { return firstLink->value; }
  void push_front(const T &);
  void push_back(const T &);
  void pop_front ();
  void pop_back ();
  iterator begin () const;
  iterator end () const;
  void sort ();
  iterator insert (const iterator&, const T&);
  void erase (const iterator & itr) { erase (itr, itr); }
  void erase (const iterator &, const iterator &);

/*{*/ virtual void touchAllPointers() const
/*{*/ {
/*{*/ }
/*{*/
/*{*/ virtual void writeText(STD ostream&) const {}
/*{*/ virtual void touchAllComponents() const
/*{*/ {
/*{*/  VisibleList/*!<T>*/* self = (VisibleList/*!<T>*/*)this;
/*{*/  self->vFirstLink = firstLink;
/*{*/  self->vLastLink = lastLink;
/*{*/  touch (vFirstLink);
/*{*/  touch (vLastLink);
/*{*/ }
protected:
  friend class listIterator<T>;

  link <T> * firstLink;/*{*/VisiblePointer<link<T>, AlgAE::S> vFirstLink; /*}*/
  link <T> * lastLink;/*{*/VisiblePointer<link<T>, AlgAE::S> vLastLink; /*}*/
};


/*{*/ int VisibleList::size () const// /*}*/template <class T> int VisibleList<T>::size () const
  // count number of elements in collection
{
  int counter = 0;
  for (link<T> * ptr = firstLink; ptr != 0; ptr = ptr->nextLink)
    counter++;
  return counter;
}


/*{*/ void VisibleList::push_front (const T & newValue)//
/*{*/ // /*}*/template <class T> void VisibleList<T>::push_front (const T & newValue)
  // add a new value to the front of a list
{
  /*{*/if (StopAtFrames) algae->FRAME("starting push_front");/*}*/link<T> * newLink = new link<T> (newValue);
  /*{*/VisiblePointer<link<T>, AlgAE::SSE> vNewLink (newLink, "newLink"); vNewLink.show(); if (StopAtFrames) algae->FRAME("allocated new node");/*}*/if (empty()) /*{*/{ /*}*/
    firstLink = lastLink = newLink;/*{*/if (StopAtFrames) algae->FRAME("added 1st node");} /*}*/
  else {
    firstLink->prevLink = newLink;/*{*/if (StopAtFrames) algae->FRAME("push_front: set back link"); /*}*/
    newLink->nextLink = firstLink;/*{*/if (StopAtFrames) algae->FRAME("push_front: set forward link"); /*}*/
    firstLink = newLink;/*{*/if (StopAtFrames) algae->FRAME("push_front: set firstLink"); /*}*/
  }
}

/*{*/ void VisibleList::push_back (const T & newValue)
/*{*/ // /*}*/template <class T> void VisibleList<T>::push_back (const T & newValue)
  // add a new value to the rear of a list
{
  /*{*/if (StopAtFrames) algae->FRAME("starting push_back");/*}*/link<T> * newLink = new link<T> (newValue);
  /*{*/VisiblePointer<link<T>, AlgAE::SSE> vNewLink (newLink, "newLink"); vNewLink.show(); if (StopAtFrames) algae->FRAME("allocated new node.");/*}*/if (empty()) /*{*/{ /*}*/
    firstLink = lastLink = newLink;/*{*/if (StopAtFrames) algae->FRAME("added 1st node.");} /*}*/
  else {
    lastLink->nextLink = newLink;/*{*/if (StopAtFrames) algae->FRAME("push_back: set forward link"); /*}*/
    newLink->prevLink = lastLink;/*{*/if (StopAtFrames) algae->FRAME("push_back: set back link"); /*}*/
    lastLink = newLink;/*{*/if (StopAtFrames) algae->FRAME("push_back: set lastLink"); /*}*/
  }
}

/*{*/ void VisibleList::pop_front()
/*{*/ // /*}*/template <class T> void VisibleList<T>::pop_front()
  // remove first element from linked list
{
  /*{*/if (StopAtFrames) algae->FRAME("starting pop_front");/*}*/link <T> * save = firstLink;
    /*{*/VisiblePointer<link<T>, AlgAE::SSE> vSave; vSave.setName("save"); vSave=save; if (StopAtFrames) algae->FRAME("saved first link");/*}*/firstLink = firstLink->nextLink;
  /*{*/if (StopAtFrames) algae->FRAME("advanced firstLink");/*}*/if (firstLink != 0)/*{*/{ /*}*/
    firstLink->prevLink = 0;/*{*/if (StopAtFrames) algae->FRAME("list is non-empty");}/*}*/
  else/*{*/{ /*}*/
    lastLink = 0;/*{*/if (StopAtFrames) algae->FRAME("list is empty");}/*}*/
  delete save;
/*{*/vSave=0; if (StopAtFrames) algae->FRAME("deleted node");/*}*/}

/*{*/ VisibleList::~VisibleList () /*}*/
/*{*/ // /*}*/template <class T>
/*{*/ // /*}*/VisibleList<T>::~VisibleList ()
  // remove each element from the list
{
  link <T> * first = firstLink;
  while (first != 0) {
    link <T> * next  = first->nextLink;
    delete first;
    first = next;
  }
}

/*{*/ VisibleList::iterator VisibleList::insert (const VisibleList::iterator & itr, const T & value)/*}*/
/*{*/ // /*}*/template <class T>
/*{*/ // /*}*/listIterator<T> VisibleList<T>::insert (const listIterator<T> & itr, const T & value)
  // insert a new element into the middle of a linked list
{/*{*/if (StopAtFrames) algae->FRAME("insert: allocate new node"); /*}*/
  link<T> * newLink = new link<T>(value);/*{*/VisiblePointer<link<T>, AlgAE::NNE> vNewLink(newLink, "newLink"); vNewLink.show(); if (StopAtFrames) algae->FRAME("insert: allocated new node"); /*}*/
  link<T> * current = itr.currentLink;/*{*/VisiblePointer<link<T>, AlgAE::NNE> vCurrent(current, "current"); vCurrent.show(); if (StopAtFrames) algae->FRAME("insert: get current node"); /*}*/
  newLink->nextLink = current;/*{*/if (StopAtFrames) algae->FRAME("insert: set nextLink"); /*}*/
  newLink->prevLink = current->prevLink;/*{*/if (StopAtFrames) algae->FRAME("insert: set prevLink"); /*}*/
  current->prevLink = newLink;/*{*/if (StopAtFrames) algae->FRAME("insert: link from ahead"); /*}*/
  current = newLink->prevLink;/*{*/if (StopAtFrames) algae->FRAME("insert: link from behind"); /*}*/
  if (current != 0)
    current->nextLink = newLink;
/*{*/if (StopAtFrames) algae->FRAME("insert: done"); /*}*/return iterator(this, newLink);}

/*{*/void VisibleList::erase (const VisibleList::iterator& start, const VisibleList::iterator& stop)
/*{*/ // /*}*/template <class T>
/*{*/ // /*}*/void VisibleList<T>::erase (const listIterator<T> & start, const listIterator<T> & stop)
  // remove values from the range of elements
{/*{*/if (StopAtFrames) algae->FRAME("erase:");
 if (stop != start)
   {
     assert (start.currentLink != 0); /*{*/WhiteBox wb; wb.show();
     link<T> * first = start.currentLink;/*{*/ VisiblePointer<link<T>, AlgAE::NNE> vfirst(first, "first"); wb.add(vfirst); if (StopAtFrames) algae->FRAME("erase: first link to erase");
     link<T> * prev = first->prevLink;/*{*/VisiblePointer<link<T>, AlgAE::NNE> vprev(prev, "prev"); wb.add(vprev); if (StopAtFrames) algae->FRAME("erase: last link to keep");
     link<T> * last = stop.currentLink;/*{*/VisiblePointer<link<T>, AlgAE::NNE> vlast(last, "last"); wb.add(vlast); if (StopAtFrames) algae->FRAME("erase: last link to erase");
     if (prev == 0) { // removing initial portion of list
       firstLink = last;/*{*/if (StopAtFrames) algae->FRAME("erase: set firstLink");
       if (last == 0)/*{*/{ /*}*/
	 lastLink = 0;/*{*/if (StopAtFrames) algae->FRAME("erase: erased entire list");}
       else/*{*/{ /*}*/
	 last->prevLink = 0;/*{*/if (StopAtFrames) algae->FRAME("erase: erased initial portion");}
     }
     else {
       prev->nextLink = last;/*{*/if (StopAtFrames) algae->FRAME("erase: bypass erased portion");
       if (last == 0)/*{*/{ /*}*/
	 lastLink = prev;/*{*/if (StopAtFrames) algae->FRAME("erase: erased final portion");}
       else/*{*/{ /*}*/
	 last->prevLink = prev;/*{*/if (StopAtFrames) algae->FRAME("erase: isolated portion to erase");}
     }
     // now delete the values
     first = start.currentLink;/*{*/ vfirst = first; /*}*/
     last = stop.currentLink;/*{*/ vlast = last; /*}*/
     while (first != last) {
       link<T> * next = first;/*{*/VisiblePointer<link<T>, AlgAE::NNE> vnext(next, "next"); wb.add(vnext); if (StopAtFrames) algae->FRAME("erase: save next position"); bool saveStop = StopAtFrames; StopAtFrames = true;  // false
       next = first->nextLink;/*{*/StopAtFrames = saveStop; vnext = next; if (StopAtFrames) algae->FRAME("erase: advanced next");
       /*{*/vfirst->del(); vfirst=0; if (StopAtFrames) algae->FRAME("erase: deleted start node"); // /*}*/delete first;
       first = next;/*{*/vfirst=first; if (StopAtFrames) algae->FRAME("erase: advanced start"); 
     /*{*/ wb.remove (&vnext);/*}*/}
   }
 /*{*/if (StopAtFrames) algae->FRAME("erase: done"); /*}*/}

/*{*/ VisibleList::iterator VisibleList::begin () const
/*{*/ // /*}*/template <class T>
/*{*/ // /*}*/VisibleList<T>::iterator VisibleList<T>::begin () const
{ /*{*/if (StopAtFrames) algae->FRAME("begin"); /*}*/
 return iterator ((VisibleList/*!<T>*/*)this, firstLink);
}

/*{*/ VisibleList::iterator VisibleList::end () const
/*{*/ // /*}*/template <class T>
/*{*/ // /*}*/VisibleList<T>::iterator VisibleList<T>::end () const
{ /*{*/if (StopAtFrames) algae->FRAME("end"); /*}*/
 return iterator ((VisibleList/*!<T>*/*)this, 0);
}