legoPArr.H

Go to the documentation of this file.

/**********************************************************************
*  File:            legoPArr.H
*
*  Designer:        Willie Glover
*
*  Description:     Header file for the LEGO array class of pointers.
*                   This implementation uses templates.
*
*                   The legoPArr class is used to construct a set of
*                   pointers to legoOp's and legoRegion's.
*
* 3/18/97 WAH:      Changed Search to return index value.
* 4/9/97 WAH:       Added IsOwner method.
* 1/6/98 WAH:       Removed annoying PRECONDITION/CHECK macros.
* 2/18/98 WAH:      Made destructor virtual.
* 3/20/98 WAH:      Added forward declarations of legoPSet, legoPArrItr.
**********************************************************************/

#ifndef LEGOPARR_H
#define LEGOPARR_H

//#ifndef LEGO_HEADER
//#include <lego.H>
//#endif

#include "globals.H"
#include "legoErr.H"

//#ifndef LEGOMORE_H
//#include "legoMore.H"
//#endif

#ifndef __STRING_H
#include <string.h>
#endif

#ifndef __STDLIB_H
#include <stdlib.h>
#endif

#ifndef MAX_UNSIGNED
#define MAX_UNSIGNED ((unsigned) -1)
#endif

template <class T> class legoPSet;
template <class T> class legoPArrItr;

/*---------------------- Class Definition -----------------------*/

//----------------------------------------------------------------
//
// The following class maintains an array of T*'s in contiguous
// memory.  The size of the array will be dynamically adjusted
// depending on how many items are stored in it.  The class T must
// have a valid default constructor and copy semantics, as well as
// valid operator == semantics.
//
// For the sake of efficiency, the array size will be initialized to
// 4 and whenever resizing is performed, the size will increase by
// 4.  This will reduce the number of calls to "ResizeArray" when
// items are added to the array.  The cost in unused storage will
// be 12 or fewer bytes for each active array.
//
//----------------------------------------------------------------

template <class T> class legoPArr {

protected:

   T           *data;               // Pointer to the array of data
   unsigned    _size,_delta;        // Size and increment values
   unsigned    count;               // Number of items in array
   int         shouldDelete;        // Flags if elements should be deleted

      // Resize the array to a new size
   void Expand(unsigned newSize);
   void Shrink();

      // Member to compute the actual size
   unsigned ComputeSize(unsigned sz)
   {
     if ((_delta != 0) && (sz % _delta != 0))
       return (((sz + _delta) / _delta) * _delta);
     else
       return sz;
   };

public:
   friend legoPSet<T>;

      // Default constructor
   legoPArr();

      // Constructor
   legoPArr(unsigned size,unsigned delta = 4);

      // Destructor: caller is responsible for destroying T data
   virtual ~legoPArr()
   {
     //     fprintf(stderr,"Deleting LEGOPARR %p\n",this);
     PEmpty();
   }

      // Copy constructors
   legoPArr(const legoPArr<T>& a,unsigned delta = LARGE_INTVAL);
   const legoPArr<T>& operator = (const legoPArr<T>& a);

      // Comparison methods for arrays
   int  operator == (const legoPArr<T>& a);
   int  operator != (const legoPArr<T>& a)
   { return !(*this == a); };

      // Indexing operators
   T& operator [] (unsigned index)
   {
     if (data == NULL)
       LegoFatal ("legoPArr operator []", "Container %x is uninitialized.",
                  this);
     if (index >= count)
       LegoFatal ("legoPArr operator []", "Index given is %d, but container "
                  "%x only has %d items.", index, this, count);
     //     PRECONDITION(data != NULL && index < count);
     return data[index];
   };

   const T& operator [] (unsigned index) const
   {
     if (data == NULL)
       LegoFatal ("legoPArr operator []", "Container %x is uninitialized.",
                  this);
     if (index < count)
       LegoFatal ("legoPArr operator []", "Index given is %d, but container "
                  "%x only has %d items.", index, this, count);
     // PRECONDITION(data != NULL && index < count);
     return data[index];
   };

      // Methods to add elements to the array
   unsigned AddItem(T item);
   void Insert(T item, unsigned index, unsigned count = 1);

      // Method to replace an element in the array
   void Replace(T item, unsigned index);

      // Method to destroy an element in the array
   void DestroyItem(unsigned index);

      // Method to search for an element in the array
   virtual  unsigned Search(T item, unsigned first, unsigned last,
                            int direction = +1) const;
   unsigned Search(T item, int direction = +1) const
   {
      if ( count == 0 ) { return MAX_UNSIGNED; }
      return Search(item, 0, count-1, direction); 
   };

      // Update the number of elements in the array (empties it)
   void SetCount(unsigned newCount);

      // Return the number of items in the array
   unsigned GetCount() const      { return count; };

      // Returns true if the array is empty
   int IsEmpty() const     { return count == 0; };

      // Returns true if the array is full
   int IsFull() const
   { return (_delta == 0) && (count == _size); };

      // Return the size/delta for the array
   unsigned GetSize() const  { return _size; };
   unsigned GetDelta() const { return _delta; };

      // Modify the delta value for the array
   void SetDelta(unsigned delta);

      // Resize the array to a new size (array is emptied of data)
   void SetSize(unsigned newSize);

      // Empties the array of all data
   void Empty();

      // Empties the array of all data with possible data destruction
   void PEmpty();

      // Returns true if the array is valid
   int  Valid() const { return (data != NULL); };

      // Returns true if the array owns its own data.
   int IsOwner() const { return shouldDelete; }

private:

   friend  class legoPArrItr<T>;
};

