Nothing Special   »   [go: up one dir, main page]

Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add set/reset/flip functions to change sequences #27

Merged
merged 4 commits into from
Oct 12, 2018

Conversation

Izaron
Copy link
Contributor
@Izaron Izaron commented Aug 23, 2018

Neither boost::dynamic_bitset nor vanilla std::bitset have the fill() function, and I propose to introduce this.
The point of the function is being used instead of loops with calling the set(pos) function.

Let's consider an example where we want either to set 1024 consecutive bits or to reset them (taking as the fact that we don't change the whole bitset, only its part).
Using a cycle we do it using, well, 1024 operations. Though we could have done it using maximum 1024/64+1=17 operations (considering the blocks as 64-bit integers) - setting the whole blocks between the first and the last bit, and optionally setting a suffix or a prefix of the first/last block respectively.

I also updated docs, tests. Yeah, the algorithm can look a bit complicated, and there are 2 helper functions added, but there's nothing hard at all.

Any suggestions, notes on possible performance improvement, arguments meaning (we change here [first; last], but can change [first;last) as it's more STL-like style); maybe naming too? I guess fill(size_type first, size_type last, bool val = true); could be named set(size_type first, size_type last, bool val = true); as well.

@Izaron Izaron force-pushed the fill branch 3 times, most recently from ff12396 to 14bdb9e Compare August 24, 2018 00:29
@codecov
Copy link
codecov bot commented Aug 24, 2018

Codecov Report

Merging #27 into develop will increase coverage by 1.35%.
The diff coverage is 90.56%.

Impacted file tree graph

@@             Coverage Diff             @@
##           develop      #27      +/-   ##
===========================================
+ Coverage    75.41%   76.76%   +1.35%     
===========================================
  Files            5        5              
  Lines          541      594      +53     
  Branches       198      210      +12     
===========================================
+ Hits           408      456      +48     
- Misses          23       24       +1     
- Partials       110      114       +4
Impacted Files Coverage Δ
include/boost/dynamic_bitset/dynamic_bitset.hpp 76.24% <90.56%> (+1.48%) ⬆️

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update b944aa3...f536fcd. Read the comment docs.

@jeking3
Copy link
Contributor
jeking3 commented Aug 29, 2018

This change is fine, however I think calling it set() makes more sense, and adding reset(f, l) and perhaps flip(f, l) so that all the bit manipulators can operate either on a single bit or a range of bits would complete the desired goal to modify sequences efficiently. As for the meaning of last as you discussed, I'm wondering if first_bit, num_bits makes sense instead of first_bit, last_bit. Then all instantiations of set forward to one implementation that would hopefully be optimal for all cases: set() -> set(0, num_bits), and set(bit) -> set(bit, 1). Just a thought - not sure it would work out that way but worth thinking about.

@Izaron
Copy link
Contributor Author
Izaron commented Aug 31, 2018

@jeking3 I like your thoughts and agree with most of them.

Using relative last bit positions instead of absolute is done in std::string and it's logical to do the same here.

I decided to not call set(bit) -> set(but, 1) and similar, because the common case (any borders) takes some calculations and is more slower than just changing a bit, or setting all the bits to 1. Moreover current set functions are tiny.

But I have a serious doubt connected with implicit conversions from int to bool.
If a programmer paid no attention to warnings and/or had to code really fast, he could write this:

int okay = 42;
/* Transforming 'okay' */
db.set(pos, okay);

The last line was supposed to be db.set(pos, okay != 0) according to the current state, but having a new function dynamic_bitset& set(size_t n, size_t len, bool value = true) makes it into db.set(pos, okay, true) implicitly, which seems to me a serious thing...

Other things seem fine to me, I'd make reset() and flip() with tests as well, after some time.

@Izaron Izaron changed the title Add fill() function to change sequences Add set/reset/swap functions to change sequences Aug 31, 2018
@Izaron Izaron changed the title Add set/reset/swap functions to change sequences Add set/reset/flip functions to change sequences Aug 31, 2018
@Izaron
Copy link
Contributor Author
Izaron commented Aug 31, 2018

So, I've added some commits and there are three new range functions... With tests, docs, without code doubling. Anyone, feel free to comment them!

@jeking3 jeking3 merged commit a449a11 into boostorg:develop Oct 12, 2018
@jeking3 jeking3 mentioned this pull request Oct 12, 2018
@@ -197,10 +198,13 @@ <h3><a id ="synopsis">Synopsis</a></h3>
dynamic_bitset <a href="#op-sl">operator&lt;&lt;</a>(size_type n) const;
dynamic_bitset <a href="#op-sr">operator&gt;&gt;</a>(size_type n) const;

dynamic_bitset&amp; <a href="#set3">set</a>(size_type n, size_type len, bool val = true);
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This has led to ambiguity. See rdkit/rdkit#2128. We need to resolve this. I will open an issue.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This needs to be resolved by Nov 7 or it will be reverted for the Boost 1.69.0 beta.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants