/**********************************************************************
// @@@ START COPYRIGHT @@@
//
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.
//
// @@@ END COPYRIGHT @@@
**********************************************************************/
/* -*-C++-*-
**************************************************************************
*
* File:         Collections.C
* Description:  Implementation for Collection type templates
* Created:      4/27/94
* Language:     C++
*
*
*
**************************************************************************
*/
 
// -----------------------------------------------------------------------
// functions for the NACollection<T> template
// -----------------------------------------------------------------------
#include "Platform.h"

  #include "Collections.h"


template <class T> NACollection<T>::~NACollection()
{
  deallocate();
}

// For HSC, define these methods as inline methods in the Collections.h header file.

template <class T>
void NACollection<T>::copy(const NACollection<T> &other) 
{
  // allocate the arrays
  // heap_       = other.heap_; //!!!do not change the value of a collection's heap_!!!
  allocate(other.maxLength_);
  usedLength_ = other.usedLength_;
  entries_    = other.entries_;
  
  // copy the entries
  for (CollIndex i = FIRST_COLL_INDEX; i < usedLength_; i++)
    {
      arr_[i] = other.arr_[i];
      usages_[i]  = other.usages_[i];
    }
}


template <class T>
void NACollection<T>::insert(CollIndex posToInsert,
			     const T   &newElement,
			     CollIndex newUsage)
{
  // is a valid position and usage given?
  assert((posToInsert < MAX_COLL_INDEX) AND
	 (newUsage    != UNUSED_COLL_ENTRY));
  
  // do we need to increase the size?
  if (posToInsert >= maxLength_)
    resize(posToInsert + 1);
  
  // is the new position in the unused portion?
  if (posToInsert >= usedLength_)
    {
      // extend the used portion by filling in the usages_
      // entries with UNUSED_COLL_ENTRY values
      for (CollIndex i = usedLength_; i <= posToInsert; i++)
	{
	  usages_[i] = UNUSED_COLL_ENTRY;
	}
      usedLength_ = posToInsert + 1;
    }
  
  // overwrite or insert?
  if (usages_[posToInsert] == UNUSED_COLL_ENTRY)
    entries_++;
  
  // ok, now we're ready to insert the new element
  usages_[posToInsert]  = newUsage;
  arr_[posToInsert] = newElement;
  
  return;
}

template <class T>
CollIndex NACollection<T>::resize(CollIndex newSize)
{
  if (newSize == maxLength_ OR
      newSize < usedLength_)
    // no need to resize or impossible to resize
    return maxLength_;
  else
    {
      
      // increment the size in larger chunks to avoid
      // many expensive resize calls
      if (newSize > maxLength_ AND
	  newSize/3 < (maxLength_+2)/2)
	{
	  newSize = 3 * (maxLength_+2)/2;
	}
  
      // shouldn't even come close to this
      assert (newSize < MAX_COLL_INDEX);

      // use a temp collection with the new size
      NACollection<T> newOne(heap_,newSize);
    
      assert(newSize >= usedLength_);

      for (CollIndex i = FIRST_COLL_INDEX; i < usedLength_; i++)
	{
	  newOne.usages_[i] = usages_[i];
	  if (usages_[i] != UNUSED_COLL_ENTRY)
	    {
	      newOne.arr_[i] = arr_[i];
	    }
	}
      
      // now just deallocate the old arrays and take the new
      // arrays and maxLength_
      deallocate();
      usages_        = newOne.usages_;
      arr_           = newOne.arr_;
      maxLength_     = newOne.maxLength_;
      
      // make sure the destructor of newOne won't mess things up
      newOne.usages_     = NULL;
      newOne.arr_        = NULL;
      newOne.usedLength_ = 0;
      newOne.maxLength_  = 0;
      
      return maxLength_;
    }
}

#ifdef __GNUC__
#  if __GNUC__ * 100 + __GNUC_MINOR__ >= 404
     // push_options added in 4.4
#pragma GCC push_options
     // GCC prior to 4.4 did not complain about this
     // need to ignore uninitialized for this statement:
     //   T temp;
#    pragma GCC diagnostic ignored "-Wuninitialized"
#  if __GNUC__ * 100 + __GNUC_MINOR__ >= 408
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#  endif
#  endif
#endif
template <class T> void NACollection<T>::allocate(CollIndex initLen)
{
  // NOTE: this assumes that the heap_ data member has been set.
  // No other data members need to be set before calling this.
  assert(initLen < MAX_COLL_INDEX);
 
  maxLength_  = initLen;
  usedLength_ = 0;
  entries_    = 0;
  if (maxLength_ > 0)
    {
      // Since new[] and new are different operators, the following
      // can not be combined, even that in new(size_t, NAMemory*)
      // used the ::operator new if NAMemory* is 0.
      if ( heap_ == NABasicObject::systemHeapPtr() )
	{
	  arr_ = new T[maxLength_];
	  usages_ = new CollIndex[maxLength_];
	}
      else
	{	
	  // The method for dynamic allocation should match the one in 
	  // deallocate. When the compiler supports the feature to overload
	  // new[] and delete[], the following two lines should be used
	  // instead.
	  //arr_ = new(heap_) T[maxLength_];
	  //usages_ = new(heap_) CollIndex[maxLength_];

	  arr_ = (T *)heap_->allocateMemory(sizeof(T) * ((size_t) maxLength_));
	  usages_ = (CollIndex *) heap_->allocateMemory(
               sizeof(CollIndex) * ((size_t) maxLength_));

          // To finish up, we copy uninitialized objects of type T into
          // the newly-alloc'd space, so vtbl-pointers get set properly.
          // (This is not always necessary, but it's a good idea in
          // general!)
          T temp; 
          for ( CollIndex i = 0 ; i < maxLength_ ; i++ )
            memcpy ((void*)&arr_[i], (void*)&temp, sizeof(T)) ;
        }
    }
  else
    {
      arr_    = NULL;
      usages_ = NULL;
    }
}
#ifdef __GNUC__
#  if __GNUC__ * 100 + __GNUC_MINOR__ >= 404
     // pop_options added in 4.4
#    pragma GCC pop_options
#  endif
#endif


template <class T> void NACollection<T>::clearFrom( CollIndex entry )
{
  assert( entry >= FIRST_COLL_INDEX );

  for (CollIndex i = entry; i < usedLength_; i++)
    usages_[i] = UNUSED_COLL_ENTRY;

  entries_    = entry;
  usedLength_ = entry;
}

template <class T> T & NACollection<T>::rawEntry(CollIndex ix)
{
  // resize, if index lies out of the allocated portion
  if (ix >= maxLength_)
    resize(ix + 1);
  
  // adjust used part to contain ix
  if (ix >= usedLength_)
    {
      for (CollIndex i = usedLength_; i <= ix; i++)
	usages_[i] = UNUSED_COLL_ENTRY;
      usedLength_ = ix + 1;
    }
  
  // if ix refers to a new entry, initialize its usage
  if (usages_[ix] == UNUSED_COLL_ENTRY)
    {
      entries_++;
      usages_[ix] = NULL_COLL_INDEX;
    }
  
  return arr_[ix];
}


template <class T>
CollIndex NACollection<T>::findUsage(const CollIndex &toFind)
{
  for (CollIndex i = FIRST_COLL_INDEX; i < usedLength_; i++)
    {
      if (usages_[i] == toFind)
	return i;
    }
  
  // return a "not found" indicator
  return NULL_COLL_INDEX;
}

// For HSC, define these methods as inline methods in the Collections.h header file.

// -----------------------------------------------------------------------
// functions for the NASubCollection<T> template
// -----------------------------------------------------------------------

template <class T>
NASubCollection<T>::NASubCollection (NACollection<T> *superset,
                                     NAMemory *heap
                                    )
     : builtin_  ( TRUE ),
       entries_  ( 0 ),
       heap_     ( (heap==NULL && superset!=NULL) ? superset->heap_ : heap ),
       maxLength_( BuiltinSubsetWords ),
       superset_ ( superset ),
       wordSize_ ( BuiltinSubsetWords ),
       lastStaleBit_(0)  
   {
   CollIndex    i     = BuiltinSubsetWords;
   WordAsBits * pBits = (WordAsBits*)(&sbits_[ 0 ]);

   pBits_ = pBits;

   do
      {
      *pBits++ = 0x0;
      }
   while (--i);
   }

template <class T>
NASubCollection<T>::NASubCollection( const NASubCollection<T> &other,
                                     NAMemory * heap
                                   ) 
     : builtin_  ( other.builtin_ ),
       entries_  ( other.entries_ ),
       heap_     ( (heap==NULL) ? other.heap_ : heap ),
       maxLength_( other.maxLength_ ),
       superset_ ( other.superset_ ),
       wordSize_ ( other.wordSize_ ),
       lastStaleBit_( other.lastStaleBit_ )
   {
   CollIndex    i          = maxLength_;
   WordAsBits * pBits;
   WordAsBits * pOtherBits = other.pBits_;

   if (builtin_)
      pBits_ = (WordAsBits*)(&sbits_[ 0 ]);
   else
      pBits_ = allocateBits( maxLength_ );

   pBits = pBits_;

   do
      {
      *pBits++ = *pOtherBits++;
      }
   while (--i);
   }

template <class T>
NASubCollection<T>::~NASubCollection()
{
  if (!builtin_)
    deallocateBits();
}

template <class T>
void NASubCollection<T>::setHeap(CollHeap *heap)
   {
   assert( builtin_ );
   heap_ = heap;
   }

template <class T>
NABoolean NASubCollection<T>::contains( const NASubCollection<T> & other ) const
   {
   assert( superset_ == other.superset_ );

   if (other.entries_)
      {
      CollIndex    otherWords  = other.wordSize_;
      CollIndex    commonWords = MINOF( wordSize_, otherWords );
      CollIndex    i           = commonWords;
      WordAsBits * pBits       = pBits_;
      WordAsBits * pOtherBits  = other.pBits_;
      WordAsBits   w;

      if (i)
         {
         do
            {
            w = *pBits++;

            // for a word present in both, "other" mustn't have bits on that
            // are off in word(i) (in other words, when ORing the two words,
            // other must not cause any changes by having additional bits set)

            if (w != (w LOR *pOtherBits++))
	              return( FALSE );
            }
         while (--i);
         }

      i = otherWords - commonWords;

      if ((Lng32) i > 0)
         {
         do
            {
            // if "other" has any bits set that "this" doesn't have, return FALSE
            if (*pOtherBits++)
               return( FALSE );
            }
         while (--i);
         }
      }

   return( TRUE );
   }


