home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / YellowBox / Kits / MiscTableScroll-138.1 / Palettes / MiscTableScroll / Framework / MiscSparseSet.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-31  |  12.5 KB  |  479 lines
  1. //=============================================================================
  2. //
  3. //    Copyright (C) 1995-1997 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 implements a sparse set.  The set is represented by an
  19. //    array of ranges kept in sorted ascending order.  Each range is
  20. //    separated from neighboring ranges by a gap of at least one value.
  21. //    In other words, ranges do not overlap, and they do not "touch" each
  22. //    other.  The upper and lower bounds in each range are inclusive.  A
  23. //    range might contain a single value.  In that case, both the upper and
  24. //    lower bounds will have the same value.  There are no empty ranges.
  25. //
  26. //-----------------------------------------------------------------------------
  27. //-----------------------------------------------------------------------------
  28. // $Id: MiscSparseSet.cc,v 1.11 97/04/04 04:57:49 sunshine Exp $
  29. // $Log:    MiscSparseSet.cc,v $
  30. //  Revision 1.11  97/04/04  04:57:49  sunshine
  31. //  0.125.6: Removed unused <assert.h> header.
  32. //  
  33. //  Revision 1.10  97/04/01  07:47:58  sunshine
  34. //  v0.125.5: Fixed comparisons between signed and unsigned integers.
  35. //  
  36. //  Revision 1.9  97/03/20  16:31:18  sunshine
  37. //  v119.1: Removed unnecessary loop from shiftDownAt()
  38. //-----------------------------------------------------------------------------
  39. #ifdef __GNUC__
  40. # pragma implementation
  41. #endif
  42. #import "MiscSparseSet.h"
  43.  
  44. extern "C" {
  45. #import <stdio.h>
  46. #import <stdlib.h>
  47. #import <string.h>
  48. }
  49.  
  50. unsigned int const INITIAL_CAPACITY = 16;
  51.  
  52.  
  53. //-----------------------------------------------------------------------------
  54. // sort
  55. //-----------------------------------------------------------------------------
  56. static inline void sort( int& low, int& high )
  57.     {
  58.     if (high < low) { int t = low; low = high; high = t; }
  59.     }
  60.  
  61.  
  62. //=============================================================================
  63. // IMPLEMENTATION
  64. //=============================================================================
  65. //-----------------------------------------------------------------------------
  66. // dump
  67. //-----------------------------------------------------------------------------
  68. void MiscSparseSet::dump( char const* msg ) const
  69.     {
  70.     fprintf( stderr, "(SPARSE-SET %s (", msg );
  71.     int last_hi = -1;
  72.     bool corrupt = false;
  73.     for (unsigned int i = 0; i < num_ranges; i++)
  74.     {
  75.     Range const& r = ranges[i];
  76.     if (r.lo <= last_hi)
  77.         corrupt = true;
  78.     last_hi = r.hi;
  79.     fprintf( stderr, "%s%d", (i != 0 ? " " : ""), r.lo );
  80.     if (r.lo != r.hi)
  81.         fprintf( stderr, "-%d", r.hi );
  82.     }
  83.     fprintf( stderr, "))%s\n", corrupt ? " *** CORRUPT ***" : "" );
  84.     }
  85.  
  86.  
  87. //-----------------------------------------------------------------------------
  88. // expand(uint)
  89. //-----------------------------------------------------------------------------
  90. void MiscSparseSet::expand( unsigned int new_capacity )
  91.     {
  92.     if (max_ranges < new_capacity)
  93.     {
  94.     max_ranges = new_capacity;
  95.     int const BYTES = max_ranges * sizeof(*ranges);
  96.     if (ranges == 0)
  97.         ranges = (Range*) malloc( BYTES );
  98.     else
  99.         ranges = (Range*) realloc( ranges, BYTES );
  100.     }
  101.     }
  102.  
  103.  
  104. //-----------------------------------------------------------------------------
  105. // expand
  106. //-----------------------------------------------------------------------------
  107. inline void MiscSparseSet::expand()
  108.     {
  109.     if (num_ranges >= max_ranges)
  110.     expand( max_ranges == 0 ? INITIAL_CAPACITY : max_ranges << 1 );
  111.     }
  112.  
  113.  
  114. //-----------------------------------------------------------------------------
  115. // coerce
  116. //-----------------------------------------------------------------------------
  117. int MiscSparseSet::coerce( int x ) const
  118.     {
  119.     if (isEmpty())
  120.     x = -1;
  121.     else
  122.     {
  123.     int i = bsearch( x );
  124.     if (i < 0)
  125.         {
  126.         i = ~i;
  127.         x = (i > 0 ? ranges[i-1].hi : ranges[i].lo);
  128.         }
  129.     }
  130.     return x;
  131.     }
  132.  
  133.  
  134. //-----------------------------------------------------------------------------
  135. // bsearch
  136. //-----------------------------------------------------------------------------
  137. int MiscSparseSet::bsearch( int x ) const
  138.     {
  139.     int lo = 0;
  140.     int hi = numRanges() - 1;
  141.     while (lo <= hi)
  142.     {
  143.     int const mid = (lo + hi) >> 1;
  144.     Range const& r = ranges[mid];
  145.     if (x > r.hi)
  146.         lo = mid + 1;
  147.     else if (x < r.lo)
  148.         hi = mid - 1;
  149.     else
  150.         return mid;
  151.     }
  152.     return ~lo;
  153.     }
  154.  
  155.  
  156. //-----------------------------------------------------------------------------
  157. // insertAt
  158. //-----------------------------------------------------------------------------
  159. void MiscSparseSet::insertAt( unsigned int i, int lo, int hi )
  160.     {
  161.     expand();
  162.     Range* const p = ranges + i;
  163.     if (i < num_ranges)
  164.     memmove( p + 1, p, (num_ranges - i) * sizeof(*ranges) );
  165.     num_ranges++;
  166.     p->lo = lo;
  167.     p->hi = hi;
  168.     }
  169.  
  170.  
  171. //-----------------------------------------------------------------------------
  172. // deleteAt
  173. //-----------------------------------------------------------------------------
  174. void MiscSparseSet::deleteAt( unsigned int i, unsigned int n )
  175.     {
  176.     num_ranges -= n;
  177.     if (i < num_ranges)
  178.     {
  179.     Range* const p = ranges + i;
  180.     memmove( p, p + n, (num_ranges - i) * sizeof(*ranges));
  181.     }
  182.     }
  183.  
  184.  
  185. //-----------------------------------------------------------------------------
  186. // add -- singleton
  187. //-----------------------------------------------------------------------------
  188. void MiscSparseSet::add( int x )
  189.     {
  190.     int i = bsearch( x );
  191.     if (i < 0)    // else, (i >= 0) already in an existing range.
  192.     {
  193.     int action = 0;
  194.     i = ~i;
  195.     if (i > 0 && ranges[i-1].hi == x - 1)            action |= 1;
  196.     if (i < int(num_ranges) && ranges[i].lo == x + 1)    action |= 2;
  197.     switch (action)
  198.         {
  199.     case 0:    insertAt( i, x, x );                break;
  200.     case 1:    ranges[i-1].hi = x;                break;
  201.     case 2:    ranges[i].lo = x;                break;
  202.     case 3:    ranges[i-1].hi = ranges[i].hi; deleteAt(i,1);    break;
  203.         }
  204.     }
  205.     }
  206.  
  207.  
  208. //-----------------------------------------------------------------------------
  209. // add -- range
  210. //-----------------------------------------------------------------------------
  211. void MiscSparseSet::add( int lo, int hi )
  212.     {
  213.     if (lo == hi)
  214.     add( lo );
  215.     else
  216.     {
  217.     sort( lo, hi );
  218.     int ilo = bsearch( lo - 1 );
  219.     int ihi = bsearch( hi + 1 );
  220.  
  221.     if (ilo == ihi)
  222.         {
  223.         if (ilo < 0)    // else both are in same existing range.
  224.         insertAt( ~ilo, lo, hi );
  225.         }
  226.     else
  227.         {            // Convert to good node coords.
  228.         int nlo = ilo; if (nlo < 0) nlo = ~nlo;    // round up
  229.         int nhi = ihi; if (nhi < 0) nhi = ~nhi - 1;    // round down
  230.  
  231.         if (nlo != nhi)
  232.         {
  233.         Range const& t = ranges[nhi];
  234.         if (hi < t.hi) hi = t.hi;
  235.         deleteAt( nlo + 1, nhi - nlo );
  236.         }
  237.  
  238.         Range& r = ranges[nlo];
  239.         if (r.lo > lo) r.lo = lo;
  240.         if (r.hi < hi) r.hi = hi;
  241.         }
  242.     }
  243.     }
  244.  
  245.  
  246. //-----------------------------------------------------------------------------
  247. // remove -- singleton
  248. // NOTE *1*: Can't use 'r.hi' here since insertAt() may have called realloc().
  249. //-----------------------------------------------------------------------------
  250. void MiscSparseSet::remove( int x )
  251.     {
  252.     int const i = bsearch( x );
  253.     if (i >= 0)    // else, (i < 0) already in a "gap".
  254.     {
  255.     int action = 0;
  256.     Range& r = ranges[i];
  257.     if (r.lo == x) action |= 1;        // Trim below.
  258.     if (r.hi == x) action |= 2;        // Trim above.
  259.     switch (action)
  260.         {
  261.     case 0:    insertAt( i + 1, x + 1, r.hi );
  262.         ranges[i].hi = x - 1;    break;    // NOTE *1*
  263.     case 1:    r.lo = x + 1;        break;
  264.     case 2:    r.hi = x - 1;        break;
  265.     case 3:    deleteAt( i, 1 );    break;
  266.         }
  267.     }
  268.     }
  269.  
  270.  
  271. //-----------------------------------------------------------------------------
  272. // remove -- range
  273. //-----------------------------------------------------------------------------
  274. void MiscSparseSet::remove( int lo, int hi )
  275.     {
  276.     if (lo == hi)
  277.     remove( lo );
  278.     else
  279.     {
  280.     sort( lo, hi );
  281.     lo--;
  282.     hi++;
  283.     int ilo = bsearch( lo );
  284.     int ihi = bsearch( hi );
  285.  
  286.     if (ilo == ihi)
  287.         {
  288.         if (ilo >= 0)    // else both in the same "gap".
  289.         {
  290.         Range& r = ranges[ilo];
  291.         int const t = r.hi;
  292.         r.hi = lo;
  293.         insertAt( ilo + 1, hi, t );
  294.         }
  295.         }
  296.     else
  297.         {
  298.         if (ilo >= 0)
  299.         {
  300.         ranges[ilo].hi = lo;
  301.         ilo++;
  302.         }
  303.         else
  304.         ilo = ~ilo;
  305.         
  306.         if (ihi >= 0)
  307.         ranges[ihi].lo = hi;
  308.         else
  309.         ihi = ~ihi;
  310.         
  311.         if (ihi > ilo)
  312.         deleteAt( ilo, ihi - ilo );
  313.         }
  314.     }
  315.     }
  316.  
  317.  
  318. //-----------------------------------------------------------------------------
  319. // Constructor [Copy]
  320. //-----------------------------------------------------------------------------
  321. MiscSparseSet::MiscSparseSet( MiscSparseSet const& s ) :
  322.     num_ranges(s.num_ranges), max_ranges(s.num_ranges), ranges(0)
  323.     {
  324.     if (max_ranges > 0)
  325.     {
  326.     int const BYTES = max_ranges * sizeof(*ranges);
  327.     ranges = (Range*) malloc( BYTES );
  328.     memcpy( ranges, s.ranges, BYTES );
  329.     }
  330.     }
  331.  
  332.  
  333. //-----------------------------------------------------------------------------
  334. // Destructor
  335. //-----------------------------------------------------------------------------
  336. MiscSparseSet::~MiscSparseSet()
  337.     {
  338.     if (ranges != 0)
  339.     free( ranges );
  340.     }
  341.  
  342.  
  343. //-----------------------------------------------------------------------------
  344. // operator=
  345. //-----------------------------------------------------------------------------
  346. MiscSparseSet& MiscSparseSet::operator=( MiscSparseSet const& s )
  347.     {
  348.     if (&s != this)
  349.     {
  350.     if (s.isEmpty())
  351.         empty();
  352.     else
  353.         {
  354.         expand( s.num_ranges );
  355.         num_ranges = s.num_ranges;
  356.         memcpy( ranges, s.ranges, num_ranges * sizeof(*ranges) );
  357.         }
  358.     }
  359.     return *this;
  360.     }
  361.  
  362.  
  363. //-----------------------------------------------------------------------------
  364. // operator==
  365. //-----------------------------------------------------------------------------
  366. bool MiscSparseSet::operator==( MiscSparseSet const& s ) const
  367.     {
  368.     return (&s == this || (num_ranges == s.num_ranges && (num_ranges == 0 ||
  369.         memcmp( ranges, s.ranges, num_ranges * sizeof(*ranges) ) == 0)));
  370.     }
  371.  
  372.  
  373. //-----------------------------------------------------------------------------
  374. // toggle
  375. //-----------------------------------------------------------------------------
  376. void MiscSparseSet::toggle( int x )
  377.     {
  378.     if (contains( x ))
  379.     remove( x );
  380.     else
  381.     add( x );
  382.     }
  383.  
  384.  
  385. //-----------------------------------------------------------------------------
  386. // shiftUpAt
  387. //-----------------------------------------------------------------------------
  388. void MiscSparseSet::shiftUpAt( int x )
  389.     {
  390.     for (unsigned int i = num_ranges;  i-- > 0;  )
  391.     {
  392.     Range& r = ranges[i];
  393.     if (r.hi >= x)
  394.         {
  395.         r.hi++;
  396.         if (r.lo >= x)
  397.         r.lo++;
  398.         }
  399.     else
  400.         break;
  401.     }
  402.  
  403.     if (contains(x))
  404.     remove(x);        // Newly inserted slots are not selected.
  405.     }
  406.  
  407.  
  408. //-----------------------------------------------------------------------------
  409. // shiftDownAt
  410. //-----------------------------------------------------------------------------
  411. void MiscSparseSet::shiftDownAt( int x )
  412.     {
  413.     if (contains(x))
  414.     remove(x);
  415.  
  416.     int i;
  417.     for (i = num_ranges; i-- > 0; )
  418.     {
  419.     Range& r = ranges[i];
  420.     if (r.hi > x)
  421.         {
  422.         r.hi--;
  423.         if (r.lo > x)
  424.         r.lo--;
  425.         }
  426.     else
  427.         break;
  428.     }
  429.  
  430.     if (i >= 0 && i + 1 < int(num_ranges) &&
  431.     ranges[i].hi + 1 == ranges[i + 1].lo)
  432.     {
  433.     ranges[i].hi = ranges[i+1].hi;        // Collapse adjacent range.
  434.     deleteAt( i + 1, 1 );
  435.     }
  436.     }
  437.  
  438.  
  439. //-----------------------------------------------------------------------------
  440. // count
  441. //-----------------------------------------------------------------------------
  442. unsigned int MiscSparseSet::count() const
  443.     {
  444.     unsigned int total = 0;
  445.     Range const* p = ranges;
  446.     Range const* const plim = p + num_ranges;
  447.     for ( ; p < plim; p++)
  448.     total += p->hi - p->lo + 1;
  449.     return total;
  450.     }
  451.  
  452.  
  453. //-----------------------------------------------------------------------------
  454. // getRangeAt
  455. //-----------------------------------------------------------------------------
  456. void MiscSparseSet::getRangeAt( unsigned int i, int& lo, int& hi ) const
  457.     {
  458.     lo = hi = -1;
  459.     if (i < num_ranges)
  460.     {
  461.     lo = ranges[i].lo;
  462.     hi = ranges[i].hi;
  463.     }
  464.     }
  465.  
  466.  
  467. //-----------------------------------------------------------------------------
  468. // getTotalRange
  469. //-----------------------------------------------------------------------------
  470. void MiscSparseSet::getTotalRange( int& lo, int& hi ) const
  471.     {
  472.     lo = hi = -1;
  473.     if (num_ranges > 0)
  474.     {
  475.     lo = ranges[ 0 ].lo;
  476.     hi = ranges[ num_ranges - 1 ].hi;
  477.     }
  478.     }
  479.