gankra / collect-rs Goto Github PK

View Code? Open in Web Editor NEW

65.0 65.0 21.0 9.16 MB

Miscellaneous Collections

License: Apache License 2.0

Shell 0.91% Rust 99.09%

collect-rs's People

Contributors

Stargazers

Watchers

collect-rs's Issues

immut_slist -> cons-list?

immut is a kinda weak naming convention, and it basically exists to emulate the cons-style lists in functional languages.

Doc tests not running

The output from cargo --test indicates that no doc tests are being run. I don't know if this is a bug in Cargo or collect.

Macro statements need semicolons now.

Trying to compile collect with rustc-dev at current HEAD (commit 840de0720) results in:

/home/csouth3/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.5/src/iter/ordered_iter.rs:311:9: 311:18 error: expected one of `.`, `;`, or `}`, found `assert_eq`
/home/csouth3/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.5/src/iter/ordered_iter.rs:311         assert_eq!(Some((12, 6, 4)), powers_of_two_and_three.next())
                                                                                                                 ^~~~~~~~~
Could not compile `collect`.

This is because rust-lang/rust#19984 makes it so that macros being used as statements need to be terminated by semicolons.

Something Something Intrusive Collections Something Something?

I have no idea but apparently it's a thing that people do?

solve the borrow issue with the LRU cache?

I've run into the same error that this person has: http://stackoverflow.com/questions/25190063/rust-borrowing-issues-with-attempted-caching

...when using std::collections::HashMap. Essentially when you get a value from the cache, the returned reference to the value is &mut when you want it to be &. This causes compile errors for code that wants to use multiple immutable references to the containing struct of the cache.

Implement `into_iter` method for all collections

The following are missing a consuming iterator:

ImmutSList
LinearMap

Enhance `LinkedHashMap`

Can't compile with nightly (2014-12-23)

I'm gettings the following compile errors with the latest nightly rust build:

root@383d85ccadd5:/cargo-build/src# cargo build
   Compiling collect v0.0.6
/root/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.6/src/trie/map.rs:26:18: 26:23 error: unresolved import `std::slice::Items`. There is no `Items` in `std::slice`
/root/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.6/src/trie/map.rs:26 use std::slice::{Items, MutItems};
                                                                                                        ^~~~~
/root/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.6/src/trie/map.rs:26:25: 26:33 error: unresolved import `std::slice::MutItems`. There is no `MutItems` in `std::slice`
/root/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.6/src/trie/map.rs:26 use std::slice::{Items, MutItems};

Rust version:

root@383d85ccadd5:/cargo-build/src# rustc --version
rustc 0.13.0-nightly (62fb41c32 2014-12-23 02:41:48 +0000)

Consider including bitmap

https://github.com/cmr/rust-bitmap

cc @cmr

Pillage rust-grabbag for delicious loots

Author has consented to misc pillaging.

Example loot:
https://github.com/DanielKeep/rust-grabbag/blob/master/src/iter.rs

cc @DanielKeep

Be consistent with `Keys` and `Values` iterators

tree_map uses a wrapper struct for its Keys and Values iterators, but trie_map does not.

Replace manual impls with `derive`

This corresponds to FIXMEs referencing rust-lang/rust#19839.

Check out cool no-unsafe-code intrusive-style dlist

@pythonesque showed this to me on IRC: https://gist.github.com/pythonesque/5943252fb464b49123fa#file-dlist-rs

It's a fascinating approach to implementing a DList that requires no unsafe code - instead of having an overarching handle to the head and tail, you instead access one node at a time, similar to a cursor or zipper over the structure, and it then safely patches itself up as you move around.

This seems like a killer justification for the use of Zippers/Cursors and/or Traversals and is also really darn cool.

can't compile w/ nightly as of 12/15/2014

