DLIList.hpp

Go to the documentation of this file.

//- Class: DLIList
//-
//- Assumptions: All data are stored contiguously in the array with 
//-              empty slots at the end of the array.
//-
//- Owner: Darryl Melander

#ifndef DLILIST_HPP
#define DLILIST_HPP

#include "CubitDefines.h"
#include <cstring>
#include <vector>
#include <set>
#include <stdexcept>
#include <algorithm>

#define DLI_COUNT_INCREMENT 8
#define DLI_COUNT_FACTOR 1.5
template<class X> class DLIListIterator;


// the following empty template acts as a pure virtual declaration so that
// new classes using DLIList will not be sorted by pointer
template <class X> struct DLIListSorter
{
//  bool operator()(const X &a, const X &b) { return a < b; }
};

// compare templates for intrinsic types

template <> struct DLIListSorter<int>
{
  bool operator()(const int &a, const int &b) { return a < b; }
};

template <> struct DLIListSorter<double>
{
  bool operator()(const double &a, const double &b) { return a < b; }
};

// compare template for CubitString.

//template <> struct DLIListSorter<CubitString>
//{
//  bool operator()(const CubitString &a, const CubitString &b) { return a < b; }
//};


// The new Apple libc++ uses a specialization for std::vector<bool> that prevents
// DLIList<bool> from re-using the std::vector<X>::const_reference typedef blindly.
// vector_const_reference_type defined below provides a wrapper to consistently use
// a plain bool type as DLIList<bool>::const_reference.
template<typename T>
struct vector_const_reference_type {
  typedef typename std::vector<T>::const_reference type;
};

template<>
struct vector_const_reference_type<bool> {
  typedef bool type;
};

template<class X> class DLIList
{
public:
  friend class DLIListIterator<X>;

  typedef typename std::vector<X>::reference reference;
  typedef typename vector_const_reference_type<X>::type const_reference;
  typedef typename std::vector<X>::pointer pointer;
  typedef typename std::vector<X>::const_pointer const_pointer;

  typedef typename std::vector<X>::const_iterator const_iterator;
  typedef typename std::vector<X>::iterator iterator;

  typedef typename std::vector<X>::value_type value_type;
  

  explicit DLIList (int size = 0);
  

  DLIList(const DLIList<X>& from);
  

  explicit DLIList(const std::vector<X>& from);


  ~DLIList();

  iterator begin();

  const_iterator begin() const;

  iterator end();

  const_iterator end() const;
  

  void step();
  

  void step(int n);
  

  void back();
  

  void back(int n);
  
  void reset();
  void last();
  

  void clean_out();
  

  void shrink(int k);
  
  CubitBoolean is_at_beginning() const;
  
  CubitBoolean is_at_end() const;

  void reverse();
  

  DLIList<X>& operator=(const DLIList<X>& from);


  DLIList<X>& operator=(const std::vector<X>& from);


  DLIList<X>& operator=(const DLIListIterator<X>& from_iterator);
  

  DLIList<X>& operator+=(const DLIList<X>& from);


  DLIList<X>& operator+=(const std::vector<X>& from);


  DLIList<X>& operator-=(const DLIList<X>& from);


  int operator==(const DLIList<X>& from);


  int operator!=(const DLIList<X>& from);


  const_reference operator[](int index) const;
  reference operator[](int index);

  reference last_item( void );
  const_reference last_item( void ) const;


  void merge_unique(const DLIList<X>& merge_list, 
                    bool merge_list_unique = false);


  template<typename Y> inline void casting_merge_unique(const DLIList<Y>& merge_list,
                                                        bool merge_list_unique = false)
    {
        // Save the current index of the merge_list
      int old_size = size();   
      int i, j, check_index;
      
      X new_item;

      // The resulting list will be at least as large as the larger of the two lists.
      // Reserve space so we don't have to reallocate so often.  Note that if
      // this list is already bigger than merge_list, the reserve won't
      // make the list shorter.
      assert((int)merge_list.size() >= 0); // Assume that the merge list size does not exceed the maximum value for a signed integer
      reserve(merge_list.size());

      for ( i = 0; i < (int)merge_list.size(); i++)
      {
          // Get the item from the merge_list and insert it into "this"
          // list if it doesn't already exist there.
        new_item = static_cast<X>(merge_list[i]);
        check_index = merge_list_unique ? old_size : size();

        // Append the new item and then remove it if necessary.
        append(new_item);
        for ( j = 0; j < check_index; j++ )
        {
          if ( listArray[j] == new_item )
          {
            listArray.resize(listArray.size()-1);
            break;
          }
        }
      }
    }


  void intersect(const DLIList<X>& merge_list);

  void intersect_unordered(const DLIList<X>& merge_list);


  CubitBoolean append_unique(const_reference new_item);
  

  void uniquify_unordered();
  void uniquify_unordered_checked();
    

  void uniquify_ordered();
  

  X remove ();
  

  bool remove (const_reference val);


  void remove_all_with_value(const_reference val);


  CubitBoolean omit (const_reference val);
  

  const_reference get () const;
  reference get ();
  

  X next () const;
  

  X next (int n) const;
  

  X prev () const;
  

  X prev (int n) const;
  

  reference get_and_step ();
  

  reference get_and_back ();
  

  reference step_and_get ();
  

  CubitBoolean move_to(const_reference item);


  CubitBoolean is_in_list(const_reference item) const;


  X pop();


  X push(X val);


  void insert (X val);


  void insert_first(X val);


  void append(const_reference new_item);


  X extract();
  

  X change_to(X val);
  

  void sort();


  typedef int (*SortFunction)(X& a, X& b);


  void sort(SortFunction f);


  void reserve(int min_size);
  

  int size() const
    { return (int)listArray.size(); }


  bool empty() const
  { return listArray.empty(); }


  int get_index()
     { return index; }
  

  int where_is_item(const_reference val) const;

  int memory_use();
   

  void copy_to(X *other_array);


  void copy_from(X *other_array, const int other_size);


  CubitBoolean move_to_nearby(const X val);


  int distance_to_nearby(const X val);


  CubitBoolean move_between(X val1, X val2);


  const std::vector<X>& as_vector() const;


  void swap(std::vector<X>& other);

private:
  void lengthen_list(int by_how_much = DLI_COUNT_INCREMENT,
                     double by_what_factor = DLI_COUNT_FACTOR );
    //- Makes the array bigger. Multiply current size 
    //- "by_what_factor" and add 'by_how_much'.
  
  int index; // Index of current item in {listArray} (so we should assume that the listArray size does not exceed the maximum value for a signed integer?)
  std::vector<X> listArray;
};