template <class T>
NABoolean NASubCollection<T>::lastUsed(CollIndex &lastBit) const
  {
  CollIndex lastNonZeroWord = getWordSize() - 1;

  // find last non-zero word -- the > 0 test is there to avoid wrapping
  // in case CollIndex is an unsigned integer
  while ((lastNonZeroWord > 0) && (word(lastNonZeroWord) == 0))
    {
      lastNonZeroWord--;
    }

  // at this point, we either found the last non-zero word or there
  // are none

  if (word(lastNonZeroWord) == 0)
    return FALSE;  // return; there are none

  // we know we have the last non-zero word; find last set bit

  lastBit = 
    (lastNonZeroWord << LogBitsPerWord) + BitsPerWord - 1;

  while (!testBit(lastBit))
    {
      lastBit--;
    }
  
  return TRUE;  // found the last set bit
  }

template <class T>
NABoolean NASubCollection<T>::operator == ( const NASubCollection<T> & other ) const
   {
   assert( superset_ == other.superset_ );

   if (other.entries_ != entries_)
      return( FALSE );
   else
      {
      if (other.entries_ == 0 && entries_ == 0)
         return( TRUE );
      }

   CollIndex    commonWords = MINOF( wordSize_, other.wordSize_ );
   CollIndex    i           = commonWords;
   WordAsBits * pBits       = pBits_;
   WordAsBits * pOtherBits  = other.pBits_;

   if (i)
      {
      //
      // compare the common words.
      //
      do
         {
         if (*pBits++ != *pOtherBits++)
            return( FALSE );
         }
      while (--i);
      }

   // if one of the bitmap arrays is longer, then it must contain zeroes.

   i = wordSize_ - commonWords;

   if ((Lng32) i > 0)
      {
      do
         {
	 if (*pBits++)
	    return( FALSE );
         }
      while (--i);
      }
   else
      {
      i = other.wordSize_ - commonWords;

      if ((Lng32) i > 0)
         {
         do
            {
            if (*pOtherBits++)
               return( FALSE );
            }
         while (--i);
         }
      }

   return( TRUE );
   }

template <class T>
NASubCollection<T> & NASubCollection<T>::addSet( const NASubCollection<T> & other )
   {
   CollIndex maxWords   = other.wordSize_;

   assert( superset_ == other.superset_ );

   if (other.entries_)
      {
      if (wordSize_ < maxWords)
         extendWordSize( maxWords );

      if (maxWords)
         {
         WordAsBits * pBits      = pBits_;
         WordAsBits * pOtherBits = other.pBits_;

         if (entries_ == 0)  // We can skip computing the entries.
            {
            do
               {
               *pBits++ |= *pOtherBits++;
               }
            while (--maxWords);

            entries_ = other.entries_;
            }
         else
            {
            Lng32 entryCount    = 0; 
            Lng32 trailingWords = (Lng32) (wordSize_ - maxWords); 

            do
               {
               *pBits |= *pOtherBits++;

               entryCount += ones( *pBits++ );
               }
            while (--maxWords);

            while (trailingWords-- > 0)
               {
               entryCount += ones( *pBits++ );
               }
 
            entries_ = entryCount;
            }
         }
      }
   if (other.lastStaleBit_ > lastStaleBit_)
     lastStaleBit_ = other.lastStaleBit_;

   return( *this );
   }

template <class T>
NASubCollection<T> & NASubCollection<T>::intersectSet( const NASubCollection<T> & other )
   {
   assert( superset_ == other.superset_ );

   if (entries_)
      {
      CollIndex commonWords = MINOF( wordSize_, other.wordSize_ );
      CollIndex i           = commonWords;
      WordAsBits * pBits    = pBits_;

      if (i)
         {
         WordAsBits * pOtherBits = other.pBits_;

        if (other.entries_)
            {
            Lng32 entryCount = 0;

            do
               {
               *pBits &= *pOtherBits++;

               entryCount += ones( *pBits++ );
               }
            while (--i);

            entries_ = entryCount;
            }
         else
            {
            do
               {
               *pBits++ = 0x0;
               }
            while (--i);

            entries_ = 0;
            }
         }

      i = wordSize_ - commonWords;

      if ((Lng32) i > 0)
         {
         do
            {
            *pBits++ = 0x0;
            }
         while (--i);
         }
      }

   return( *this );
   }


template <class T>
NASubCollection<T> & NASubCollection<T>::subtractSet( const NASubCollection<T> & other )
   {
   assert( superset_ == other.superset_ );

   if (other.entries_ && entries_)
      {
      CollIndex commonWords = MINOF( wordSize_, other.wordSize_ );

      if (commonWords)
         {
         Lng32         entryCount    = 0;
         CollIndex    trailingWords = wordSize_ - commonWords;
         WordAsBits * pBits         = pBits_;
         WordAsBits * pOtherBits    = other.pBits_;

         do
            {
            *pBits &= LNOT *pOtherBits++;

            entryCount += ones( *pBits++ );
            }
         while (--commonWords);

         while (trailingWords-- > 0)
            {
            entryCount += ones( *pBits++ );
            } 
         entries_ = entryCount;
         }
      }

   return( *this );
   }


template <class T>
WordAsBits NASubCollection<T>::hash() const
   {
   CollIndex    i      = wordSize_;
   WordAsBits   result = 0x0;
   WordAsBits * pBits  = pBits_;

   if (i && entries_)
      {
      do
         {
         result ^= *pBits++;
         }
      while (--i);
      }

   return( result );
   }

