search

rust-lang-ja / ac-library-rs

ac-library-rs is a rust port of AtCoder Library (ACL).
Creative Commons Zero v1.0 Universal
223 stars 26 forks source link

Fix FromIterator for Segtree #138

Open mousecrusher2 opened 8 months ago

mousecrusher2 commented 8 months ago

This pull request fixes the FromIterator implementation for the Segtree struct. The previous implementation use Iterator::size_hint().0 to get length of the iterator. However, that is incorrect.

TonalidadeHidrica commented 7 months ago

You are correct. The current implementation, introduced by @mizar in #115, uses size_hint().0 as the number of elements in the segtree, but this is actually the lower bound of the element that is actually yielded from the iterator; moreover, it may be completely wrong. It's my fault overlooking it, thank you for pointing it out.

I guess however that my implementation in #107 is still correct. The implementation uses size_hint().0 to avoid reallocation when the number of elements is estimated correctly. It also fix the length of the slice for the parent nodes if there are not enough or too many of them compared to the number actually obtained by the iterator. Thus, I think this PR is superceded by #107, provided that I add the filter test that you suggested.

(By the way, despite https://github.com/rust-lang-ja/ac-library-rs/pull/115#issuecomment-1484337588, the FromIterator was not actually reverted. That's also my oversight...)

Comment me if someone (the OP or a maintainer) has any concern; otherwise I'm closing this PR.