coelacanth ~/src/projects/rust/collect-rs 05:18:31 $ rustc --version
rustc 0.13.0-nightly (126db549b 2014-12-15 00:07:35 +0000)
coelacanth ~/src/projects/rust/collect-rs 05:18:34 $ cargo build
   Compiling collect v0.0.5 (file:///home/wolfson/src/projects/rust/collect-rs)
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:708:5: 710:6 error: method `bitor` has an incompatible type for trait: expected &-ptr, found struct tree::set::TreeSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:708     fn bitor(self, rhs: &TreeSet<T>) -> TreeSet<T> {
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:709         self.union(rhs).cloned().collect()
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:710     }
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:753:5: 755:6 error: method `bitand` has an incompatible type for trait: expected &-ptr, found struct tree::set::TreeSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:753     fn bitand(self, rhs: &TreeSet<T>) -> TreeSet<T> {
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:754         self.intersection(rhs).cloned().collect()
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:755     }
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:798:5: 800:6 error: method `bitxor` has an incompatible type for trait: expected &-ptr, found struct tree::set::TreeSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:798     fn bitxor(self, rhs: &TreeSet<T>) -> TreeSet<T> {
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:799         self.symmetric_difference(rhs).cloned().collect()
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:800     }
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:843:5: 845:6 error: method `sub` has an incompatible type for trait: expected &-ptr, found struct tree::set::TreeSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:843     fn sub(self, rhs: &TreeSet<T>) -> TreeSet<T> {
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:844         self.difference(rhs).cloned().collect()
/home/wolfson/src/projects/rust/collect-rs/src/tree/set.rs:845     }
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:503:5: 505:6 error: method `bitor` has an incompatible type for trait: expected &-ptr, found struct trie::set::TrieSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:503     fn bitor(self, rhs: &TrieSet) -> TrieSet {
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:504         self.union(rhs).collect()
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:505     }
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:548:5: 550:6 error: method `bitand` has an incompatible type for trait: expected &-ptr, found struct trie::set::TrieSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:548     fn bitand(self, rhs: &TrieSet) -> TrieSet {
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:549         self.intersection(rhs).collect()
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:550     }
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:593:5: 595:6 error: method `bitxor` has an incompatible type for trait: expected &-ptr, found struct trie::set::TrieSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:593     fn bitxor(self, rhs: &TrieSet) -> TrieSet {
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:594         self.symmetric_difference(rhs).collect()
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:595     }
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:638:5: 640:6 error: method `sub` has an incompatible type for trait: expected &-ptr, found struct trie::set::TrieSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:638     fn sub(self, rhs: &TrieSet) -> TrieSet {
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:639         self.difference(rhs).collect()
/home/wolfson/src/projects/rust/collect-rs/src/trie/set.rs:640     }
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:196:5: 198:6 error: method `sub` has an incompatible type for trait: expected &-ptr, found struct enum_set::EnumSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:196     fn sub(self, e: EnumSet<E>) -> EnumSet<E> {
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:197         EnumSet {bits: self.bits & !e.bits}
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:198     }
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:211:5: 213:6 error: method `bitor` has an incompatible type for trait: expected &-ptr, found struct enum_set::EnumSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:211     fn bitor(self, e: EnumSet<E>) -> EnumSet<E> {
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:212         EnumSet {bits: self.bits | e.bits}
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:213     }
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:226:5: 228:6 error: method `bitand` has an incompatible type for trait: expected &-ptr, found struct enum_set::EnumSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:226     fn bitand(self, e: EnumSet<E>) -> EnumSet<E> {
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:227         EnumSet {bits: self.bits & e.bits}
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:228     }
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:241:5: 243:6 error: method `bitxor` has an incompatible type for trait: expected &-ptr, found struct enum_set::EnumSet [E0053]
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:241     fn bitxor(self, e: EnumSet<E>) -> EnumSet<E> {
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:242         EnumSet {bits: self.bits ^ e.bits}
/home/wolfson/src/projects/rust/collect-rs/src/enum_set.rs:243     }
error: aborting due to 12 previous errors
Could not compile `collect`.

To learn more, run the command again with --verbose.

Something Something Lock-Free Collections

Some experiments in https://github.com/reem/rust-lockfree, my goal is to build a bunch of primitives then a POC spsc queue (then maybe mpsc or mpmc if I have time to learn C++ and read boost::lockfree), which might want to be integrated into collect-rs, though I don't think all the primitives (atomic buffer etc.) should necessarily go here so as to avoid clutter.

Something Something Streaming Iterators Something Something?

cc @BurntSushi

Merge rust-lang/rust#19679 "Clean up `collections::EnumSet`"

rust-lang/rust#19679

Add debugging integrity checks to data structures

Each data structure should have an integrity-checking private method that is called via debug_assert as a pre- and post-condition to every (non-trivial) public method of the data structure. This would make it harder for bugs like #40 to creep in. For example:

struct SomeMap<K, V> { ... }
impl<K, V> SomeMap<K, V> {
    #[cfg(not(ndebug))]
    fn is_valid(&self) -> bool { ... }

    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
        debug_assert!(self.is_valid());
        let old_value = ...
        debug_assert!(self.is_valid());
        old_value
    }
}

