vislist.h

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

#ifndef VISLIST_H
#define VISLIST_H

#include <algae/algae.h>
#include <algae/visible.h>
#include <iterator>
#include <cstddef>


//
// List,
//   Steven J Zeil
//   Old Dominion University,
//   Dept. of Computer Science
//     May, 1995
//
// This is a list template in the style of the STL list template.  It differs
// from the STL list in that it lacks: 
//        A) allocators
//        B) template member functions
//
// On the other hand, it compiles and runs on many compilers where
// the HP version of the STL does not (or simply is not available).

#include <algae/config.h>

#include <cassert>
#include <limits.h>
 
struct ListNodeBase: public Visible
{
  ListNodeBase* prev;
  ListNodeBase* next;

  ListNodeBase (AlgAE::Color c): Visible(c) {}
  virtual ~ListNodeBase() {}
  virtual bool isANode() const = 0;
};


template <class T>
struct ListNode: public ListNodeBase
{
  T data;
  bool showPrev;
  
  ListNode(AlgAE::Color c = AlgAE::PaleMagenta, bool showPrevPtrs = true)
    : ListNodeBase(c), showPrev(showPrevPtrs)
    {next = this; prev = this;};

  virtual ~ListNode() {}

  ListNode(const T& t, ListNodeBase* p, ListNodeBase* n,
	   AlgAE::Color c = AlgAE::PaleMagenta)
    : ListNodeBase(c), data(t)   {prev = p; next= n;}


  ////////////////////////////////////////////////
  // Required for animation
  virtual bool isANode() const {return true;}


  virtual void touchAllPointers() const
    {
      if (showPrev)
	{
	  if (prev != 0 && prev->isANode())
	    touch (prev, AlgAE::W);
	  else
	    touch (0, AlgAE::W);
	}
      if (next != 0 && next->isANode())
	touch (next, AlgAE::E);
      else
	touch (0, AlgAE::E);
    }
  
  virtual void writeText (ostream & out) const
    {
      out << data;
    }


};


///////////////////////////////////////////////////////////////

template <class T>
class ListIterator;

template <class T>
class VisibleList;





template <class T>
class const_ListIterator: public Visible,
			  public bidirectional_iterator<T, ptrdiff_t>
{
private:
  const ListNodeBase* at;

  const_ListIterator(ListNodeBase* n): Visible(AlgAE::PaleGreen), at(n) {}
  friend class VisibleList<T>;
  friend class ListIterator<T>;

public:
  const_ListIterator(): Visible(AlgAE::PaleGreen), at(0) {}
 
  const_ListIterator& operator++() //prefix
  {
    assert(at !=0);
    at = at->next;
    return (*this);
  }

  const_ListIterator operator++(int) //postfix
  {
    assert(at !=0);
    at = at->next;
    return const_ListIterator<T>(at->prev);
  }

  const_ListIterator& operator--()  //prefix
  {
    assert(at !=0);
    at = at->prev;
    return (*this);
  }

  const_ListIterator operator--(int)  //postfix
  {
    assert(at !=0);
    at = at->prev;
    return const_ListIterator<T> (at->next);
  }

  const T& operator* () const
  {
    assert(at !=0);
    return ((const ListNode<T>*)at)->data;
  }

  bool operator== (const const_ListIterator& i) const
  {
    return at==i.at;
  }

  bool operator != (const const_ListIterator& i) const
  {
    return at != i.at;
  }

  ////////////////////////////////////////////////
  // Required for animation
  virtual void touchAllPointers() const
    {
      touch (at, AlgAE::AnyDir);
    }
  
  virtual void writeText (ostream&) const{}
};



///////////////////////////////////////////////////////////////


template <class T>
class ListIterator : public const_ListIterator<T>
{
private:
  ListIterator(ListNodeBase* n): const_ListIterator<T>(n) {}
  friend class VisibleList<T>;

public:
  ListIterator() {}
 
  ListIterator& operator++() //prefix
  {
    assert(at !=0);
    at = at->next;
    return (*this);
  }

  ListIterator operator++(int) //postfix
  {
    assert(at !=0);
    at = at->next;
    return ListIterator<T>(at->prev);
  }


  ListIterator& operator--()  //prefix
  {
    assert(at !=0);
    at = at->prev;
    return (*this);
  }