//-------------------------------------------------------------------
//
// The following classes are used to iterate through the elements
// in the array.  Generally you can simply do normal array indexing
// rather than using an iterator.
//
//-------------------------------------------------------------------

template <class T> class legoPArrItr {

protected:

        const legoPArr<T>        *a;
        unsigned                        cursor,lower,upper;

public:

      // Default constructor
   legoPArrItr()
   { a = NULL; cursor = lower = upper = 0; };

      // Constructor given an array reference
   legoPArrItr(const legoPArr<T>& arr)
   { a = &arr; Restart(0,arr.GetCount()); };

      // Constructor given an array reference and range
   legoPArrItr(const legoPArr<T>& arr, unsigned start, unsigned stop)
   { a = &arr; Restart(start,stop); };

      // Initialize an array iterator from an array
   const legoPArrItr<T>& operator = (const legoPArr<T>& arr)
   { a = &arr; Restart(0,arr.GetCount());
     return *this;
   };

      // Initialize an array iterator from another iterator
   const legoPArrItr<T>& operator = (const legoPArrItr<T>& i)
   { a = i.a; Restart(i.lower,i.upper);
     return *this;
   };

      // Overloaded cast to an integer
   operator int () { return cursor < upper; };

      // Convert the iterator to the corresponding node
   T node()
   {
     if (cursor >= upper)
       LegoFatal ("LegoPArrItr::node", "Cursor out of range.");
     //     PRECONDITION(cursor < upper);
     return (*a)[cursor];
   };

      // Pre-increment operator
   T operator ++ ()
   { if (++cursor < upper) return (*a)[cursor];
     else                  return (*a)[upper-1];
   };

      // Post-increment operator
   T operator ++ (int)
   { if (cursor < upper)   return (*a)[cursor++];
     else                  return (*a)[upper-1];
   };

      // Method to restart the array iterator
   void Restart()  { Restart(lower,upper); };

      // Method to restart with a new range
   void Restart(unsigned start,unsigned stop)
   {  cursor = lower = start; upper = stop; };
};

/*---------------------------- Implementation -----------------------------*/

// 1/6/98 WAH: I tried moving all of these into legoPArr.C, but the compiler
//             doesn't seem to generate the actual functions correctly
//             (in particular, PEmpty and Search). If this is a compiler
//             bug, and someone fixes it, these should be shoved off ASAP.

template <class T> unsigned legoPArr<T>::AddItem(T item)
/*-----------------------------------------------------------------------
* Function:             legoPArr<T>::AddItem
* Parameters:   item    - Item to add to the array
* Description:  Resizes the array if the count exceeds the size of the
*               array, and copies the item into the last position.
* Return:       1 if successful, 0 if unsuccessful
------------------------------------------------------------------------*/
{
    //      fprintf(stderr,"In legoPArr::AddItem(T)\n");
        if (!Valid())
          LegoFatal ("legoPArr::AddItem", "Container %x is uninitialized.",
                     this);
        //      CHECK(Valid());
        if (count == _size) Expand(count+1);
        if (count >= _size)
          LegoFatal ("legoPArr::AddItem", "Expansion of container %x "
                     "failed!", this);
        //      CHECK(count < _size);
        if (Valid()) {
           data[count++] = item;
           return 1;
        }
        else { return 0; }
}