Structures

~~IntervalHeap~~
TreeMap

Document trait impl behavior

All implementations of (at least) the following traits should specify their exact behavior using a doc comment on the appropriate impl methods:

Default -- exactly how the collection is constructed (e.g. by delegating to some other method)
Extend -- whether the new elements are inserted in the same order they are yielded from the iterator, and, for maps and sets, what happens in the case that there are duplicates (including what it means for there to be a duplicate)
FromIterator -- same requirements as Default and Extend
{PartialEq, Eq} -- what constitutes the equivalence relation
{PartialOrd, Ord} -- what constitutes the partial/total order

Additionally, all types implementing Iterator should document their ordering invariants (including the case in which there are none).

version was not bumped on crates.io?

I can't compile the version from crates.io, but can compile the one from git.

LruCache doesn't play nice with Mutexes or Threads anymore

Sorry in advance; I don't have a specific error message at the moment as I'm away from my machine until Thursday, but I understand what the issue is.

I have a project that I'm working on which uses LruCache along with mutexes and threads, and it broke on my last nightly update.

The issue is that both struct LruCache and struct LruEntry contain at least one member which is a *mut LruEntry. Since *mut T doesn't impl Send or Sync, this means that neither LruCache nor LruEntry impl Send or Sync anymore, and thus LruCache can no longer be Mutex protected or used in Threads.

I believe that if it is possible to change all of these *mut's to std::ptr::Unique's, that would probably fix the issue but I'm not familiar enough with Unique and it's full semantics to know if that's possible to do here or not.

Link to and host the rustdoc-generated docs

Github has a field for each repo where you can specify the project's website. Would be cool to link to the rustdoc-generated docs for this repo, so we could more easily browse the collections.

Cheers!

Deprecate `trie` in favor of external crate

Tone down some greedy benches?

