vislist.h

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

      return (i == x.end());
    }
  else
    return false;
}




template <class T>
bool operator<(const VisibleList<T>& x, const VisibleList<T>& y)
{
  VisibleList<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 VisibleList<T>::kill(ListNodeBase* first, ListNodeBase* last)
{
  ListNodeBase* nxt;
  
  while (first != last)
    {
      nxt = first->next;
      delete first;
      first = nxt;
    }
}


template <class T>
VisibleList<T>::VisibleList(Size_Type n, const T& value,
	      AlgAE::Color c, bool showPrevPtrs)
  : _size(0), ListNodeBase(c), showPrev(showPrevPtrs)
{        
  next=prev=this;
  insert(begin(), n, value);
}


template <class T>
VisibleList<T>::VisibleList(const VisibleList<T>& x)
  : _size(0), ListNodeBase(x.color()), showPrev(x.showPrev)
{
  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> VisibleList<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 VisibleList<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 VisibleList<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 VisibleList<T>::insert(ListIterator<T> position, Size_Type n, const T& x)
{
  assert(position !=0);
  while (n--)
    insert(position, x);
}


template <class T>
void VisibleList<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 VisibleList<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 VisibleList<T>&  VisibleList<T>::operator=( const VisibleList<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 VisibleList<T>::swap(VisibleList<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 VisibleList<T>::splice(ListIterator<T> position, VisibleList<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 VisibleList<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 VisibleList<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 VisibleList<T>::merge(VisibleList<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 VisibleList<T>::reverse()
{
  if (_size > 1)
    {
      VisibleList<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 VisibleList<T>::sort()
{
  if (_size > 1)
    {
      VisibleList<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