// *** inline function definitions *******************************************
template <class X> inline 
DLIList<X>& DLIList<X>::operator=(const DLIListIterator<X>& from_iter)
{ 
  if ( from_iter.dlIList ) 
    *this = *(from_iter.dlIList); 
  else
    clean_out();
  return *this; 
}

template <class X> inline
typename DLIList<X>::const_reference DLIList<X>::operator[](int indexIn) const
{
  assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if(indexIn < 0 || (size_t)indexIn >= listArray.size())
    throw std::out_of_range("Index out of Bounds\n");
  return listArray[indexIn];
}

template <class X> inline
typename DLIList<X>::reference DLIList<X>::operator[](int indexIn)
{
  assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if(indexIn < 0 || (size_t)indexIn >= listArray.size())
    throw std::out_of_range("Index out of Bounds\n");
  return listArray[indexIn];
}

template <class X> inline
typename DLIList<X>::reference DLIList<X>::last_item(void)
{
    assert( listArray.size() > 0 );
    return listArray[listArray.size()-1];
}

template <class X> inline
typename DLIList<X>::const_reference DLIList<X>::last_item(void) const
{
    assert( listArray.size() > 0 );
    return listArray[listArray.size()-1];
}

template <class X> inline void DLIList<X>::step()
{
  if (!listArray.empty())
    index++; 
  assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if (index >= (int)listArray.size())
    index = 0;
}

template <class X> inline void DLIList<X>::step(int n)
{
  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if (itemCount > 0)
  {
    index += n;
    if (index < 0)
      index = itemCount - (-index) % itemCount;
    if (index >= itemCount)
      index %= itemCount;
  }
}

// Chop off the last (k) items in the list.
template <class X> inline void DLIList<X>::shrink(int k)
{
  if (k > 0)
  {
    const int itemCount = (int)listArray.size();
    assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer

    if (itemCount > k)
      listArray.resize(itemCount - k);
    else
      listArray.clear();

    const int itemNewCount = (int)listArray.size();
    if (index >= itemNewCount)
    {
      if (itemNewCount > 0)
        index = itemNewCount - 1;
      else
        index = 0;
    }
  }
}

template <class X> inline void DLIList<X>::back()
{
  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if (itemCount > 0)
  {
    index--;
    if (index < 0)
      index = itemCount - 1;
  }
}

template <class X> inline void DLIList<X>::back(int n)
{
  step(-n);
}

template <class X> inline void DLIList<X>::reset()
{
  index = 0;
}

template <class X> inline void DLIList<X>::last()
{
  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if (itemCount > 0)
    index = itemCount - 1;
}

