### 1 unstable release

0.1.0 | Jan 12, 2019 |
---|

#**2334** in Data structures

**MIT**license

62KB

1K
SLoC

# index-set

An ordered set that stores indices in a sparse bit field.

## Usage

Add the following to

:`Cargo.toml`

`[``dependencies``]`
`index-set ``=` `"`0.1`"`

## License

This project is licensed under the MIT license.

###
`lib.rs`

:

An ordered set that stores indices in a sparse bit field.

works similarly to a normal collection, but only stores indices
of its elements. In effect, `IndexSet`

stores whether or not an element is
part of the set, whilst allowing the actual element itself to be stored
elsewhere; `IndexSet`

s do not take ownership of their elements, or even a
reference to them, and elements can appear in multiple `IndexSet`

s at
once.`IndexSet`

can also be used as an efficient way of storing integers in an
ordered set.`IndexSet`

See the documentation for

for more information.`IndexSet`

# Examples

Basic usage:

`use` `index_set``::``{`IndexSet`,` ToIndex`}``;`
`enum` `Topping` `{`
Anchovies`,`
Cheese`,`
Ham`,`
Pineapple`,`
`}`
`impl` `ToIndex ``for`` ``Topping` `{`
`type` `Index` `=` `u8``;`
`fn` `to_index``(``&``self``)`` ``->` `u8` `{`
`match` `self` `{`
`Topping``::`Anchovies `=>` `0``,`
`Topping``::`Cheese `=>` `1``,`
`Topping``::`Ham `=>` `2``,`
`Topping``::`Pineapple `=>` `3``,`
`}`
`}`
`}`
`let` `mut` pizza `=` `IndexSet``::``<`Topping`>``::`new`(``)``;`
pizza`.``insert``(``&``Topping``::`Cheese`)``;`
pizza`.``insert``(``&``Topping``::`Ham`)``;`
pizza`.``insert``(``&``Topping``::`Pineapple`)``;`
`assert_eq!``(`pizza`.``contains``(``&``Topping``::`Pineapple`)``,` `true``)``;`
`assert_eq!``(`pizza`.``contains``(``&``Topping``::`Anchovies`)``,` `false``)``;`

Storing integers:

`use` `index_set``::`IndexSet`;`
`let` `mut` set `=` `IndexSet``::``<``u32``>``::`new`(``)``;`
set`.``insert``(``&``1000000``)``;`
set`.``insert``(``&``1``)``;`
set`.``insert``(``&``3``)``;`
set`.``insert``(``&``2``)``;`
`let` vec`:` `Vec``<``u32``>` `=` set`.``into_iter``(``)``.``collect``(``)``;`
`assert_eq!``(`vec`,` `[``1``,` `2``,` `3``,` `1000000``]``)`

# Implementation

Internally,

uses a sparse bit field to represent the existence
of indices in the set. The bit field is divided into buckets of 256 bits and
stored in a `IndexSet`

.`BTreeMap`