FryingPan/framework/Generic/VectorT.h

   1 /*
   2  * Amiga Generic Set - set of libraries and includes to ease sw development for all Amiga platforms
   3  * Copyright (C) 2001-2011 Tomasz Wiszkowski Tomasz.Wiszkowski at gmail.com.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  */
  19
  20 #ifndef _VECTORT_H_
  21 #define _VECTORT_H_
  22
  23 #include "Types.h"
  24 #include <LibC/LibC.h>
  25
  26 namespace GenNS
  27 {
  28    template <typename T, long minSize=16>
  29       class VectorT
  30    {
  31       T*          pElements;
  32       int32       lCurrentSize;
  33       int32       lTotalSize;
  34       bool        bSorted;
  35
  36    protected:
  37       void        qsort(T* arr, int size, int(func)(const T&, const T&))
  38       {
  39          if (size > 1)
  40          {
  41             int s1  = 0;            // best result will be given
  42             int s2  = size;         // ....
  43             T*  ar2 = new T[size];  // when we use pointers here :]
  44             T   el  = arr[size/2];  // middle element
  45
  46             for (int i=0; i<size; i++)       // so, for almost every element
  47             {
  48                if (i == size/2)              // almost - except for the middle one
  49                   continue;
  50
  51                if (func(arr[i], el) < 0)     // fill table from both ways
  52                   ar2[s1++] = arr[i];        // if smaller - from one end
  53                else                          //
  54                   ar2[--s2] = arr[i];        // if greater - from another
  55             }
  56
  57             ar2[s1] = el;                    // put last element :)
  58
  59             for (int i=0; i<size; i++)       // clone table
  60                arr[i] = ar2[i];              //
  61
  62             delete [] ar2;                   // kill the temp
  63
  64             qsort(arr, s1, func);
  65             qsort(&arr[s2], size-s2, func);
  66          }
  67       };
  68
  69       void        expand()
  70       {
  71          ASSERT(lCurrentSize <= lTotalSize);
  72          if (lCurrentSize == lTotalSize)
  73          {
  74             lTotalSize   <<= 1; // twice that much
  75             T* pNewElem    = new T[lTotalSize];
  76             for (int32 i=0; i<lCurrentSize; i++)
  77                pNewElem[i] = pElements[i];
  78             delete [] pElements;
  79             pElements      = pNewElem;
  80          }
  81       };
  82
  83       static int  compare(const T &a, const T &b)
  84       {
  85          return (a < b) ? -1 :
  86             (a == b) ? 0  : 1;
  87       }
  88
  89    public:
  90
  91       VectorT()
  92       {
  93          if (minSize < 4)
  94             lTotalSize  = 4;
  95          else
  96             lTotalSize  = minSize;
  97
  98          lCurrentSize   = 0;
  99          pElements      = new T[lTotalSize];
 100          bSorted        = true;
 101       }
 102
 103       VectorT(const VectorT<T, minSize> &src)
 104       {
 105          *this = src;
 106       }
 107
 108       virtual ~VectorT()
 109       {
 110          delete [] pElements;
 111       }
 112
 113       T& operator [] (int32 lElement) const
 114       {
 115          ASSERT((lElement >= -lCurrentSize) && (lElement < lCurrentSize));
 116
 117          if (lElement >= 0)
 118             return pElements[lElement];
 119          else
 120             return pElements[lCurrentSize + lElement];
 121       }
 122
 123       T& Get(int lElement) const
 124       {
 125          return (*this)[lElement];
 126       }
 127
 128       VectorT<T, minSize>& operator << (T pNewElement)
 129       {
 130          expand();
 131
 132          pElements[lCurrentSize] = pNewElement;
 133          ++lCurrentSize;
 134
 135          bSorted = false;
 136
 137          return *this;
 138       }
 139
 140       int32 Count() const
 141       {
 142          return lCurrentSize;
 143       }
 144
 145       int32 Max() const
 146       {
 147          return lTotalSize;
 148       }
 149
 150       void Empty()
 151       {
 152          bSorted = true;
 153          lCurrentSize = 0;
 154          lTotalSize = minSize;
 155          delete [] pElements;
 156          pElements = new T[minSize];
 157       }
 158
 159       bool IsSorted()
 160       {
 161          return bSorted;
 162       }
 163
 164       VectorT<T, minSize>& operator >> (T pOldElement)
 165       {
 166          int32 i;
 167          for (i=0; i<lCurrentSize; i++)
 168          {
 169             if (pElements[i] == pOldElement)
 170             {
 171                break;
 172             }
 173          }
 174
 175          if (i == lCurrentSize)  // not found.
 176             return *this;
 177
 178          --lCurrentSize;
 179
 180          for (; i<lCurrentSize; i++)
 181          {
 182             pElements[i] = pElements[i+1];
 183          }
 184
 185          // removing item does not change order;
 186
 187          return *this;
 188       }
 189
 190       const T* GetArray()
 191       {
 192          return pElements;
 193       }
 194
 195       VectorT<T, minSize>& Sort(int(func)(const T&, const T&))
 196       {
 197          if (func == 0)
 198             func = &compare;
 199
 200          qsort(pElements, lCurrentSize, func);
 201          bSorted = true;
 202          return *this;
 203       }
 204
 205       VectorT<T, minSize>& ForEach(bool(func)(const T&))
 206       {
 207          for (int32 i=0; i<lCurrentSize; i++)
 208          {
 209             if (!func(pElements[i]))
 210                break;
 211          }
 212
 213          return *this;
 214       }
 215
 216       VectorT<T, minSize>& InsertElem(T elem, int32 pos)
 217       {
 218          ASSERT((pos >= 0) && (pos <= lCurrentSize));
 219
 220          if (pos >= (int32)lCurrentSize)
 221          {
 222             *this << elem;
 223             return *this;
 224          }
 225          else if (pos < 0)
 226          {
 227             return *this;
 228          }
 229
 230          expand();
 231          for (int i=lCurrentSize; i>pos; --i)
 232             pElements[i] = pElements[i-1];
 233          pElements[pos] = elem;
 234          lCurrentSize++;
 235          return *this;
 236       };
 237
 238       VectorT<T, minSize>& RemoveElem(int32 pos)
 239       {
 240          ASSERT((pos >= 0) && (pos < lCurrentSize));
 241          *this >> pElements[pos];
 242          return *this;
 243       }
 244
 245       VectorT<T, minSize>& InsertSorted(T elem, int(func)(const T&, const T&))
 246       {
 247          register int pos  = (lCurrentSize + 1) / 2;
 248          register int step = pos;
 249
 250          if (func == 0)
 251             func = &compare;
 252
 253          do
 254          {
 255             // left-check
 256             if (pos > 0)
 257             {
 258                if (0 > func(elem, pElements[pos-1]))
 259                {
 260                   step = (step+1) / 2;
 261                   pos -= step;
 262                   if (pos < 0)
 263                      pos = 0;
 264                   continue;
 265                }
 266             }
 267
 268             if (pos < (int32)lCurrentSize)
 269             {
 270                if (0 < func(elem, pElements[pos]))
 271                {
 272                   step = (step+1) / 2;
 273                   pos += step;
 274                   if (pos > (int32)lCurrentSize)
 275                      pos = lCurrentSize;
 276                   continue;
 277                }
 278             }
 279
 280             break;
 281          }
 282          while (true);
 283          return InsertElem(elem, pos);
 284       }
 285
 286       int IndexOf(T elem, int(func)(const T&, const T&))
 287       {
 288          register int pos  = (lCurrentSize) / 2;
 289          register int step = (lCurrentSize+1) / 2;
 290          int res;
 291          int chance = 0;
 292
 293          if (lCurrentSize == 0)
 294             return -1;
 295
 296          if (func == 0)
 297             func = &compare;
 298
 299          do
 300          {
 301             if (0 == func(elem, pElements[pos]))
 302                return pos;
 303
 304             /*
 305              * check if we have a match
 306              */
 307             res = func(elem, pElements[pos]);
 308             if (res == 0)
 309                return pos;
 310             if ((pos == (lCurrentSize-1)) && (res > 0))
 311                return -1;
 312             if ((pos == 0) && (res == 0))
 313                return -1;
 314             if (step == 1)
 315                ++chance;
 316             if (chance == 3)
 317                return -1;
 318
 319             step = (step+1) / 2;
 320
 321             if (0 > res)
 322             {
 323                pos -= step;
 324                if (pos < 0)
 325                   pos = 0;
 326             }
 327             else
 328             {
 329                pos += step;
 330                if (pos >= lCurrentSize)
 331                   pos = lCurrentSize-1;
 332             }
 333          }
 334          while (true);
 335       }
 336
 337       VectorT<T, minSize>& operator =(const VectorT<T, minSize> &src)
 338       {
 339          lCurrentSize = src.lCurrentSize;
 340          lTotalSize   = src.lTotalSize;
 341          pElements    = new T[lTotalSize];
 342          bSorted      = src.bSorted;
 343
 344          for (int32 i=0; i<lCurrentSize; i++)
 345          {
 346             pElements[i] = src.pElements[i];
 347          }
 348
 349          return *this;
 350       }
 351    };
 352 };
 353
 354 #endif //_VECTORT_H_
 355    // vim: ts=3 et