list.h

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

#ifndef LIST_H
#define LIST_H

//
// 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 <algae/assert.h>
#include <limits.h>

 

struct ListNodeBase
{
  ListNodeBase* prev;
  ListNodeBase* next;

  virtual ~ListNodeBase() {}
};


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

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


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

template <class T>
class ListIterator;

template <class T>
class list;





template <class T>
class const_ListIterator
{
private:
  const ListNodeBase* 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<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;
  }

};



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


template <class T>
class ListIterator : public const_ListIterator<T>
{
private:
  ListIterator(ListNodeBase* n): const_ListIterator<T>(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<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 list: private 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);

 
public:

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

  list(size_type n, const T& value = T());

  list(const list<T>& x);

  ~list()		        {  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); }



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

  void swap(list<T>& x);
 

  void splice(iterator position, list<T>& x)
     {
       assert (&x != this);
       splice (position, x, 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);
 

  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>::kill(ListNodeBase* first, ListNodeBase* last)
{
  ListNodeBase* nxt;
  
  while (first != last)
    {
      nxt = first->next;
      delete first;
      first = nxt;
    }
}


template <class T>
list<T>::list(Size_Type n, const T& value)
  : _size(0)
{        
  next=prev=this;
  insert(begin(), n, value);
}


template <class T>
list<T>::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);
}



template <class T>
ListIterator<T> list<T>::insert(ListIterator<T> position, const T& x)
{
  assert(position.at != 0);
  ListNodeBase* newNode;
  if (next == this)
    {
      next = prev = newNode =
          new ListNode<T>(x, (ListNode<T>*)this, (ListNode<T>*)this);
    }
  else
    {
      ListNodeBase* pos = (ListNodeBase*)(position.at);
      newNode = new ListNode<T>(x, pos->prev, pos);
      pos->prev->next = newNode;
      pos->prev = newNode;
    }

  ++_size;
  return newNode;
}


template <class T>
void list<T>::insert(ListIterator<T> position,
		     ListIterator<T> first,
		     ListIterator<T> last) 
{
  assert(position !=0 );
  for (; first != last; ++first)
    insert(position, *first);
}
    


template <class T>
void list<T>::insert(ListIterator<T> position,
		     const_ListIterator<T> first,
		     const_ListIterator<T> last) 
{
  assert(position !=0 );
  for (; first != last; ++first)
    insert(position, *first);
}

    
template <class T>
void list<T>::insert(ListIterator<T> position, Size_Type n, const T& x)
{
  assert(position !=0);
  while (n--)
    insert(position, x);
}


template <class T>
void list<T>::erase(ListIterator<T> position)
{
  assert (position.at != 0 && position.at != this);
  position.at->prev->next = position.at->next;
  position.at->next->prev = position.at->prev;
  delete (ListNodeBase*)(position.at);
  --_size;
}


template <class T>
void list<T>::erase(ListIterator<T> first, ListIterator<T> last)
{
  assert (first.at != 0 && last.at != 0);
  size_type count = 0;
  for (ListIterator<T> p = first; p != last; ++p) ++count;
  if (first.at != last.at)
    {
      assert (first.at != this);
      ListNodeBase* lastAt = (ListNodeBase*)last.at;
      first.at->prev->next = lastAt;
      lastAt->prev = first.at->prev;
      kill ((ListNodeBase*)first.at, lastAt);
    }
  _size -= count;
}


 
template <class T>
const list<T>&  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;
}  


template <class T>
void list<T>::swap(list<T>& x)
{
  if (&x != this)
    {
      {
	size_type temp = _size;
	_size = x._size;
	x._size = temp;
      }
      {
	ListNodeBase* xprev = x.prev;
	ListNodeBase* thprev = prev;
	ListNodeBase* xnext = x.next;
	ListNodeBase* thnext = next;
        ListNodeBase* xAddr = xnext->prev;

        if (_size > 0)
          {
            prev = xprev;
            next = xnext;
            prev->next = this;
            next->prev = this;
          }
        else
          prev = next = this;

        if (x._size > 0)
          {
            x.prev = thprev;
            x.next = thnext;
            x.prev->next = xAddr;
            x.next->prev = xAddr;
          }
        else
          x.prev = x.next = xAddr;
      }
    }
}
 


template <class T>
void list<T>::splice(ListIterator<T> position, list<T>& x,
		     ListIterator<T> first,
		     ListIterator<T> last)
{
  assert (position.at != 0 && first.at != 0 && last.at != 0);
  
  if (first.at != last.at)
    {
      unsigned count = 0;
      for (iterator p = first; p != last; ++p)
	++count;

      ListNodeBase* firstAt = (ListNodeBase*)first.at;
      ListNodeBase* lastAt = (ListNodeBase*)last.at;
      ListNodeBase* lastInclusive = (ListNodeBase*)(lastAt->prev);
      
      firstAt->prev->next = lastAt;
      lastAt->prev = (ListNodeBase*)(firstAt->prev);
      x._size -= count;

      ListNodeBase* pos = (ListNodeBase*)position.at;
      ListNodeBase* posPrev = pos->prev;
      posPrev->next = firstAt;
      firstAt->prev = posPrev;
      pos->prev = lastInclusive;
      lastInclusive->next = pos;
      _size += count;
    }
}




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

#undef Size_Type

#endif