// $Id: arraylist.h,v 1.1.1.1 2000/11/02 08:47:16 fritzi Exp $

// This file is part of the DEAL Library
// DEAL is Copyright(1995) by
// Roland Becker, Guido Kanschat, Franz-Theo Suttmeier


#ifndef __arraylist_h
#define __arraylist_h

#ifndef __pool_h
#include <deal/pool.h>
#endif
#ifndef __errors_h
#include <deal/errors.h>
#endif

template<class T, int BS> class ArrayList;

/*
CLASS
   ArrayNode
   Linked memory block
KEYWORDS
   Container
OVERVIEW
   The class template ArrayNode<T,BS> builds a linkable block
   containing memory for BS objects of type T to be used by ArrayList<T,BS>.
   Elements of ArrayNode should only be accessed via ArrayList, therefore
   no public member functions are defined.

   Since an array of T's is member of ArrayNode, T must have a standard constructor.
   */
template<class T, int BS>
class ArrayNode
{
  friend class ArrayList<T,BS>;

  static Pool pool;
  int start;
  T data[BS];
  ArrayNode* next;

  ArrayNode(ArrayNode* n = 0)
  {
    next = n;
    if (next) start = next->start+BS;
    else start = 0;
  };

public:
  void* operator new(size_t sz) { return pool.alloc(sz); }
  void operator delete(void*p) { pool.free(p,sizeof(ArrayNode<T,BS>)); }
};

/*
CLASS
   ArrayList
   Combination of array and list structure
KEYWORDS
   Container
OVERVIEW
   ArrayList<T,BS> implements a dynamic array designed for small data
   types T. The overhead for list structures is only one pointer for BS
   elements.
   */
template<class T, int BS>
class ArrayList
{
  typedef ArrayNode<T,BS> Node;

  Node* first;

  void expand()
  {
    first = new Node(first);
  }
public:
  //////////
  //
  // Constructor creating an empty array of length 0.
  // This array uses only memory for one pointer and grows on
  // access to its elements
  //
  ArrayList() : first(0) {}
  //////////
  //
  // Destructor.
  //
  ~ArrayList()
  {
    Node* p;
    for (p=first; p ;)
    {
      Node* n=p->next;
      delete p;
      p=n;
    }
  }

  //////////
  //
  // This r/w access function automatically expands the array to be able to hold
  // at least i+1 items. It returns a reference to the i'th item.
  //
  T& change(int i)
  {
    Node* p;
    THROW2(i<0, IntError(IntError::Range,i));
    if (!first) first = new Node;
    while (i>=first->start+BS) expand();
    for (p=first; i<p->start; p=p->next);
    return p->data[i-p->start];
  }

  //////////
  //
  // Read access to a data item. This function does not expand the array and
  // therefore can only read existing items.
  //
  T operator() (int i) const
  {
    Node* p;
    THROW2(!first, IntError(IntError::Range,i,"()", "ArrayList"));
    THROW2((i<0) || (i>=first->start+BS), IntError(IntError::Range,i));
    for (p=first; i<p->start; p=p->next);
    return p->data[i-p->start];
  }
};    
#endif