template <class X> inline CubitBoolean DLIList<X>::is_at_beginning() const
{
  if (!index)
    return CUBIT_TRUE;
  else
    return CUBIT_FALSE;
}

template <class X> inline CubitBoolean DLIList<X>::is_at_end() const
{
  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if (itemCount == 0 || index == itemCount - 1)
    return CUBIT_TRUE;
  else
    return CUBIT_FALSE;
}

template <class X> inline void DLIList<X>::clean_out()
{
  listArray.clear();
  index = 0;
}

template <class X> inline CubitBoolean DLIList<X>::is_in_list(const_reference item) const
{
  return where_is_item(item) >= 0 ? CUBIT_TRUE : CUBIT_FALSE;
}

//- Add item to end of list, do not change current index value.
//- This function used to reduce time required to do an insert 
//- followed by a move_to back to where we were.
template <class X> inline void DLIList<X>::append(const_reference new_item)
{
    // see if the list must be lengthened
  if (listArray.capacity() == listArray.size())
    lengthen_list();

  listArray.push_back(new_item);
}

template <class X> inline typename DLIList<X>::reference DLIList<X>::get()
{
  if ( listArray.empty() )
  {
    throw std::out_of_range("Attempted get of empty DLIList\n");
    /*PRINT_WARNING("Attempted get of empty DLIList\n");*/
  }

  return listArray[index];
}

template <class X> inline typename DLIList<X>::const_reference DLIList<X>::get() const
{
  if ( listArray.empty() )
  {
    throw std::out_of_range("Attempted get of empty DLIList\n");
    /*PRINT_WARNING("Attempted get of empty DLIList\n");*/
  }
  return listArray[index];
}

template <class X> inline typename DLIList<X>::reference DLIList<X>::get_and_step()
{
  if ( listArray.empty() )
  {
    throw std::out_of_range("Attempted get_and_step from empty DLIList\n");
    /*PRINT_WARNING("Attempted get_and_step from empty DLIList\n");*/
  }
  reference temp = listArray[index++];
  assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if (index == (int)listArray.size())
    index = 0;
  return temp;
}

template <class X> inline typename DLIList<X>::reference DLIList<X>::get_and_back ()
{
   if ( listArray.empty() )
   {
     throw std::out_of_range("Attempted get_and_back from empty DLIList\n");
      /*PRINT_WARNING("Attempted get_and_back from empty DLIList\n");*/
   }
   reference temp = listArray[index--];
   assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
   if (index < 0)
      index = (int)listArray.size() - 1;
   return temp;
}

template <class X> inline X DLIList<X>::next() const
{
  if (listArray.empty())
  {
    throw std::out_of_range("Attempted next of empty DLIList\n");
    /*PRINT_WARNING("Attempted next of empty DLIList\n");*/
  }
  else {
    assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
    if (index == (int)listArray.size() - 1)
      return listArray[0];
    else
      return listArray[index + 1];
  }
}

template <class X> inline X DLIList<X>::next(int n) const
{
  if ( listArray.empty() )
  {
    throw std::out_of_range("Attempted next of empty DLIList\n");
    /*PRINT_WARNING("Attempted next of empty DLIList\n");*/
  }
  else
  {
      // return the proper index
      // beware of negative n leading to negative new_index
    int new_index = index+n;
    assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
    while (new_index < 0)
      new_index += listArray.size();
    if ((size_t)new_index >= listArray.size())
      new_index %= listArray.size();
    
    return listArray[new_index];
  }
}

template <class X> inline X DLIList<X>::prev() const
{
  return this->next(-1);
}

template <class X> inline X DLIList<X>::prev(int n) const
{
  return this->next(-n);
}

//- put new item in list at index 0 and make it current
template <class X> inline void DLIList<X>::insert_first(X new_item)
{
  // set index to -1 ... index will be set to 0 in insert
  index = -1;
  insert(new_item);
}

template <class X> inline CubitBoolean DLIList<X>::move_to (const_reference item)
{
  int item_index = where_is_item(item);
  CubitBoolean rv = CUBIT_FALSE;
  if (item_index >= 0)
  {
    index = item_index;
    rv = CUBIT_TRUE;
  }
  return rv;
}

template <class X> inline X DLIList<X>::change_to (X new_value)
{
  if ( listArray.empty() )
  {
    throw std::out_of_range("DLIList: Attempted update of empty list\n");
    //PRINT_WARNING("DLIList: Attempted update of empty list\n");
  }

  X temp = listArray[index];
  listArray[index] = new_value;
  return temp;
}

