home *** CD-ROM | disk | FTP | other *** search
/ Nebula 2 / Nebula Two.iso / SourceCode / MiscKit1.7.1 / MiscKit / Palettes / MiscTableScroll / MiscSparseSet.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1996-02-11  |  13.6 KB  |  518 lines
  1. //=============================================================================
  2. //
  3. //        Copyright (C) 1995 by Paul S. McCarthy and Eric Sunshine.
  4. //                Written by Paul S. McCarthy and Eric Sunshine.
  5. //                            All Rights Reserved.
  6. //
  7. //        This notice may not be removed from this source code.
  8. //
  9. //        This object is included in the MiscKit by permission from the authors
  10. //        and its use is governed by the MiscKit license, found in the file
  11. //        "License.rtf" in the MiscKit distribution.    Please refer to that file
  12. //        for a list of all applicable permissions and restrictions.
  13. //        
  14. //=============================================================================
  15. //-----------------------------------------------------------------------------
  16. // MiscSparseSet.cc
  17. //
  18. //        This object impelements a sparse set.  The set is represented by an
  19. //        array of ranges kept in sorted ascending order.
  20. //
  21. //-----------------------------------------------------------------------------
  22. //-----------------------------------------------------------------------------
  23. // $Id: MiscSparseSet.cc,v 1.1 95/09/27 12:21:21 zarnuk Exp $
  24. // $Log:        MiscSparseSet.cc,v $
  25. //    Revision 1.1  95/09/27    12:21:21  zarnuk
  26. //    Initial revision
  27. //    
  28. //-----------------------------------------------------------------------------
  29. #ifdef __GNUC__
  30. # pragma implementation
  31. #endif
  32. #import "MiscSparseSet.h"
  33.  
  34. extern "C" {
  35. #import <assert.h>
  36. #import <stdlib.h>
  37. #import <string.h>
  38. }
  39.  
  40. unsigned int const INITIAL_CAPACITY = 16;
  41.  
  42.  
  43. //-----------------------------------------------------------------------------
  44. // sort
  45. //-----------------------------------------------------------------------------
  46. static inline void sort( int& low, int& high )
  47.     {
  48.     if (high < low) { int t = low; low = high; high = t; }
  49.     }
  50.  
  51.  
  52. //=============================================================================
  53. // IMPLEMENTATION
  54. //=============================================================================
  55. //-----------------------------------------------------------------------------
  56. // expand(uint)
  57. //-----------------------------------------------------------------------------
  58. void MiscSparseSet::expand( unsigned int new_capacity )
  59.     {
  60.     if (new_capacity > capacity)
  61.         {
  62.         capacity = new_capacity;
  63.         int const BYTES = capacity * sizeof(*array);
  64.         if (array == 0)
  65.             array = (Range*) malloc( BYTES );
  66.         else
  67.             array = (Range*) realloc( array, BYTES );
  68.         }
  69.     }
  70.  
  71.  
  72. //-----------------------------------------------------------------------------
  73. // expand
  74. //-----------------------------------------------------------------------------
  75. void MiscSparseSet::expand()
  76.     {
  77.     if (lim >= capacity)
  78.         expand( capacity == 0 ? INITIAL_CAPACITY : capacity << 1 );
  79.     }
  80.  
  81.  
  82. //-----------------------------------------------------------------------------
  83. // bsearch
  84. //-----------------------------------------------------------------------------
  85. int MiscSparseSet::bsearch( int x ) const
  86.     {
  87.     int lo = 0;
  88.     int hi = numRanges() - 1;
  89.     while (lo <= hi)
  90.         {
  91.         int const mid = (lo + hi) >> 1;
  92.         Range const& r = array[mid];
  93.         if (x > r.max_val)
  94.             lo = mid + 1;
  95.         else if (x < r.min_val)
  96.             hi = mid - 1;
  97.         else
  98.             return mid;
  99.         }
  100.     return ~lo;
  101.     }
  102.  
  103.  
  104. //-----------------------------------------------------------------------------
  105. // fixCursor
  106. //
  107. //        If cursor is out of bounds, make it INVALID.  If cursor points to a
  108. //        slot not in this set then adjust it to point to a valid slot.
  109. //-----------------------------------------------------------------------------
  110. void MiscSparseSet::fixCursor()
  111.     {
  112.     if (lim == 0 || cursor < 0)
  113.         {
  114.         clearCursor();
  115.         }
  116.     else
  117.         {
  118.         int i = bsearch( cursor );
  119.         if (i < 0)
  120.             {
  121.             i = ~i;
  122.             cursor = (i > 0 ? array[i - 1].max_val : array[i].min_val);
  123.             }
  124.         }
  125.     }
  126.  
  127.  
  128. //-----------------------------------------------------------------------------
  129. // insertAt
  130. //-----------------------------------------------------------------------------
  131. void MiscSparseSet::insertAt( unsigned int x, unsigned int lo,
  132.                                         unsigned int hi )
  133.     {
  134.     assert( x <= lim );
  135.     expand();
  136.     if (x < lim)
  137.         memmove( array + x + 1, array + x, (lim - x) * sizeof(*array) );
  138.     lim++;
  139.     array[ x ].min_val = lo;
  140.     array[ x ].max_val = hi;
  141.     }
  142.  
  143.  
  144. //-----------------------------------------------------------------------------
  145. // deleteAt
  146. //-----------------------------------------------------------------------------
  147. void MiscSparseSet::deleteAt( unsigned int x, unsigned int slots )
  148.     {
  149.     assert( x < lim );
  150.     assert( slots > 0 );
  151.     int const s = lim - (x + slots);
  152.     assert( s >= 0 );
  153.     lim -= slots;
  154.     if (x < lim)
  155.         memmove( array + x, array + x + slots, s * sizeof(*array));
  156.     }
  157.  
  158.  
  159. //-----------------------------------------------------------------------------
  160. // Constructor [Copy]
  161. //-----------------------------------------------------------------------------
  162. MiscSparseSet::MiscSparseSet( MiscSparseSet const& s ) :
  163.     lim(s.lim), capacity(s.lim), array(0), cursor(INVALID)
  164.     {
  165.     if (capacity > 0)
  166.         {
  167.         int const BYTES = capacity * sizeof(*array);
  168.         array = (Range*) malloc( BYTES );
  169.         memcpy( array, s.array, BYTES );
  170.         }
  171.     fixCursor();
  172.     }
  173.  
  174.  
  175. //-----------------------------------------------------------------------------
  176. // Destructor
  177. //-----------------------------------------------------------------------------
  178. MiscSparseSet::~MiscSparseSet()
  179.     {
  180.     if (array != 0)
  181.         free( array );
  182.     }
  183.  
  184.  
  185. //-----------------------------------------------------------------------------
  186. // operator=
  187. //-----------------------------------------------------------------------------
  188. MiscSparseSet& MiscSparseSet::operator=( MiscSparseSet const& s )
  189.     {
  190.     if (&s != this)
  191.         {
  192.         if (s.isEmpty())
  193.             {
  194.             empty();
  195.             }
  196.         else
  197.             {
  198.             expand( s.lim );
  199.             lim = s.lim;
  200.             memcpy( array, s.array, lim * sizeof(*array) );
  201.             cursor = s.cursor;
  202.             fixCursor();
  203.             }
  204.         }
  205.     return *this;
  206.     }
  207.  
  208.  
  209. //-----------------------------------------------------------------------------
  210. // operator==
  211. //-----------------------------------------------------------------------------
  212. bool MiscSparseSet::operator==( MiscSparseSet const& s ) const
  213.     {
  214.     return (&s == this || (lim == s.lim && (lim == 0 ||
  215.             memcmp( array, s.array, lim * sizeof(*array) ) == 0)));
  216.     }
  217.  
  218.  
  219. //-----------------------------------------------------------------------------
  220. // merge
  221. //
  222. //        Cases when merging coords into adjacent ranges:
  223. //
  224. //        CASE
  225. //        *1* If x is the only coord between two ranges then expand range 1 to
  226. //                encompass all, and delete range 2.
  227. //        *2* If x is directly adjacent to the range preceeding it then expand
  228. //                that range to encompass x.
  229. //        *3* If x is directly adjacent to the range following it then expand
  230. //                that range to encompass x.
  231. //-----------------------------------------------------------------------------
  232. int MiscSparseSet::merge( int x, unsigned int at )
  233.     {
  234.     assert( at <= lim );
  235.     assert( at == lim || array[at].min_val > x );
  236.     assert( at == 0 || x > array[at - 1].max_val );
  237.     int ret = ~at;
  238.     if (at > 0 && at < lim &&
  239.         x - 1 == array[at - 1].max_val && x + 1 == array[at].min_val)    // *1*
  240.         {
  241.         ret = at - 1;
  242.         array[ret].max_val = array[at].max_val;
  243.         deleteAt( at, 1 );
  244.         }
  245.     else if (at > 0 && x - 1 == array[at - 1].max_val)                    // *2*
  246.         {
  247.         ret = at - 1;
  248.         array[ret].max_val = x;
  249.         }
  250.     else if (at < lim && x + 1 == array[at].min_val)                    // *3*
  251.         {
  252.         ret = at;
  253.         array[ret].min_val = x;
  254.         }
  255.     return ret;
  256.     }
  257.  
  258.  
  259. //-----------------------------------------------------------------------------
  260. // add
  261. //        Cases after merging coords into existing adjacent ranges if possible:
  262. //
  263. //        CASE
  264. //        *1* Both in same new range
  265. //                ->> insert new range
  266. //        *2* Both in different new ranges
  267. //                ->> extend low range, purge excess high ranges
  268. //        *3* High in new range only
  269. //                ->> extend low range, purge excess high ranges
  270. //        *4* Low in new range only
  271. //                ->> extend high range, purge excess low ranges
  272. //        *5* Both in different existing ranges
  273. //                ->> extend low range, purge excess high ranges
  274. //        *6* Both in same existing range
  275. //                ->> we're done!
  276. //
  277. //-----------------------------------------------------------------------------
  278. void MiscSparseSet::add( int low, int high )
  279.     {
  280.     sort( low, high );
  281.     int rLow  = bsearch( low  );
  282.     if (rLow  < 0) rLow     = merge( low,    ~rLow  );
  283.     int rHigh = bsearch( high );
  284.     if (rHigh < 0) rHigh = merge( high, ~rHigh );
  285.  
  286.     if (rLow < 0 && rLow == rHigh)                        // *1*
  287.         {
  288.         insertAt( ~rLow, low, high );
  289.         }
  290.     else if (rLow < 0 && rHigh < 0)                        // *2*
  291.         {
  292.         array[ ~rLow ].min_val = low;
  293.         array[ ~rLow ].max_val = high;
  294.         if (~rHigh - ~rLow > 1)
  295.             deleteAt( ~rLow + 1, ~rHigh - ~rLow - 1 );
  296.         }
  297.     else if (rHigh < 0)                                    // *3*
  298.         {
  299.         array[ rLow ].max_val = high;
  300.         if (~rHigh - rLow > 1)
  301.             deleteAt( rLow + 1, ~rHigh - rLow - 1);
  302.         }
  303.     else if (rLow < 0)                                    // *4*
  304.         {
  305.         array[ rHigh ].min_val = low;
  306.         if (~rLow < rHigh)
  307.             deleteAt( ~rLow, rHigh - ~rLow );
  308.         }
  309.     else if (rLow < rHigh)                                // *5*
  310.         {
  311.         array[ rLow ].max_val = high;
  312.         deleteAt( rLow + 1, rHigh - rLow );
  313.         }                                                // *6*
  314.     setCursor( high );
  315.     }
  316.  
  317.  
  318. //-----------------------------------------------------------------------------
  319. // slice
  320. //        Four cases when slicing coords off of ranges:
  321. //
  322. //        CASE
  323. //        *1* If x is the only coord in the range then purge the range.
  324. //        *2* If x is the min_val of the range then increment min_val.
  325. //        *3* If x is the max_val of the range then decrement max_val.
  326. //        *4* If x is not at an extreme of the range, leave it alone.
  327. //-----------------------------------------------------------------------------
  328. int MiscSparseSet::slice( int x, unsigned int at )
  329.     {
  330.     assert( at < lim );
  331.     assert( array[at].min_val <= x );
  332.     assert( x <= array[at].max_val );
  333.     int ret = at;
  334.     if (x == array[at].min_val && x == array[at].max_val)        // *1*
  335.         {
  336.         ret = ~at;
  337.         deleteAt( at, 1 );
  338.         }
  339.     else if (x == array[at].min_val)                            // *2*
  340.         {
  341.         ret = ~at;
  342.         array[at].min_val++;
  343.         }
  344.     else if (x == array[at].max_val)                            // *3*
  345.         {
  346.         ret = ~(at + 1);
  347.         array[at].max_val--;
  348.         }                                                        // *4*
  349.     return ret;
  350.     }
  351.  
  352.  
  353. //-----------------------------------------------------------------------------
  354. // remove
  355. //        Cases after slicing extremity coords off of ranges if possible:
  356. //
  357. //        CASE
  358. //        *1* Both in same range
  359. //                ->> split into two ranges, slice max & min
  360. //        *2* Both in different ranges
  361. //                ->> slice max & min, purge excess mid ranges
  362. //        *3* Low in range only
  363. //                ->> slice max, purge excess high ranges
  364. //        *4* High in range only
  365. //                ->> slice min, purge excess low ranges
  366. //        *5* Both outside of different ranges
  367. //                ->> purge excess mid ranges
  368. //        *6* Both outside of same range
  369. //                ->> we're done!
  370. //-----------------------------------------------------------------------------
  371. void MiscSparseSet::remove( int low, int high )
  372.     {
  373.     sort( low, high );
  374.     int rLow  = bsearch( low  );
  375.     if (rLow  >= 0) rLow  = slice( low,     rLow  );
  376.     int rHigh = bsearch( high );
  377.     if (rHigh >= 0) rHigh = slice( high, rHigh );
  378.  
  379.     if (rLow >= 0 && rLow == rHigh)                                // *1*
  380.         {
  381.         insertAt( rLow + 1, high + 1, array[ rLow ].max_val );
  382.         array[ rLow ].max_val = low - 1;
  383.         }
  384.     else if (rLow >= 0 && rHigh >= 0)                            // *2*
  385.         {
  386.         array[ rLow     ].max_val = low - 1;
  387.         array[ rHigh ].min_val = high + 1;
  388.         if (rHigh - rLow > 1)
  389.             deleteAt( rLow + 1, rHigh - rLow - 1 );
  390.         }
  391.     else if (rLow >= 0)                                            // *3*
  392.         {
  393.         array[ rLow ].max_val = low - 1;
  394.         if (~rHigh - rLow > 1)
  395.             deleteAt( rLow + 1, ~rHigh - rLow -1 );
  396.         }
  397.     else if (rHigh >= 0)                                        // *4*
  398.         {
  399.         array[ rHigh ].min_val = high + 1;
  400.         if (rHigh > ~rLow)
  401.             deleteAt( ~rLow, rHigh - ~rLow );
  402.         }
  403.     else if (~rLow < ~rHigh)                                    // *5*
  404.         {
  405.         deleteAt( ~rLow, ~rHigh - ~rLow );
  406.         }                                                        // *6*
  407.     fixCursor();
  408.     }
  409.  
  410.  
  411. //-----------------------------------------------------------------------------
  412. // toggle
  413. //-----------------------------------------------------------------------------
  414. void MiscSparseSet::toggle( int x )
  415.     {
  416.     if (contains( x ))
  417.         remove( x );
  418.     else
  419.         add( x );
  420.     setCursor( x );
  421.     }
  422.  
  423.  
  424. //-----------------------------------------------------------------------------
  425. // shiftUpAt
  426. //-----------------------------------------------------------------------------
  427. void MiscSparseSet::shiftUpAt( int x )
  428.     {
  429.     for (unsigned int i = lim;    i-- > 0;  )
  430.         {
  431.         Range& r = array[i];
  432.         if (r.max_val >= x)
  433.             {
  434.             r.max_val++;
  435.             if (r.min_val >= x)
  436.                 r.min_val++;
  437.             }
  438.         else
  439.             break;
  440.         }
  441.  
  442.     if (cursor >= x)
  443.         cursor++;
  444.  
  445.     if (contains(x))
  446.         remove(x);                // Newly inserted slots are not selected.
  447.     }
  448.  
  449.  
  450. //-----------------------------------------------------------------------------
  451. // shiftDownAt
  452. //-----------------------------------------------------------------------------
  453. void MiscSparseSet::shiftDownAt( int x )
  454.     {
  455.     if (contains(x))
  456.         remove(x);
  457.  
  458.     for (unsigned int i = lim;    i-- > 0;  )
  459.         {
  460.         Range& r = array[i];
  461.         if (r.max_val > x)
  462.             {
  463.             r.max_val--;
  464.             if (r.min_val > x)
  465.                 r.min_val--;
  466.             }
  467.         else
  468.             break;
  469.         }
  470.  
  471.     if (cursor > x)
  472.         {
  473.         cursor--;
  474.         fixCursor();
  475.         }
  476.     }
  477.  
  478.  
  479. //-----------------------------------------------------------------------------
  480. // count
  481. //-----------------------------------------------------------------------------
  482. unsigned int MiscSparseSet::count() const
  483.     {
  484.     unsigned int total = 0;
  485.     for (int i = lim; i-- > 0; )
  486.         total += (array[i].max_val - array[i].min_val + 1);
  487.     return total;
  488.     }
  489.  
  490.  
  491. //-----------------------------------------------------------------------------
  492. // getRangeAt
  493. //-----------------------------------------------------------------------------
  494. void MiscSparseSet::getRangeAt( unsigned int i,
  495.                                 int& lo, int& hi ) const
  496.     {
  497.     lo = hi = INVALID;
  498.     if (i < lim)
  499.         {
  500.         lo = array[i].min_val;
  501.         hi = array[i].max_val;
  502.         }
  503.     }
  504.  
  505.  
  506. //-----------------------------------------------------------------------------
  507. // getTotalRange
  508. //-----------------------------------------------------------------------------
  509. void MiscSparseSet::getTotalRange( int& lo, int& hi ) const
  510.     {
  511.     lo = hi = INVALID;
  512.     if (lim > 0)
  513.         {
  514.         lo = array[0].min_val;
  515.         hi = array[lim].max_val;
  516.         }
  517.     }
  518.