template <class T> void legoPArr<T>::SetCount(unsigned newCount)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::SetCount
* Parameters:   newCount        - New count for the array
* Description:  Sets the count value for the array, expanding the size
*               if necessary. The array will be filled with the default
*               value.
------------------------------------------------------------------------*/
{
        SetSize(newCount);
        count = newCount;
}

template <class T>
void legoPArr<T>::Replace(T item, unsigned index)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::Replace
* Parameters:   item    - Item to replace in the array
*               index   - Index of the item in the array to replace
* Description:  Replaces the item in the array with the new item. The index
*               MUST fall within the current bounds of the array.
------------------------------------------------------------------------*/
{
        if (!Valid())
          LegoFatal ("legoPArr::AddItem", "Container %x is uninitialized.",
                     this);
        //      CHECK(Valid());
        if (index >= count)
          LegoFatal ("legoPArr::Replace", "Index given is %d, but container "
                  "%x only has %d items.", index, this, count);
        //      PRECONDITION(index < count);
        if (shouldDelete)
                delete data[index];
        data[index] = item;
}

template <class T> legoPArr<T>::legoPArr()
        : _size(4), _delta(4), count(0)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::legoPArr
* Description:  Default constructor for the array template. This creates
*               an empty array of size 4, with an increment of 4.
------------------------------------------------------------------------*/
{
  //  fprintf(stderr,"Creating LEGOPARR %p\n",this);
        shouldDelete = true;
        data = new T[_size];
        //      CHECK(data != NULL);
}

template <class T> legoPArr<T>::legoPArr(unsigned size,unsigned delta)
        : _delta(delta), count(0)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::legoPArr
* Parameters:   size    - Initial size of the array
*               delta   - Initial increment value for the array
* Description:  Constructor for the array template, given the size of the
*               array to create, and the expansion ratio. If the increment
*               is zero, the array is of a fixed size and will not be
*               expanded.
*               The array is initially empty containing no valid data.
------------------------------------------------------------------------*/
{
  //  fprintf(stderr,"Creating LEGOPARR %p\n",this);
        shouldDelete = true;
        _size = ComputeSize(size);
        data = new T[_size];
        //      CHECK(data != NULL);
}

template <class T> legoPArr<T>::legoPArr(const legoPArr<T>& a,
                                         unsigned delta = LARGE_INTVAL)
        : count(a.count)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::legoPArr
* Parameters:   a       - legoPArr to copy
* Description:  Copy constructor for arrays. Allocate space for new array,
*               and copy each item individually using memcpy.
------------------------------------------------------------------------*/
{
  //  fprintf(stderr,"Creating LEGOPARR %p\n",this);
        shouldDelete = false;
        if (!(a.Valid()))
          LegoFatal ("legoPArr::legoPArr [copy constructor]",
                     "Original container %x is uninitialized.", a);
        //      CHECK(a.Valid());
        _delta = (delta == LARGE_INTVAL) ? a._delta : delta;
        _size = ComputeSize(a._size);
        data = new T[_size];
        if (Valid())
                memcpy(data,a.data,count * sizeof(T));
}

template <class T> const legoPArr<T>& legoPArr<T>::operator = (const legoPArr<T>& a)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::operator =
* Parameters:   a       - Array to copy
* Description:  Assignment operator for array's. Allocates space for the
*               new array and copies the data with a fast memcpy call.
*               Since only pointers are copied,  the original owns data.
------------------------------------------------------------------------*/
{
   // Check to make sure both instances are valid and that the assignment
   //    is not to itself.
  //  fprintf(stderr,"Assigning LEGOPARR %p\n",this);
        if (!Valid())
          LegoFatal ("LegoPArr operator =", "Container %x (dest.) is "
                     "uninitialized.", this);
        if (!(a.Valid()))
          LegoFatal ("LegoPArr operator =", "Source container is "
                     "uninitialized.");
        //      CHECK(Valid() && a.Valid());
        if (data != a.data) {
                PEmpty();
                shouldDelete = false;
                _size = a._size;
                _delta = a._delta;
                count = a.count;
                delete [] data;
                data = new T[_size];
                if (Valid())
                        memcpy(data,a.data,count * sizeof(T));
                }
        return *this;
}