// Removes every instance of 'val' in list.
// Set to beginning of list after this call.
template <class X> inline void DLIList<X>::remove_all_with_value(const_reference val)
{
  size_t j = 0;
  size_t i = 0;
  const size_t itemCount = listArray.size();

  for ( ; i < itemCount; i++)
    if (listArray[i] != val && j++ != i)
      listArray[j-1] = listArray[i];

  listArray.resize(j);
  index = 0;
}

// Searches for item and removes the next instance from the list.
// If the item was found and removed it is returned, else 0 is returned.
template <class X> inline bool DLIList<X>::remove (const_reference item)
{
  if (move_to(item))
  {
    remove();
    return true;
  }
  return false;
}

template <class X> inline int DLIList<X>::where_is_item (const_reference item) const
{
  if (listArray.empty())
    return -1;

  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  
    // loop through list searching for item ...
    // if found return index
  
    // Search from current index to end of array
  int i;
  for (i=index; i < itemCount; i++)
    if (listArray[i] == item)
      return i;
  
    // Now search from beginning of array to index...
  for (i = 0; i < index && i < itemCount; i++)
    if (listArray[i] == item)
      return i;
  
    // item is not in array, return -1
  return -1;
}
//- Append this new_item to the list if it doesn't already exist in it.
//- Make sure the index is unchanged.
template <class X> inline CubitBoolean DLIList<X>::append_unique(const_reference new_item)
{
    // Append new_item, if it isn't already there.
  if( where_is_item(new_item) < 0 ) 
  {
    append (new_item);
    return CUBIT_TRUE;
  }
  return CUBIT_FALSE;
}

template <class X> inline X DLIList<X>::push(X value)
{
  //- swapped last and append; current position is set new end
   append(value);
   last();
   return value;
}

template <class X> inline X DLIList<X>::pop()
{
  last();
  return remove();
}

//- Constructor: Create a list with initial size 0. The list
//- will be grown by {increment} each time it is filled. Memory for the
//- list is not allocated until the first element is inserted using
//- {insertLink}.
template <class X> inline DLIList<X>::DLIList (int sizeIn)
{
   index      = 0;
   listArray.reserve(sizeIn);
}

//- Copy Constructor
template <class X> inline DLIList<X>::DLIList(const DLIList<X>& from)
{
   if (&from != this)
   {
     index = from.index;
     listArray = from.listArray;
   }
}

//- Copy constructor for std::vector
template <class X> inline DLIList<X>::DLIList(const std::vector<X>& from)
{
    // Setup the variables
    index = 0;
    listArray = from;
}

// Destructor
template <class X> inline DLIList<X>::~DLIList()
{
}

template <class X> inline void DLIList<X>::reserve(int min_size)
{
  listArray.reserve(min_size);
}

template <class X> inline void DLIList<X>::lengthen_list(int by_how_much,
                                                  double by_what_factor)
{
    // Make a new array
  int new_size = (int) ((double)listArray.capacity() * by_what_factor) + by_how_much;
  assert(new_size > 0);
  reserve(new_size);
}

//- put new item in list after current item and make it current
template <class X> inline void DLIList<X>::insert(X new_item)
{
     // see if the list must be lengthened
   if ( listArray.size() == listArray.capacity())
   {
      lengthen_list();
   }

     // set new index
   if ( !listArray.empty() )
   {
      index++;
   }
   else
   {
      index = 0;
   }

   listArray.insert(listArray.begin()+index, new_item);
}

//- merge the input list, merge_list, with the current list, making
//- sure not to add duplicate items into the current list
template <class X> inline
void DLIList<X>::merge_unique ( const DLIList<X>& merge_list,
                                bool  merge_list_unique )
{
  this->casting_merge_unique(merge_list, merge_list_unique);
}

template <class X> inline void DLIList<X>::intersect_unordered(
  const DLIList<X>& merge_list )
{
  if ( &merge_list == this )
     return;

  intersect (merge_list);
  return;

  DLIList <X> intersect_list(merge_list);   // copy input list so can sort
  sort();
  intersect_list.sort();

  typename std::vector<X>::iterator iter1 = listArray.begin();                      // iterator for this array
  typename std::vector<X>::iterator end1 = listArray.end();               // end of this array
  typename std::vector<X>::iterator iter2 = intersect_list.listArray.begin();       // iterstor for other array
  typename std::vector<X>::iterator end2 = intersect_list.listArray.end();// end of other array
  typename std::vector<X>::iterator insertIt;                     // location of last insert
  bool first = true;

  for ( ; iter1 < end1; ++iter1 )
  {
    while (iter2 < end2 && *iter2 < *iter1)
      ++iter2;

    if (iter2 == end2)
      break;

    // items are the same and ...
    if (*iter2 == *iter1)
    {
      // is the first item or ...
      if(first)
      {
        first = false;
        insertIt = listArray.begin();
        *insertIt = *iter1;
      }
      // is not the same as the previous item
      else if(*iter1 != *insertIt)
      {
        *++insertIt = *iter1;
      }
    }
  }

  if(first)
  {
    // no intersections
    listArray.clear();
  }
  else
  {
    listArray.resize(insertIt - listArray.begin() + 1);
  }
  reset();
}

