/****************************************************************************/
/*                                                                          */
/*  Copyright (C) 1994-1996                                                 */
/*  Jeremy Levitt                                                           */
/*  All Rights Reserved                                                     */
/*                                                                          */
/****************************************************************************/

#ifndef _chunklist_h_
#define _chunklist_h_

#include <assert.h>
#include <iostream.h>


const int CHUNK_SIZE = 10;

/****************************************************************************/
/*  class Chunk                                                             */
/****************************************************************************/
template <class Element> 
class Chunk {
private:
  Element _element[CHUNK_SIZE];
  Chunk *_next;
  int _numElems;
  
public:
  Chunk(Chunk &chunk);
  Chunk() : _next(NULL), _numElems(0) {}
  int NumElems() const { return(_numElems); }
  int Append(Element element);
  void Delete(int index);
  void SetNext(Chunk* next) { _next = next; }
  Element& operator[] (int index) { return(_element[index]); }
  Chunk*& Next() { return(_next); }
};


/****************************************************************************/
/*  class Chunk_List                                                        */
/****************************************************************************/
template <class Element> 
class Chunk_List {
private:
  int _numElems;
  Chunk<Element> *_firstChunk;
  Chunk<Element> *_lastChunk;

  void Copy(const Chunk_List& rhs);
  void DeleteChunks();
  Chunk<Element>* FindChunkContainingElem(int &index) const;
  void Init_Chunk_List();

public:
  Chunk_List() { Init_Chunk_List(); }
  Chunk_List(const Chunk_List &chunk_List) { Copy(chunk_List); }
  Chunk_List(const Chunk_List *chunk_List) { Copy(*chunk_List); }
  Chunk_List(Element elem) { Init_Chunk_List(); Append(elem); }
  Chunk_List(Element elem1, Element elem2) 
    { Init_Chunk_List(); Append(elem1); Append(elem2); }
  ~Chunk_List() { DeleteChunks(); }
  void Destroy() { DeleteChunks(); Init_Chunk_List(); }
  int NumElems() const { return(_numElems); }
  int Append(Element element);
  int Append(Chunk_List &elements);
  void Delete(int index);
  Element& operator[] (int index) const;
  Chunk_List& operator= (const Chunk_List<Element> &rhs);
  Element* CopyToArray();
};


/****************************************************************************/
/*  Chunk_List::Init_Chunk_List()                                           */
/****************************************************************************/
template <class Element>
void Chunk_List<Element>::Init_Chunk_List()
{
  _numElems = 0;
  _firstChunk = _lastChunk = new Chunk<Element>();
}


/****************************************************************************/
/*  Chunk_List::operator= (Chunk_List<Element> &rhs)                        */
/****************************************************************************/
template <class Element>
Chunk_List<Element>& Chunk_List<Element>::operator= 
(const Chunk_List<Element> &rhs)
{
  if (this != &rhs) {
    DeleteChunks();
    Copy(rhs);
  }

  return(*this);
}


/****************************************************************************/
/*  Chunk_List::operator= (Chunk_List<Element> &rhs)                        */
/****************************************************************************/
template <class Element>
Element* Chunk_List<Element>::CopyToArray()
{
  Element *copy = new Element[NumElems()];

  for (int i=0; i<NumElems(); i++)
    copy[i]= (*this)[i];

  return copy;
}


/****************************************************************************/
/*  Chunk_List::Copy(Chunk_List rhs)                                        */
/****************************************************************************/
template <class Element>
void Chunk_List<Element>::Copy(const Chunk_List<Element> &rhs)
{
  assert(rhs._firstChunk != NULL);

  Chunk<Element> *rhsTemp = rhs._firstChunk, **lhsTemp = &_firstChunk;
  for(; rhsTemp != NULL; rhsTemp = rhsTemp->Next()) {
    _lastChunk = *lhsTemp = new Chunk<Element>(*rhsTemp);
    lhsTemp = &(*lhsTemp)->Next();
  }

  _numElems = rhs._numElems;
}