template <class T> int legoPArr<T>::operator == (const legoPArr<T>& a)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::operator ==
* Parameters:   a       - Array to compare to this array
* Returns:              True if all array elements are equal, false if not.
*                       Returns false unless items in same order.
*                       True = 1, False = 0
------------------------------------------------------------------------*/
{
        if (!Valid())
          LegoFatal ("LegoPArr operator ==", "Container %x (first) is "
                     "uninitialized.", this);
        if (!(a.Valid()))
          LegoFatal ("LegoPArr operator ==", "Second container is "
                     "uninitialized.");
        //      CHECK(Valid() && a.Valid());
        if (count != a.count)
                return 0;
        T *p = data, *pa = a.data;
        for (unsigned i = 0; i < count; i++)
                if (!(*p++ == *pa++))
                        return 0;
        return 1;
}

template <class T> void legoPArr<T>::Insert(T item,
                                            unsigned index, unsigned aCount)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::Insert
* Parameters:   item    - Item to insert into the array
*               index   - Index to insert the item in front of
*               aCount  - Count of elements to insert
* Description:  Inserts the specified item into the array at the index'th
*               position. All the elements from [index,count] are moved
*               up one position to make room. The index must be in the
*               range [0,count], and if the value is count it is simply
*               tacked onto the end of the array.
------------------------------------------------------------------------*/
{
   if (!Valid())
     LegoFatal ("legoPArr::Insert", "Container %x is uninitialized.",
                this);
  //   CHECK(Valid());

   if (index > count)
     LegoFatal ("legoPArr::Insert", "Index given is %d, but container "
                "%x only has %d items.", index, this, count);
   //   PRECONDITION(index <= count);
   if (count+aCount > _size)       Expand(count+aCount);

   // Move the items up one position in the array to make room, and insert

   if (Valid()) {
      memmove(&data[index+aCount],&data[index],(count-index) * sizeof(T));
      for (unsigned i = 0; i < aCount; i++)
         data[index+i] = item;
      count += aCount;
   }
}

template <class T> unsigned legoPArr<T>::Search(T item,
                   unsigned first, unsigned last, int direction) const
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::Search
* Parameters:   item      - Item to search for
*               first     - Index of first element to search
*               last      - Index of last element to search
*               direction - End to search from (+1 = start, -1 = end)
* Returns:      index of item if it is in the array, MAX_UNSIGNED if not found
* Description:  Performs a simple linear search for the item from the
*               specified end of the array. Compares pointers.
* DANGER DANGER! If the set contains 2^32 items, a search for the last
* item will return not found. Look out buddy.
------------------------------------------------------------------------*/
{
   if (!Valid())
     LegoFatal ("legoPArr::Search", "Container %x is uninitialized.",
                this);
   //   CHECK(Valid());

   if (count <= first || count <= last)
     LegoFatal ("legoPArr::Search", "Search indices given are %d to %d, but "
                "container %x only has %d items.", first, last, this, count);
   //   PRECONDITION((first < count) && (last < count));

   if (direction != -1 && direction != +1)
     {
       LegoNonFatal ("legoPArr::Search", "Direction specified was %d, should "
                     "be either +1 or -1. Defaulting to forward search.",
                     direction);
       direction = +1;
     }
   //   PRECONDITION(direction == +1 || direction == -1);

   if (direction == +1) {
      T *p = &data[first];
      for (unsigned i = first; i <= last; i++) {
//          fprintf(stderr,"item=%p count=%d\n",item,count);
          if (*(p++) == item)  return i;
      }
   }
   else {
      T *p = &data[last];
      for (unsigned i = last; i >= first; i--)
         { if (*(p--) == item) return i; }
   }
   //   fprintf(stderr,"In legoPArr<T>::Search(,,,) return 0\n");
   return MAX_UNSIGNED;
}
/*------------------------------------------------------------------------
 * The following method can be modified to search for a particular
 * field within the item instance of T.  It derefernces the T* so that
 * the data rather than the pointer is compared.
 -----------------------------------------------------------------------*/
//{
//        CHECK(Valid());
//        PRECONDITION(first < count && last < count);
//        PRECONDITION(direction == +1 || direction == -1);
//        if (direction == +1) { T **p = &data[first];
//                               for (unsigned i = first; i <= last; i++)
//                                   if (*(*p++) == *item) return 1; }
//        else {                 T **p = &data[last];
//                               for (unsigned i = last; i >= first; i--)
//                                   if (*(*p--) == *item) return 1; }
//        return 0;
//}