template <class X> inline void DLIList<X>::intersect ( const DLIList<X>& merge_list )
{
  if ( &merge_list == this )
     return;

  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  std::vector<X> tmp;

  for ( int i=0; i<itemCount; i++ )
  {
    if (merge_list.is_in_list(listArray[i]))
    {
      tmp.push_back(listArray[i]);
    }
  }

  this->listArray.swap(tmp);
  index = 0;
}

//template <class X> inline void DLIList<X>::intersect ( void* merge_list )
//{
//  intersect( *(DLIList<X>*)merge_list );
//}


//- remove the item at the current location and return a pointer to it.
//- The next node becomes the current node
//- Returns 0 if there are no items in list
template <class X> inline X DLIList<X>::remove ()
{
   if ( listArray.empty() )
   {
     throw std::out_of_range("Attempted link removal from empty DLIList\n");
      /*PRINT_WARNING("Attempted link removal from empty DLIList\n");*/
   }

     // save the current value
   X temp = listArray[index];

   listArray.erase(listArray.begin() + index);
   assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
   if ( index == (int)listArray.size() )
   {
      index = 0;
   }

   return temp;
}


//- remove the item at the current location and return a pointer to it.
//- used for efficiency in cases where preservation of list order is not
//- important.  moves last list item (itemCount - 1) to current index and
//- decrements itemCount.  eliminates the need to perform the list bubble
//- down (i.e. cut_link) but sacrifices list order in the process.  this
//- function should not be used when up-stream order from the removed node is
//- important.  when processing a list using this function the user should
//- reset the list to the head (index = 0) before beginning to ensure all
//- list nodes are processed properly.
//- Returns 0 if there are no items in list
template <class X> inline X DLIList<X>::extract ()
{
   if ( listArray.empty() )
   {
     throw std::out_of_range("Attempted link removal from empty DLIList\n");
      /*PRINT_WARNING("Attempted link removal from empty DLIList\n");*/
   }

     // save the current value
   X temp = listArray[index];

     // assign last node to the current index
   listArray[index] = listArray[listArray.size() - 1];

     // decrement
   listArray.resize(listArray.size() - 1);
   assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
   if ( index == (int)listArray.size() && index > 0)
        // The choices here are index at beginning or end.
        // End seems to work better when 'extract' is being used
        // with calls to 'move_to_item'.
      index--;

   return temp;
}

//+//Added so list removals don't disturb current position. PRK 05-23-94
//+//Corrected for omitting the last item in the list. PRK 09-16-94
//+//Corrected for omitting before the current position. PRK 10-07-94
//- Finds instance of item by matching value and delets first instance
//- of it from the list. The current position of the list is not changed.
//- Returns CUBIT_TRUE if the item was found and deleted, CUBIT_FALSE if not.
template <class X> inline CubitBoolean DLIList<X>::omit(const_reference old_val)
{
   int scan_index;
   int squeeze_index = 0;
   CubitBoolean found = CUBIT_FALSE;
   const int itemCount = (int)listArray.size();
   assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
   for(scan_index = 0; scan_index < itemCount; ++scan_index)
   {
      if(listArray[scan_index] == old_val)
      {
         found = CUBIT_TRUE;
         if(index == scan_index)
            index = squeeze_index - 1;
      }
      else
      {
         if(scan_index != squeeze_index)
         {
            listArray[squeeze_index] = listArray[scan_index];
            if(index == scan_index) index = squeeze_index;
         }
         ++squeeze_index;
      }
   }

   if(found)
   {
      listArray.resize(squeeze_index);
//+//   If the first item was deleted and index pointed to it, make an
//+//   adjustment here. If itemCount is zero, don't assign -1 again.
      if(index < 0)
         index = listArray.empty() ? 0 : listArray.size()-1;
   }

   return found;
}

template <class X> inline typename DLIList<X>::reference DLIList<X>::step_and_get ()
{
   if ( listArray.empty() )
   {
     throw std::out_of_range("Attempted step_and_get from empty DLIList\n");
      /*PRINT_WARNING("Attempted step_and_get from empty DLIList\n");*/
   }
   assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
   if (++index == (int)listArray.size())
      index = 0;
   return listArray[index];
}

