Re: [boost] set arithmetic proposal

From: christopher diggins (cdiggins_at_[hidden])
Date: 2005-06-02 09:37:42

----- Original Message ----- 
From: "Victor A. Wagner Jr." <vawjr_at_[hidden]>
To: <boost_at_[hidden]>; <boost_at_[hidden]>
Sent: Thursday, June 02, 2005 9:25 AM
Subject: Re: [boost] set arithmetic proposal

> At 16:16 2005-05-26, Dominic Herity wrote:
>>I've often wished that STL sets supported set arithmetic operations.

Me too.

>>Addition, multiplication and subtraction operators could be overloaded 
>>with
>>set union, intersection and difference respectively.
>>
>>For example:
>>             set<char> s1;            // s1 <- {}
>>             s1 += 'a';               // s1 <- {a}
>>             set<char> s2 = s1 + 'b'; // s2 <- {a,b}
>>             set<char> s3 = s2 - s1;  // s3 <- {b}
>>             set<char> s4 = s1 * s2;  // s4 <- {a}
>>
>>Achieving the above results with the existing STL library is by comparison
>>cumbersome, error-prone and unclear.

I have a char_set class to contribute, which behaves as above. (and is 
released under the boost license) at 
http://www.ootl.org/yard/yard_char_set.hpp.htm . A more recent version is 
available at http://www.ootl.org/ootl-0-3-0.zip

char_set x1('a', 'c'); // a..c
char_set x2('d', 'f'); // d..f
char_set x3(x1 & x2); // a..f
char_set x4(char_set('a','z') | x3); // g..z

assert(!x4['a']);
assert(x4['z']);

There is also a compile-time version of the char_set which allows the 
construction of compile_time sets:

For instance:

typedef char_set_range<'a', 'c'> x1_t;
typedef char_set_range<'d', 'f'> x2_t;
typedef char_set_union<x1_t, x2_t> x3_t;
typedef char_set_intersection<char_set_range<'a','z'>, x3_c> x4_t;

const x4_t X4;

assert(!X4['a']);
assert(X4['z']);

>>Although this proposal does not follow the STL design philosophy, it meets 
>>a
>>real developer need. It can be implemented using global operator 
>>overloads,
>>which should avoid conflicts with other uses of STL sets.
>>
>>Comments and suggestions welcome.
>
> I guess you and I must be the only two former Pascal programmers hanging 
> around boost.

Me too!

> It seems to me that  "set of" from Pascal wasn't ever popular with anyone 
> but those who really _really_ used them heavily (e.g. Ada dropped them 
> when it was derived from Pascal).

I used them heavily for writing a Heron compiler in Delphi.

> I argued (unsuccessfully) that when the boost::dynamic_bitset<> was 
> proposed that the _least_ we could do would be to fix the 
> mis-characterization of operators <= and >= with regards to sets (for 
> those who haven't studied sets,    {b,c,d} <= {a,b,c,d}  but that's not 
> how it will evaluate with either std::set or boost::dynamic_bitset). 
> Absent that oddity, I suspect that you could rather easily overload some 
> global operators to handle what you want using any of std::set, 
> std::bitset, or boost::dynamic_bitset (the backwardness of the comparison 
> operators would still bother me, though).  Hmmmm, maybe I should look more 
> closely at the "unordered collections" (hash_set) proposal further and see 
> if that correctly manages the set concept.

It might be very interesting to also overload comma to return sets, thus 
allowing:

namespace true_sets
{
  assert((1, 2, 3) + (4, 5) < (1,2,3,4,5,6)}
  assert((1, 2) == (2, 1)}
  assert(range(1, 3) == (2, 1, 3)}
}

-Christopher Diggins