template <class T>
NASubCollection<T> & NASubCollection<T>::complement()
   {
  // can only take the complement of a subset
  assert(superset_ != NULL);

  CollIndex maxWords;
  CollIndex superSetSize = superset_->getSize();

  resize(superSetSize);
  maxWords = getWordSize();

  // for each used entry in the superset, toggle the corresponding subset bit
  for (Int32 i = 0; i < (Int32) superSetSize; i++)
    {
      if (superset_->getUsage(i) == UNUSED_COLL_ENTRY)
	{
	  // a subset shouldn't have an element that's not part of
	  // the superset
	  assert(NOT testBit(i));
	}
      else
	{
	  // is the element in the subset
	  if (testBit(i))
	    // yes, then delete it
	    subtractElement(i);
	  else
	    // no, then add it
	    addElement(i);
	}
    }
  
  return *this;
  }

// -----------------------------------------------------------------------
// functions for the NASet<T> template
// -----------------------------------------------------------------------

template <class T>
NASet<T>::~NASet()
{}

template <class T>
T & NASet<T>::operator [] (CollIndex i)
{
  CollIndex userIndex;
  CollIndex arrayIndex;

  if (i >= this->entries())
    ABORT("Set index exceeds # of entries");

  if (userIndexCache_ <= i)
    {
      // start with the cached position
      userIndex = userIndexCache_;
      arrayIndex = arrayIndexCache_;
    }
  else
    {
      // start with the first occupied entry
      userIndex = 0;
      arrayIndex = 0;

      // skip over unused entries
      while (this->getUsage(arrayIndex) == UNUSED_COLL_ENTRY AND
	     arrayIndex < this->getSize())
	arrayIndex ++;
    }

  // advance to the desired entry
  while (userIndex < i)
    {
      userIndex++;
      arrayIndex++;
      // skip over unused entries
      while (this->getUsage(arrayIndex) == UNUSED_COLL_ENTRY AND
	     arrayIndex < this->getSize())
	arrayIndex ++;
    }

  // cache the results
  userIndexCache_ = userIndex;
  arrayIndexCache_ = arrayIndex;

  return this->usedEntry(arrayIndex);
}

template <class T>
const T & NASet<T>::operator [] (CollIndex i) const
{
  CollIndex userIndex = 0;
  CollIndex arrayIndex = 0;

  if (i >= this->entries())
    ABORT("Set index exceeds # of entries");

  // skip over unused entries
  while (this->getUsage(arrayIndex) == UNUSED_COLL_ENTRY AND
	 arrayIndex < this->getSize())
    arrayIndex ++;
  
  // advance to the desired entry
  while (userIndex < i)
    {
      userIndex++;
      arrayIndex++;
      // skip over unused entries
      while (this->getUsage(arrayIndex) == UNUSED_COLL_ENTRY AND
	     arrayIndex < this->getSize())
	arrayIndex ++;
    }

  return this->constEntry(arrayIndex);
}

template <class T>
NABoolean  NASet<T>::operator==(const NASet<T> &other) const
{
  CollIndex count = this->entries();

  if (count != other.entries())
    return FALSE;

  for (CollIndex i = 0; i < count; i++)
    {
      if (NOT this->contains(other[i]))
	  return FALSE;
    }

  return TRUE;
}

// -----------------------------------------------------------------------
// functions for the NAList<T> template
// -----------------------------------------------------------------------

template <class T>
NAList<T>::~NAList()
{}


template <class T>
NAList<T> & NAList<T>::operator=(const NAList<T> &other)
{
  if ( this != &other ) // avoid copy-self!
    {
      this->deallocate();
      NACollection<T>::copy( (const NACollection<T>&) other);
      first_ = other.first_;
      last_ = other.last_;
      userIndexCache_ = other.userIndexCache_;
      arrayIndexCache_ = other.arrayIndexCache_;
    }
  return *this;
}

template <class T>
NABoolean NAList<T>::operator== (const NAList<T> &other) const
{
  if (this->entries() != other.entries())
    return FALSE;

  for (CollIndex i = 0; i < this->entries(); i++)
    {
      if (NOT (at(i) == other.at(i)))
	return FALSE;
    }

  return TRUE;
}

  
template <class T>
NABoolean NAList<T>::find(const T &elem, T &returnedElem) const
{
  CollIndex foundIndex;
  
  if ((foundIndex = NACollection<T>::find(elem)) == NULL_COLL_INDEX)
    return FALSE;
  else
    {
      returnedElem = this->constEntry(foundIndex);
      return TRUE;
    }
}

template <class T>
T & NAList<T>::operator [] (CollIndex i)
{
  CollIndex userIndex;
  CollIndex arrayIndex;

  if (userIndexCache_ <= i)
    {
      // start with the cached position
      userIndex = userIndexCache_;
      arrayIndex = arrayIndexCache_;
    }
  else
    {
      // start with the first entry
      userIndex = 0;
      arrayIndex = first_;
    }

  while (userIndex < i)
    {
      userIndex++;
      arrayIndex = this->getUsage(arrayIndex);
      if (arrayIndex == NULL_COLL_INDEX)
	ABORT("List index exceeds # of entries");
    }

  userIndexCache_ = userIndex;
  arrayIndexCache_ = arrayIndex;

  return this->usedEntry(arrayIndex);
}

template <class T>
const T & NAList<T>::operator [] (CollIndex i) const
{
  CollIndex userIndex;
  CollIndex arrayIndex;

  if (userIndexCache_ <= i)
    {
      // start with the cached position
      userIndex = userIndexCache_;
      arrayIndex = arrayIndexCache_;
    }
  else
    {
      // start with the first entry
      userIndex = 0;
      arrayIndex = first_;
    }

  while (userIndex < i)
    {
      userIndex++;
      arrayIndex = this->getUsage(arrayIndex);
      if (arrayIndex == NULL_COLL_INDEX)
	{
	  ABORT("List index exceeds # of entries");
	}
    }

  // We cast away const-ness from _this_ so that we can update the 2
  // IndexCache data members.  Semantically, this is alright, since
  // changing those 2 data members does not truly "modify" the NAList
  // object.  But we get a big performance benefit from this.
  //
  // Yes, if MSVC++ supported the mutable keyword reliably, this unusual
  // cast would not be necessary.
  NAList<T>* thisPtr = (NAList<T>*) this ;

  thisPtr->userIndexCache_  = userIndex;
  thisPtr->arrayIndexCache_ = arrayIndex;

  return this->constEntry(arrayIndex);
}


