Re: [boost] dynamic_bitset request

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-29 13:11:07

That's a good start. Why don't you finish fleshing this out in C++.

BTW, it would be nice if I could implement this "set" interface for
dynamic_bitset without conflicting with current operations. For example,
operator<= is already taken to mean lexicographically less or equal.
However, if that leads to too much ugliness, we can always go the adaptor
route.

Also, we'd probably want the combination assignment operators, such as |=
and &= that are already in std::bitset and dynamic_bitset.

Cheers,
Jeremy

On Mon, 29 Jul 2002, Victor A. Wagner, Jr. wrote:
vawjr> It seems to me that if we're seriously going to consider adding "set
vawjr> semantics" to some set (pun intended) of classes; we could do a lot worse
vawjr> than look at a language that actually had set as part of its fundamental
vawjr> design (Pascal).
vawjr>
vawjr> IIRC Pascal (and I belive, Modula) sets supported the following operators
vawjr> -(unary) not (flip all truth elements in the set)
vawjr> +       union (C++ would probably use |)
vawjr> *       intersection (C++ would probably use &)
vawjr> -       difference .... a - b is equivalent to   a * (-b)
vawjr> xor(^)  bit for bit ^
vawjr> in      set membership (usage:  if y in myset then.....)
vawjr> <=      proper subset
vawjr>  >=      proper superset
vawjr> =       equality (in C++ we use ==)
vawjr> <>      inequality (in C++ we use !=)
vawjr>
vawjr> all sets were "bounded" i.e. had a defined lower and upper bound of
vawjr> possible members.
vawjr>
vawjr> IMO, there are good reasons to provide operators instead of just standard
vawjr> functions  especially if an algebraic notation already exists for the
vawjr> concept.  for example, it's a _lot_ easier to write
vawjr>
vawjr> a = b ^ c;
vawjr>
vawjr> than
vawjr>
vawjr> a.clear();
vawjr> set_symmetric_difference(b.begin(), b.end(), c.begin(), c.end(),
vawjr> back_inserter(a));
vawjr> //or whatever one would have to write to get the equivalent of
vawjr> back_inserter() for a set.
vawjr>
vawjr>
vawjr> At Monday 2002/07/29 08:37, you wrote:
vawjr> >Hi Dave,
vawjr> >
vawjr> >On Sat, 27 Jul 2002, David Abrahams wrote:
vawjr> >dave> How about operator-() for set difference? That seems like an obvious
vawjr> >dave> need...
vawjr> >
vawjr> >One small problem with this is that one metaphor for dynamic_bitset is
vawjr> >that of a big integer. All the current operators are borrowed from the
vawjr> >builtin operators on an unsigned int. The problem is that operator-
vawjr> >doesn't mean set difference for unsigned int, but subtraction.
vawjr> >
vawjr> >One idea I've had in the past is to create a "Set"  concept, which would
vawjr> >include things like union, difference, intersection, etc.  For the general
vawjr> >idea of what the interface would look like, see:
vawjr> >
vawjr> >boost/graph/detail/set_adaptor.hpp
vawjr> >
vawjr> >Under this framework, it would make sense to implement this "Set"
vawjr> >interface for dynamic_bitset, in addition to other classes that can be
vawjr> >thought of as implementing sets, such as std::set.
vawjr> >
vawjr> >Cheers,
vawjr> >Jeremy
vawjr> >
vawjr> >
vawjr> >----------------------------------------------------------------------
vawjr> >  Jeremy Siek                          http://php.indiana.edu/~jsiek/
vawjr> >  Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
vawjr> >  C++ Booster (http://www.boost.org)   office phone: [phone]
vawjr> >----------------------------------------------------------------------
vawjr> >
vawjr> >
vawjr> >_______________________________________________
vawjr> >Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
vawjr>
vawjr> Victor A. Wagner Jr.      http://rudbek.com
vawjr> PGP RSA fingerprint = 4D20 EBF6 0101 B069 3817 8DBF C846 E47A
vawjr> PGP D-H fingerprint = 98BC 65E3 1A19 43EC 3908 65B9 F755 E6F4 63BB 9D93
vawjr> The five most dangerous words in the English language:
vawjr>                "There oughta be a law"
vawjr>
vawjr> _______________________________________________
vawjr> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
vawjr>

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------