test blist::bench::bench_collect_into                             ... bench:      3743 ns/iter (+/- 13)
test blist::bench::bench_iter                                     ... bench:      1651 ns/iter (+/- 13)
test blist::bench::bench_iter_mut                                 ... bench:       722 ns/iter (+/- 70)
test blist::bench::bench_iter_mut_rev                             ... bench:       904 ns/iter (+/- 23)
test blist::bench::bench_iter_rev                                 ... bench:      1502 ns/iter (+/- 92)
test blist::bench::bench_push_back                                ... bench:        47 ns/iter (+/- 0)
test blist::bench::bench_push_back_pop_back                       ... bench:       221 ns/iter (+/- 3)
test blist::bench::bench_push_front                               ... bench:        51 ns/iter (+/- 0)
test blist::bench::bench_push_front_pop_front                     ... bench:       286 ns/iter (+/- 1)
test blist::bench::bench_trav                                     ... bench:       343 ns/iter (+/- 4)
test immut_slist::tests::bench_append                             ... bench:       161 ns/iter (+/- 2)
test immut_slist::tests::bench_append_tail                        ... bench:       143 ns/iter (+/- 1)
test immut_slist::tests::bench_collect_into                       ... bench:      7460 ns/iter (+/- 148)
test immut_slist::tests::bench_iter                               ... bench:       314 ns/iter (+/- 2)
test iter::ordered_iter::tests::inner_join_map                    ... bench:  43657715 ns/iter (+/- 1502601)
test proto::dlist::bench::bench_collect_into                      ... bench:      4836 ns/iter (+/- 114)
test proto::dlist::bench::bench_iter                              ... bench:       471 ns/iter (+/- 6)
test proto::dlist::bench::bench_iter_mut                          ... bench:       266 ns/iter (+/- 6)
test proto::dlist::bench::bench_iter_mut_rev                      ... bench:       265 ns/iter (+/- 1)
test proto::dlist::bench::bench_iter_rev                          ... bench:       265 ns/iter (+/- 1)
test proto::dlist::bench::bench_push_back                         ... bench:        54 ns/iter (+/- 9)
test proto::dlist::bench::bench_push_back_pop_back                ... bench:        49 ns/iter (+/- 1)
test proto::dlist::bench::bench_push_front                        ... bench:        69 ns/iter (+/- 2)
test proto::dlist::bench::bench_push_front_pop_front              ... bench:        86 ns/iter (+/- 12)
test proto::linear_map::bench::bench_get_middle_big               ... bench:       960 ns/iter (+/- 10)
test proto::linear_map::bench::bench_get_middle_medium            ... bench:       130 ns/iter (+/- 7)
test proto::linear_map::bench::bench_get_middle_small             ... bench:        14 ns/iter (+/- 0)
test proto::linear_map::bench::bench_get_none_big                 ... bench:      1870 ns/iter (+/- 29)
test proto::linear_map::bench::bench_get_none_medium              ... bench:       221 ns/iter (+/- 8)
test proto::linear_map::bench::bench_get_none_small               ... bench:        25 ns/iter (+/- 1)
test proto::linear_map::bench::bench_insert_big                   ... bench:    369910 ns/iter (+/- 32431)
test proto::linear_map::bench::bench_insert_medium                ... bench:      5777 ns/iter (+/- 216)
test proto::linear_map::bench::bench_insert_small                 ... bench:       193 ns/iter (+/- 2)
test proto::linear_map::bench::bench_remove_insert_big            ... bench:    686706 ns/iter (+/- 8441)
test proto::linear_map::bench::bench_remove_insert_medium         ... bench:     10088 ns/iter (+/- 830)
test proto::linear_map::bench::bench_remove_insert_small          ... bench:       266 ns/iter (+/- 13)
test proto::linear_map::bench::bench_remove_rev_insert_big        ... bench:    880160 ns/iter (+/- 626092)
test proto::linear_map::bench::bench_remove_rev_insert_medium     ... bench:     12527 ns/iter (+/- 444)
test proto::linear_map::bench::bench_remove_rev_insert_small      ... bench:       289 ns/iter (+/- 3)
test proto::par_vec::test::par_prime_factors_1000                 ... bench:   4108270 ns/iter (+/- 811345)
test proto::par_vec::test::seq_prime_factors_1000                 ... bench:   4349825 ns/iter (+/- 61474)
test proto::shootout::std_dlist_bench::bench_collect_into         ... bench:      3248 ns/iter (+/- 27)
test proto::shootout::std_dlist_bench::bench_iter                 ... bench:       375 ns/iter (+/- 15)
test proto::shootout::std_dlist_bench::bench_iter_mut             ... bench:       307 ns/iter (+/- 5)
test proto::shootout::std_dlist_bench::bench_iter_mut_rev         ... bench:       290 ns/iter (+/- 15)
test proto::shootout::std_dlist_bench::bench_iter_rev             ... bench:       290 ns/iter (+/- 2)
test proto::shootout::std_dlist_bench::bench_push_back            ... bench:        58 ns/iter (+/- 4)
test proto::shootout::std_dlist_bench::bench_push_back_pop_back   ... bench:        55 ns/iter (+/- 1)
test proto::shootout::std_dlist_bench::bench_push_front           ... bench:        55 ns/iter (+/- 3)
test proto::shootout::std_dlist_bench::bench_push_front_pop_front ... bench:        61 ns/iter (+/- 6)
test tree::map::bench::find_rand_100                              ... bench:         5 ns/iter (+/- 0)
test tree::map::bench::find_rand_10_000                           ... bench:         6 ns/iter (+/- 0)
test tree::map::bench::find_seq_100                               ... bench:         0 ns/iter (+/- 0)
test tree::map::bench::find_seq_10_000                            ... bench:         0 ns/iter (+/- 0)
test tree::map::bench::insert_rand_100                            ... bench:       118 ns/iter (+/- 2)
test tree::map::bench::insert_rand_10_000                         ... bench:       582 ns/iter (+/- 347)
test tree::map::bench::insert_seq_100                             ... bench:       261 ns/iter (+/- 196)
test tree::map::bench::insert_seq_10_000                          ... bench:       549 ns/iter (+/- 86)
test tree::map::bench::iter_1000                                  ... bench:      5102 ns/iter (+/- 2536)
test tree::map::bench::iter_100000                                ... bench:   2489808 ns/iter (+/- 321058)
test tree::map::bench::iter_20                                    ... bench:       118 ns/iter (+/- 5)
test trie::map::bench::bench_get                                  ... bench:     10257 ns/iter (+/- 608)
test trie::map::bench::bench_get_entry                            ... bench:     37620 ns/iter (+/- 1014)
test trie::map::bench::bench_insert_large                         ... bench:    542011 ns/iter (+/- 10697)
test trie::map::bench::bench_insert_large_entry                   ... bench:    604821 ns/iter (+/- 35931)
test trie::map::bench::bench_insert_large_low_bits                ... bench:    316913 ns/iter (+/- 26545)
test trie::map::bench::bench_insert_small                         ... bench:    204727 ns/iter (+/- 20117)
test trie::map::bench::bench_insert_small_low_bits                ... bench:    165779 ns/iter (+/- 9817)
test trie::map::bench::bench_lower_bound                          ... bench:       373 ns/iter (+/- 7)
test trie::map::bench::bench_remove                               ... bench:    192118 ns/iter (+/- 1345)
test trie::map::bench::bench_remove_entry                         ... bench:    239567 ns/iter (+/- 6211)
test trie::map::bench::bench_upper_bound                          ... bench:       375 ns/iter (+/- 34)
test trie::map::bench::iter_1000                                  ... bench:     33306 ns/iter (+/- 2251)
test trie::map::bench::iter_100000                                ... bench:   8326038 ns/iter (+/- 432640)
test trie::map::bench::iter_20                                    ... bench:       385 ns/iter (+/- 148)

