Re: [boost] request for comment on possible submission to library

From: Richard Scott (rtscott_at_[hidden])
Date: 2002-08-19 19:02:52

Rich,

My thought was that you might want use all positive integers to get the full range for bit setting or packing into a word.  I do this for some short word instantiated arrays in embedded applications.  That is, a failed search returns the maximum possible unsigned integer type for a certain word width since I can NEVER make an array that big in those peculiar circumstances.  I had a similar thought for your bitset operations within the word.

On the other hand, it seems fine to me to make it a template parameter in case you wanted to use some other special value.

Richard 
  ----- Original Message ----- 
  From: spamjunk 
  To: boost_at_[hidden] 
  Sent: Monday, August 19, 2002 4:02 PM
  Subject: Re: [boost] request for comment on possible submission to library

  Sure, what's your thinking?  Would it be better if the actual sentinel value was given as part of the template parameters?
    ----- Original Message ----- 
    From: Richard Scott 
    To: boost_at_[hidden] 
    Sent: Sunday, August 18, 2002 9:28 AM
    Subject: Re: [boost] request for comment on possible submission to library

    Rich,

    I think this could be a very useful contribution but I was wondering if instead of "The only requirement is that the range of values is greater than or equal to zero, and that the element type has a representation for -1 (used as a (hidden) sentinel in argument lists of elements)",you could reserve the maximum possible positive integer as your sentinel?

    Richard
      ----- Original Message ----- 
      From: spamjunk 
      To: boost 
      Sent: Saturday, August 17, 2002 9:17 AM
      Subject: [boost] request for comment on possible submission to library

       I was wondering if anyone would be interested in a Set Library, similar to Pascal's set type for ordinal types. I want to make sure someone would fine it useful (and not trivial, done-to-death, etc.) before I take the time to "Boostify" it and get a release from my employer.

      A while ago I needed a set type that was compact, fast, and avoided heap allocation. The number of elements was constant for a particular set type, and the element type could be any integral type (primarily enums).  Similar types from STL are set, vector<bool>, and bitset, but none quite suited the application. My set type (Set) stores elements at the bit level, like vector<bool> and bitset, but it allows the creation of compile-time set constants. Also, with a good optimizing
      compiler, operations on constant sets will be done at compile-time, though as of yet, there is no direct support for guaranteeing this in the code. The class provides the usual set operations.

      For efficiency, set operations are done in parallel groups of the machine's word size. So, set types whose max. number of elements is less than or equal to the machine's word size, will have most of its operations done in constant time (usually one machine instruction per operation). Sets whose max. number of elements is greater than the machine's word size will be done in linear time, usually in E / Wb cycles, where E is the max. number of elements and Wb is the machine's word size in bits. Though, with a good compile (through inlining and loop unrolling), this linear time would only be E / Wb instructions.  On an average 32-bit processor, that's just 8 instructions to perform the union or intersection of a set of 256 elements. Originally, I avoided loops and used metatemplates to inline the operations, but this resulted in very long compile-times without any gains in performance! And sometimes it resulted in worse performance. That will teach me not to try and second guess today's optimizing compilers!

      As I stated above, the class template may be instantiated with any integral type, but it was primarily meant for enumerations with will give you the added bonuses of type-safely and symbolic names for the elements. The class assumes that the range given is not disjoint (i.e., 0-63 and not 0 - 16, 19, 63). You may use disjoint ranges, but your sets will contain wasted space. The only requirement is that the range of values is greater than or equal to zero, and that the element type has a representation for -1 (used as a (hidden) sentinel in argument lists of elements). You could even conceivably use a class that was "castable" to int.

      For example:

      // element type
      enum Color {red, orange, yellow, green, blue, violet, NumColors,
      NilColor = -1};

      // type for set of colors
      typedef Set<Color, NumColors> ColorSet;

      // set constant
      const ColorSet rgb = ColorSet::SetOf<red, green, blue>::value(); // this is done at compile-time

      void foo()
      {
          // construction
          ColorSet s = ColorSet::SetOf<orange, yellow, violet>::value(); // this is done at compile-time
          ColorSet s1 = ColorSet(a); // this *may* be at compile-time
          ColorSet s2 = ColorSet(orange, yellow, violet); // this is NOT done at compile-time 
                                                          // (but allows non-constant elements)

          // operations, some of which *may* be done at compile-time by a smart compiler
          ColorSet a = s; // assignment
          ColorSet b = s + rgb; // union
          ColorSet c = s * rgb; // intersection
          ColorSet d = s - rgb; // difference
          ColorSet e = s / rgb; // symmetric difference
          bool b1 = s == rgb; // equality
          bool b1 = s != rgb; // unequality
          bool b3 = s >= rgb; // superset
          bool b4 = s > rgb; // proper superset
          bool b5 = s < rgb; // subset
          bool b6 = s > rgb; // proper subset

          if (b.contains(red)) // test for set membership
              std::cout << "b contains the element red" << std::endl;

          if (red == b) // same as above. can anyone suggest a better operator?
                        // maybe use red -> b and use NULL for false?
                        // or maybe remove and just use b.contains(red)?
              std::cout << "b contains the element red" << std::endl;
      }

      What do you think?

      Thanks,

      Rich
      (spamjunk_at_[hidden])