template <class T> void legoPArr<T>::Expand(unsigned newSize)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::Expand
* Parameters:   newSize - New size of the array
* Description:  Expands the array to be a multiple of 'delta' that includes
*               the specified newSize for the array. The array data is
*               re-allocated and copied to the resized array.
*
*               Note that 'count' must contain the actual number of elements
*               in the array.
------------------------------------------------------------------------*/
{
   if (!Valid())
     LegoFatal ("legoPArr::Expand", "Container %x is uninitialized.",
                this);
   //   CHECK(Valid());

   if (_delta == 0)  // not resizeable
     return;
   //   PRECONDITION(_delta != 0);
   if (newSize < count)
     {
       LegoNonFatal ("legoPArr::Expand", "New size %d is smaller than "
                     "current count %d of container %x. Skipping expansion.",
                     newSize, count, this);
       return;
     }
   //   PRECONDITION(newSize >= count);

   T *temp = new T[_size = ComputeSize(newSize)];

      // Copy the data from old array to the new array.

   if (temp != NULL)
     {
       memcpy(temp,data,count * sizeof(T));
       delete[] data;
     } // end if
   else
     {
       LegoNonFatal ("legoPArr::Expand", "Expansion failed.");
       temp = data;
     } // end else
   data = temp;
}

template <class T> void legoPArr<T>::Shrink()
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::Shrink
* Description:  Shrinks the allocated space for the array, if the
*               threshold point has been reached.
------------------------------------------------------------------------*/
{
   if (!Valid())
     LegoFatal ("legoPArr::Shrink", "Container %x is uninitialized.",
                this);
   //   CHECK(Valid());

   if (_delta == 0)                // Array is not resizeable when _delta == 0
           return;

   // Only shrink the array when the amount of free space gets smaller
   // than half of the delta value, and it is at least delta in size

   if ((_size - count) > (_delta + _delta/2) && (_size > _delta)) {
      T *temp = new T[_size = ComputeSize(_size - _delta)];
      if (temp != NULL)
        {
          memcpy(temp, data, count * sizeof(T));
          delete [] data;
        } // end if
      else
        {
          LegoNonFatal("legoPArr::Shrink", "Shrinking failed.");
          temp = data;
        } // end else
      data = temp;
   } // end if
}

template <class T> void legoPArr<T>::SetDelta(unsigned delta)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::SetDelta
* Parameters:   delta   - New delta value for the array
* Description:  Sets the delta value for the array, expanding or
*               shrinking the array as need be.
------------------------------------------------------------------------*/
{
        if (delta >= _delta) {
                _delta = delta;
                Expand(_size);
                }
        else {
                _delta = delta;
                Shrink();
                }
}

template <class T> void legoPArr<T>::SetSize(unsigned newSize)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::SetSize
* Parameters:   newSize - New size for the array
* Description:  Resizes the array to the new size. If the array is non-
*               resizeable, we bomb out. Note that the array will be empty
*               after this operation.
------------------------------------------------------------------------*/
{
  if (_delta == 0) return;  // not resizeable
  //    PRECONDITION(_delta != 0);
        Empty();
        Expand(newSize);
}

template <class T> void legoPArr<T>::Empty()
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::Empty
* Description:  Empties the array of all elements.
------------------------------------------------------------------------*/
{
        count = 0;
        Shrink();
}

template <class T> void legoPArr<T>::PEmpty()
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::PEmpty
* Description:  Destroys the array elements and their data if
*               shouldDelete is true (default).
-------------------------------------------------------------------------*/
{
        if (shouldDelete) {
                for (unsigned i = 0; i < count; i++)
                        delete data[i];
                }
        Empty();
}

template <class T> void legoPArr<T>::DestroyItem(unsigned index)
/*------------------------------------------------------------------------
* Function:             legoPArr<T>::DestroyItem
* Parameters:   index   - Index of element to remove
* Description:  Removes an indexed element from the array, by copying all
*               the data down one position. The index must be in the
*               range [0,count). If shouldDelete is true, the element is
*               deleted, otherwise just the ptr is removed.
------------------------------------------------------------------------*/
{
        if (!Valid())
          LegoFatal ("legoPArr::DestroyItem", "Container %x is uninitialized.",
                     this);
        //      CHECK(Valid());
        if (index >= count)
          LegoFatal ("legoPArr::DestroyItem", "Index given is %d, but "
                     "container %x only has %d items.", index, this, count);
        //      PRECONDITION(index < count);

        // Move the items down one position, and shrink the allocated memory

        if (shouldDelete)
                delete data[index];
        count--;
        memmove(&data[index],&data[index+1],(count-index) * sizeof(T));
        Shrink();
}

#endif  // LEGOPARR_H

---