7-digits is a bit much, no?

'Miscellaneous' is spelled 'Miscellaneous'

Spelling error in the github subtitle-thing :)

Reintroduce collection traits

In their most general form, these may require features that haven't been added to Rust yet, but we can probably start thinking about what they would look like.

Something Something Persistent Collections Something Something?

cc @reem @matthieum @jurily

Consolidate map and set tests

It would be nice to have a module containing tests for the behavior that is common to all map and set implementations. @gankro started something similar with https://github.com/Gankro/rust-collection-tests, but it needs to be updated for various changes to the language and libraries, including the removal of the collection traits. For now, this could use macros.

Try out some collection traits

Add yo names to authors

do it

do it good

Rewrite Comparator impls to get rid of the need for `old_impl_check`

Push new version to crates.io

The current version hasn't built on Rust nightly in quite some time.

This may want to wait until the fate of #148 has been decided.

collect does not compile on nightly 3-21

Compiling collect v0.0.26
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/immut_slist.rs:65:22: 65:27 error: unresolved name `range`. Did you mean `n`?
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/immut_slist.rs:65             for _ in range(0, n) {
                                                                                                                           ^~~~~
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/interval_heap.rs:334:22: 334:27 error: unresolved name `range`. Did you mean `self`?
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/interval_heap.rs:334         for hsize in range(2, vec.len()).rev() {
                                                                                                                              ^~~~~
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/proto/dlist.rs:538:18: 538:23 error: unresolved name `range`. Did you mean `by`?
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/proto/dlist.rs:538         for _ in range(0, by) { self.next(); }
                                                                                                                        ^~~~~
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/proto/dlist.rs:543:18: 543:23 error: unresolved name `range`. Did you mean `self`?
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/proto/dlist.rs:543         for _ in range(0, by) { self.prev(); }
                                                                                                                        ^~~~~
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/proto/linear_map.rs:208:18: 208:23 error: unresolved name `range`. Did you mean `self`?
/Users/jmitchell/.cargo/registry/src/github.com-1ecc6299db9ec823/collect-0.0.26/src/proto/linear_map.rs:208         for i in range(0, self.storage.len()) {

Found the same issue with num which I filed here

Bors

Would be to cool to setup bors. Always wanted to r+ stuff.

Clean up and enhance `TreeMap`

I've started work on a replacement at https://github.com/apasel422/tree.

Add Haskell-style traversables

The Traversable type class is a pretty powerful abstraction in Haskell (found here on Hackage). Rust already has a fold method for IteratorExt, which provides similar functionality to a foldr-based implementation of Traversable's parent, Foldable. But a traverse() method in IteratorExt could do much more!

Note that as far as I can tell (which may not be far :P), this "Traversable" is disjoint from the "Traversable traits" discussion, which (as far as I can tell) was more about working around the lack of HKTs vis-à-vis a trait for .iter() methods.

Disband collect-rs in favour of separate crates?

We're constantly getting winged and whammed by some weird language change breaking some thing we're doing. The whole crate's kinda unfocused and we've got all these cargo features to paper over the fact that we're really a collection of distinct crates. Meanwhile the cargo ecosystem seems to really favour "just do this one thing" crates.

The main downside I see is that this loses us the group maintenance effect.

Thoughts?

@aturon @alexcrichton @cgaebel @apasel422 @reem @huonw

Some types are missing `Debug` impls

The following collections are missing a std::fmt::Debug impl:

interval_heap::IntervalHeap (I have an upcoming PR for this)
proto::linear_map::LinearMap
proto::par_vec::ParVec

The following types are missing a Debug impl, but it is not clear whether they should have one or what the output should be. One possibility is just the name of the struct or enum variant.

Prototype out IntervalHeap or std's BinaryHeap with a comparator-based API

This would allow a heap to be reinterpretted as min/max without affecting the consumer of the collection (no wrapping the data to redefine Ord). It may also be the future of searching in maps/sets. However Heaps are a good simple place to test the ideas out on.

See this PR for preliminary work done in the area. It got blocked on unboxed closures becoming more coherent, which is now the case.

Ideally comparators would be part of the type, with a default Natural Comparator that just uses Ord. A Reverse Comparator would also be useful, in the same vein as the Reverse iterator adaptor. We could also consider providing a Fake Comparator for wrapping PartialOrd impls unsafely.

Unboxed closures that return Ord should presumably work as Comparators.

CC @huonw @sellibitze @aturon @reem

Consider including HAMT

https://github.com/michaelwoerister/rs-persistent-datastructures

CC @michaelwoerister

Implement common traits for iterators

Audit iterators to ensure that they implement Clone, DoubleEndedIterator, and ExactSizeIterator where appropriate. Note that the last two were recently untangled.

Consider including `TypeMap` and `AnyMap`

As the title says. One is from @reem and the other one from @chris-morgan IIRC.

`IntervalHeap::from_vec` builds the heap incorrectly

Test case, compiled with 044db2e and rustc 0.13.0-nightly (62fb41c32 2014-12-23 02:41:48 +0000):

extern crate collect;

use collect::IntervalHeap;

#[test]
fn test_push() {
    let mut heap = IntervalHeap::new();
    heap.push(2u);
    heap.push(1);
    heap.push(3);
    assert_eq!(heap.get_min(), Some(&1));
    assert_eq!(heap.get_max(), Some(&3));
}

#[test]
fn test_from_vec() {
    let heap = IntervalHeap::from_vec(vec![2u, 1, 3]);
    assert_eq!(heap.get_min(), Some(&1));
    assert_eq!(heap.get_max(), Some(&3));
}

test_push passes, while test_from_vec fails on the second assert_eq:

running 2 tests
test test_push ... ok
test test_from_vec ... FAILED

failures:

---- test_from_vec stdout ----
    thread 'test_from_vec' panicked at 'assertion failed: `(left == right) && (right == left)` (left: `Some(2)`, right: `Some(3)`)', lib.rs:19

Compilation fails on rust master

Compilation fails on rustc 1.0.0-nightly (fed12499e 2015-03-03) (built 2015-03-04) due to some types changing from usize to u32:

src/trie/map.rs:36:40: 36:45 error: mismatched types:
 expected `u32`,
    found `usize`
(expected u32,
    found usize) [E0308]
src/trie/map.rs:36 const MAX_DEPTH: usize = usize::BITS / SHIFT;
                                                          ^~~~~
src/trie/map.rs:36:26: 36:45 error: mismatched types:
 expected `usize`,
    found `u32`
(expected usize,
    found u32) [E0308]
src/trie/map.rs:36 const MAX_DEPTH: usize = usize::BITS / SHIFT;
                                            ^~~~~~~~~~~~~~~~~~~
src/trie/map.rs:704:28: 704:48 error: mismatched types:
 expected `u32`,
    found `usize`
(expected u32,
    found usize) [E0308]
src/trie/map.rs:704     let sh = usize::BITS - (SHIFT * (idx + 1));
                                               ^~~~~~~~~~~~~~~~~~~~
src/enum_set.rs:107:9: 107:31 error: mismatched types:
 expected `usize`,
    found `u32`
(expected usize,
    found u32) [E0308]
src/enum_set.rs:107         self.bits.count_ones()
                            ^~~~~~~~~~~~~~~~~~~~~~
src/enum_set.rs:241:10: 241:15 error: mismatched types:
 expected `usize`,
    found `u32`
(expected usize,
    found u32) [E0308]
src/enum_set.rs:241         (exact, Some(exact))
                             ^~~~~
src/enum_set.rs:241:22: 241:27 error: mismatched types:
 expected `usize`,
    found `u32`
(expected usize,
    found u32) [E0308]
src/enum_set.rs:241         (exact, Some(exact))

`TreeMap::insert`'s behavior differs from `{BTreeMap, HashMap}`

{BTreeMap, HashMap}::insert does not replace the existing key with the new one, but TreeMap::insert does. In common usage, this doesn't matter, as derived {Hash, Eq}/Ord impls incorporate all fields, but custom impls can experience surprising behavior despite meeting the requirements for {Hash, Eq}/Ord:

extern crate collect;

use std::cmp::Ordering;
use std::hash;

struct Foo(u32, &'static str);

impl hash::Hash for Foo {
    fn hash<H: hash::Hasher>(&self, h: &mut H) { self.0.hash(h); }
}

impl PartialEq for Foo {
    fn eq(&self, other: &Foo) -> bool { self.0 == other.0 }
}

impl Eq for Foo {}

impl PartialOrd for Foo {
    fn partial_cmp(&self, other: &Foo) -> Option<Ordering> { Some(self.cmp(other)) }
}

impl Ord for Foo {
    fn cmp(&self, other: &Foo) -> Ordering { self.0.cmp(&other.0) }
}

#[test]
fn test_tree_map() {
    use collect::TreeMap;

    let mut m = TreeMap::new();

    m.insert(Foo(1, "a"), ());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_some());

    m.insert(Foo(1, "b"), ());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_none());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "b").is_some());
}

