glist.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/base/glist.imp,v $
// $Date: 2002/08/26 05:49:57 $
// $Revision: 1.3 $
//
// DESCRIPTION:
// Implementation of a generic (doubly) linked-list container class
//
// This file is part of Gambit
// Copyright (c) 2002, The Gambit Project
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//

#include "base.h"
#include <assert.h>

template <class T>
gText gList<T>::BadIndex::Description(void) const
{ return "Bad index in gList"; }


//--------------------------------------------------------------------------
//                 gNode: Member function implementations
//--------------------------------------------------------------------------

template <class T> 
gList<T>::gNode::gNode(const T &_data,
		       gList<T>::gNode *_prev, gList<T>::gNode *_next)
  : data(_data), prev(_prev), next(_next)
{ }

//--------------------------------------------------------------------------
//                 gList<T>: Member function implementations
//--------------------------------------------------------------------------

template <class T> gList<T>::gList(void) 
: length(0), head(0), tail(0), CurrIndex(0), CurrNode(0)
{ }

template <class T> gList<T>::gList(const gList<T> &b)
 : length(b.length)
{
  if (length)  {  
    gNode *n = b.head;
    head = new gNode(n->data, 0, 0);
    n = n->next;
    tail = head;
    while (n)  { 
      tail->next = new gNode(n->data, tail, 0);
      n = n->next;
      tail = tail->next;
    }
    CurrIndex = 1;
    CurrNode = head;
  }
  else  {
    head = tail = 0;
    CurrIndex = 0;
    CurrNode = 0;
  }
}

template <class T> gList<T>::~gList()
{
  Flush();
}

template <class T> int gList<T>::InsertAt(const T &t, int num)
{
  if (num < 1 || num > length + 1)   throw BadIndex();
  
  if (!length)  {
    head = tail = new gNode(t, 0, 0);
    length = 1;
    CurrIndex = 1;
    CurrNode = head;
    return length;
  }

  gNode *n;
  int i;
  
  if( num <= 1 )  {
    n = new gNode(t, 0, head);
    head->prev = n;
    CurrNode = head = n;
    CurrIndex = 1;
  }
  else if( num >= length + 1)  {
    n = new gNode(t, tail, 0);
    tail->next = n;
    CurrNode = tail = n;
    CurrIndex = length + 1;
  }
  else  {
    assert( CurrIndex >= 1 && CurrIndex <= length );
    if( num < CurrIndex )
      for (i = CurrIndex, n = CurrNode; i > num; i--, n = n->prev);
		else
      for (i = CurrIndex, n = CurrNode; i < num; i++, n = n->next);
    n = new gNode(t, n->prev, n);
    CurrNode = n->prev->next = n->next->prev = n;
    CurrIndex = num;
  }

  length++;
  return num;
}

//--------------------- visible functions ------------------------

template <class T> gList<T> &gList<T>::operator=(const gList<T> &b)
{
  if (this != &b)   {
    Flush();
    length = b.length;
    CurrIndex = b.CurrIndex;
    if (length)   {
      gNode *n = b.head;
      head = new gNode(n->data, 0, 0);
      if (b.CurrNode == n) CurrNode = head;
      n = n->next;
      tail = head;
      while (n)  {
	tail->next = new gNode(n->data, tail, 0);
	if (b.CurrNode == n) CurrNode = tail->next;
	n = n->next;
	tail = tail->next;
      }
    }
    else
      head = tail = 0;
  }
  return *this;
}

template <class T> bool gList<T>::operator==(const gList<T> &b) const
{
  if (length != b.length) return false;
  for (gNode *m = head, *n = b.head; m; m = m->next, n = n->next)
    if (m->data != n->data)  return false;
  return true;
}

template <class T> bool gList<T>::operator!=(const gList<T> &b) const
{
  return !(*this == b);
}

template <class T> const T &gList<T>::operator[](int num) const
{
  if (num < 1 || num > length)    throw BadIndex();

  int i;
  gNode *n;
  if( num < CurrIndex )
    for (i = CurrIndex, n = CurrNode; i > num; i--, n = n->prev);
  else
    for (i = CurrIndex, n = CurrNode; i < num; i++, n = n->next);
  // CurrIndex = i;
  // CurrNode = n;
  return n->data;
}

