simplear.h

Go to the documentation of this file.

/**
 * \file simplear.h <mi32/simplear.h>
 * \brief Definitions for SIMPLE_ARRAY template
 *
 * \if NODOC
 * $Id: simplear.h_v 1.44 2004/04/16 21:50:03 scowan Exp $
 *
 * $Log: simplear.h_v $
 * Revision 1.44  2004/04/16 21:50:03  scowan
 * Added locate method.
 *
 * Revision 1.43  2004/04/01 21:33:44  mju
 * Add GetLast and RemoveLast methods.
 *
 * Revision 1.42  2003/09/22 19:09:40  dwilliss
 * Version of array index operator that takes long for SUN64 to avoid gcc
 * error
 *
 * Revision 1.41  2003/09/15 13:49:56  fileserver!dwilliss
 * Doxygen
 *
 * Revision 1.40  2003/07/28 13:41:45  mju
 * Remove deprecated methods.
 *
 * Revision 1.39  2003/07/25 20:58:42  mju
 * Add Assign() method, deprecate old SetItems().
 * Add SetItems variant which does not shrink array.
 *
 * Revision 1.38  2003/06/24 21:47:30  scowan
 * Compiler optimization error also in remove fast method.
 *
 * Revision 1.37  2003/06/18 14:27:26  mju
 * Fix compiler optimization bug in RemoveItem by decrement numitems before memmove.
 *
 * Revision 1.36  2003/06/17 21:49:27  mju
 * *** empty log message ***
 *
 * Revision 1.35  2003/04/09 19:12:52  dwilliss
 * Don't use _T in templates.  Mac's ctype defines a global _T
 *
 * Revision 1.34  2002/10/03 16:49:19  mju
 * Remove allocincrement stuff and deprecate method to set.
 *
 * Revision 1.33  2002/09/30 17:32:57  mju
 * Remove redundant swapitems methods as is equivalent to Reverse().
 *
 * Revision 1.32  2002/09/12 14:54:24  scowan
 * Added has item method.
 *
 * Revision 1.31  2002/07/05 21:53:53  scowan
 * resize memset in case _CT is an object with deprecated memset stuff.
 *
 * Revision 1.30  2002/06/20 15:51:51  scowan
 * Prevent ABR.
 *
 * Revision 1.29  2002/04/02 18:24:29  mju
 * Add IsEmpty() method.
 * Clarify what will be cleared when 'clear' set to true in Resize().
 *
 * Revision 1.28  2002/03/18 15:19:21  dwilliss
 * Need to include stdansic.h if we want to be sure memcpy has a prototype
 *
 * Revision 1.27  2001/12/18 17:40:31  scowan
 * Set allocincrement in constructors.
 *
 * Revision 1.26  2001/10/30 16:52:50  dwilliss
 * Documented what the CompFunc for Sort() is expected to return
 *
 * Revision 1.25  2001/09/07 17:15:22  scowan
 * Change sort compare function to return int.
 *
 * Revision 1.24  2001/05/24 20:50:34  scowan
 * Adjuect some method names.
 *
 * Revision 1.23  2001/05/24 18:00:09  scowan
 * Added multiple helper methods.
 *
 * Revision 1.22  2001/02/06 17:35:26  mju
 * Add ReserveExc and AppendExc methods.
 *
 * Revision 1.21  2001/01/30 15:01:10  mju
 * Add Get/SetItem methods as array/cast operators confused if array type is pointer.
 *
 * Revision 1.20  2000/12/04 16:31:25  mju
 * Fix genitor 'end ignore' tag.
 *
 * Revision 1.19  2000/10/13 16:45:07  dwilliss
 * Added array operater overloads taking long on Mac only to avoid stupid
 * ambiguous function overload error
 *
 * Revision 1.18  2000/08/23 15:53:16  scowan
 * Do an bouns check on Clear Items().
 *
 * Revision 1.17  2000/08/18 14:41:03  scowan
 * Removed additional array operators because the other platforms went Huh!?!?
 * Stupid VC6.0.
 *
 * Revision 1.16  2000/08/17 16:01:00  scowan
 * Added unsigned int versions of array operator methods, was causeing a
 * strange error to occur if an unsigned int was used to access a simple array
 * entry.
 *
 * Revision 1.15  2000/08/09 13:46:54  mju
 * Add Append() methods using C-style array and SIMPLE_ARRAY.
 *
 * Revision 1.14  2000/08/02 21:43:38  mju
 * Change Resize() to only clear new entries if keepold 'true'.
 *
 * Revision 1.13  2000/08/01 14:04:54  dwilliss
 * Added a Copy() method.
 * Fixed error in methods taking/returning SIMPLE_ARRAY.  Needs to specify
 *   the template type.
 *
 * Revision 1.12  2000/07/27 17:18:14  mju
 * Retire SetNumItems().
 *
 * Revision 1.11  2000/07/27 15:40:36  dwilliss
 * Wrote Attach()/Detach() methods
 *
 * Revision 1.10  2000/07/26 16:08:36  dwilliss
 * Fixed compile error in Free()
 *
 * Revision 1.9  2000/07/21 22:25:36  scowan
 * Added Free() method
 *
 * Revision 1.8  2000/07/18 20:56:57  mju
 * Add Resize() and deprecate SetNumItems().
 *
 * Revision 1.7  2000/06/22 14:52:55  mju
 * Fix ClearItems to not clear past ending item.
 *
 * Revision 1.5  2000/06/21 16:39:24  scowan
 * Set items must return a value error fix.
 *
 * Revision 1.3  2000/06/21 15:23:31  scowan
 * Added swap bytes method.
 *
 * Revision 1.2  2000/05/11 20:33:22  mju
 * Change GetSizeInBytes to return required size, not allocated size.
 * Add Swap() method.
 *
 * Revision 1.1  2000/05/10 13:26:15  mju
 * Initial revision
 *
 * \endif
**/