template <class X> inline DLIList<X>& DLIList<X>::
                       operator=(const DLIList<X>& from)
{
   if (this != &from)
   {
      index = from.index;
      listArray = from.listArray;
   }
   return *this;
}

template <class X> inline DLIList<X>& DLIList<X>::
                       operator=(const std::vector<X>& from)
{
  index = 0;
  listArray = from;
  return *this;
}

template <class X> inline DLIList<X>& DLIList<X>::
                       operator+=(const DLIList<X>& from)
{
   listArray.insert(listArray.end(), from.listArray.begin(), from.listArray.end());
   return *this;
}

template <class X> inline DLIList<X>& DLIList<X>::
                       operator+=(const std::vector<X>& from)
{
  listArray.insert(listArray.end(), from.begin(), from.end());
  return *this;
}

template <class X> inline DLIList<X>& DLIList<X>::
                       operator-=(const DLIList<X>& from)
{
    // step through items in from list, removing them from this list.
   for (int i = from.listArray.size(); i--; )
   {
     // quit early if this list is empty.
     if (listArray.empty())
       break;
     remove_all_with_value(from.listArray[i]);
   }
   return *this;
}

template <class X> inline int DLIList<X>::operator==(const DLIList<X> &from)
{
  if(listArray.size() != from.listArray.size())
     return CUBIT_FALSE;
  DLIList<X> temp_list = from;
  for( size_t i = 0; i < listArray.size(); i++)
     if(temp_list.move_to(listArray[i]))
        temp_list.remove();
  return temp_list.listArray.size() == 0;
}
template <class X> inline int DLIList<X>::operator!=(const DLIList<X> &from)
{
  return !( *this == from );
}

// Sorts list from low to high value, according to the > operator
// of the list type.
// List is sorted using a standard Heap Sort algorithm ("Algorithms in C++",
// Robert Sedgewick).
template <class X> inline void DLIList<X>::sort(typename DLIList<X>::SortFunction f)
{
    // Only sort it if there is more than one
    // item in the list
  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  if (itemCount > 1)
  {

    //std::sort(listArray.begin(),listArray.end(),f);
    //return;

    int mid = (itemCount >> 1) + 1;
    int ir = itemCount;
    X temp_element;

      // You loop until ir is 1 (ir = iterations remaining)
    while(CUBIT_TRUE)
    {
      if (mid > 1)
      {
        mid--;
        temp_element = listArray[mid - 1];
      }
      else
      {
        ir--;
        temp_element = listArray[ir];
        listArray[ir] = listArray[0];
        if (ir == 1)
        {
          listArray[0] = temp_element;
          return;
        }
      }

      int i = mid;
      int j = mid + mid;

      while (j <= ir)
      {
        if (j < ir)
        {
          if (f(listArray[j], listArray[j - 1]) >= 0)
            j++;
        }
        if (f(listArray[j - 1], temp_element) >= 0)
        {
          listArray[i - 1] = listArray[j - 1];
          i = j;
          j += j;
        }
        else
        {
          j = ir + 1;
        }
      }
      listArray[i - 1] = temp_element;
    }
  }
}

template <class X> inline void DLIList<X>::sort()
{
  const int itemCount = (int)listArray.size();
  assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  // Only sort it if there is more than one
  // item in the list
  if (itemCount > 1)
  {
    //std::sort(listArray.begin(),listArray.end(),DLIListSorter<X>());
    //return;

    int mid = (itemCount >> 1) + 1;
    int ir = itemCount;
    X temp_element;

      // You loop until ir is 1 (ir = iterations remaining)
    while(CUBIT_TRUE)
    {
      if (mid > 1)
      {
        mid--;
        temp_element = listArray[mid - 1];
      }
      else
      {
        ir--;
        temp_element = listArray[ir];
        listArray[ir] = listArray[0];
        if (ir == 1)
        {
          listArray[0] = temp_element;
          return;
        }
      }

      int i = mid;
      int j = mid + mid;

      while (j <= ir)
      {
        if (j < ir)
        {
          if (listArray[j] >= listArray[j - 1])
            j++;
        }
        if (listArray[j - 1] >= temp_element)
        {
          listArray[i - 1] = listArray[j - 1];
          i = j;
          j += j;
        }
        else
        {
          j = ir + 1;
        }
      }
      listArray[i - 1] = temp_element;
    }
  }

}

