### 10 unstable releases (4 breaking)

0.5.0 | Oct 4, 2021 |
---|---|

0.4.1 | May 20, 2021 |

0.4.0 | Apr 18, 2021 |

0.3.5 | Feb 27, 2021 |

0.1.1 | Aug 13, 2020 |

#**468** in Data structures

**108** downloads per month

Used in intersect2d

**MIT/Apache**

140KB

3K
SLoC

# rb_tree

This crate contains an implementation of the red-black tree data structure and several data structures that are built on top of this implementation. The data structures currently include RBTree, RBMap, and RBQueue.

## Data Structures

### RBTree

This data structure can be used as a set and has methods to support its use as a set. Methods specific to this data structure include set operations such as union, difference etc. Values are stored in their

ordering.`PartialOrd`

### RBMap

This data structure provides an interface for using the RBTree as a map. Values in the map are ordered by their keys'

ordering.`PartialOrd`

### RBQueue

This data structure allows the use of the underlying red-black tree as a priority queue. A comparison function is provided on instantiation (either with

or `RBQueue ::`new

`(`

`Fn`

`(`

`&`T

`,`

`&`T

`)`

`->``std``::``cmp`Ordering`::``)`

`new_c_queue!``(``Fn``(``&`T`,` `&`T`)` `->` `i8``)`

) which is used to order the entries.## Features

The above data structures can be optionally excluded (all are included by default). If you are only using one or two of the types you can exclude the other(s) to help minimise your binary size. However, because

is a wrapper type for `RBMap`

including the former will always include the latter. To do this, add to your dependencies:`RBTree`

`[``dependencies``]`
`rb_tree = { version = "*", default-features = false, features ``=` `[``"`map`"` | `"`set`"` | `"`queue`"``]`}

This will add to your binary the

, `RBMap`

, and `RBTree`

types respectively. It is important you set `RBQueue`

to false as all features are enabled by default.`default-features`

Additionally, support for serialisation for the above types can be added with the

feature.`serde`

See here for more info about cargo's feature system.

## Examples

`use` `rb_tree``::`RBTree`;`
`//` uses an rbtree to sort data
`fn` `sort``<`T`:` `PartialOrd``>``(``to_order``:` `Vec``<`T`>``)`` ``->` `Vec``<`T`>` `{`
`let` `mut` tree `=` `RBTree``::`new`(``)``;`
`let` `mut` ordered `=` `Vec``::`new`(``)``;`
`for` v `in` to_order `{`
tree`.``insert``(`v`)``;`
`}`
`while` `let` `Some``(`v`)` `=` tree`.``pop``(``)` `{`
ordered`.``push``(`v`)``;`
`}`
ordered
`}`
`fn` `main``(``)`` ``{`
`let` eg1 `=` `vec!``(``3``,` `6``,` `1``,` `2``,` `0``,` `4``,` `-``1``,` `5``,` `10``,` `11``,` `-``13``)``;`
`assert_eq!``(``sort``(`eg1`)``,` `vec!``(``-``13``,` `-``1``,` `0``,` `1``,` `2``,` `3``,` `4``,` `5``,` `6``,` `10``,` `11``)``)``;`
`let` eg2 `=` `vec!``(``"`Is`"``,` `"`this`"``,` `"`the`"``,` `"`real`"``,` `"`life`"``)``;`
`assert_eq!``(``sort``(`eg2`)``,` `vec!``(``"`Is`"``,` `"`life`"``,` `"`real`"``,` `"`the`"``,` `"`this`"``)``)`
`}`

`use` `rb_tree``::`RBMap`;`
`fn` `main``(``)`` ``{`
`let` `mut` squares `=` `RBMap``::`new`(``)``;`
`for` i `in` `0``..``10` `{`
squares`.``insert``(`i`,` i`)``;`
`}`
squares`.``values_mut``(``)``.``for_each``(``|``v``|` `*`v `=` `(``*`v `as` `f64``)``.``powi``(``2``)` `as` `u32``)``;`
`for` i `in` `0``..``10` `{`
`assert_eq!``(``*`squares`.``get``(``&`i`)``.``unwrap``(``)``,` `(`i `as` `f64``)``.``powi``(``2``)` `as` `u32``)``;`
`}`
`}`

`#``[``macro_use``(``new_c_queue``)``]`
`extern` `crate` rb_tree`;`
`use` `rb_tree``::`RBQueue`;`
`fn` `main``(``)`` ``{`
`//` use the default comarator
`let` `mut` q1 `=` `RBQueue``::`new`(``|``l``:` `&``i64``,` `r``|` `{`
l`.``cmp``(`r`)`
`}``)``;`
`//` compare in the reverse order
`let` `mut` q2 `=` `new_c_queue!``(``|``l``:` `&``i64``,` `r``|` `(`r `-` l`)``)``;`
q1`.``insert``(``1``)``;`
q1`.``insert``(``2``)``;`
q1`.``insert``(``3``)``;`
q2`.``insert``(``1``)``;`
q2`.``insert``(``2``)``;`
q2`.``insert``(``3``)``;`
`assert_eq!``(`q1`.``ordered``(``)``,` `[``&``1``,` `&``2``,` `&``3``]``)``;`
`assert_eq!``(`q2`.``ordered``(``)``,` `[``&``3``,` `&``2``,` `&``1``]``)``;`
`}`

# License

This project is licensed under the terms of the MIT license.

#### Dependencies

~225KB