/****************************************************************************/
/*  Chunk_List::operator[]                                                  */
/****************************************************************************/
template <class Element>
Element& Chunk_List<Element>::operator[] (int index) const
{
  // Check that index is valid.
  assert(index>=0 && index<NumElems());

  Chunk<Element> *theChunk = FindChunkContainingElem(index);
  return((*theChunk)[index]);
}


/****************************************************************************/
/*  Chunk_List::FindChunkContainingElem(int &index)                         */
/****************************************************************************/
template <class Element>
inline Chunk<Element>* Chunk_List<Element>::FindChunkContainingElem(int &index) const
{
  // Check that index is valid.
  assert((index>=0) && (index<NumElems()));

  Chunk<Element> *temp = _firstChunk;
  while (index>=temp->NumElems()) {
	index-=temp->NumElems();
	temp=temp->Next();
  }

  return(temp);
}


/****************************************************************************/
/*  Chunk::Append(Element element)                                          */
/****************************************************************************/
template <class Element>
int Chunk<Element>::Append(Element element)
{
  // Is there any space to add another element to the chunk?
  if (_numElems == CHUNK_SIZE) return(0);

  _element[_numElems] = element;
  _numElems++;
  return(1);
}


/****************************************************************************/
/*  Chunk_List::Append(Element element)                                     */
/****************************************************************************/
template <class Element>
int Chunk_List<Element>::Append(Element element)
{
  // Is there enough space in the lastChunk for appending?
  if (!_lastChunk->Append(element)) {

    //No, so link a new chunk into the list and append the element to it.
    Chunk<Element> *newLastChunk = new Chunk<Element>();
    _lastChunk->SetNext(newLastChunk);
    _lastChunk = newLastChunk;
    _lastChunk->Append(element);
  }

  return _numElems++;
}


/****************************************************************************/
/*  Chunk_List::Append(Chunk_List &elements)                                */
/****************************************************************************/
template <class Element>
int Chunk_List<Element>::Append(Chunk_List &elements)
{
  for (int i=0; i<elements.NumElems(); i++)
    Append(elements[i]);

  return _numElems;
}


/****************************************************************************/
/*  Chunk_List::Delete(int index)                                           */
/****************************************************************************/
template <class Element>
void Chunk_List<Element>::Delete(int index)
{
  Chunk<Element> *theChunk = FindChunkContainingElem(index);
  theChunk->Delete(index);
  _numElems--;
}


/****************************************************************************/
/*  Chunk::Chunk(Chunk &)                                                   */
/****************************************************************************/
template <class Element>
Chunk<Element>::Chunk(Chunk<Element> &chunk)
  : _next(NULL), _numElems(chunk._numElems)
{
  for (int i=0; i<CHUNK_SIZE; i++)
    _element[i] = chunk._element[i];
}


/****************************************************************************/
/*  Chunk::Delete(int index)                                                */
/****************************************************************************/
template <class Element>
void Chunk<Element>::Delete(int index)
{
  for (int i=index; i<_numElems-1; i++)
	_element[i] = _element[i+1];

  _numElems--;
}


/****************************************************************************/
/*  Chunk_List::DeleteChunks()                                               */
/****************************************************************************/
template <class Element>
void Chunk_List<Element>::DeleteChunks()
{
  Chunk<Element> *temp=_firstChunk, *next=_firstChunk->Next();

  for(; temp != NULL; temp = next) {
    next = temp->Next();
    delete temp;
  }

  _firstChunk = _lastChunk = NULL;
}


/****************************************************************************/
/*  operator<<                                                              */
/****************************************************************************/
template <class Element>
ostream& operator<<(ostream& os, const Chunk_List<Element>& list)
{
  os << "***chunk_list contents***\n";
  for (int i=0; i<list.NumElems(); i++)
    os << "element[" << i << "]=" << Chunk_List<Element>(list)[i] << '\n';
  return os;
}

#endif /* _chunklist_h_ */