On Sat, 10 Apr 2004 10:34:49 -0400, David Abrahams <dave@boost-consulting.com> wrote:

Gennaro Prota <gennaro_prota@yahoo.com> writes:

...

Hi everybody,

as I have mentioned in some post here, a new version of dynamic_bitset is in the sandbox.

Neat! I just noticed that the old one is missing an empty() member function.

Yes. I noticed that but was not sure whether adding it or not (just to avoid cluttering the interface with too many "utility" functions). I've added it now, with tests (wow :)).

...

I've finished everything 4/5 days ago (including new and more tests) and thought to move it to the main repository, as Jeremy asked too.

What does your change do?

Hmm. Here's an extremely condensed (not exhaustive) summary of changes, future directions and open issues. Sorry if it's terse and incomplete, but I don't have time right now. Don't be afraid for the number of changes though; the tests pass with at least 7 compilers, and there are more tests than before, so we shouldn't have big problems/regressions. Exception Safety All exception safety guarantees are now documented (I haven't committed the docs yet, but the important functions have a comment that says what guarantee they offer - the html file is almost done). Where possible, such as for append(begin, end), the strong guarantee is provided. Implementation Everything is now implemented in terms of std::vector<>. This has quite simplified the code, and made more evident, from reading, the exception guarantees of each member function, as they immediately follow from the corresponding std::vector<>'s ones. Most functions have been rewritten, either to fix errors or to improve efficiency; or to satisfy exception guarantees. The nested class reference has been reimplemented. Formerly it stored an index and a pointer to the bitset: besides being inefficient, that meant that swapping bitsets either made references invalid or changed the element they were referring to. Both problems are now solved by storing a reference into a block and a pre-computed mask. I've also added a namespace scope swap (It's in namespace boost. Ok?) NOTE: for now a reference to a bit remains valid if an exception is thrown by a strong-guarantee operation and, as said, it is stable after a swap(). However rules for invalidation are not documented. If I document them I would go for rules modeled after std::deque, rather than std::vector, so that we leave open the door to implement everything in terms of std::deque. Anyway, I see this more as a future issue: if Jeremy's new iterator categories will get into the standard dynamic_bitset could have iterators; for now, instead, I don't feel the need to have precise invalidation rules for references to bits. The function count() is completely portable, including to platforms that have padding bits in built-in integer types. Conversions from and to string (i.e.: from_string, to_string a constructor, and the undocumented dump_to_string) are internationalized (but see below). A missing parameter in the constructor from basic_string has been added (however see below) Stream operators are internationalized and take into account exception masks on the stream. That's exercised by the tests, in dyn_bitset_unit_tests4. They don't use std::basic_string as an intermediary. (The special versions for old libstdc++ also don't use string as intermediary, but of course they don't know about exception masks etc.) The functions to_block_range and from_block_range have been fixed (but see below) Tests There are much more tests. I can't post a detailed list now. Will do as soon as possible. (Some) Future directions - deprecating conversions from and to string Conversions to and from string are a design error of std::bitset that we have transposed into boost. dynamic_bitset has nothing to do with strings. If one needs a "textual" representation of the data stored in a bitset object there are the stream operators, which are the standard C++ convention for formatting data. By using << and >> you have a neat separation of concerns between the class that stores the data (dynamic_bitset in this case) and the one that stores their textual representation (basic_string), a generic name, operator>> or operator <<, for the free function that connects them (which is important for template programming) and none of the two classes encumbered with knowledge of the other. Also, you can easily deal with locale-related issues. - making reference private (and inhibit copying?) (Some) Open Issues: - Semantics of from_block_range should be clarified for the case where distance(first, last) == b.numblocks() *but* b.size() < (bits_per_block * b.num_blocks()). Example: say bits_per_block = 8, b.size() = 9 and you copy two blocks into b; should the bitset size become 16 or not? I think there are three possibilities: - make this case undefined behavior - enlarging the bitset as needed: // UNTESTED! from_block_range(BlockIterator first, BlockIterator last, dynamic_bitset<B, A>& result) { // PRE: distance(first, last) <= numblocks() // if ( m_bits.end() == std::copy (first, last, result.m_bits.begin()) ) m_num_bits = bits_per_block * b.num_blocks(); } - ignoring additional bits ... std::copy (first, last, result.m_bits.begin()); result.m_zero_unused_bits(); My doubt with this last case concerns input iterators, because once you have consumed the last element it could be lost for ever (not sure if this is a problem or not) - the copy assignment operator currently provides the strong guarantee: operator=(const dynamic_bitset<Block, Allocator>& b) { dynamic_bitset<Block, Allocator> tmp(b); this->swap(tmp); return *this; } Should it? I lean towards 'no'. - Should reserve() and capacity() be added? I think not, because std::deque doesn't have them. So if you add them to the dynamic_bitset interface then you can't implement it in terms of deque (that's why I have removed the two functions, after having initially implemented them) - should std::swap be specialized/overloaded for dynamic_bitsets? - The implementation of operator <, > and all comparison operators require the compared bitsets to have the same size, but that's not documented. The docs simply say that the lexicographical order is considered, and that suggests, for instance, that 10 is < 101. - The docs for to_block_range say: "The type BlockOutputIterator must be a model of Output Iterator and its value_type must be the same type as Block." But output iterators have no notion of "value type". iterator_traits<OutputIterator>::value_type is defined as void. - Imitating std::bitset, the function to_ulong checks whether there's any 1 bit beyond the positions representable in an unsigned long, eventually throwing an overflow_error. That goes against the "don't pay for what you don't use" principle (think for instance if your bitset has 20 000 elements and you are sure that only the first 8 can be set). It's also the only place where we still check "preconditions" with exceptions and the only reason why dynamic_bitset.hpp still needs to include <stdexcept>. Genny.

On Tue, 13 Apr 2004 08:46:57 -0400, David Abrahams <dave@boost-consulting.com> wrote:

Gennaro Prota <gennaro_prota@yahoo.com> writes:

...

On Sat, 10 Apr 2004 10:34:49 -0400, David Abrahams <dave@boost-consulting.com> wrote:

...

Gennaro Prota <gennaro_prota@yahoo.com> writes:

...

Hi everybody,

as I have mentioned in some post here, a new version of dynamic_bitset is in the sandbox.

Neat! I just noticed that the old one is missing an empty() member function.

Yes. I noticed that but was not sure whether adding it or not (just to avoid cluttering the interface with too many "utility" functions). I've added it now, with tests (wow :)).

...

...

I've finished everything 4/5 days ago (including new and more tests) and thought to move it to the main repository, as Jeremy asked too.

What does your change do?

Hmm. Here's an extremely condensed (not exhaustive) summary of changes, future directions and open issues. Sorry if it's terse and incomplete, but I don't have time right now.

<snip>

Wow, that's terse!?!? I'm *very* impressed.

Thanks :) BTW, I forgot to say that the stream extractor has also different semantics: formerly, it extracted at most b.size() characters; now it enlarges the dynamic_bitset as needed. The docs have a section named 'Changes from previous versions'. I also added the following functions: find_first, find_next, get_allocator(), max_size(), intersects() and empty(). About the stream extractor: the fixed-size semantics it had before were chosen to make it possible for users to write template functions like this: template <class Bitset> void foo(Bitset& b) {   cin >> b;   // etc... } and use them with both std::bitset and boost::dynamic_bitset. Of course this was at the cost of sacrificing the natural semantics for a dynamic structure. After some discussions with Jeremy we agreed to adopt the dynamic behavior by default and require a little more work to reuse the template above. In particular you can recycle foo() with a little wrapper: template <typename T> class fix_size { T& m_t; public: fix_size(T & t):m_t(t) {} template <typename T> friend std::istream & operator>>(std::istream & is, fix_size<T>& obj); }; template <typename T> std::istream & operator>>(std::istream & is, fix_size<T>& obj) { [width saver object here...] return is >> std::setw(obj.m_t.size()) >> obj.m_t; } This is basically a proxy for the actual bitset type. You can use it up in the call chain, where you actually construct the bitset to be passed to the generic functions (note that it's usable for both dynamic and static bitsets and has no effects on the latter): typedef boost::dynamic_bitset<> bitset_type; bitset_type b(4); fix_size<bitset_type> proxy(b); foo(proxy); std::cout << b; If one is reusing a foo function that also calls bitset functions other than the extractor (e.g. any() or count(), etc.) the wrapper becomes a little more complex but is still feasible; it just has more boilerplate code. Genny.

Gennaro Prota <gennaro_prota@yahoo.com> writes:

On Wed, 14 Apr 2004 09:34:14 +0200, Gennaro Prota <gennaro_prota@yahoo.com> wrote:

...

I also added the following functions: find_first, find_next, get_allocator(), max_size(), intersects() and empty().

The function intersects() was a user request. It returns true if and only if the two bitsets have any bit "in common", i.e.:

a.intersects(b) == true <=> An index i < a.size(), b.size() exists such as a[i] == true and b[i] == true

Logically, this is the same as doing (a & b).any() [except that currently a & b requires the two bitsets to have the same size - this restriction will likely be removed in the future if we reach a consensus on semantics] but is faster because it doesn't require any copy and can be done with one pass through the blocks

I was thinking, however: what about returning the index of the first bit in common (or npos), instead of true/false?

Ugh, not bit indices, at least not with *that* name! if (intersects(a,b)) // oops { } Maybe optional<std::size_t>?

Secondly, does anyone find confusing that empty() means size() == 0 rather than "the set is empty"?

Not at all. This is not a std::set<> after all. It's well known that it has the semantics of an array. But maybe you should rename it bit_array or bit_vector instead of dynamic_bitset ;-)

Someone could be tempted to write e.g.

if ((a ^ b).empty()) ...

instead of

if ((a ^ b).none()) ...

IMO if (a ^ b) should be supported. But then again, this is making me think of expression templates ;-) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