template <class T>
CollIndex NAList<T>::removeCounted(const T &elem, const CollIndex desiredCount)
{
  CollIndex actualCount = 0;
  CollIndex curr = first_;             // current entry
  CollIndex pred = NULL_COLL_INDEX;    // predecessor of current entry

  while (curr != NULL_COLL_INDEX) {

    if (this->usedEntry(curr) == elem) {
      // ok, found (first) matching entry, now delete it
      if (pred == NULL_COLL_INDEX)
	// we have a new first element in the list
	first_ = this->getUsage(curr);
      else
	// unlink this element from the list
	this->setUsage(pred,this->getUsage(curr));

      // delete the actual entry
      NACollection<T>::remove(curr);

      // take care of the last_ pointer
      if (last_ == curr) last_ = pred;

      if (++actualCount == desiredCount) break;
      curr = pred;
    }

    // go to the next element
    pred = curr;
    curr = this->getUsage(curr);
  }

  // invalidate the cache if necessary
  if (actualCount) invalidateCache();

  return actualCount;
}


template <class T>
CollIndex NAList<T>::findArraysIndex(CollIndex i)
{
  CollIndex userIndex;
  CollIndex arrayIndex;

  if (userIndexCache_ <= i)
    {
      // start with the cached position
      userIndex = userIndexCache_;
      arrayIndex = arrayIndexCache_;
    }
  else
    {
      // start with the first entry
      userIndex = 0;
      arrayIndex = first_;
    }

  while (userIndex < i)
    {
      userIndex++;
      arrayIndex = this->getUsage(arrayIndex);
      if (arrayIndex == NULL_COLL_INDEX)
	ABORT("List index exceeds # of entries");
    }

  userIndexCache_ = userIndex;
  arrayIndexCache_ = arrayIndex;

  return arrayIndex;
}

template <class T>
CollIndex NAList<T>::findArraysIndex(CollIndex i) const
{
  CollIndex userIndex;
  CollIndex arrayIndex;

  if (userIndexCache_ <= i)
    {
      // start with the cached position
      userIndex = userIndexCache_;
      arrayIndex = arrayIndexCache_;
    }
  else
    {
      // start with the first entry
      userIndex = 0;
      arrayIndex = first_;
    }

  while (userIndex < i)
    {
      userIndex++;
      arrayIndex = this->getUsage(arrayIndex);
      if (arrayIndex == NULL_COLL_INDEX)
	ABORT("List index exceeds # of entries");
    }

  // We cast away const-ness from _this_ so that we can update the 2
  // IndexCache data members.  Semantically, this is alright, since
  // changing those 2 data members does not truly "modify" the NAList
  // object.  But we get a big performance benefit from this.
  //
  // Yes, if MSVC++ supported the mutable keyword reliably, this unusual
  // cast would not be necessary.
  NAList<T>* thisPtr = (NAList<T>*) this ;

  thisPtr->userIndexCache_  = userIndex;
  thisPtr->arrayIndexCache_ = arrayIndex;

  return arrayIndex;
}

// For HSC, define this method as an inline method in the Collections.h header file.

// A dumb but easy implementation for insert one LIST into another
template <class T>
void NAList<T>::insert(const NAList<T> &other)
{
  CollIndex count = other.entries();
  for (CollIndex i = 0; i < count; i++)
    {
      insert(other[i]);
    } // for loop for iterating over members of the set
} // insert(LIST(T))

// For HSC, define this method as an inline method in the Collections.h header file.

template <class T>
NABoolean NAList<T>::getLast(T &elem)
{
  if (this->entries() > 0)
    {
      // copy last element
      elem = this->usedEntry(last_);

      // remove the last element from the list
      NACollection<T>::remove(last_);

      // fix up the list pointers
      if (first_ == last_)
	first_ = last_ = NULL_COLL_INDEX;
      else
	{
	  last_ = this->findUsage(last_);
	  this->setUsage(last_, NULL_COLL_INDEX);
	}

      // invalidate the cache, if necessary
      if (userIndexCache_ >= this->entries())
	invalidateCache();

      return TRUE;
    }
  else
    return FALSE;
}

// -----------------------------------------------------------------------
// functions for the NAArray<T> template
// -----------------------------------------------------------------------

template <class T>
NABoolean NAArray<T>::operator ==(const NAArray<T> &other) const
{
  if(this->entries() != other.entries())
    return FALSE;

  for(CollIndex i = 0; i < this->entries(); i++)
    {
      if(NOT(at(i) == other.at(i)))
	return FALSE;
    }

  return TRUE;
}

// -----------------------------------------------------------------------
// functions for the NASubArray<T> template
// -----------------------------------------------------------------------

template <class T>
NASubArray<T>::~NASubArray()
{}

// ***********************************************************************
// functions for the Hash Dictionary
// ***********************************************************************

template <class K, class V>
NAHashBucketEntry<K,V>::~NAHashBucketEntry()
{
} //  NAHashBucketEntry<K,V>::~NAHashBucketEntry()
				    