template <class X> inline void DLIList<X>::reverse()
{
  int front = 0;
  assert((int)listArray.size() >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
  int tail  = (int)listArray.size() - 1;
  X temp;

  while (front < tail)
  {
     temp             = listArray[front];
     listArray[front] = listArray[tail];
     listArray[tail]  = temp;
     tail--;
     front++;
  }
}

template <class X> inline int DLIList<X>::memory_use()
{
   // report amount of memory allocated

   int sizeIn = listArray.capacity() * sizeof(X);

//   if (verbose_boolean)
//   {
//      PRINT_INFO("      DLIList: %d bytes\n",sizeIn);
//   }

   return sizeIn;
}

template <class X> inline void DLIList<X>::copy_to(X *other_array)
    //- copy this list's listArray into other_array
{
  if(other_array == 0)
    throw std::invalid_argument("Array is NULL");

  if (listArray.size() > 0)
  {
    const int itemCount = (int)listArray.size();
    assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
    for (int i = 0; i < itemCount; i++)
      other_array[i] = listArray[i];
  }
}

template <class X> inline void DLIList<X>::copy_from(X *other_array, const int other_size)
  //- copy other_array into listArray
{
  if(other_array == 0)
    throw std::invalid_argument("Array is NULL");

  listArray.clear();
  listArray.insert(listArray.end(), other_array, other_array+other_size);
  index = 0;
}

template <class X> inline CubitBoolean DLIList<X>::move_to_nearby(const X item)
{
//  if (nullItem && (X)nullItem == item)
//     return CUBIT_FALSE;
//  else
  if (listArray.empty())
     return CUBIT_FALSE;
  else
  {
    const int itemCount = (int)listArray.size();
    assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer
    typename std::vector<X>::iterator ptr_up = listArray.begin() + index;
    if (*ptr_up == item)
       return CUBIT_TRUE;

    int i_up, i_down;
    i_up = i_down = index;
    typename std::vector<X>::iterator ptr_down = ptr_up;
    while (1)
    {
        // check forward in the list increment
      if ( ++i_up < itemCount )
         ptr_up++;
      else
      {
        i_up = 0;
        ptr_up = listArray.begin();
      }
        // check
      if ( *ptr_up == item )
      {
        index = i_up;
        return CUBIT_TRUE;
      }
      if ( i_up == i_down )
      {
        return CUBIT_FALSE;
      }

        // check backward in the list
        //  increment
      if ( --i_down >= 0 )
         ptr_down--;
      else
      {
        i_down = itemCount-1;
        ptr_down = listArray.begin()+ i_down;
      }
        // check
      if ( *ptr_down == item )
      {
        index = i_down;
        return CUBIT_TRUE;
      }
      if ( i_up == i_down )
      {
        return CUBIT_FALSE;
      }

    }
  }
}

template <class X> inline int DLIList<X>::distance_to_nearby(const X body)
{
//  if (nullItem && (X)nullItem == body)
//     return CUBIT_FALSE;
//  else
  {
    int old_index = index;
    move_to_nearby( body );
    int distance = abs(index - old_index);
    if (distance > listArray.size() / 2)
       distance = listArray.size() - distance;
    index = old_index;
    return distance;
  }
}

template <class X> inline CubitBoolean DLIList<X>::move_between(X item1, X item2)
{
  {
    if ( listArray.empty() )
       return CUBIT_FALSE;

    const int itemCount = (int)listArray.size();
    assert(itemCount >= 0); // Assume that the listArray size does not exceed the maximum value for a signed integer

    for ( int i = 0; i < itemCount; i++ )
    {
      if ( listArray[i] == item1 )
      {
          //  dance around looking for item2
        if ( i+1 < itemCount ) {
          if ( listArray[i+1] == item2 ) {
            index = i+1;
            return CUBIT_TRUE;
          }
        }
        if ( i > 0 ) {
          if ( listArray[i-1] == item2 ) {
            index = i;
            return CUBIT_TRUE;
          }
        }
        if ( ( i+1 == itemCount && listArray[0] == item2 )
             || ( i == 0 && listArray[itemCount-1] == item2 ) )
        {
          index = 0;
          return CUBIT_TRUE;
        }
      }
    }
    return CUBIT_FALSE;
  }
}

// Removes every instance of 'val' in list.
// Set to beginning of list after this call.
template <class X> inline void DLIList<X>::uniquify_unordered()
{
  const size_t itemCount = listArray.size();
  if ( itemCount < 2 )
    return;

  sort();

  listArray.erase(std::unique(listArray.begin(), listArray.end()), listArray.end());

  index = 0;
}
// Removes every instance of 'val' in list.
// Set to beginning of list after this call.
template <class X> inline void DLIList<X>::uniquify_unordered_checked()
{
  const size_t itemCount = listArray.size();
  if ( itemCount < 2 )
    return;

  sort();

  size_t j = 1;
  size_t i = 0;

  while (j < itemCount)
  {
    if (listArray[i] != listArray[j])
      listArray[++i] = listArray[j++];
    else
      j++;
  }

  listArray.resize(i + 1);
  index = 0;
}

template <class X> inline void DLIList<X>::uniquify_ordered()
{
  std::set<X> encountered;
  typename std::vector<X>::iterator read_iter, write_iter, end_iter = listArray.end();

    // To avoid copying the array onto itself in the case
    // where the list contains no duplicates, loop twice.

    // Find first duplicate entry.
  for ( read_iter = listArray.begin(); read_iter != end_iter; ++read_iter )
    if ( ! encountered.insert(*read_iter).second )
      break;

    // Now compact array, removing duplicates.  If there
    // are no duplicates, this loop will not run (read_iter == end_iter).
  for ( write_iter = read_iter; read_iter != end_iter; ++read_iter )
    if ( encountered.insert(*read_iter).second )
      *(write_iter++) = *read_iter;

  listArray.resize(write_iter - listArray.begin());
  index = 0;
}

template <class X> inline const std::vector<X>& DLIList<X>::as_vector() const
{
  return listArray;
}

template <class X> class DLIListIterator
{
  friend class DLIList<X>;
public:
    // constructor
  DLIListIterator() :
      mIndex(0),
      dlIList(NULL)
    {}
  
    // destructor
  virtual ~DLIListIterator()
    {}
  
  void watch( const DLIList <X> *dl_i_list )
    {
      dlIList = dl_i_list;
      mIndex = dlIList->index;
    }
  
  void reset()
    { mIndex = 0; }
  
  void step( int n = 1 ) 
    {
      if (!size())
        mIndex = 0;
      else
      {
        mIndex += n;
        while (mIndex < 0)
          mIndex += dlIList->size();
        mIndex %= dlIList->size();
      }
    }
  
  int size() const
    { return dlIList ? dlIList->size() : 0; }
  
  X get() const
    { return next(0); }
  X next( int n = 1 ) const;
  X get_and_step( int n = 1 ) 
    {
      X temp = get();
      step( n );
      return temp;
    }
  
    //- Moves to the next instance of this value, wrapping if necessary
  CubitBoolean move_to(X item)
    { 
      mIndex = where_is_item( item );
      return mIndex >= 0 ? CUBIT_TRUE : CUBIT_FALSE; 
    }
  
    //- Return True if item is in the list, false otherwise.
  CubitBoolean is_in_list(X item) const
    { return where_is_item(item) >= 0 ? CUBIT_TRUE : CUBIT_FALSE; }
  
    // Returns CUBIT_TRUE if we're pointing at the last item in the list.
  CubitBoolean is_at_end() const
    {
      if (size() == 0 || mIndex == size() - 1)
        return CUBIT_TRUE;
      return CUBIT_FALSE;
    }
  
    //- returns CUBIT_TRUE if we're pointing at the first item in the list.
  CubitBoolean is_at_beginning() const
    {
      if (!mIndex || mIndex == size())
        return CUBIT_TRUE;
      return CUBIT_FALSE;
    }
  
protected:
    // utility functions
  int where_is_item( X item ) const
    { return dlIList ? dlIList->where_is_item( item ) : -1; }
  
    // data
  int mIndex;
  const DLIList<X> *dlIList;
};

template <class X> 
inline X DLIListIterator<X>::next( int n ) const
{
  int size_loc = size();
  if ( size_loc == 0 )
    return NULL;
  int index_loc = mIndex + n;
  while ( index_loc < 0 )
    index_loc += size_loc;
  while ( index_loc >= size_loc )
    index_loc -= size_loc;
  
    // if dlIList == NULL, then size == 0 and returned already 
  return dlIList->listArray[index_loc];
}

template <class X>
inline typename DLIList<X>::iterator DLIList<X>::begin()
{
  return this->listArray.begin();
}

template <class X>
inline typename DLIList<X>::const_iterator DLIList<X>::begin() const
{
  return this->listArray.begin();
}

template <class X>
inline typename DLIList<X>::iterator DLIList<X>::end()
{
  return this->listArray.end();
}

template <class X>
inline typename DLIList<X>::const_iterator DLIList<X>::end() const
{
  return this->listArray.end();
}

template <class X> inline void DLIList<X>::swap(std::vector<X>& other)
{
  this->listArray.swap(other);
}


#endif //- DLILIST_HPP