home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 August: Tool Chest / Dev.CD Aug 94.toast / New System Software Extensions / OpenDoc A6 / OpenDoc Parts Framework / OPF / Found / BCCollec / Support / BCDynami.cpp next >
Encoding:
Text File  |  1994-04-21  |  9.2 KB  |  360 lines  |  [TEXT/MPS ]
  1. //  The C++ Booch Components (Version 2.1)
  2. //  (C) Copyright 1990-1993 Grady Booch. All Rights Reserved.
  3. //
  4. //  Restricted Rights Legend
  5. //  Use, duplication, or disclosure is subject to restrictions as set forth 
  6. //  in subdivision (c)(1)(ii) of the Rights in Technical Data and Computer 
  7. //  Software clause at DFARS 252.227-7013. 
  8. //
  9. //  BCDynami.cpp
  10. //
  11. //  This file contains the definition for the dynamic array-based class
  12. //  used for the representation of dynamic structures.
  13.  
  14. #include "BCDynami.h"
  15.  
  16. template<class Item, class StorageManager>
  17. BC_TDynamic<Item, StorageManager>::BC_TDynamic()
  18.   : fRep(0),
  19.     fSize(0),
  20.     fTotalChunks(0),
  21.     fChunkSize(0),
  22.     fStart(0), 
  23.     fStop(0) {}
  24.  
  25. template<class Item, class StorageManager>
  26. BC_TDynamic<Item, StorageManager>::BC_TDynamic(BC_Index chunkSize)
  27.   : fRep(0),
  28.     fTotalChunks(0),
  29.     fSize(0),
  30.     fChunkSize(chunkSize),
  31.     fStart(0), 
  32.     fStop(0) {}
  33.  
  34. template<class Item, class StorageManager>
  35. BC_TDynamic<Item, StorageManager>::
  36.   BC_TDynamic(const BC_TDynamic<Item, StorageManager>& c)
  37.     : fRep(0),
  38.       fTotalChunks(0),
  39.       fSize(0),
  40.       fChunkSize(c.fChunkSize),
  41.       fStart(0),
  42.       fStop(0) 
  43. {
  44.   operator=(c);
  45. }
  46.  
  47. template<class Item, class StorageManager>
  48. BC_TDynamic<Item, StorageManager>::~BC_TDynamic()
  49. {
  50.   Clear();
  51. }
  52.  
  53. template<class Item, class StorageManager>
  54. BC_TDynamic<Item, StorageManager>&
  55.   BC_TDynamic<Item, StorageManager>::
  56.     operator=(const BC_TDynamic<Item, StorageManager>& c)
  57. {
  58.   if (this == &c)
  59.     return *this;
  60.   Resize(Length(), c.Length(), 0);
  61.   BC_Index index;
  62.   fSize = c.Length();
  63.   fStart = (fSize) ? 1 : 0;
  64.   fStop = 0;
  65.   if (c.fStart) {
  66.     if (c.fStart <= c.fStop)
  67.       for (index = c.fStart; (index <= c.fStop); index++)
  68.         fRep[fStop++] = c.fRep[index - 1];
  69.     else {
  70.       for (index = c.fStart; (index <= c.fSize); index++)
  71.         fRep[fStop++] = c.fRep[index - 1];
  72.       for (index = 1; (index <= c.fStop); index++)
  73.         fRep[fStop++] = c.fRep[index - 1];
  74.     }
  75.   }
  76.   return *this;
  77. }
  78.  
  79. template<class Item, class StorageManager>
  80. BC_Boolean BC_TDynamic<Item, StorageManager>::
  81.   operator==(const BC_TDynamic<Item, StorageManager>& c) const
  82. {
  83.   if (this == &c)
  84.     return 1;
  85.   BC_Index count = Length();
  86.   if (count == c.Length()) {
  87.     for (BC_Index index = 0; (index < count); index++)
  88.       if (ItemAt(index) != c.ItemAt(index))
  89.         return 0;
  90.     return 1;
  91.   } else
  92.     return 0;
  93. }
  94.  
  95. template<class Item, class StorageManager>
  96. void BC_TDynamic<Item, StorageManager>::Preallocate(BC_Index newLength)
  97. {
  98.   BC_Index currentLength = Length();
  99.   if (currentLength < newLength)
  100.     Resize(currentLength, newLength);
  101. }
  102.  
  103. template<class Item, class StorageManager>
  104. void BC_TDynamic<Item, StorageManager>::Clear()
  105. {
  106.   Resize(0, 0, 0);
  107. }
  108.  
  109. template<class Item, class StorageManager>
  110. void BC_TDynamic<Item, StorageManager>::Insert(const Item& item)
  111. {
  112.   BC_Index count = Length();
  113.   if (count == fSize)
  114.     Resize(count, count + 1);
  115.   if (!count)
  116.     fStart = fStop = 1;
  117.   else {
  118.     fStart--;
  119.     if (!fStart)
  120.       fStart = fSize;
  121.   }
  122.   fRep[fStart - 1] = item;
  123. }
  124.  
  125. template<class Item, class StorageManager>
  126. void BC_TDynamic<Item, StorageManager>::Insert(const Item& item, BC_Index before)
  127. {
  128.   BC_Index count = Length();
  129.   BC_Assert((before < count), BC_XRangeError("BC_TDynamic::Insert", BC_kInvalidIndex));
  130.   if (count == fSize)
  131.     Resize(count, count + 1);
  132.   if (!count) {
  133.     fStart = fStop = 1;
  134.     fRep[0] = item;
  135.   } else {
  136.     if (fStart <= fStop) {
  137.       if (before <= (fStop - fStart - before + 1))
  138.         fRep[ExpandLeft(fStart + before - 1)] = item;
  139.       else
  140.         fRep[ExpandRight(fStart + before - 1)] = item;
  141.     } else {
  142.       if (before <= (fSize - fStart))
  143.         fRep[ExpandLeft(fStart + before - 1)] = item;
  144.       else
  145.         fRep[ExpandRight(fStart + before - fSize - 1)] = item;
  146.     }
  147.   }
  148. }
  149.  
  150. template<class Item, class StorageManager>
  151. void BC_TDynamic<Item, StorageManager>::Append(const Item& item)
  152. {
  153.   BC_Index count = Length();
  154.   if (count == fSize)
  155.     Resize(count, count + 1);
  156.   if (!count)
  157.     fStart = fStop = 1;
  158.   else {
  159.     fStop++;
  160.     if (fStop > fSize)
  161.       fStop = 1;
  162.   }
  163.   fRep[fStop - 1] = item;
  164. }
  165.  
  166. template<class Item, class StorageManager>
  167. void BC_TDynamic<Item, StorageManager>::Append(const Item& item, BC_Index after)
  168. {
  169.   BC_Index count = Length();
  170.   BC_Assert((after < count), 
  171.             BC_XRangeError("BC_TDynamic::Append", BC_kInvalidIndex));
  172.   if (count == fSize)
  173.     Resize(count, count + 1);
  174.   if (!count) {
  175.     fStart = fStop = 1;
  176.     fRep[0] = item;
  177.   } else {
  178.     if (fStart <= fStop) {
  179.       if (after < (fStop - fStart - after))
  180.         fRep[ExpandLeft(fStart + after)] = item;
  181.       else
  182.         fRep[ExpandRight(fStart + after)] = item;
  183.     } else {
  184.       if (after <= (fSize - fStart))
  185.         fRep[ExpandLeft(fStart + after)] = item;
  186.       else
  187.         fRep[ExpandRight(fStart + after - fSize)] = item;
  188.     }
  189.   }
  190. }
  191.  
  192. template<class Item, class StorageManager>
  193. void BC_TDynamic<Item, StorageManager>::Remove(BC_Index at)
  194. {
  195.   BC_Index count = Length();
  196.   BC_Assert((at < count), 
  197.             BC_XRangeError("BC_TDynamic::Remove", BC_kInvalidIndex));
  198.   BC_Assert(count, BC_XUnderflow("BC_TDynamic::Remove", BC_kEmpty));
  199.   if (count == 1)
  200.     fStart = fStop = 0;
  201.   else {
  202.     if (fStart <= fStop) {
  203.       if (at <= (fStop - fStart - at + 1))
  204.         ShrinkLeft(fStart + at - 1);
  205.       else
  206.         ShrinkRight(fStart + at - 1);
  207.     } else {
  208.       if (at <= (fSize - fStart))
  209.         ShrinkLeft(fStart + at - 1);
  210.       else
  211.         ShrinkRight(fStart + at - fSize - 1);
  212.     }
  213.   }
  214.   Resize(count - 1, count - 1);
  215. }
  216.  
  217. template<class Item, class StorageManager>
  218. void BC_TDynamic<Item, StorageManager>::Replace(BC_Index at, const Item& item)
  219. {
  220.   BC_Assert((at < Length()),
  221.             BC_XRangeError("BC_TDynamic::Replace", BC_kInvalidIndex));
  222.   fRep[at] = item;
  223. }
  224.  
  225. template<class Item, class StorageManager>
  226. BC_Index BC_TDynamic<Item, StorageManager>::Length() const
  227. {
  228.   if (fStart)
  229.     if (fStart <= fStop)
  230.       return (fStop - fStart + 1);
  231.     else
  232.       return (fSize - fStart + fStop + 1);
  233.     else
  234.       return 0;
  235. }
  236.  
  237. template<class Item, class StorageManager>
  238. const Item& BC_TDynamic<Item, StorageManager>::ItemAt(BC_Index index) const
  239. {
  240.   index += fStart - 1;
  241.   if ((fStart > fStop) && (index >= fSize))
  242.     index -= fSize;
  243.   return fRep[index];
  244. }
  245.  
  246. template<class Item, class StorageManager>
  247. Item& BC_TDynamic<Item, StorageManager>::ItemAt(BC_Index index)
  248. {
  249.   index += fStart - 1;
  250.   if ((fStart > fStop) && (index >= fSize))
  251.     index -= fSize;
  252.   return fRep[index];
  253. }
  254.  
  255. template<class Item, class StorageManager>
  256. BC_ExtendedIndex BC_TDynamic<Item, StorageManager>::
  257.   Location(const Item& i, BC_Index start) const
  258. {
  259.   BC_Index count = Length();
  260.   BC_Assert((start <= count),
  261.             BC_XRangeError("BC_TDynamic::Location", BC_kInvalidIndex));
  262.   for (BC_Index index = start; (index < count); index++)
  263.     if (ItemAt(index) == i) 
  264.       return index;
  265.   return -1;
  266. }
  267.  
  268. template<class Item, class StorageManager>
  269. void* BC_TDynamic<Item, StorageManager>::operator new(size_t s)
  270. {
  271.   return StorageManager::Allocate(s);
  272. }
  273.  
  274. template<class Item, class StorageManager>
  275. void BC_TDynamic<Item, StorageManager>::operator delete(void* p, size_t s)
  276. {
  277.   StorageManager::Deallocate(p, s);
  278. }
  279.  
  280. template<class Item, class StorageManager>
  281. void BC_TDynamic<Item, StorageManager>::
  282.   Resize(BC_Index currentLength, BC_Index newLength, BC_Boolean preserve)
  283. {
  284.   BC_Index totalChunks = 0;
  285.   if (newLength)
  286.     totalChunks = (unsigned int)(((newLength - 1) / fChunkSize)) + 1;
  287.   if (fTotalChunks != totalChunks) {
  288.     BC_Index size = totalChunks * fChunkSize;
  289.     Item* newRep =
  290.       (size) ?
  291.         (Item*)(StorageManager::Allocate(size * sizeof(Item))) : 0;
  292.     if (preserve)
  293.       for (BC_Index index = 0; (index < currentLength); index++)
  294.         newRep[index] = ItemAt(index);
  295.     StorageManager::Deallocate(fRep, fSize * sizeof(Item));
  296.     fRep = newRep;
  297.     fSize = size;
  298.     fTotalChunks = totalChunks;
  299.     if (!newLength)
  300.       fStart = fStop = 0;
  301.     else {
  302.       fStart = currentLength ? 1 : 0;
  303.       fStop = currentLength;
  304.     }
  305.   }
  306. }
  307.  
  308. template<class Item, class StorageManager>
  309. BC_Index BC_TDynamic<Item, StorageManager>::ExpandLeft(BC_Index from)
  310. {
  311.   BC_Index index = --fStart;
  312.   if (!fStart) {
  313.     if (from)
  314.       fRep[fSize - 1] = fRep[0];
  315.     fStart = fSize;
  316.     index++;
  317.   }
  318.   for (; (index < from); index++)
  319.     fRep[index - 1] = fRep[index];
  320.   return (from) ? (from - 1) : (fSize - 1);
  321. }
  322.  
  323. template<class Item, class StorageManager>
  324. BC_Index BC_TDynamic<Item, StorageManager>::ExpandRight(BC_Index from)
  325. {
  326.   BC_Index index = fStop;
  327.   if (index == fSize) {
  328.     if (from)
  329.       fRep[0] = fRep[fSize - 1];
  330.     fStop = 1;
  331.     index--;
  332.   } else
  333.     fStop++;
  334.   for (; (index > from); index--)
  335.     fRep[index] = fRep[index - 1];
  336.   return (from >= fSize) ? 0 : from;
  337. }
  338.  
  339. template<class Item, class StorageManager>
  340. void BC_TDynamic<Item, StorageManager>::ShrinkLeft(BC_Index from)
  341. {
  342.   for (BC_Index index = from; (index > (fStart - 1)); index--)
  343.     fRep[index] = fRep[index - 1];
  344.   if (fStart == fSize)
  345.     fStart = 1;
  346.   else
  347.     fStart++;
  348. }
  349.  
  350. template<class Item, class StorageManager>
  351. void BC_TDynamic<Item, StorageManager>::ShrinkRight(BC_Index from)
  352. {
  353.   for (BC_Index index = from; (index < (fStop - 1)); index++)
  354.     fRep[index] = fRep[index + 1];
  355.   if (fStop == 1)
  356.     fStop = fSize;
  357.   else
  358.     fStop--;
  359. }
  360.