template <class K, class V>
void NAHashBucketEntry<K,V>::clear(NABoolean deleteContents)
{
  if (deleteContents)
    {
      delete key_;
      delete value_;
    }
} //  NAHashBucketEntry<K,V>::clear()
				    
template <class K, class V>
void NAHashBucketEntry<K,V>::display() const
{
  printf("(%p,%p) ",key_, value_);
} //  NAHashBucketEntry<K,V>::display()
				    
template <class K, class V>
Int32 NAHashBucketEntry<K,V>::printStatistics(char *buf)
{
  return sprintf(buf, "(0X%X,0X%X) ",key_, value_);
} //  NAHashBucketEntry<K,V>::printStatistics()
				    
// -----------------------------------------------------------------------
// NAHashBucket::NAHashBucket()
// -----------------------------------------------------------------------
template <class K, class V>
NAHashBucket<K,V>::NAHashBucket(const NAHashBucket<K,V> & other, NAMemory * heap)
     : heap_( (heap==NULL) ? other.heap_ : heap )
       ,bucket_(other.bucket_)
{
} // NAHashBucket<K,V>::NAHashBucket()

template <class K, class V>
NAHashBucket<K,V>::~NAHashBucket()
{
  clear(FALSE); // delete all hash bucket entries
} // NAHashBucket<K,V>::~NAHashBucket()

// -----------------------------------------------------------------------
// NAHashBucket::clear()
// -----------------------------------------------------------------------
template <class K, class V>
void NAHashBucket<K,V>::clear(NABoolean deleteContents)
{
  CollIndex ne = bucket_.entries();
  for (CollIndex index = 0; index < ne; index++)
    {
      bucket_[index]->clear(deleteContents);
      delete bucket_[index];
    }
  bucket_.clear(); // clear list head
} // NAHashBucket<K,V>::clear()

// -----------------------------------------------------------------------
// NAHashBucket::contains()
// Making two separate contains() methods allows a hash dictionary with
// a value type for which we don't have a comparison operator
// -----------------------------------------------------------------------
template <class K, class V>
NABoolean NAHashBucket<K,V>::contains(const K* key) const 
{
  CollIndex ne = bucket_.entries();
  
  for (CollIndex index = 0; index < ne; index++)
    {
      // ----------------------------------------------------------------
      // Index a hash bucket entry.
      // ----------------------------------------------------------------
      NAHashBucketEntry<K,V>* bep = bucket_[index];

      // ----------------------------------------------------------------
      // Compare the stored key value with the given key value.
      // ----------------------------------------------------------------
      if (*bep->getKey() == * key)  // NOTE: uses K::operator==()
	{
          return TRUE;
	} // endif

    } // end for

  return FALSE;

} // NAHashBucket<K,V>::contains()

template <class K, class V>
NABoolean NAHashBucket<K,V>::contains(const K* key, const V* value) const 
{
  CollIndex ne = bucket_.entries();
  
  for (CollIndex index = 0; index < ne; index++)
    {
      // ----------------------------------------------------------------
      // Index a hash bucket entry.
      // ----------------------------------------------------------------
      NAHashBucketEntry<K,V>* bep = bucket_[index];

      // ----------------------------------------------------------------
      // Compare the stored key value with the given key value.
      // ----------------------------------------------------------------
      if (*bep->getKey() == * key)  // NOTE: uses K::operator==()
	{

	  if (value) // a value is also supplied
	    {
	      // --------------------------------------------------------
	      // Compare the stored value with the given value.
	      // --------------------------------------------------------
	      if (*bep->getValue() == * value) // NOTE: uses V::operator==()
		return TRUE;
	    }
	  else           // keys are equal
	    return TRUE;

	} // endif

    } // end for

  return FALSE;

} // NAHashBucket<K,V>::contains()

// -----------------------------------------------------------------------
// NAHashBucket::display()
// -----------------------------------------------------------------------
template <class K, class V>
void NAHashBucket<K,V>::display() const
{
  CollIndex ne = bucket_.entries();
  if (ne > 0)
    {
      for (CollIndex index = 0; index < ne; index++)
	{
	  bucket_[index]->display();
	  if (index > 0 AND (index/4* 4 == index)) printf("\n");
	}
    }
  else
    printf("*** empty ***\n");
} //  NAHashBucket<K,V>::display()
				    
// -----------------------------------------------------------------------
// NAHashBucket::printStatistics()
// -----------------------------------------------------------------------
template <class K, class V>
Int32 NAHashBucket<K,V>::printStatistics(char *buf)
{
  CollIndex ne = bucket_.entries(); Int32 c = 0;
  if (ne > 0) {
    for (CollIndex index = 0; index < ne; index++) {
	  c += bucket_[index]->printStatistics(buf+c);
	  if (index > 0 AND (index/4* 4 == index)) 
        c += sprintf(buf+c,"\n");
	}
  }
  else {
    c = sprintf(buf,"*** empty ***\n");
  }
  return c;
} //  NAHashBucket<K,V>::printStatistics()
				    
// -----------------------------------------------------------------------
// NAHashBucket::getFirstValue()
// -----------------------------------------------------------------------
template <class K, class V>
V* NAHashBucket<K,V>::getFirstValue(const K* key) const
{
  CollIndex ne = bucket_.entries();
  
  for (CollIndex index = 0; index < ne; index++)
    {
      // ----------------------------------------------------------------
      // Index a hash bucket entry.
      // ----------------------------------------------------------------
      NAHashBucketEntry<K,V>* bep = bucket_[index];

      // ----------------------------------------------------------------
      // Compare the stored key value with the given key value.
      // ----------------------------------------------------------------
      if (*bep->getKey() == *key)  // NOTE: uses K::operator==()
	return bep->getValue();
      
    } // end for

  return NULL; // key not found in the hash dictionary
  
} // NAHashBucket<K,V>::getFirstValue()

