home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / YellowBox / Kits / MiscTableScroll-138.1 / Palettes / MiscTableScroll / Framework / MiscSparseSet.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-31  |  3.5 KB  |  104 lines
  1. #ifndef __MiscSparseSet_h
  2. #define __MiscSparseSet_h
  3. #ifdef __GNUC__
  4. # pragma interface
  5. #endif
  6. //=============================================================================
  7. //
  8. //    Copyright (C) 1995-1997 by Paul S. McCarthy and Eric Sunshine.
  9. //        Written by Paul S. McCarthy and Eric Sunshine.
  10. //                All Rights Reserved.
  11. //
  12. //    This notice may not be removed from this source code.
  13. //
  14. //    This object is included in the MiscKit by permission from the authors
  15. //    and its use is governed by the MiscKit license, found in the file
  16. //    "License.rtf" in the MiscKit distribution.  Please refer to that file
  17. //    for a list of all applicable permissions and restrictions.
  18. //    
  19. //=============================================================================
  20. //-----------------------------------------------------------------------------
  21. // MiscSparseSet.h
  22. //
  23. //    This object implements a sparse set.  The set is represented by an
  24. //    array of ranges kept in sorted ascending order.  Each range is
  25. //    separated from neighboring ranges by a gap of at least one value.
  26. //    In other words, ranges do not overlap, and they do not "touch" each
  27. //    other.  The upper and lower bounds in each range are inclusive.  A
  28. //    range might contain a single value.  In that case, both the upper and
  29. //    lower bounds will have the same value.  There are no empty ranges.
  30. //
  31. // NOTE *1*
  32. //    coerce(x) will return x if x is a member of the set.  Otherwise, it
  33. //    will return the closest previous member of the set, if any.  Otherwise
  34. //    it will return the closest following member of the set.  Otherwise
  35. //    it will return -1 if the set is empty.
  36. //
  37. //-----------------------------------------------------------------------------
  38. //-----------------------------------------------------------------------------
  39. // $Id: MiscSparseSet.h,v 1.5 96/12/30 09:13:42 sunshine Exp $
  40. // $Log:    MiscSparseSet.h,v $
  41. //  Revision 1.5  96/12/30  09:13:42  sunshine
  42. //  v107.1: Added coerce().
  43. //  
  44. //  Revision 1.4  96/12/30  03:12:49  sunshine
  45. //  v104.1: Removed "cursor" wart.  Now this is a simple generic class.
  46. //  
  47. //  Revision 1.3  96/04/30  05:38:43  sunshine
  48. //  Ported to OpenStep 4.0 for Mach PR2.
  49. //-----------------------------------------------------------------------------
  50. #include "bool.h"
  51.  
  52. class MiscSparseSet
  53.     {
  54. private:
  55.     struct Range
  56.         {
  57.         int lo;
  58.         int hi;
  59.         };
  60.  
  61.     unsigned int num_ranges;
  62.     unsigned int max_ranges;
  63.     Range* ranges;
  64.  
  65.     void expand( unsigned int new_capacity );
  66.     void expand();
  67.     int bsearch( int x ) const;
  68.     void insertAt( unsigned int i, int lo, int hi );
  69.     void deleteAt( unsigned int i, unsigned int n );
  70.  
  71. public:
  72.     MiscSparseSet():num_ranges(0),max_ranges(0),ranges(0){}
  73.     MiscSparseSet( MiscSparseSet const& );
  74.     ~MiscSparseSet();
  75.  
  76.     MiscSparseSet& operator=( MiscSparseSet const& );
  77.     bool operator==( MiscSparseSet const& ) const;
  78.     bool operator!=( MiscSparseSet const& s ) const
  79.                     { return !operator==(s); }
  80.  
  81.     bool contains( int x ) const    { return (bsearch( x ) >= 0); }
  82.     bool isEmpty() const        { return (num_ranges == 0); }
  83.     void empty()            { num_ranges = 0; }
  84.     unsigned int count() const;    // # elments in set
  85.  
  86.     void add( int lo, int hi );    // add a range
  87.     void add( int x );
  88.     void remove( int lo, int hi );    // remove a range
  89.     void remove( int x );
  90.     void toggle( int x );
  91.     void shiftUpAt( int x );
  92.     void shiftDownAt( int x );
  93.  
  94.     int coerce( int x ) const;    // NOTE *1*
  95.  
  96.     unsigned int numRanges() const    { return num_ranges; }
  97.     void getRangeAt( unsigned int i, int& lo, int& hi ) const;
  98.     void getTotalRange( int& lo, int& hi ) const;
  99.  
  100.     void dump( char const* msg ) const;
  101.     };
  102.  
  103. #endif // __MiscSparseSet_h
  104.