template <class T> T &gList<T>::operator[](int num)
{
  if (num < 1 || num > length)   throw BadIndex();
  gNode *n;
  int i;
  if( num < CurrIndex )
    for (i = CurrIndex, n = CurrNode; i > num; i--, n = n->prev);
  else
    for (i = CurrIndex, n = CurrNode; i < num; i++, n = n->next);
  CurrIndex = i;
  CurrNode = n;
  return n->data;
}

template <class T> gList<T> gList<T>::operator+(const T &e) const
{
  gList<T> result(*this);
  result.Append(e);
  return result;
}

template <class T> gList<T> &gList<T>::operator+=(const T &e)
{
  Append(e);
  return *this;
}

template <class T> gList<T> gList<T>::operator+(const gList<T> &b) const
{
  gList<T> result(*this);
  gNode *n = b.head;
  while (n)  {
    result.Append(n->data);
    n = n->next;
  }
  return result;
}

template <class T> gList<T> &gList<T>::operator+=(const gList<T> &b)
{
  gNode *n = b.head;
  
  while (n)  {
    Append(n->data);
    n = n->next;
  }
  return *this;
}

template <class T> gList<T> &gList<T>::Combine(gList<T> &b)
{
  if (this == &b)   return *this;

  if (!head)   {
    head = b.head;
    tail = b.tail;
    length = b.length;
    b.head = 0;
    b.tail = 0;
    b.length = 0;
    b.CurrIndex = 0;
    b.CurrNode = 0;
    return *this;
  }

  tail->next = b.head;
  if (b.head)  b.head->prev = tail;
  length += b.length;
  if (b.tail)  tail = b.tail;
  b.head = 0;
  b.tail = 0;
  b.length = 0;
  b.CurrIndex = 0;
  b.CurrNode = 0;
  return *this;
}

template <class T> 
gList<T> gList<T>::InteriorSegment(int first, int last) const
{
  gList<T> answer;

  for (int i = first; i <= last; i++)
    answer += (*this)[i];

  return answer;
}

template <class T> int gList<T>::Append(const T &t)
{
  return InsertAt(t, length + 1);
}

template <class T> int gList<T>::Insert(const T &t, int n)
{
  return InsertAt(t, (n < 1) ? 1 : ((n > length + 1) ? length + 1 : n));
}

template <class T> T gList<T>::Remove(int num)
{
  if (num < 1 || num > length)   throw BadIndex();
  gNode *n;
  int i;

  if( num < CurrIndex )
    for (i = CurrIndex, n = CurrNode; i > num; i--, n = n->prev);
  else
    for (i = CurrIndex, n = CurrNode; i < num; i++, n = n->next);

  if (n->prev)
    n->prev->next = n->next;
  else
    head = n->next;
  if (n->next)
    n->next->prev = n->prev;
  else
    tail = n->prev;

  length--;
  CurrIndex = i;
  CurrNode = n->next;
  if( CurrIndex > length )
  {
    CurrIndex = length;
    CurrNode = tail;
  }
  T ret = n->data;
  delete n;
  return ret;
}

template <class T> bool gList<T>::HasARedundancy()
{
  int i = 1; int j = 2;		
  while (i < Length()) {
    if ((*this)[i] == (*this)[j])
      return true;
    else 
      j++;
    if (j > Length()) { i++; j = i+1; }
  }
  return false;
}

template <class T> void gList<T>::RemoveRedundancies()
{
  int i = 1; int j = 2;		
  while (i < Length()) {
    if ((*this)[i] == (*this)[j])
      Remove(j);
    else 
      j++;
    if (j > Length()) { i++; j = i+1; }
  }
}

template <class T> int gList<T>::Find(const T &t) const
{
  if (length == 0)  return 0;
  gNode *n = head;
  for (int i = 1; n; i++, n = n->next)
    if (n->data == t)   return i;
  return 0;
}

template <class T> bool gList<T>::Contains(const T &t) const
{
  return (Find(t) != 0);
}

template <class T> int gList<T>::Length(void) const
{
  return length;
}

template <class T> void gList<T>::Flush(void)
{
  length = 0;
  gNode *n = head;
  while (n)  {
    gNode *next = n->next;
    delete n;
    n = next;
  }
  head = tail = 0;
  CurrIndex = 0;
  CurrNode = 0;
}

template <class T> void gList<T>::Dump(gOutput &f) const
{
  if (length)   {
    gNode *n = head;
    int i = 1;
    while (n)  {
      f << i << ": " << (n->data) << '\n';
      i++;
      n = n->next;
    }
  }
}

template <class T> gOutput &operator<<(gOutput &f, const gList<T> &b)
{
  b.Dump(f);   return f;
}