On Wed, 14 Apr 2004 09:12:35 -0400, David Abrahams <dave@boost-consulting.com> wrote:

...

On Wed, 14 Apr 2004 09:34:14 +0200, Gennaro Prota <gennaro_prota@yahoo.com> wrote: I was thinking, however: what about returning the index of the first bit in common (or npos), instead of true/false?

Ugh, not bit indices, at least not with *that* name!

Yes, not with that name :)

if (intersects(a,b)) // oops {

}

Maybe optional<std::size_t>?

I would rather prefer a Barton-Nackman Fallible<size_type>. I don't know if it has a place into boost, though (what about its license? is it compatible with the boost one?). Of course find_first/next, and eventually their variations, would return a Fallible<> too. Genny.

On Thu, 15 Apr 2004 14:21:12 -0500, Jeremy Siek <jsiek@osl.iu.edu> wrote:

Hi Gennaro,

On Apr 14, 2004, at 4:06 AM, Gennaro Prota wrote:

...

I was thinking, however: what about returning the index of the first bit in common (or npos), instead of true/false?

That functionality sounds useful,

Besides usefulness, the idea was to not "throw away" information that the function already has (well, almost: it knows the two blocks which have a non-null bitwise and; then it's just a matter of calling my lowest_bit function). Of course one could want a mechanism to get, then, the second bit in common, then the third, etc... If anyone has ideas... :)

but I think the current intersects() function should not be removed since it provides for a common use case. Adding another function with the semantics you describe would be good.

I see. But my worry is that we'll have a much dirtier interface if we add utility functions (shortcuts to other functions) light-heartedly. Since dynamic_bitset has already a lot of functions I think we should have a fairly minimalist policy. Genny.

Gennaro Prota <gennaro_prota@yahoo.com> writes:

I also added the following functions: find_first, find_next

You also need find_first_not and find_next_not. Maybe also find_last and all of those variations? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

"Gennaro Prota" <gennaro_prota@yahoo.com> wrote

Hmm. Here's an extremely condensed (not exhaustive) summary of changes, future directions and open issues.

Off topic: what is your opinion on being able to use negative indexes in operator[]? Like bs[-1] would return the last value stored? (Or with different syntax bs[boost.end - 1].) Such feature has been asked for with circular_buffer. /Pavel

Gennaro Prota <gennaro_prota@yahoo.com> writes:

On Tue, 13 Apr 2004 15:08:35 +0200, "Pavel Vozenilek" <pavel_vozenilek@hotmail.com> wrote:

...

"Gennaro Prota" <gennaro_prota@yahoo.com> wrote

...

Hmm. Here's an extremely condensed (not exhaustive) summary of changes, future directions and open issues.

Off topic:

It isn't off topic, I guess :)

...

what is your opinion on being able to use negative indexes in operator[]?

Just for the case index == -1 or in general?

In general, this is a very useful idiom in Python. I'm not sure that C++ should adopt it, though, because it imposes a speed penalty for the normal case of indexing from the front (need to check for negative numbers). You don't pay for what you don't use and all that.

...

Like bs[-1] would return the last value stored? (Or with different syntax bs[boost.end - 1].)

That one is interesting because overload resolution can ensure that there's no speed penalty. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

On 4/13/04 5:17 AM, "Gennaro Prota" <gennaro_prota@yahoo.com> wrote: [SNIP]

- Imitating std::bitset, the function to_ulong checks whether there's any 1 bit beyond the positions representable in an unsigned long, eventually throwing an overflow_error. That goes against the "don't pay for what you don't use" principle (think for instance if your bitset has 20 000 elements and you are sure that only the first 8 can be set). It's also the only place where we still check "preconditions" with exceptions and the only reason why dynamic_bitset.hpp still needs to include <stdexcept>.

I always thought that the exception-throwing behavior of std::bitset::to_ulong was a misfeature. You could just have it truncate off the top bits, just like in converting from one unsigned built-in to a shorter type. If you don't have it, you could add a "highest bit" const member function for those that have to know if truncation occurred. Maybe you can change/add "to_ulong" to return boost::uintmax_t. The function would have to be (re)named "to_uintmax". -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com

On Tue, 13 Apr 2004 08:48:15 -0400, David Abrahams <dave@boost-consulting.com> wrote:

Gennaro Prota <gennaro_prota@yahoo.com> writes:

...

So I ask: should I move everything to the main repository or should I wait until I can devote more time to follow discussions and fix possible regressions?

I would "go for it".

Committed today. Please patient one more week if there are problems, etc. I won't be able to work on anything before next Saturday. I've updated the Jamfile to include the new tests etc. There's a new dynamic_bitset subdirectory in boost-root, which will hold a separate configuration header. The two files integer_log2.hpp and lowest_bit.hpp are in boost/pending/. The docs are still incomplete, and will be completed as soon as possible. I'll also post a message with a detailed list of changes and open issues (which I hope to be able to write at the office, this week, shortening a bit the launch break :)). Have a nice week, Genny.

On Wed, 14 Apr 2004 11:00:23 +0200, Viktor Peters <viktor.peters@uni-bielefeld.de> wrote:

Hello,

I tried the new dynamic_bitset primarily because of the find_first/next thing but ran into trouble with multiple definitions of count_table<true>::table.

Will look into it tomorrow, thanks. Genny.