#[test]
fn test_btree_map() {
    use std::collections::BTreeMap;

    let mut m = BTreeMap::new();

    m.insert(Foo(1, "a"), ());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_some());

    m.insert(Foo(1, "b"), ());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_none());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "b").is_some());
}

#[test]
fn test_hash_map() {
    use std::collections::HashMap;

    let mut m = HashMap::new();

    m.insert(Foo(1, "a"), ());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_some());

    m.insert(Foo(1, "b"), ());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_none());
    assert!(m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "b").is_some());
}

running 3 tests
test test_btree_map ... FAILED
test test_hash_map ... FAILED
test test_tree_map ... ok

failures:

---- test_btree_map stdout ----
    thread 'test_btree_map' panicked at 'assertion failed: m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_none()', src/lib.rs:50


---- test_hash_map stdout ----
    thread 'test_hash_map' panicked at 'assertion failed: m.iter().find(|&(k, _)| k.0 == 1 && k.1 == "a").is_none()', src/lib.rs:64

The fix for collect is simple (remove this line), but I'm not sure if this should be considered a bug in std. In either case, the behavior should be the same.

gankra / collect-rs Goto Github PK

collect-rs's People

Contributors

Stargazers

Watchers

Forkers

collect-rs's Issues

Structures

Recommend Projects

Recommend Topics

Recommend Org