// -----------------------------------------------------------------------
// NAHashBucket::getKeyValuePair()
// -----------------------------------------------------------------------
template <class K, class V>
void NAHashBucket<K,V>::getKeyValuePair(const K* key, const V* value,
				        NAHashBucket<K,V>& container) const
{
  CollIndex ne = bucket_.entries();
  
  if (key)
    { // a key is given
      for (CollIndex index = 0; index < ne; index++)
	{
	  // -------------------------------------------------------------
	  // Index a hash bucket entry.
	  // -------------------------------------------------------------
	  NAHashBucketEntry<K,V>* bep = bucket_[index];

	  // -------------------------------------------------------------
	  // Compare the stored key value with the given key value.
	  // -------------------------------------------------------------
	  if (*bep->getKey() == * key)  // NOTE: uses K::operator==()
	    {

	      if (value) // a value is also supplied
		{
		  // -----------------------------------------------------
		  // Compare the stored value with the given value.
		  // -----------------------------------------------------
		  if (*bep->getValue() == * value) // NOTE: uses V::operator==()
		    container.insert(bep->getKey(), bep->getValue());
		}
	      else      // keys are equal
		container.insert(bep->getKey(), bep->getValue());

	    } // endif stored key == given key

	} // end for

    } // a key is given
  else
    {
      // Return all hash bucket entries
      for (CollIndex index = 0; index < ne; index++)
	container.insert(bucket_[index]->getKey(), bucket_[index]->getValue());
    }
  
} // NAHashBucket<K,V>::getKeyValuePair()

// -----------------------------------------------------------------------
// NAHashBucket::remove()
// -----------------------------------------------------------------------
template <class K, class V>
K* NAHashBucket<K,V>::remove(K* key)
{
  CollIndex ne = bucket_.entries();
  
  for (CollIndex index = 0; index < ne; index++)
    {
      // ----------------------------------------------------------------
      // Index a hash bucket entry.
      // ----------------------------------------------------------------
      NAHashBucketEntry<K,V>* bep = bucket_[index];

      // ----------------------------------------------------------------
      // Compare the stored key value with the given key value.
      // ----------------------------------------------------------------
      if (*bep->getKey() == *key)  // NOTE: uses K::operator==()
	{
	  bucket_.removeAt(index);
      delete bep;
	  return key;
	}
      
    } // end for

  return NULL; // key not found in the hash dictionary
  
} // NAHashBucket<K,V>::remove()

// ----------------------------------------------------------------------
// NAHashDictionary constructor functions
// ----------------------------------------------------------------------
template <class K, class V>
NAHashDictionary<K,V>::NAHashDictionary(
// see long detailed comment in Collections.h about the hash function param.
			ULng32 (*hashFunction)(const K &), 
			ULng32 hashSize,
			NABoolean enforceUniqueness,
			NAMemory* heap)
			: heap_(heap),
		       hash_(hashFunction),
		       entries_(0), 
		       enforceUniqueness_(enforceUniqueness)
{
   createHashTable(hashSize);
}

template <class K, class V>
NAHashDictionary<K,V>::NAHashDictionary (const NAHashDictionary<K,V> & other,
                                         NAMemory * heap) 
     : heap_( (heap==NULL) ? other.heap_ : heap ),
       hash_(other.hash_),
       entries_(other.entries_), 
       enforceUniqueness_(other.enforceUniqueness_)
{
  createHashTable(other.hashSize_);
  for (CollIndex index = 0; index < hashSize_; index++)
     (*hashTable_)[index] = (*other.hashTable_)[index];
}

// ----------------------------------------------------------------------
// NAHashDictionary destructor function.
// ----------------------------------------------------------------------
template <class K, class V>
NAHashDictionary<K,V>::~NAHashDictionary() 
{
  for (CollIndex index = 0; index < hashSize_; index++)
    delete (*hashTable_)[index];
  delete hashTable_; 
}

// ----------------------------------------------------------------------
// NAHashDictionary::clear()
// Deletes all entries in the hash buckets.
// Does not delete any key or value.
// Does not delete any hash bucket or the hash table.
// ----------------------------------------------------------------------
template <class K, class V>
void NAHashDictionary<K,V>::clear(NABoolean deleteContents)
{
  for (ULng32 index = 0; index < hashSize_; index++)
    (*hashTable_)[index]->clear(deleteContents);
  entries_ = 0;
} //  NAHashDictionary<K,V>::clear()

// ----------------------------------------------------------------------
// NAHashDictionary::createHashTable()
// Helper function for creating a hash table.
// ----------------------------------------------------------------------
template <class K, class V>
void NAHashDictionary<K,V>::createHashTable(ULng32 hashSize)
{
  assert (hashSize > 0);
  hashSize_ = hashSize;
  hashTable_ = new(heap_) NAArray<NAHashBucket<K,V>* >(heap_,hashSize);
  for (CollIndex index = 0; index < hashSize; index++)
     hashTable_->insertAt(index, new(heap_) NAHashBucket<K,V>(heap_));
} //  NAHashDictionary<K,V>::createHashTable()

