forwlist.h

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

#ifndef LIST_H
#define LIST_H

//
// List,
//   Steven J Zeil, Jun Zhang
//   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) splice operations
//        C) sort operations
//
// 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 STDASSERT
#include <values.h>

 

struct ListNodeBase
{
  ListNodeBase* prev;
  ListNodeBase* next;

  virtual ~ListNodeBase() {}
  
};


template <class T>
struct ListNode: public ListNodeBase {
 T data;
 ListNode(): next(this), prev(this) {};

 ListNode(const T& t, ListNode<T>* p, ListNode<T>* n)
   : data(t), prev(p), next(n) {}
};


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


template <class T>
class const_ListIterator
{
private:
  const ForwardListNodeBase* at;

  const_ListIterator(ListNodeBase* n): at(n) {}
  friend class list<T>;
  friend class ListIterator<T>;

public:
  const_ListIterator(): 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(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 (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;
  }

};



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


template <class T>
class ListIterator : public const_ListIterator<T>
{
private:
  ListIterator(ListNodeBase* n): const_ListIterator(n) {}
  friend class list<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(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(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 list: private ListNodeBase {
public:
   typedef T value_type;
   typedef T* pointer;
   typedef T& reference;
   typedef const T& const_reference;
   typedef unsigned size_type;
   typedef int difference_type;
  
   typedef ListIterator<T> iterator;
   typedef const_ListIterator<T> const_iterator;
    
private:
   size_type _size;

   void kill(ListNodeBase<T>* first, ListNodeBase<T>* last)
   {
     ListNodeBase<T>* nxt;

     while (first != last)
       {
	 nxt = curr->next;
	 delete curr;
	 first = nxt;
       }
   }
  
 
public:

  list()		: _size(0)  {prev=this; next=this;}

  list(size_type n, const T& value = T())
    : _size(0)
  {        
    next=prev=this;
    insert(begin(), n, value);
  }


  list(const list<T>& x)
    : _size(0)
  {
    next=prev=this;
    if (x._size > 0)
      for (const_iterator i=x.begin(); i !=x.end(); i++)
	insert(end(), *i);
  }

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


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


  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(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)
  {
    assert(position !=0);
    if (next == this)
      {   
        next=prev=new ListNode<T>(x, (ListNode<T>*)this, (ListNode<T>*)this); 
      }
    else
      {
	ListNodeBase* newNode = new
	  ListNode<T>(x,
		      position.at->prev,
		      position.at);
	position.at->prev->next = newNode;
	position.at->prev = newNode;
      }

    ++_size;
  }


   void insert(iterator position,
	       iterator first,
	       iterator last) 
  {
    assert(position !=0 );
    for (; first != last; ++first)
      insert(position, *first);
  }
    


  void insert(iterator position,
	      const_iterator first,
	      const_iterator last) 

  {
    assert(position !=0 );
    for (; first != last; ++first)
      insert(position, *first);
  }

    
  void insert(iterator position, size_type n, const T& x)
  {
    assert(position !=0);
    while (n--)
      insert(position, x);
  }


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

  void erase(iterator position)
  {
    assert (position.at != 0 && position.at != this);
    position.at->prev->next = position.at->next;
    position.at->next->prev = position.at->prev;
    delete position.at;
    --_size;
  }


  void erase(iterator first, iterator last)
  {
    assert (first.at != 0 && last.at != 0);
    if (first.at != last.at)
      {
	assert (first.at != this);
        first.at->prev->next = last.at;
	last.at->prev = first.at->prev;
        kill (first.at, last.at);
      }
  }

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


 
  const list<T>&  operator=( const list<T>& x )
  {
    if (&x != this )
      {
	erase (begin(), end());
	for (const_iterator i=x.begin(); i !=x.end(); i++)
	  push_back(*i);
      }
    return *this;
  }  


  void swap(list<T>& x)
  {
    if (&x != this)
      {
	{
	  size_type temp = _size;
	  _size = x._size;
	  x._size = temp;
	}
	{
	  ListNodeBase* temp = prev;
	  prev = x.prev;
	  x.prev = temp;

	  temp = next;
	  next = x.next;
	  x.next = temp;
	}
      }
  }
 

protected:
    void transfer(iterator position, iterator first, iterator last) {
        last.at->prev->next = position.at;
        first.at->prev->next =last.at;
        position.at->prev->next = first.at;  
        ListNodeBase* tmp = position.at->prev;
        position.at->prev = last.at->prev;
        last.at->prev = first.at->prev; 
        first.at->prev = tmp;
    }


public:
  void splice(iterator position, list<T>& x)
  {
    assert (&x != this);
    splice (position, x.begin(), x.end());
  }
  



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

  void splice(iterator position, list<T>& x, iterator first, iterator last)
  {
    assert (position.at != 0 && first.at != 0 && last.at != 0);
  
    if (first.at != last.at)
      {
	unsigned count = 0;
	for (ListNodeBase*p = first; p != last; p = p->next)
	  ++count;

	ListNodeBase* lastInclusive = last->prev;

	first->prev->next = last;
	last->prev = first->prev;
	x._size -= count;

	ListNodeBase* posPrev = position->prev;
	posPrev->next = first;
	first->prev = posPrev;
	position->prev = lastInclusive;
	lastInclusive->next = position;
	_size += count;
      }
  }


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

};




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

template <class T>
bool operator==(const list<T>& x, const list<T>& y)
{

  if (x.size() == y.size())
    {
      list<T>::const_iterator i, j;
      for ( i = x.begin(), j = y.begin();
	   i != x.end() && *i == *j;
	   ++i, ++j) {}
      return (i == x.end());
    }
  else
    return false;
}


template <class T>
bool operator<(const list<T>& x, const list<T>& y)
{
  list<T>::const_iterator i, j;
  for ( i = x.begin(), j = y.begin();
	i != x.end() && *j != y.end() && *i == *j;
	++i, ++j) {}
  if (i == x.end())
    if (j == y.end())
      return false; // lists are ==
    else
      return true;  // y is an "extension" of x
  else
    if (j == y.end())
      return false;  // x is an extension of y
    else
      return (*i < *j); // lists differ at these corresponding positions
}


template <class T>
void list<T>::remove(const T& value)
{
  iterator first = begin();
  iterator last = end();
  iterator next;
  while (first != last)
    {
      next = first;
      ++next;
      if (*first == value)
	erase(first);
      first = next;
    }
}


template <class T>
void list<T>::unique() 
{
  if (size() > 1)
    {
      iterator first = begin();
      iterator next = first;
      ++next;
      iterator last = end();
      while (next != last)
	{
	  if (*first == *next)
	    {
	      erase(next);
	      next = first;
	    }
	  else
	    {
	      first = next;
	    }
	  ++next;
	}
    }
}

	  

template <class T>
void list<T>::merge(list<T>& x)
{
  iterator first1 = begin();
  iterator last1 = end();
  iterator first2 = x.begin();
  iterator last2 = x.end();

  while (first1 != last1 && first2 != last2)
    {
      if (*first2 < *first1)
	{
	  iterator next = first2;
          splice (first1, x, first2);
	  first2 = next;
        }
      else
	++first1;
    }

  if (first2 != last2)
    splice (first1, x, first2, last2);
}


template <class T>
void list<T>::reverse()
{
  if (_size > 1)
    {
      list<T> temp;
      iterator first = begin();
      iterator last = end();
      iterator next;
      
      while (first != last)
	{
	  next = first;
	  ++next;
	  splice (temp.begin(), *this, first);
	  first = next;
      }
      swap(temp);
    }
}



template <class T>
void list<T>::sort()
{
  if (_size > 1)
    {
      list<T> secondHalf;
      size_type half = _size / 2;
      iterator median = begin();
      while (half > 0)
	{
	  ++median;
	  --half;
	}
      secondHalf.splice(secondHalf.begin(), *this, median, end());

      sort();
      secondHalf.sort();
      merge (secondHalf);
    }
}


#endif