  ListIterator operator--(int)  //postfix
  {
    assert(at !=0); 
    at = at->prev;
   return ListIterator<T>(at->next);
  }


  T& operator* ()  const 
  { 
    return ((ListNode<T>*) at)->data;
  }

  bool operator== (const ListIterator& i) const
  {
    return at==i.at;
  }

  bool operator != (const ListIterator& i) const
  {
    return at != i.at;
  }
};


///////////////////////////////////////////////////////////////


template <class T>
class VisibleList: public ListNodeBase {
public:
  typedef T value_type;
  typedef T* pointer;
  typedef T& reference;
  typedef const T& const_reference;
#define Size_Type unsigned
  typedef Size_Type size_type;
  typedef int difference_type;
  
  typedef ListIterator<T> iterator;
  typedef const_ListIterator<T> const_iterator;
    
private:
  size_type _size;

  void kill(ListNodeBase* first, ListNodeBase* last);

  bool showPrev;
  
public:

  VisibleList(AlgAE::Color c = AlgAE::Magenta, bool showPrevPtrs = false)
    : ListNodeBase(c), showPrev(showPrevPtrs), _size(0)
    {prev=this; next=this;}

  VisibleList(size_type n, const T& value = T(),
       AlgAE::Color c = AlgAE::Magenta, bool showPrevPtrs = false);

  VisibleList(const VisibleList<T>& x);

  ~VisibleList()		        {  kill(next, this); }


  bool empty() const            { return _size == 0; }
  size_type size() const        { return _size; }
  size_type max_size() const    { return INT_MAX; }


  iterator begin()      	{ return iterator (next); }
  const_iterator begin() const  { return const_iterator(next); }

  iterator end()                { return iterator(this); }
  const_iterator end() const    { return const_iterator((ListNodeBase*)this); }

  reference front()             { assert (_size != 0);
                                  return ((ListNode<T>*)next)->data; }

  const_reference front() const { assert (_size != 0);
                                  return ((const ListNode<T>*)next)->data; }

  reference back()              { assert (_size != 0);
                                  return ((ListNode<T>*)prev)->data; }

  const_reference back() const  { assert (_size != 0);
                                  return ((const ListNode<T>*)prev)->data; }


  iterator insert(iterator position, const T& x);
  void     insert(iterator position, iterator first, iterator last);
  void     insert(iterator position, const_iterator first,
		  const_iterator last);
  void     insert(iterator position, size_type n, const T& x);


  void push_front(const T& x)  { insert(begin(), x); }
  void push_back(const T& x)   { insert( end(), x); }

  void erase(iterator position);
  void erase(iterator first, iterator last);

  void pop_front()             { assert (_size > 0); erase(next); }
  void pop_back()              { assert (_size > 0); erase (prev); }

  void clear()                 {erase(begin(), end());}


  const VisibleList<T>&  operator=( const VisibleList<T>& x );

  void swap(VisibleList<T>& x);
 

  void splice(iterator position, VisibleList<T>& x)
     {
       assert (&x != this);
       splice (position, x, x.begin(), x.end());
     }
  void splice(iterator position, VisibleList<T>& x, iterator i)
     {
       assert (i.at != 0);
       splice (position, x, i, iterator(i.at->next));
     }

  void splice(iterator position, VisibleList<T>& x, iterator first, iterator last);
 

  void remove(const T& value);
  void unique();
  void merge(VisibleList<T>& x);
  void reverse();
  void sort();

  ////////////////////////////////////////////////
  // Required for animation
  virtual bool isANode() const {return false;}


  virtual void touchAllPointers() const
    {
      if (showPrev)
	{
	  if (prev != 0 && prev->isANode())
	    touch (prev, AlgAE::W);
	  else
	    touch (0, AlgAE::W);
	}
      if (next != 0 && next->isANode())
	touch (next, AlgAE::E);
      else
	touch (0, AlgAE::E);
    }

  virtual void writeText (ostream&) const {}

  void setShowPrev (bool showIt) {showPrev = showIt;}
};





/////////////////////////////////////////////////////////////////////////////

template <class T>
bool operator ==(const VisibleList<T>& x, const VisibleList<T>& y)
{
  if (x.size() == y.size())
    {
      VisibleList<T>::const_iterator i, j;
      for ( i = x.begin(), j = y.begin();
	   i != x.end() && *i == *j;
	   ++i, ++j) {}