#ifndef  INC_MI32_SIMPLEAR_H
#define  INC_MI32_SIMPLEAR_H

#ifndef  INC_MI32_MIODEFNS_H
#include <mi32/miodefns.h>    //! For MmAlloc/Realloc/Free defns
#endif

#ifndef  INC_MI32_STDANSIC_H
#include <mi32/stdansic.h>    //! memcpy()
#endif

#ifndef  INC_MI32_MEMBUF_H
#include <mi32/membuf.h>      //! For SwapBytes() defn
#endif

//! Simple array template.
//!
//! This template is designed to contain an array of items which can be allocated
//! using MmAlloc/MmRealloc.  The primary purpose of this template is to replace
//! allocated arrays where direct access to both array elements and the ability
//! to access a pointer to the first element (as for a C array) is required.
//! Do not use this template with classes which require constructors or have
//! virtual methods or which do not have compiler-generated assignment operators.
//!
//! For maximum efficiency, only minimal validation of access to array elements is performed.
//! No initialization of array items is performed by the template.
//!
//! For doubles and objects based on doubles, use DOUBLE_ARRAY<> in mi32/doublear.h
//!
//! Instances of this class are passed to DLLs, so do not add or remove members.

template <class _CT> class SIMPLE_ARRAY {
   public:

      //! Default constructor, creates empty array.
      SIMPLE_ARRAY (
         ):
         m_items(0),
         m_numitems(0),
         m_numalloc(0),
         m_spare(0)
         { }

      //! Copy constructor.
      SIMPLE_ARRAY (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         MmAllocExc((void**)&m_items,rhs.m_numalloc*sizeof(_CT));
         m_numalloc = rhs.m_numalloc;
         memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
         m_numitems = rhs.m_numitems;
         m_spare = rhs.m_spare;
         }

      //! Destructor.
      ~SIMPLE_ARRAY (
         ) {
         if (m_items != 0) free(m_items);
         }

      //! Assignment.
      SIMPLE_ARRAY<_CT>& operator= (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         if (this != &rhs) {
            if (m_numalloc < rhs.m_numalloc) {
               //! Free the old array instead of using realloc to avoid expensive copy.
               MmFree(m_items);
               MmAllocExc((void**)&m_items,rhs.m_numalloc*sizeof(_CT));
               m_numalloc = rhs.m_numalloc;
               }
            memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
            m_numitems = rhs.m_numitems;
            }
         return (*this);
         }

      //! Equality operator.
      bool operator== (
         const SIMPLE_ARRAY<_CT>& rhs
         ) const {
         if (m_numitems != rhs.m_numitems) return (false);
         if (m_numitems == 0) return (true);
         return (memcmp(m_items,rhs.m_items,m_numitems*sizeof(_CT)) == 0);
         }

      //! Inequality operator.
      bool operator!= (
         const SIMPLE_ARRAY<_CT>& rhs
         ) const {
         return (!operator==(rhs));
         }

      //! Cast to const array of template type.
      operator const _CT*(
         ) const {
         return (m_items);
         }

      //! Cast to array of template type.
      operator _CT*(
         ) {
         return (m_items);
         }

      //! Read (const) access to array element.
      //!
      //! @note Does not verify that index is within valid range.
      const _CT& operator[] (
         int index
         ) const {
         return (m_items[index]);
         }

      //! Write (non-const) access to array element.
      //!
      //! @note Does not verify that index is within valid range.
      _CT& operator[] (
         int index
         ) {
         return (m_items[index]);
         }

      #ifndef GENERATING_DOXYGEN_OUTPUT
   #if defined(MAC_NATIVE) || defined(SUN64)
      // Fixes ambiguity error on Macintosh.
      
      // Read (const) access to array element.
      //
      // @note Does not verify that index is within valid range.
      const _CT& operator[] (
         long index
         ) const {
         return (m_items[index]);
         }

      // Write (non-const) access to array element.
      //
      // @note Does not verify that index is within valid range.
      _CT& operator[] (
         long index
         ) {
         return (m_items[index]);
         }
   #endif
      #endif //!< GENERATING_DOXYGEN_OUTPUT

      //! Append item to end of array, extending if necessary.
      ERRVALUE Append (
         const _CT& item
         ) {
         if (m_numitems >= m_numalloc) {
            int err;
            if ((err = Reserve(MAX(16,2*m_numitems))) < 0) return (err);
            }
         m_items[m_numitems++] = item;
         return (0);
         }

      //! Append items from C array, reserving space if needed.
      ERRVALUE Append (
         const _CT *items,                //!< Items to append
         int numitems                     //!< Number of items to append
         ) {
         int err;
         if ((err = Reserve(m_numitems+numitems)) < 0) return (err);
         memcpy(m_items+m_numitems,items,numitems*sizeof(_CT));
         m_numitems += numitems;
         return (0);
         }

      //! Append items from SIMPLE_ARRAY reserving space if needed.
      ERRVALUE Append (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         int err;
         if ((err = Reserve(m_numitems+rhs.m_numitems)) < 0) return (err);
         memcpy(m_items+m_numitems,rhs.m_items,rhs.m_numitems*sizeof(_CT));
         m_numitems += rhs.m_numitems;
         return (0);
         }

      //! Append item to end of array, extending if necessary.
      //! Throws exception if out of memory.
      void AppendExc (
         const _CT& item
         ) {
         if (m_numitems >= m_numalloc) {
            ReserveExc(MAX(16,2*m_numitems));
            }
         m_items[m_numitems++] = item;
         return;
         }

      //! Append items from C array, reserving space if needed.
      //! Throws exception if out of memory.
      void AppendExc (
         const _CT *items,                //!< Items to append
         int numitems                     //!< Number of items to append
         ) {
         ReserveExc(m_numitems+numitems);
         memcpy(m_items+m_numitems,items,numitems*sizeof(_CT));
         m_numitems += numitems;
         return;
         }

      //! Append items from SIMPLE_ARRAY reserving space if needed.
      //! Throws exception if out of memory.
      void AppendExc (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         ReserveExc(m_numitems+rhs.m_numitems);
         memcpy(m_items+m_numitems,rhs.m_items,rhs.m_numitems*sizeof(_CT));
         m_numitems += rhs.m_numitems;
         return;
         }

      //! Append item to end of array if unique, extending if necessary.
      ERRVALUE AppendUnique (
         const _CT& item
         ) {
         INT32 j;
         for (j = 0;(j < m_numitems);++j) {
            if (m_items[j] == item) break;
            }
         return ((j == m_numitems) ? Append(item) : 0);
         }

      //! Append item to end of array if unique, extending if necessary.
      //! Throws exception if out of memory.
      void AppendUniqueExc (
         const _CT& item
         ) {
         INT32 j;
         for (j = 0;(j < m_numitems);++j) {
            if (m_items[j] == item) break;
            }
         if (j == m_numitems) AppendExc(item);
         return;
         }

      //! Assign from C array, reserving space if needed.
      //! Resizes the array to the specified number of items.
      ERRVALUE Assign (
         const _CT *items,                //!< Items to copy to array
         int numitems                     //!< Number of items to copy
         ) {
         int err;
         if ((err = Reserve(numitems)) < 0) return (err);
         memcpy(m_items,items,numitems*sizeof(_CT));
         m_numitems = numitems;
         return (0);
         }

      //! Attach a buffer to the SIMPLE_ARRAY.
      //! After passing a buffer to Attach(), the SIMPLE_ARRAY "<b>owns</b>" the
      //! buffer and will free it in its destructor.  
      //! @param items Reference to a pointer to the templated data type.
      //! The reason it's a reference is that after recording the pointer,
      //! Attach() will set <i>your</i> pointer to 0.  This will prevent you
      //! from accidently freeing a pointer you no longer own.  If you want
      //! it back, call the Detach() method
      void Attach (
         _CT *& items,                 
         int numitems               //!< Number of items in array
         ) {
         Free();
         m_items = items;
         m_numitems = m_numalloc = numitems;
         items = 0;
         return;
         }


      //! Clear the array, does not free resources.
      void Clear (
         ) {
         m_numitems = 0;
         return;
         }

      //! Clear items in the array
      void ClearItems (
         int start = 0,
         int end = -1                  //!< Default -1, use number of items
         ) {
         if (end < start) end = m_numitems - 1;
         if (end >= start) {     //! Start might be larger than end
            memset(m_items + start, 0, (end - start + 1) * sizeof(_CT));
            }
         return;
         }


      //! Copy the contents of another SIMPLE_ARRAY.
      //! Same as assignment, but returns an error code instead of throwing an exception.
      ERRVALUE Copy (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         if (this != &rhs) {
            if (m_numalloc < rhs.m_numalloc) {
               //! Free the old array instead of using realloc to avoid expensive copy.
               MmFree(m_items);
               ERRVALUE err = MmAlloc((void**)&m_items,rhs.m_numalloc*sizeof(_CT));
               if (err < 0) return (err);
               m_numalloc = rhs.m_numalloc;
               }
            memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
            m_numitems = rhs.m_numitems;
            }
         return (0);
         }

      //! Detach the buffer from the SIMPLE_ARRAY.
      //!
      //! This turns ownership of the buffer over to the caller, who is then
      //! responsibile for seeing that it gets disposed of.
      //! After calling Detach(), the SIMPLE_ARRAY will behave as if it had
      //! just been constructed.  In other words, it will be a NULL pointer
      //! pointing to 0 items.
      //! This means that if you want to know how many items are in the
      //! array returned, you'd better find out @{before} you call Detach()!
      _CT* Detach (
         ) {
         _CT* ret = m_items;
         m_numalloc = m_numitems = 0;
         m_items = 0;
         return (ret);
         }

      //! Free the array.
      void Free (
         ) {
         m_numalloc = m_numitems = 0;
         MmFree(m_items);
         return;
         }

      //! Get array item, does not verify index range.
      const _CT& GetItem (
         int index
         ) const { return (m_items[index]); }

      //! Get last item in array.
      //! Does not verify that array is non-empty.
      const _CT& GetLast (
         ) const { return (m_items[m_numitems-1]); }

      //! Get maximum number of items in array.
      int GetMaxItems (
         ) const { return (m_numalloc); }

      //! Get number of items in array.
      int GetNumItems (
         ) const { return (m_numitems); }

      //! Get size of array required to hold current number of items in bytes.
      int GetSizeInBytes (
         ) const { return (m_numitems*sizeof(_CT)); }

      //! Determine if an item exists in the array.
      //! Item must have a valid operator==()
      //! @return 'True' if item found
      bool HasItem (
         const _CT& item
         ) const {
         for (INT32 i = 0;(i < m_numitems);++i) {
            if (m_items[i] == item) return (true);
            }
         return (false);
         }

      //! Insert multiple items into the array
      void InsertItems (
         int start,
         int num = 1
         ) {
         ReserveExc(m_numitems+num);
         memmove(&m_items[start + num], &m_items[start], (m_numitems - start) * sizeof(_CT));
         m_numitems += num;
         return;
         }

      //! Determine if array is empty.
      bool IsEmpty (
         ) const { return (GetNumItems() == 0); }

      //! Binary search for an entry or the place where the entry should be
      //! _Pr is a functor that returns -1 if 1st item < 2nd, 1 if 1st > 2nd, 0 if 1st == 2nd
      //! 'item' is the first parameter passed to the _Pr functor
      //! @return Position that is equal or immediately less than 'item', or GetNumItems() if item > all list items
      template<class _Pr1>
      INT32 Locate (
         const _CT& item,
         _Pr1 _Pr
         ) const {
         if (m_numitems == 0) return (0);
         INT32 l = 0, r = m_numitems-1, q;
         do {
            q = (l+r)/2;
            int test = _Pr(item, m_items[q]);
            if (test == 0) return (q);
            if (test < 0) {
               r = q - 1;
               q = r;
               }
            else {
               l = q + 1;
               q = l;
               }
            } while (l <= r);
         return (q);
         }

      //! Remove duplicate entries in the list, assume not sorted    
      void RemoveDuplicates (
         ) {
         for (INT32 i = 0;(i < m_numitems);++i) {
            for (INT32 k = i+1;(k < m_numitems);++k) {
               if (m_items[i] == m_items[k]) {
                  m_items[k] = m_items[m_numitems-1];
                  m_numitems --;
                  k --;
                  }
               }
            }
         return;
         }     

      //! Remove an item by placing the end item in its place.
      void RemoveFast (
         INT32 item
         ) {
         if (item >= 0 && item < m_numitems) {
            m_numitems --;
            m_items[item] = m_items[m_numitems];
            }
         return;
         }

      //! Remove item at specified index, maintaining order.
      //! Note that this is inefficient for large arrays.
      void RemoveItem (
         INT32 item
         ) {
         if (item < m_numitems && item >= 0) {
            --m_numitems;
            if (item < m_numitems) { memmove(&m_items[item], &m_items[item+1], (m_numitems - item) * sizeof(_CT)); }
            }
         return;
         }

      //! Remove last item(s) from array.
      void RemoveLast (
         INT32 count = 1                           //!< Number of items to remove
         ) {
         if (count > m_numitems)
            m_numitems = 0;
         else
            m_numitems -= count;
         return;
         }

      //! Remove items matching the item passed in.  _CT must have a operator==() defined
      //! Maintains item order
      //! @return 'True' if one or more items was removed
      bool RemoveMatchingItems (
         const _CT& item
         ) {
         INT32 i, num;
         for (num = i = 0;(i < m_numitems); ++i) {
            if (m_items[i] != item) {
               if (num < i) m_items[num] = m_items[i];      // Avoid expensive copy if not needed
               num ++;
               }
            }
         bool retval = (m_numitems != num);
         m_numitems = num;
         return (retval);
         }

      //! Reserve space in array for up to specified number of items.
      ERRVALUE Reserve (
         int newmaxitems,                 //!< New maximum number of items
         bool clear = false               //!< Clear the array by resetting number of items to 0
         ) {
         if (clear) m_numitems = 0;
         if (newmaxitems > m_numalloc) {
            int err;
            if (m_numitems == 0) {
               //! Free the old array to avoid expensive copy in reallocation
               MmFree(m_items);
               }
            if ((err = MmRealloc((void**)&m_items,newmaxitems*sizeof(_CT))) < 0) return (err);
            m_numalloc = newmaxitems;
            }
         return (0);
         }

      //! Reserve space in array for up to specified number of items.
      //! Throws exception if out of memory.
      void ReserveExc (
         int newmaxitems,                 //!< New maximum number of items
         bool clear = false               //!< Clear the array by resetting number of items to 0
         ) {
         if (clear) m_numitems = 0;
         if (newmaxitems > m_numalloc) {
            if (m_numitems == 0) {
               //! Free the old array to avoid expensive copy in reallocation
               MmFree(m_items);
               }
            MmReallocExc((void**)&m_items,newmaxitems*sizeof(_CT));
            m_numalloc = newmaxitems;
            }
         return;
         }

      //! Resize array to specified number of items.
      //! If the new size is larger than the previous size and the array is
      //! not cleared the new array entries will have indeterminant values.
      ERRVALUE Resize (
         int numitems,                    //!< New number of items desired
         bool keepold = true,             //!< Keep old array entries
         bool clear = false               //!< Clear new array items to zeros
         ) {
         int err;
         if ((err = Reserve(numitems,!keepold)) < 0) return (err);
         if (clear && numitems > m_numitems) memset(static_cast<void*>(m_items+m_numitems),0,(numitems-m_numitems)*sizeof(_CT));
         m_numitems = numitems;
         return (0);
         }

      //! Reverse order of items in array.
      void Reverse (
         ) {
         for (int i = 0; (i < m_numitems/2); ++i) {
            _CT temp(m_items[i]);
            m_items[i] = m_items[m_numitems-i-1];
            m_items[m_numitems-i-1] = temp;
            }
         return;
         }

      //! Set single item, does not verify index range.
      void SetItem (
         int index,                       //!< Item index, must be in range from 0 to NumItems-1
         const _CT& item                     //!< Item value to set
         ) {
         m_items[index] = item;
         }

      //! Set array items from C array, expanding if needed.
      //! Will not reduce the number of items in the array.
      ERRVALUE SetItems (
         int firstitem,                   //!< First array item to replace
         const _CT *items,                //!< Items to copy to array
         int numitems                     //!< Number of items to copy
         ) {
         int err;
         if ((err = Reserve(firstitem+numitems)) < 0) return (err);
         memcpy(m_items+firstitem,items,numitems*sizeof(_CT));
         if (m_numitems < firstitem + numitems) m_numitems = firstitem + numitems;
         return (0);
         }

      //! Sort the items in the array.
      //! CompFunc should return 1 if the first item < the 2nd item
      //! Otherwise, return 0.
      void Sort (
         int (*CompFunc)(_CT*, _CT*, void*),
         void *data = 0
         ) {
         //! Compare function cannot return 'bool', must be 'int'.
         heapsort(m_items, m_numitems, sizeof(_CT), reinterpret_cast<int (*)(void*, void*, void*)>(CompFunc), data);
         }
         
      //! Swap (exchange) two SIMPLE_ARRAYs.
      //! This exchanges the internal buffers so minimal copying is performed for efficiency.
      void Swap (
         SIMPLE_ARRAY<_CT>& rhs
         ) {
         _CT *t_items = m_items;
         m_items = rhs.m_items;
         rhs.m_items = t_items;
         int t_numitems = m_numitems;
         m_numitems = rhs.m_numitems;
         rhs.m_numitems = t_numitems;
         int t_numalloc = m_numalloc;
         m_numalloc = rhs.m_numalloc;
         rhs.m_numalloc = t_numalloc;
         }

      //! Swap bytes in a SIMPLE_ARRAY, assume that there is an overload to swap a _CT
      void SwapBytes (
         ) {
         for (int i = 0;(i < m_numitems);++i) ::SwapBytes(m_items[i]);
         }

   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      _CT *m_items;                       //!< The actual array
      int m_numitems;                     //!< Number of valid items
      int m_numalloc;                     //!< Number of items allocated
      int m_spare;
      #endif // GENERATING_DOXYGEN_OUTPUT

   };

#endif   //!< INC_MI32_SIMPLEAR_H

---