dynamicarray.h

用于词法分析的词法分析器

/* $Id: DynamicArray.h,v 1.3 1997/02/02 01:31:03 matt Exp $

   Expanding array similar to a Perl array.  Array automatically
   expands by multiples of 16 elements.

   Only indirect storage scheme is supported (direct storage allows no
   way to define how null values are represented).
   
   (c) 1996 Matt Phillips */

#ifndef _DYNAMIC_ARRAY_H
#define _DYNAMIC_ARRAY_H

#include <util/maxmin.h>

#include "Container.h"
#include "Data.h"

#define CHECK_NEG_INDEX(i)  CHECK (i >= 0, "negative index in array")

template <class T, class E>
class DynamicArrayImp : public Container<T>
{
public:

  typedef class DynamicArrayImpIter<T, E> Iterator;

  // create an empty array (no heap storage allocated).
  DynamicArrayImp () : arraySize (0), array (0) {}
  // create an array with initSize elements.
  DynamicArrayImp (int initSize) :
    arraySize (0), array (0) {expand (initSize);}
  // copy constructor
  DynamicArrayImp (const DynamicArrayImp<T, E> &a) :
    arraySize (0), array (0) {add (a);}

  // destruct array
  ~DynamicArrayImp () {clear ();}
   
  const char *name () const {return "DynamicArray";}

  // add item at index.  array expands if necessary, any filling
  // elements are set to null.
  T *add (T &item, int index);

  // add item to the end of the array.
  T *add (T &item) {return add (item, _nItems++);}

  // add items to the end of the array.
  T *add (const DynamicArrayImp<T, E> &items);

  // get item at index or null of item does not exist.
  T *get (int index) const;

  // remove item at index.
  void remove (int index);

  // delete all items and deallocate storage.
  void clear ();

  // as as get ().
  T *operator [] (int index) const {return get (index);}

  Iterator *makeIter () const {return new Iterator (*this);}

protected:

  enum {BlockSize = 16};

  friend class Iterator;

  // expand array to newArraySize
  void expand (int newArraySize);

  static int roundBlockSize (int size);

  int arraySize;
  E *array;
};


template <class T, class E>
void DynamicArrayImp<T, E>::clear () 
{
  if (E::isOwner ())
  {
    E *cell = array;
    int c = 0;

    while (c < _nItems)
    {
      if (cell)
	cell->destroy ();

      c++;
      cell++;
    }
  }

  delete array;
  arraySize = 0;
  _nItems = 0;
}

template <class T, class E>
T *DynamicArrayImp<T, E>::add (T &item, int index)
{
  CHECK_NEG_INDEX (index);

  if (index >= arraySize)
  {
    // new size is rounded up to nearest multiple of BlockSize
    expand (roundBlockSize (index + 1));
  }

  E *cell = array + index;

  // replace old with new.
  cell->destroy ();
  cell->set (item);

  _nItems = max (_nItems, index + 1);

  return &(cell->ref ());
}

template <class T, class E>
T *DynamicArrayImp<T, E>::add (const DynamicArrayImp<T, E> &items)
{
  if (items._nItems > arraySize - _nItems)
    expand (roundBlockSize (_nItems + items._nItems));

  if (E::isOwner ())
  {
    // make copies of all items
    E *dest = array + _nItems;
    E *src  = items.array;
    E *destEnd = dest + items._nItems;
    
    for ( ; dest < destEnd; dest++, src++)
    {
      if (src->data)
      {
	dest->data = new T (src->ref ());
      }
    }
  } else
  {
    // just brute force copy contents
    memcpy (array + _nItems, items.array, items._nItems * sizeof (E));
  }

  _nItems += items._nItems;
}

template <class T, class E>
T *DynamicArrayImp<T, E>::get (int index) const
{
  CHECK_NEG_INDEX (index);
  if (index < _nItems)
    return array [index].data;
  else
    return 0;
}

template <class T, class E>
void DynamicArrayImp<T, E>::remove (int index)
{
  CHECK_NEG_INDEX (index);
  if (index < _nItems)
    array [index].destroy ();
}

template <class T, class E>
void DynamicArrayImp<T, E>::expand (int newArraySize)
{
  E *newArray = new E [newArraySize];
  
  // copy old array to new array
  memcpy (newArray, array, arraySize * sizeof (E));
  
  // null uncopied cells
  for (int c = arraySize; c < newArraySize; c++)
    newArray [c].data = 0;
  
  delete array;
  array = newArray;
  arraySize = newArraySize;
}

template <class T, class E>
int DynamicArrayImp<T, E>::roundBlockSize (int size)
{
  int roundedSize = size;
  int modVal = roundedSize % BlockSize;  
  if (modVal != 0)
    roundedSize += BlockSize - modVal;
  return roundedSize;
}

template <class T, class E>
class DynamicArrayImpIter : public RContainerIter<T>
{
public:

  DynamicArrayImpIter (const DynamicArrayImp<T, E> &a) :
    array (a), i (a.array) {findNext ();}

  virtual T &ref () const
  {ITER_CURRENT (int (*this)); return i->ref ();}

  virtual void operator ++ (int)
  {
    ITER_BOUND (i < array.array + array._nItems);
    i++;
    findNext ();
  }

  virtual void operator -- (int)
  {
    ITER_BOUND (i > array.array);
    i--;
    findPrev ();
  }

  virtual operator int () const
  {return i >= array.array && i < array.array + array._nItems;}

  virtual void resetStart () {i = array.array;}
  virtual void resetEnd () {i = array.array + array._nItems - 1;}

protected:

  void findNext ();
  void findPrev ();

  E *i;
  const DynamicArrayImp<T, E> &array;
};

template <class T, class E>
void DynamicArrayImpIter<T, E>::findNext ()
{
  E *last = array.array + array._nItems - 1;
  
  while (i <= last && i->data == 0)
  {
    i++;
  } 
}

template <class T, class E>
void DynamicArrayImpIter<T, E>::findPrev ()
{
  while (i >= array.array && i->data == 0)
  {
    i--;
  }
}

#define TypeIDynamicArray(T)  DynamicArrayImp<T, ICell<T, 0> >
#define TypeIODynamicArray(T) DynamicArrayImp<T, ICell<T, 1> >

#endif