// ----------------------------------------------------------------------
// NAHashDictionary::getHashCode()
// Function for generating a hash code
// ----------------------------------------------------------------------
template <class K, class V>
ULng32 NAHashDictionary<K,V>::getHashCode(const K& key) const
{
  // use the key's hash method to get the hash value
//  unsigned long hashValue = key.hash() % hashSize_;
//#else
  ULng32 hashValue = hash_(key) % hashSize_;
//#endif
  assert(hashValue < hashSize_);
  return hashValue;
} //  NAHashDictionary<K,V>::getHashCode()

// ----------------------------------------------------------------------
// NAHashDictionary::insert()
// ----------------------------------------------------------------------
template <class K, class V>
K* NAHashDictionary<K,V>::insert(K* key, V* value) 
{ 
  if (enforceUniqueness_ AND contains(key))
    {
      assert(enforceUniqueness_);
      return NULL; // don't insert a duplicate key
    }
  (*hashTable_)[getHashCode(*key)]->insert(key, value); 
  entries_++;
  return key;
} // NAHashDictionary<K,V>::insert()				

// ----------------------------------------------------------------------
// NAHashDictionaryIterator::ctor()
// ----------------------------------------------------------------------
template <class K, class V>
NAHashDictionaryIterator<K,V>::NAHashDictionaryIterator (const NAHashDictionary<K,V> & dict,
                                                         const K* key, 
                                                         const V* value)
     : iterator_(dict.heap_)
{
  if (key)
    (*(dict.hashTable_))[dict.getHashCode(*key)]->getKeyValuePair(key,value,iterator_);
  else 
    {      
      // iterate over all key value pairs in the hash table
      for (CollIndex index = 0; index < dict.hashSize_; index++)
	(*(dict.hashTable_))[index]->getKeyValuePair(key,value,iterator_) ; 
    } 
  // iterator_ now contains all the qualifying key value pairs  
  reset() ; // set the position so we're ready to iterate

} // NAHashDictionaryIterator<K,V>()

// ----------------------------------------------------------------------
// NAHashDictionaryIterator::copy ctor()
// ----------------------------------------------------------------------
template <class K, class V>
NAHashDictionaryIterator<K,V>::NAHashDictionaryIterator (const NAHashDictionaryIterator<K,V> & other, NAMemory * heap)
     : iterator_(heap) // NB: we always put copies on the stmt heap
{
  iterator_         = other.iterator_ ; 
  iteratorPosition_ = other.iteratorPosition_ ; 
} // NAHashDictionaryIterator<K,V>() copy ctor()

// ----------------------------------------------------------------------
// ~NAHashDictionaryIterator()
// ----------------------------------------------------------------------
template <class K, class V>
NAHashDictionaryIterator<K,V>::~NAHashDictionaryIterator() 
{
  iterator_.clear() ; 
  reset() ; 
} // ~NAHashDictionaryIterator<K,V>

// ----------------------------------------------------------------------
// NAHashDictionaryIterator::getNext()
// ----------------------------------------------------------------------
template <class K, class V>
void NAHashDictionaryIterator<K,V>::getNext(K*& key, V*& value)
{
  if (iteratorPosition_ < iterator_.entries())
    {
      key = iterator_[iteratorPosition_]->getKey();
      value = iterator_[iteratorPosition_]->getValue();
      iteratorPosition_++ ;
    }
  else
    {
      // If the application has advanced the iterator beyond the number
      // of entries, signal that there are no more keys and values.
      key = NULL;
      value = NULL;
    }

} // NAHashDictionaryIterator<K,V>::getNext()				

// ----------------------------------------------------------------------
// NAHashDictionary::remove()
// ----------------------------------------------------------------------
template <class K, class V>
K* NAHashDictionary<K,V>::remove(K* key)
{
  K* removedKey = (*hashTable_)[getHashCode(*key)]->remove(key);
  if (removedKey)
    entries_--;
  return removedKey;
} // NAHashDictionary<K,V>::remove()				

// ----------------------------------------------------------------------
// NAHashDictionary::resize()
// ----------------------------------------------------------------------
template <class K, class V>
void NAHashDictionary<K,V>::resize(ULng32 newHashSize)
{
  assert(newHashSize > 0);

  // TODO -- if indeed this is dead code -- remove this method !

  // This method is not used anywhere, and makes calls to undefined functions
  // like iteratorCreate() and iteratorDestroy()
  assert(FALSE);
} // NAHashDictionary<K,V>::resize()				

// ----------------------------------------------------------------------
// NAHashDictionary::display()
// ----------------------------------------------------------------------
template <class K, class V>
void NAHashDictionary<K,V>::display() const
{
  if (hashSize_ > 0)
    {
      for (CollIndex index = 0; index < hashSize_; index++)
	{
	  printf("\nbucket[%d] : \n",index);
	  (*hashTable_)[index]->display();
	}
    }
  else
    printf("*** hash table is empty ***");
  printf("\n");
} //  NAHashDictionary<K,V>::display()
				    
// ----------------------------------------------------------------------
// NAHashDictionary::printStatistics()
// ----------------------------------------------------------------------
template <class K, class V>
Int32 NAHashDictionary<K,V>::printStatistics(char *buf)
{
  Int32 c = 0;
  if (hashSize_ > 0) {
    for (CollIndex index = 0; index < hashSize_; index++) {
	  c += sprintf(buf+c, "\nbucket[%d] : \n",index);
	  c += (*hashTable_)[index]->printStatistics(buf+c);
	}
  }
  else 
    c = sprintf(buf,"*** hash table is empty ***");
  c += sprintf(buf+c,"\n");
  return c;
} //  NAHashDictionary<K,V>::printStatistics()