lib/include/bear/Array.h

   1 /*
   2  * File:   Array.h
   3  * Author: patrik
   4  *
   5  * Created on August 1, 2009, 7:12 PM
   6  */
   7
   8 #pragma once
   9
  10 #include "debug.h"
  11 #include "mathw.h"
  12
  13 namespace bear
  14 {
  15   /// ***** Header Class *****
  16
  17   template < class Item >
  18   class Array
  19   {
  20   public:
  21     Array();
  22     Array(const Array<Item>& a);
  23     virtual ~Array() {}
  24
  25     void init(unsigned int uiStartSize = 8, unsigned int uiSizeMultiplier = 2);
  26     void fini();
  27
  28     void alloc(unsigned int uiSize);
  29     void trim();
  30
  31     bool isEmpty() const;
  32     unsigned int getLength() const;
  33
  34     const Item& getAt(unsigned int uiIndex) const;
  35
  36     const Item& getFront() const;
  37     const Item& getBack() const;
  38
  39     void pushFront(const Item& i);
  40     void pushBack(const Item& i);
  41
  42     void popFront();
  43     void popBack();
  44
  45     void clear();
  46
  47   private:
  48     unsigned int getSpaceNeeded(unsigned int uiSize) const;
  49
  50     // alloc helpers
  51     void      allocFirstTime(unsigned int uiSize);
  52     void      allocWhenNeeded(unsigned int uiSize);
  53     void      allocForce(unsigned int uiSize);
  54
  55     static Item*    getNextHead(Item* pHead, unsigned int uiAllocated, Item* pArrayItems);
  56     static Item*    getPrevHead(Item* pHead, unsigned int uiAllocated, Item* pArrayItems);
  57     static Item*    getNextTail(Item* pTail, unsigned int uiAllocated, Item* pArrayItems);
  58     static Item*    getPrevTail(Item* pTail, unsigned int uiAllocated, Item* pArrayItems);
  59
  60     static Item*    withinBounds(Item* pValue, Item* pMinBound, Item* pMaxBound);
  61
  62   private:
  63     unsigned int    m_uiStartSize;
  64     unsigned int    m_uiSizeMultiplier;
  65
  66     unsigned int    m_uiAllocated;
  67     Item*           m_pArrayItems;
  68
  69     // NULL Head _and_ NULL Tail means empty
  70     Item*           m_pHead;
  71     Item*           m_pTail;
  72   };
  73
  74 } // namespace bear
  75
  76 template < class Item >
  77 bear::Array<Item>::Array()
  78     :   m_uiStartSize(0),
  79         m_uiSizeMultiplier(0),
  80         m_uiAllocated(0),
  81         m_pArrayItems(NULL),
  82         m_pHead(NULL),
  83         m_pTail(NULL)
  84 {
  85
  86 }
  87
  88 template < class Item >
  89 bear::Array<Item>::Array(const Array<Item>& a)
  90     :   m_uiStartSize(0),
  91         m_uiSizeMultiplier(0),
  92         m_uiAllocated(0),
  93         m_pArrayItems(NULL),
  94         m_pHead(NULL),
  95         m_pTail(NULL)
  96 {
  97   // TODO: talk with colton about init/fini when using a copy constructor
  98   //       (potentialling called from a constructor's initailizer list.)
  99
 100   init();
 101   alloc(a.getLength());
 102
 103   // HACK: this should be a memcpy or something better
 104   for(unsigned int ui=0; ui < a.getLength(); ui++)
 105   {
 106     pushBack(a.getAt(ui));
 107   }
 108 }
 109
 110 template < class Item >
 111 void bear::Array<Item>::init
 112 (
 113   unsigned int uiStartSize,
 114   unsigned int uiSizeMultiplier
 115 )
 116 {
 117   // Sanity checks
 118   bear::DASSERT(0 < uiStartSize);
 119   bear::DASSERT(1 < uiSizeMultiplier);
 120
 121   m_uiStartSize       = uiStartSize;
 122   m_uiSizeMultiplier  = uiSizeMultiplier;
 123
 124   m_uiAllocated       = 0;
 125
 126   // If this fires you have memory leaks
 127   bear::DASSERT(NULL == m_pArrayItems);
 128   m_pArrayItems       = NULL;
 129
 130   m_pHead             = NULL;
 131   m_pTail             = NULL;
 132 }
 133 template < class Item >
 134 void bear::Array<Item>::fini()
 135 {
 136   m_uiStartSize       = 0;
 137   m_uiSizeMultiplier  = 0;
 138
 139   m_uiAllocated       = 0;
 140
 141   if(NULL != m_pArrayItems)
 142   {
 143     delete m_pArrayItems;
 144     m_pArrayItems       = NULL;
 145   }
 146
 147   m_pHead             = NULL;
 148   m_pTail             = NULL;
 149 }
 150
 151 template < class Item >
 152 void bear::Array<Item>::alloc(unsigned int uiSize)
 153 {
 154   if(NULL == m_pArrayItems)
 155   {
 156     allocFirstTime(uiSize);
 157   }
 158   else if(m_uiAllocated < uiSize)
 159   {
 160     allocForce(uiSize);
 161   }
 162
 163   bear::DASSERT(m_uiAllocated >= uiSize);
 164
 165   // TODO: return error when new fails
 166 }
 167
 168 template < class Item >
 169 void bear::Array<Item>::trim()
 170 {
 171   unsigned int uiSize = getLength();
 172   if(NULL == m_pArrayItems)
 173   {
 174     allocFirstTime(uiSize);
 175   }
 176   else
 177   {
 178     allocForce(uiSize);
 179   }
 180
 181   // Sanity checks
 182   bear::DASSERT(uiSize == getLength());
 183   bear::DASSERT(uiSize == m_uiAllocated);
 184 }
 185
 186 template < class Item >
 187 bool bear::Array<Item>::isEmpty() const
 188 {
 189   if ( NULL == m_pHead )
 190   {
 191     bear::DASSERT(NULL == m_pTail);
 192     return true;
 193   }
 194   else
 195   {
 196     bear::DASSERT(NULL != m_pTail);
 197     return false;
 198   }
 199 }
 200
 201 template < class Item >
 202 const Item& bear::Array<Item>::getAt(unsigned int uiIndex) const
 203 {
 204   // This is very bad. Fix your code
 205   DASSERT(uiIndex < getLength());
 206
 207   return *withinBounds( m_pHead + uiIndex, m_pArrayItems, m_pArrayItems + m_uiAllocated );
 208 }
 209
 210 template < class Item >
 211 const Item& bear::Array<Item>::getFront() const
 212 {
 213   // This is very bad. Fix your code
 214   bear::DASSERT(!isEmpty());
 215
 216   // sanity check
 217   //bear::DASSERT(m_pHead <= m_uiAllocated);
 218
 219   return *m_pHead;
 220 }
 221
 222 template < class Item >
 223 const Item& bear::Array<Item>::getBack() const
 224 {
 225   // This is very bad. Fix your code
 226   bear::DASSERT(!isEmpty());
 227
 228   // sanity check
 229   //bear::DASSERT(m_pTail <= m_uiAllocated);
 230
 231   return *m_pTail;
 232 }
 233
 234 template < class Item >
 235 void bear::Array<Item>::pushFront(const Item& i)
 236 {
 237   // Make sure we have the space to add an item
 238   allocWhenNeeded( getLength() + 1 );
 239
 240   if(isEmpty())
 241   {
 242     m_pHead = m_pArrayItems;
 243     m_pTail = m_pArrayItems;
 244   }
 245   else
 246   {
 247     m_pHead = getNextHead(m_pHead, m_uiAllocated, m_pArrayItems);
 248   }
 249
 250   *m_pHead = i;
 251 }
 252
 253 template < class Item >
 254 void bear::Array<Item>::pushBack(const Item& i)
 255 {
 256   // Make sure we have the space to add an item
 257   allocWhenNeeded( getLength() + 1 );
 258
 259   if(isEmpty())
 260   {
 261     m_pHead = m_pArrayItems;
 262     m_pTail = m_pArrayItems;
 263   }
 264   else
 265   {
 266     m_pTail = getNextTail(m_pTail, m_uiAllocated, m_pArrayItems);
 267   }
 268
 269   *m_pTail = i;
 270 }
 271
 272 template < class Item >
 273 void bear::Array<Item>::popFront()
 274 {
 275   bear::DASSERT(!isEmpty());
 276
 277   if( m_pHead == m_pTail )
 278   {
 279     m_pHead = NULL;
 280     m_pTail = NULL;
 281   }
 282   else
 283   {
 284     m_pHead = getPrevHead(m_pHead, m_uiAllocated, m_pArrayItems);
 285   }
 286 }
 287
 288 template < class Item >
 289 void bear::Array<Item>::popBack()
 290 {
 291   bear::DASSERT(!isEmpty());
 292
 293   if( m_pHead == m_pTail )
 294   {
 295     m_pHead = NULL;
 296     m_pTail = NULL;
 297   }
 298   else
 299   {
 300     m_pTail = getPrevTail(m_pTail, m_uiAllocated, m_pArrayItems);
 301   }
 302 }
 303
 304 template < class Item >
 305 void bear::Array<Item>::clear()
 306 {
 307   // HACK
 308   while(!isEmpty())
 309   {
 310     popFront();
 311   }
 312 }
 313
 314
 315 template < class Item >
 316 unsigned int bear::Array<Item>::getLength() const
 317 {
 318   if ( isEmpty() )
 319   {
 320     return 0;
 321   }
 322   else
 323   {
 324     return mod( m_pTail - m_pHead, m_uiAllocated ) + 1;
 325   }
 326 }
 327
 328 template < class Item >
 329 void bear::Array<Item>::allocFirstTime(unsigned int uiSize)
 330 {
 331   // santiy checks
 332   bear::DASSERT(0 == m_uiAllocated);
 333   bear::DASSERT(NULL == m_pArrayItems);
 334   bear::DASSERT(isEmpty());
 335
 336   if(0 < uiSize)
 337   {
 338     unsigned int    uiNewAllocated  = uiSize;
 339     Item *          pNewArrayItems  = new Item[uiNewAllocated];
 340
 341     m_uiAllocated   = uiNewAllocated;
 342     m_pArrayItems   = pNewArrayItems;
 343   }
 344 }
 345
 346 template < class Item >
 347 void bear::Array<Item>::allocWhenNeeded(unsigned int uiSize)
 348 {
 349   unsigned int uiSizeNeeded = (0 == m_uiAllocated) ? m_uiStartSize : m_uiAllocated;
 350
 351   bear::DASSERT(0 < m_uiStartSize);
 352   bear::DASSERT(1 < m_uiSizeMultiplier);
 353
 354   while ( uiSizeNeeded < uiSize )
 355   {
 356     uiSizeNeeded *= m_uiSizeMultiplier;
 357   }
 358
 359   if(uiSizeNeeded > m_uiAllocated)
 360   {
 361     alloc(uiSizeNeeded);
 362   }
 363 }
 364
 365 template < class Item >
 366 void bear::Array<Item>::allocForce(unsigned int uiSize)
 367 {
 368   unsigned int    uiOldLength     = getLength();
 369
 370   unsigned int    uiOldAllocated  = m_uiAllocated;
 371   Item *          pOldArrayItems  = m_pArrayItems;
 372   Item *          pOldHead        = m_pHead;
 373   Item *          pOldTail        = m_pTail;
 374
 375   m_uiAllocated   = 0;
 376   m_pArrayItems   = NULL;
 377   m_pHead         = 0;
 378   m_pTail         = 0;
 379
 380   unsigned int    uiNewAllocated  = uiSize;
 381   Item *          pNewArrayItems  = new Item[uiNewAllocated];
 382   Item *          pNewHead        = pNewArrayItems;
 383   Item *          pNewTail        = pNewHead + uiOldLength - 1;
 384
 385   {
 386     // Copy old items into new array
 387     Item * pNewItem = pNewHead;
 388     Item * pOldItem = pOldHead;
 389
 390     // TODO: this could be done using at most 2 memcpys
 391     for( unsigned int ii = 0; ii < uiOldLength; ii++ )
 392     {
 393       *pNewItem = *pOldItem;
 394
 395       // Pick next item
 396       pNewItem = getNextTail(pNewItem, uiNewAllocated, pNewArrayItems);
 397       pOldItem = getNextTail(pOldItem, uiOldAllocated, pOldArrayItems);
 398     }
 399
 400     // santiy checks
 401     bear::DASSERT(pNewTail == getPrevTail(pNewItem, uiNewAllocated, pNewArrayItems));
 402     bear::DASSERT(pOldTail == getPrevTail(pOldItem, uiOldAllocated, pOldArrayItems));
 403
 404     delete pOldArrayItems;
 405     pOldArrayItems = NULL;
 406   }
 407
 408   m_uiAllocated   = uiNewAllocated;
 409   m_pArrayItems   = pNewArrayItems;
 410   m_pHead         = pNewHead;
 411   m_pTail         = pNewTail;
 412 }
 413
 414
 415 template < class Item >
 416 Item*    bear::Array<Item>::getNextHead
 417 (
 418   Item*           pHead,
 419   unsigned int    uiAllocated,
 420   Item*           pArrayItems
 421 )
 422 {
 423   return withinBounds( pHead - 1, pArrayItems, pArrayItems + uiAllocated );
 424 }
 425
 426 template < class Item >
 427 Item*    bear::Array<Item>::getPrevHead
 428 (
 429   Item*           pHead,
 430   unsigned int    uiAllocated,
 431   Item*           pArrayItems
 432 )
 433 {
 434   return withinBounds( pHead + 1, pArrayItems, pArrayItems + uiAllocated );
 435 }
 436
 437 template < class Item >
 438 Item*    bear::Array<Item>::getNextTail
 439 (
 440   Item*           pTail,
 441   unsigned int    uiAllocated,
 442   Item*           pArrayItems
 443 )
 444 {
 445   return withinBounds( pTail + 1, pArrayItems, pArrayItems + uiAllocated );
 446 }
 447
 448 template < class Item >
 449 Item*    bear::Array<Item>::getPrevTail
 450 (
 451   Item*           pTail,
 452   unsigned int    uiAllocated,
 453   Item*           pArrayItems
 454 )
 455 {
 456   return withinBounds( pTail - 1, pArrayItems, pArrayItems + uiAllocated );
 457 }
 458
 459 template < class Item >
 460 Item*    bear::Array<Item>::withinBounds
 461 (
 462   Item* pValue,
 463   Item* pMinBound,
 464   Item* pMaxBound
 465 )
 466 {
 467   unsigned int  uiValue         = reinterpret_cast<unsigned int>(  pValue     );
 468   unsigned int  uiMinBound      = reinterpret_cast<unsigned int>(  pMinBound  );
 469   unsigned int  uiMaxBound      = reinterpret_cast<unsigned int>(  pMaxBound  );
 470
 471   unsigned int  uiBoundedValue  = uiMinBound + mod(uiValue - uiMinBound, uiMaxBound - uiMinBound);
 472
 473   Item*         pBoundedValue   = reinterpret_cast<Item*>(uiBoundedValue);
 474
 475   // sanity checks
 476   bear::DASSERT(pMinBound <= pBoundedValue);
 477   bear::DASSERT(pMaxBound >  pBoundedValue);
 478
 479   return pBoundedValue;
 480 }