mi32/simplear.h

Go to the documentation of this file.

#ifndef  INC_MI32_SIMPLEAR_H
#define  INC_MI32_SIMPLEAR_H

#ifndef  INC_MI32_MEMALLOC_H
#include <mi32/memalloc.h>    // For MmAlloc/Realloc/Free defns
#endif

#ifndef  INC_MI32_SORT_H
#include <mi32/sort.h>
#endif

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

#ifndef  INC_MEMORY_H
#ifndef GENERATING_DOXYGEN_OUTPUT
#include <memory.h>           // memcpy()
#define  INC_MEMORY_H
#endif
#endif

#ifndef  INC_STRING_H
#ifndef GENERATING_DOXYGEN_OUTPUT
#include <string.h>           // memmove/memset
#define  INC_STRING_H
#endif
#endif


template <class _CT> class SIMPLE_ARRAY {
   public:

      SIMPLE_ARRAY (
         ):
         m_items(0),
         m_numitems(0),
         m_numalloc(0),
         m_RefCount(1)
         { }

      SIMPLE_ARRAY (
         const SIMPLE_ARRAY<_CT>& rhs
         ):
         m_items(0),
         m_numitems(0),
         m_numalloc(0),
         m_RefCount(1)
         {
         if (rhs.m_numitems > 0) {
            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;
            }
         }

      ~SIMPLE_ARRAY (
         ) {
         if (m_items != 0) {
            free(m_items);
            m_numitems = 0;
            }
         }

      SIMPLE_ARRAY<_CT>& operator= (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         if (this != &rhs) {
            if (m_numalloc < rhs.m_numitems) {
               Free();
               MmAllocExc((void**)&m_items,rhs.m_numitems*sizeof(_CT));
               m_numalloc = rhs.m_numitems;
               }
            memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
            m_numitems = rhs.m_numitems;
            }
         return (*this);
         }

      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);
         }

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

      operator const _CT*(
         ) const {
         return (m_items);
         }

      operator _CT*(
         ) {
         return (m_items);
         }

      template <typename _IDXTYPE> const _CT& operator[] (
         _IDXTYPE index
         ) const {
         return (m_items[index]);
         }

      template <typename _IDXTYPE> _CT& operator[] (
         _IDXTYPE index
         ) {
         return (m_items[index]);
         }

      void AddRef (
         ) { ++m_RefCount; }

      ERRVALUE Append (
         const _CT& item
         ) {
         if (m_numitems >= m_numalloc) {
            ERRVALUE err;
            if ((err = Reserve(MAX(16,2*m_numitems))) < 0) return (err);
            }
         m_items[m_numitems++] = item;
         return (0);
         }

      ERRVALUE Append (
         const _CT *items,                
         unsigned numitems                   
         ) {
         ERRVALUE err;
         if ((err = Reserve(m_numitems+numitems)) < 0) return (err);
         memcpy(m_items+m_numitems,items,numitems*sizeof(_CT));
         m_numitems += numitems;
         return (0);
         }

      ERRVALUE Append (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         ERRVALUE 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);
         }

      void AppendExc (
         const _CT& item
         ) {
         if (m_numitems >= m_numalloc) {
            ReserveExc(MAX(16,2*m_numitems));
            }
         m_items[m_numitems++] = item;
         return;
         }

      void AppendExc (
         const _CT *items,                
         unsigned numitems                   
         ) {
         ReserveExc(m_numitems+numitems);
         memcpy(m_items+m_numitems,items,numitems*sizeof(_CT));
         m_numitems += numitems;
         return;
         }

      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;
         }

      ERRVALUE AppendUnique (
         const _CT& item
         ) {
         unsigned j;
         for (j = 0; (j < m_numitems); ++j) {
            if (m_items[j] == item) break;
            }
         return ((j == m_numitems) ? Append(item) : 0);
         }

      void AppendUniqueExc (
         const _CT& item
         ) {
         unsigned j;
         for (j = 0; (j < m_numitems); ++j) {
            if (m_items[j] == item) break;
            }
         if (j == m_numitems) AppendExc(item);
         return;
         }

      ERRVALUE Assign (
         const _CT *items,                
         unsigned numitems                
         ) {
         ERRVALUE err;
         if ((err = Reserve(numitems)) < 0) return (err);
         memcpy(m_items,items,numitems*sizeof(_CT));
         m_numitems = numitems;
         return (0);
         }

      void Attach (
         _CT *& items,                 
         unsigned numitems             
         ) {
         Free();
         m_items = items;
         m_numitems = m_numalloc = numitems;
         items = 0;
         return;
         }

      ERRVALUE Extend (
         ) {
         if (m_numitems >= m_numalloc) {
            ERRVALUE err;
            if ((err = Reserve(MAX(16,2*m_numitems))) < 0) return (err);
            }
         ++m_numitems;
         return (0);
         }

      void Clear (
         ) { m_numitems = 0; }

      void ClearItems (
         ) { memset(m_items, 0, m_numitems * sizeof(_CT)); }

      void ClearItems (
         unsigned start,
         unsigned end = -1                
         ) {
         if (end >= m_numitems) end = m_numitems - 1;
         if (end >= start) {     // Start might be past end
            memset(m_items + start, 0, (end - start + 1) * sizeof(_CT));
            }
         return;
         }

      ERRVALUE Copy (
         const SIMPLE_ARRAY<_CT>& rhs
         ) {
         if (this != &rhs) {
            if (m_numalloc < rhs.m_numitems) {
               Free();
               ERRVALUE err = MmAlloc((void**)&m_items,rhs.m_numitems*sizeof(_CT));
               if (err < 0) return (err);
               m_numalloc = rhs.m_numitems;
               }
            memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
            m_numitems = rhs.m_numitems;
            }
         return (0);
         }

      _CT* Detach (
         ) {
         _CT* ret = m_items;
         m_numalloc = m_numitems = 0;
         m_items = 0;
         return (ret);
         }

      void ExchangeItems (
         unsigned index1,
         unsigned index2
         ) {
         _CT temp = m_items[index1];
         m_items[index1] = m_items[index2];
         m_items[index2] = temp;
         return;
         }

      void Free (
         ) {
         m_numalloc = m_numitems = 0;
         MmFree(m_items);
         return;
         }

      const _CT& GetItem (
         unsigned index
         ) const { return (m_items[index]); }

      const _CT* GetItems (
         ) const { return (m_items); }

      _CT* GetItems (
         ) { return (m_items); }

      const _CT& GetLast (
         ) const { return (m_items[m_numitems-1]); }

      unsigned GetMaxItems (
         ) const { return (m_numalloc); }

      unsigned GetNumItems (
         ) const { return (m_numitems); }

      UINT32 GetRefCount (
         ) const { return (m_RefCount); }

      unsigned GetSizeInBytes (
         ) const { return (m_numitems*sizeof(_CT)); }

      bool HasItem (
         const _CT& item
         ) const {
         for (unsigned i = 0; (i < m_numitems); ++i) {
            if (m_items[i] == item) return (true);
            }
         return (false);
         }

      ERRVALUE Insert (
         unsigned pos,
         const _CT& item
         ) {
         if (pos < 0 || pos > m_numitems) return (EBadFuncParm);
         if (m_numitems >= m_numalloc) {
            ERRVALUE err;
            if ((err = Reserve(MAX(16,2*m_numitems))) < 0) return (err);
            }
         if (pos < m_numitems) {
            memmove(&m_items[pos+1], &m_items[pos], (m_numitems - pos) * sizeof(_CT));
            }
         ++m_numitems;
         m_items[pos] = item;
         return (0);
         }

      void InsertItems (
         unsigned start,
         unsigned num = 1
         ) {
         ReserveExc(m_numitems+num);
         memmove(&m_items[start + num], &m_items[start], (m_numitems - start) * sizeof(_CT));
         m_numitems += num;
         return;
         }

      bool IsEmpty (
         ) const { return (GetNumItems() == 0); }

      template<typename _Pr1> unsigned Locate (
         const _CT& item,
         _Pr1 _Pr,
         bool& bFound               
         ) const {
         bFound = false;
         unsigned l = 1, r = m_numitems;
         while (l <= r) {
            unsigned q = (l+r) / 2 - 1;
            int test = _Pr(item, m_items[q]);
            if (test == 0) { bFound = true; return (q); }
            if (test < 0) {
               r = q;
               }
            else {
               l = q + 2;
               }
            }
         return (m_numitems);
         }

      void Release (
         ) { if (--m_RefCount == 0) delete this; }

      void RemoveDuplicates (
         ) {
         for (unsigned i = 0; (i < m_numitems); ++i) {
            for (unsigned 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;
         }     

      void RemoveFast (
         unsigned item
         ) {
         if (item >= 0 && item < m_numitems) {
            --m_numitems;
            m_items[item] = m_items[m_numitems];
            }
         return;
         }

      void RemoveItem (
         unsigned 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;
         }

      void RemoveItems (
         unsigned item,
         unsigned count
         ) {
         if (item < m_numitems) {
            if (count < 0 || item + count > m_numitems) count = m_numitems - item;
            m_numitems -= count;
            if (item < m_numitems) { memmove(&m_items[item], &m_items[item+count], (m_numitems - item) * sizeof(_CT)); }
            }
         return;
         }

      void RemoveLast (
         unsigned count = 1                           
         ) {
         if (count > m_numitems)
            m_numitems = 0;
         else
            m_numitems -= count;
         return;
         }

      bool RemoveMatchingItems (
         const _CT& item
         ) {
         unsigned 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);
         }

      ERRVALUE Reserve (
         unsigned newmaxitems,                  
         bool clear = false               
         ) {
         if (clear) m_numitems = 0;
         if (newmaxitems > m_numalloc) {
            ERRVALUE err;
            if (m_numitems == 0) {
               MmFree(m_items);
               }
            if ((err = MmRealloc((void**)&m_items,newmaxitems*sizeof(_CT))) < 0) return (err);
            m_numalloc = newmaxitems;
            }
         return (0);
         }

      void ReserveExc (
         unsigned newmaxitems,                  
         bool clear = false               
         ) {
         if (clear) m_numitems = 0;
         if (newmaxitems > m_numalloc) {
            if (m_numitems == 0) {
               MmFree(m_items);
               }
            MmReallocExc((void**)&m_items,newmaxitems*sizeof(_CT));
            m_numalloc = newmaxitems;
            }
         return;
         }

      ERRVALUE Resize (
         unsigned numitems,                     
         bool keepold = true,             
         bool clear = false               
         ) {
         ERRVALUE 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);
         }

      void Reverse (
         ) {
         for (unsigned 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;
            }
         }

      void SetAll (
         const _CT& value
         ) {
         for (unsigned i = 0; (i < m_numitems); ++i) {
            m_items[i] = value;
            }
         }

      void SetItem (
         unsigned index,                     
         const _CT& item                     
         ) {
         m_items[index] = item;
         }

      ERRVALUE SetItems (
         unsigned firstitem,                 
         const _CT *items,                   
         unsigned numitems                   
         ) {
         ERRVALUE 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);
         }

      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);
         }
         
      void SortRange (
         int (*CompFunc)(_CT*, _CT*, void*),
         unsigned firstidx,
         unsigned numitems,
         void *data = 0
         ) {
         if (numitems <= 0 || firstidx < 0 || firstidx + numitems > m_numitems) return;
         heapsort(m_items + firstidx, numitems, sizeof(_CT), reinterpret_cast<int (*)(void*, void*, void*)>(CompFunc), data);
         }
         
      void Swap (
         SIMPLE_ARRAY<_CT>& rhs
         ) {
         _CT *t_items = m_items;
         m_items = rhs.m_items;
         rhs.m_items = t_items;
         unsigned t_numitems = m_numitems;
         m_numitems = rhs.m_numitems;
         rhs.m_numitems = t_numitems;
         unsigned t_numalloc = m_numalloc;
         m_numalloc = rhs.m_numalloc;
         rhs.m_numalloc = t_numalloc;
         }

      void SwapBytes (
         ) {
         for (unsigned i = 0; (i < m_numitems); ++i) ::SwapBytes(m_items[i]);
         }

   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      _CT *m_items;                       // The actual array
      unsigned m_numitems;                // Number of valid items
      unsigned m_numalloc;                // Number of items allocated
      UINT32 m_RefCount;
      #endif // GENERATING_DOXYGEN_OUTPUT

   };

#endif   // INC_MI32_SIMPLEAR_H

---