im_rc/
lib.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! # Immutable Data Structures for Rust
6//!
7//! This library implements several of the more commonly useful immutable data
8//! structures for Rust.
9//!
10//! ## What are immutable data structures?
11//!
12//! Immutable data structures are data structures which can be copied and
13//! modified efficiently without altering the original. The most uncomplicated
14//! example of this is the venerable [cons list][cons-list]. This crate offers a
15//! selection of more modern and flexible data structures with similar
16//! properties, tuned for the needs of Rust developers.
17//!
18//! Briefly, the following data structures are provided:
19//!
20//! * [Vectors][vector::Vector] based on [RRB trees][rrb-tree]
21//! * [Hash maps][hashmap::HashMap]/[sets][hashset::HashSet] based on [hash
22//!   array mapped tries][hamt]
23//! * [Ordered maps][ordmap::OrdMap]/[sets][ordset::OrdSet] based on
24//!   [B-trees][b-tree]
25//!
26//! ## Why Would I Want This?
27//!
28//! While immutable data structures can be a game changer for other
29//! programming languages, the most obvious benefit - avoiding the
30//! accidental mutation of data - is already handled so well by Rust's
31//! type system that it's just not something a Rust programmer needs
32//! to worry about even when using data structures that would send a
33//! conscientious Clojure programmer into a panic.
34//!
35//! Immutable data structures offer other benefits, though, some of
36//! which are useful even in a language like Rust. The most prominent
37//! is *structural sharing*, which means that if two data structures
38//! are mostly copies of each other, most of the memory they take up
39//! will be shared between them. This implies that making copies of an
40//! immutable data structure is cheap: it's really only a matter of
41//! copying a pointer and increasing a reference counter, where in the
42//! case of [`Vec`][std::vec::Vec] you have to allocate the same
43//! amount of memory all over again and make a copy of every element
44//! it contains. For immutable data structures, extra memory isn't
45//! allocated until you modify either the copy or the original, and
46//! then only the memory needed to record the difference.
47//!
48//! Another goal of this library has been the idea that you shouldn't
49//! even have to think about what data structure to use in any given
50//! situation, until the point where you need to start worrying about
51//! optimisation - which, in practice, often never comes. Beyond the
52//! shape of your data (ie. whether to use a list or a map), it should
53//! be fine not to think too carefully about data structures - you can
54//! just pick the one that has the right shape and it should have
55//! acceptable performance characteristics for every operation you
56//! might need. Specialised data structures will always be faster at
57//! what they've been specialised for, but `im` aims to provide the
58//! data structures which deliver the least chance of accidentally
59//! using them for the wrong thing.
60//!
61//! For instance, [`Vec`][std::vec::Vec] beats everything at memory
62//! usage, indexing and operations that happen at the back of the
63//! list, but is terrible at insertion and removal, and gets worse the
64//! closer to the front of the list you get.
65//! [`VecDeque`][std::collections::VecDeque] adds a little bit of
66//! complexity in order to make operations at the front as efficient
67//! as operations at the back, but is still bad at insertion and
68//! especially concatenation. [`Vector`][vector::Vector] adds another
69//! bit of complexity, and could never match [`Vec`][std::vec::Vec] at
70//! what it's best at, but in return every operation you can throw at
71//! it can be completed in a reasonable amount of time - even normally
72//! expensive operations like copying and especially concatenation are
73//! reasonably cheap when using a [`Vector`][vector::Vector].
74//!
75//! It should be noted, however, that because of its simplicity,
76//! [`Vec`][std::vec::Vec] actually beats [`Vector`][vector::Vector] even at its
77//! strongest operations at small sizes, just because modern CPUs are
78//! hyperoptimised for things like copying small chunks of contiguous memory -
79//! you actually need to go past a certain size (usually in the vicinity of
80//! several hundred elements) before you get to the point where
81//! [`Vec`][std::vec::Vec] isn't always going to be the fastest choice.
82//! [`Vector`][vector::Vector] attempts to overcome this by actually just being
83//! an array at very small sizes, and being able to switch efficiently to the
84//! full data structure when it grows large enough. Thus,
85//! [`Vector`][vector::Vector] will actually be equivalent to
86//! [Vec][std::vec::Vec] until it grows past the size of a single chunk.
87//!
88//! The maps - [`HashMap`][hashmap::HashMap] and
89//! [`OrdMap`][ordmap::OrdMap] - generally perform similarly to their
90//! equivalents in the standard library, but tend to run a bit slower
91//! on the basic operations ([`HashMap`][hashmap::HashMap] is almost
92//! neck and neck with its counterpart, while
93//! [`OrdMap`][ordmap::OrdMap] currently tends to run 2-3x slower). On
94//! the other hand, they offer the cheap copy and structural sharing
95//! between copies that you'd expect from immutable data structures.
96//!
97//! In conclusion, the aim of this library is to provide a safe
98//! default choice for the most common kinds of data structures,
99//! allowing you to defer careful thinking about the right data
100//! structure for the job until you need to start looking for
101//! optimisations - and you may find, especially for larger data sets,
102//! that immutable data structures are still the right choice.
103//!
104//! ## Values
105//!
106//! Because we need to make copies of shared nodes in these data structures
107//! before updating them, the values you store in them must implement
108//! [`Clone`][std::clone::Clone].  For primitive values that implement
109//! [`Copy`][std::marker::Copy], such as numbers, everything is fine: this is
110//! the case for which the data structures are optimised, and performance is
111//! going to be great.
112//!
113//! On the other hand, if you want to store values for which cloning is
114//! expensive, or values that don't implement [`Clone`][std::clone::Clone], you
115//! need to wrap them in [`Rc`][std::rc::Rc] or [`Arc`][std::sync::Arc]. Thus,
116//! if you have a complex structure `BigBlobOfData` and you want to store a list
117//! of them as a `Vector<BigBlobOfData>`, you should instead use a
118//! `Vector<Rc<BigBlobOfData>>`, which is going to save you not only the time
119//! spent cloning the big blobs of data, but also the memory spent keeping
120//! multiple copies of it around, as [`Rc`][std::rc::Rc] keeps a single
121//! reference counted copy around instead.
122//!
123//! If you're storing smaller values that aren't
124//! [`Copy`][std::marker::Copy]able, you'll need to exercise judgement: if your
125//! values are going to be very cheap to clone, as would be the case for short
126//! [`String`][std::string::String]s or small [`Vec`][std::vec::Vec]s, you're
127//! probably better off storing them directly without wrapping them in an
128//! [`Rc`][std::rc::Rc], because, like the [`Rc`][std::rc::Rc], they're just
129//! pointers to some data on the heap, and that data isn't expensive to clone -
130//! you might actually lose more performance from the extra redirection of
131//! wrapping them in an [`Rc`][std::rc::Rc] than you would from occasionally
132//! cloning them.
133//!
134//! ### When does cloning happen?
135//!
136//! So when will your values actually be cloned? The easy answer is only if you
137//! [`clone`][std::clone::Clone::clone] the data structure itself, and then only
138//! lazily as you change it. Values are stored in tree nodes inside the data
139//! structure, each node of which contains up to 64 values. When you
140//! [`clone`][std::clone::Clone::clone] a data structure, nothing is actually
141//! copied - it's just the reference count on the root node that's incremented,
142//! to indicate that it's shared between two data structures. It's only when you
143//! actually modify one of the shared data structures that nodes are cloned:
144//! when you make a change somewhere in the tree, the node containing the change
145//! needs to be cloned, and then its parent nodes need to be updated to contain
146//! the new child node instead of the old version, and so they're cloned as
147//! well.
148//!
149//! We can call this "lazy" cloning - if you make two copies of a data structure
150//! and you never change either of them, there's never any need to clone the
151//! data they contain. It's only when you start making changes that cloning
152//! starts to happen, and then only on the specific tree nodes that are part of
153//! the change. Note that the implications of lazily cloning the data structure
154//! extend to memory usage as well as the CPU workload of copying the data
155//! around - cloning an immutable data structure means both copies share the
156//! same allocated memory, until you start making changes.
157//!
158//! Most crucially, if you never clone the data structure, the data inside it is
159//! also never cloned, and in this case it acts just like a mutable data
160//! structure, with minimal performance differences (but still non-zero, as we
161//! still have to check for shared nodes).
162//!
163//! ## Data Structures
164//!
165//! We'll attempt to provide a comprehensive guide to the available
166//! data structures below.
167//!
168//! ### Performance Notes
169//!
170//! "Big O notation" is the standard way of talking about the time
171//! complexity of data structure operations. If you're not familiar
172//! with big O notation, here's a quick cheat sheet:
173//!
174//! *O(1)* means an operation runs in constant time: it will take the
175//! same time to complete regardless of the size of the data
176//! structure.
177//!
178//! *O(n)* means an operation runs in linear time: if you double the
179//! size of your data structure, the operation will take twice as long
180//! to complete; if you quadruple the size, it will take four times as
181//! long, etc.
182//!
183//! *O(log n)* means an operation runs in logarithmic time: for
184//! *log<sub>2</sub>*, if you double the size of your data structure,
185//! the operation will take one step longer to complete; if you
186//! quadruple the size, it will need two steps more; and so on.
187//! However, the data structures in this library generally run in
188//! *log<sub>64</sub>* time, meaning you have to make your data
189//! structure 64 times bigger to need one extra step, and 4096 times
190//! bigger to need two steps. This means that, while they still count
191//! as O(log n), operations on all but really large data sets will run
192//! at near enough to O(1) that you won't usually notice.
193//!
194//! *O(n log n)* is the most expensive operation you'll see in this
195//! library: it means that for every one of the *n* elements in your
196//! data structure, you have to perform *log n* operations. In our
197//! case, as noted above, this is often close enough to O(n) that it's
198//! not usually as bad as it sounds, but even O(n) isn't cheap and the
199//! cost still increases logarithmically, if slowly, as the size of
200//! your data increases. O(n log n) basically means "are you sure you
201//! need to do this?"
202//!
203//! *O(1)** means 'amortised O(1),' which means that an operation
204//! usually runs in constant time but will occasionally be more
205//! expensive: for instance,
206//! [`Vector::push_back`][vector::Vector::push_back], if called in
207//! sequence, will be O(1) most of the time but every 64th time it
208//! will be O(log n), as it fills up its tail chunk and needs to
209//! insert it into the tree. Please note that the O(1) with the
210//! asterisk attached is not a common notation; it's just a convention
211//! I've used in these docs to save myself from having to type
212//! 'amortised' everywhere.
213//!
214//! ### Lists
215//!
216//! Lists are sequences of single elements which maintain the order in
217//! which you inserted them. The only list in this library is
218//! [`Vector`][vector::Vector], which offers the best all round
219//! performance characteristics: it's pretty good at everything, even
220//! if there's always another kind of list that's better at something.
221//!
222//! | Type | Algorithm | Constraints | Order | Push | Pop | Split | Append | Lookup |
223//! | --- | --- | --- | --- | --- | --- | --- | --- | --- |
224//! | [`Vector<A>`][vector::Vector] | [RRB tree][rrb-tree] | [`Clone`][std::clone::Clone] | insertion | O(1)\* | O(1)\* | O(log n) | O(log n) | O(log n) |
225//!
226//! ### Maps
227//!
228//! Maps are mappings of keys to values, where the most common read
229//! operation is to find the value associated with a given key. Maps
230//! may or may not have a defined order. Any given key can only occur
231//! once inside a map, and setting a key to a different value will
232//! overwrite the previous value.
233//!
234//! | Type | Algorithm | Key Constraints | Order | Insert | Remove | Lookup |
235//! | --- | --- | --- | --- | --- | --- | --- |
236//! | [`HashMap<K, V>`][hashmap::HashMap] | [HAMT][hamt] | [`Clone`][std::clone::Clone] + [`Hash`][std::hash::Hash] + [`Eq`][std::cmp::Eq] | undefined | O(log n) | O(log n) | O(log n) |
237//! | [`OrdMap<K, V>`][ordmap::OrdMap] | [B-tree][b-tree] | [`Clone`][std::clone::Clone] + [`Ord`][std::cmp::Ord] | sorted | O(log n) | O(log n) | O(log n) |
238//!
239//! ### Sets
240//!
241//! Sets are collections of unique values, and may or may not have a
242//! defined order. Their crucial property is that any given value can
243//! only exist once in a given set.
244//!
245//! | Type | Algorithm | Constraints | Order | Insert | Remove | Lookup |
246//! | --- | --- | --- | --- | --- | --- | --- |
247//! | [`HashSet<A>`][hashset::HashSet] | [HAMT][hamt] | [`Clone`][std::clone::Clone] + [`Hash`][std::hash::Hash] + [`Eq`][std::cmp::Eq] | undefined | O(log n) | O(log n) | O(log n) |
248//! | [`OrdSet<A>`][ordset::OrdSet] | [B-tree][b-tree] | [`Clone`][std::clone::Clone] + [`Ord`][std::cmp::Ord] | sorted | O(log n) | O(log n) | O(log n) |
249//!
250//! ## In-place Mutation
251//!
252//! All of these data structures support in-place copy-on-write
253//! mutation, which means that if you're the sole user of a data
254//! structure, you can update it in place without taking the
255//! performance hit of making a copy of the data structure before
256//! modifying it (this is about an order of magnitude faster than
257//! immutable operations, almost as fast as
258//! [`std::collections`][std::collections]'s mutable data structures).
259//!
260//! Thanks to [`Rc`][std::rc::Rc]'s reference counting, we are able to
261//! determine whether a node in a data structure is being shared with
262//! other data structures, or whether it's safe to mutate it in place.
263//! When it's shared, we'll automatically make a copy of the node
264//! before modifying it. The consequence of this is that cloning a
265//! data structure becomes a lazy operation: the initial clone is
266//! instant, and as you modify the cloned data structure it will clone
267//! chunks only where you change them, so that if you change the
268//! entire thing you will eventually have performed a full clone.
269//!
270//! This also gives us a couple of other optimisations for free:
271//! implementations of immutable data structures in other languages
272//! often have the idea of local mutation, like Clojure's transients
273//! or Haskell's `ST` monad - a managed scope where you can treat an
274//! immutable data structure like a mutable one, gaining a
275//! considerable amount of performance because you no longer need to
276//! copy your changed nodes for every operation, just the first time
277//! you hit a node that's sharing structure. In Rust, we don't need to
278//! think about this kind of managed scope, it's all taken care of
279//! behind the scenes because of our low level access to the garbage
280//! collector (which, in our case, is just a simple
281//! [`Rc`][std::rc::Rc]).
282//!
283//! ## Thread Safety
284//!
285//! The data structures in the `im` crate are thread safe, through
286//! [`Arc`][std::sync::Arc]. This comes with a slight performance impact, so
287//! that if you prioritise speed over thread safety, you may want to use the
288//! `im-rc` crate instead, which is identical to `im` except that it uses
289//! [`Rc`][std::rc::Rc] instead of [`Arc`][std::sync::Arc], implying that the
290//! data structures in `im-rc` do not implement [`Send`][std::marker::Send] and
291//! [`Sync`][std::marker::Sync]. This yields approximately a 20-25% increase in
292//! general performance.
293//!
294//! ## Feature Flags
295//!
296//! `im` comes with optional support for the following crates through Cargo
297//! feature flags. You can enable them in your `Cargo.toml` file like this:
298//!
299//! ```no_compile
300//! [dependencies]
301//! im = { version = "*", features = ["proptest", "serde"] }
302//! ```
303//!
304//! | Feature | Description |
305//! | ------- | ----------- |
306//! | [`pool`](https://crates.io/crates/refpool) | Constructors and pool types for [`refpool`](https://crates.io/crates/refpool) memory pools (only available in `im-rc`) |
307//! | [`proptest`](https://crates.io/crates/proptest) | Strategies for all `im` datatypes under a `proptest` namespace, eg. `im::vector::proptest::vector()` |
308//! | [`quickcheck`](https://crates.io/crates/quickcheck) | [`quickcheck::Arbitrary`](https://docs.rs/quickcheck/latest/quickcheck/trait.Arbitrary.html) implementations for all `im` datatypes (not available in `im-rc`) |
309//! | [`rayon`](https://crates.io/crates/rayon) | parallel iterator implementations for [`Vector`][vector::Vector] (not available in `im-rc`) |
310//! | [`serde`](https://crates.io/crates/serde) | [`Serialize`](https://docs.rs/serde/latest/serde/trait.Serialize.html) and [`Deserialize`](https://docs.rs/serde/latest/serde/trait.Deserialize.html) implementations for all `im` datatypes |
311//! | [`arbitrary`](https://crates.io/crates/arbitrary/) | [`arbitrary::Arbitrary`](https://docs.rs/arbitrary/latest/arbitrary/trait.Arbitrary.html) implementations for all `im` datatypes |
312//!
313//! [std::collections]: https://doc.rust-lang.org/std/collections/index.html
314//! [std::collections::VecDeque]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html
315//! [std::vec::Vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html
316//! [std::string::String]: https://doc.rust-lang.org/std/string/struct.String.html
317//! [std::rc::Rc]: https://doc.rust-lang.org/std/rc/struct.Rc.html
318//! [std::sync::Arc]: https://doc.rust-lang.org/std/sync/struct.Arc.html
319//! [std::cmp::Eq]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
320//! [std::cmp::Ord]: https://doc.rust-lang.org/std/cmp/trait.Ord.html
321//! [std::clone::Clone]: https://doc.rust-lang.org/std/clone/trait.Clone.html
322//! [std::clone::Clone::clone]: https://doc.rust-lang.org/std/clone/trait.Clone.html#tymethod.clone
323//! [std::marker::Copy]: https://doc.rust-lang.org/std/marker/trait.Copy.html
324//! [std::hash::Hash]: https://doc.rust-lang.org/std/hash/trait.Hash.html
325//! [std::marker::Send]: https://doc.rust-lang.org/std/marker/trait.Send.html
326//! [std::marker::Sync]: https://doc.rust-lang.org/std/marker/trait.Sync.html
327//! [hashmap::HashMap]: ./struct.HashMap.html
328//! [hashset::HashSet]: ./struct.HashSet.html
329//! [ordmap::OrdMap]: ./struct.OrdMap.html
330//! [ordset::OrdSet]: ./struct.OrdSet.html
331//! [vector::Vector]: ./struct.Vector.html
332//! [vector::Vector::push_back]: ./vector/enum.Vector.html#method.push_back
333//! [rrb-tree]: https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf
334//! [hamt]: https://en.wikipedia.org/wiki/Hash_array_mapped_trie
335//! [b-tree]: https://en.wikipedia.org/wiki/B-tree
336//! [cons-list]: https://en.wikipedia.org/wiki/Cons#Lists
337
338#![forbid(rust_2018_idioms)]
339#![deny(unsafe_code, nonstandard_style)]
340#![warn(unreachable_pub, missing_docs)]
341#![cfg_attr(has_specialisation, feature(specialization))]
342
343#[cfg(test)]
344#[macro_use]
345extern crate pretty_assertions;
346
347mod config;
348mod nodes;
349mod sort;
350mod sync;
351
352#[macro_use]
353mod util;
354
355#[macro_use]
356mod ord;
357pub use crate::ord::map as ordmap;
358pub use crate::ord::set as ordset;
359
360#[macro_use]
361mod hash;
362pub use crate::hash::map as hashmap;
363pub use crate::hash::set as hashset;
364
365#[macro_use]
366pub mod vector;
367
368pub mod iter;
369
370#[cfg(any(test, feature = "proptest"))]
371pub mod proptest;
372
373#[cfg(any(test, feature = "serde"))]
374#[doc(hidden)]
375pub mod ser;
376
377#[cfg(feature = "arbitrary")]
378#[doc(hidden)]
379pub mod arbitrary;
380
381#[cfg(all(threadsafe, feature = "quickcheck"))]
382#[doc(hidden)]
383pub mod quickcheck;
384
385#[cfg(any(threadsafe, not(feature = "pool")))]
386mod fakepool;
387
388#[cfg(all(threadsafe, feature = "pool"))]
389compile_error!(
390    "The `pool` feature is not threadsafe but you've enabled it on a threadsafe version of `im`."
391);
392
393pub use crate::hashmap::HashMap;
394pub use crate::hashset::HashSet;
395pub use crate::ordmap::OrdMap;
396pub use crate::ordset::OrdSet;
397#[doc(inline)]
398pub use crate::vector::Vector;
399
400#[cfg(test)]
401mod test;
402
403#[cfg(test)]
404mod tests;
405
406/// Update a value inside multiple levels of data structures.
407///
408/// This macro takes a [`Vector`][Vector], [`OrdMap`][OrdMap] or [`HashMap`][HashMap],
409/// a key or a series of keys, and a value, and returns the data structure with the
410/// new value at the location described by the keys.
411///
412/// If one of the keys in the path doesn't exist, the macro will panic.
413///
414/// # Examples
415///
416/// ```
417/// # #[macro_use] extern crate im_rc as im;
418/// # use std::sync::Arc;
419/// # fn main() {
420/// let vec_inside_vec = vector![vector![1, 2, 3], vector![4, 5, 6]];
421///
422/// let expected = vector![vector![1, 2, 3], vector![4, 5, 1337]];
423///
424/// assert_eq!(expected, update_in![vec_inside_vec, 1 => 2, 1337]);
425/// # }
426/// ```
427///
428/// [Vector]: ../vector/enum.Vector.html
429/// [HashMap]: ../hashmap/struct.HashMap.html
430/// [OrdMap]: ../ordmap/struct.OrdMap.html
431#[macro_export]
432macro_rules! update_in {
433    ($target:expr, $path:expr => $($tail:tt) => *, $value:expr ) => {{
434        let inner = $target.get($path).expect("update_in! macro: key not found in target");
435        $target.update($path, update_in!(inner, $($tail) => *, $value))
436    }};
437
438    ($target:expr, $path:expr, $value:expr) => {
439        $target.update($path, $value)
440    };
441}
442
443/// Get a value inside multiple levels of data structures.
444///
445/// This macro takes a [`Vector`][Vector], [`OrdMap`][OrdMap] or [`HashMap`][HashMap],
446/// along with a key or a series of keys, and returns the value at the location inside
447/// the data structure described by the key sequence, or `None` if any of the keys didn't
448/// exist.
449///
450/// # Examples
451///
452/// ```
453/// # #[macro_use] extern crate im_rc as im;
454/// # use std::sync::Arc;
455/// # fn main() {
456/// let vec_inside_vec = vector![vector![1, 2, 3], vector![4, 5, 6]];
457///
458/// assert_eq!(Some(&6), get_in![vec_inside_vec, 1 => 2]);
459/// # }
460/// ```
461///
462/// [Vector]: ../vector/enum.Vector.html
463/// [HashMap]: ../hashmap/struct.HashMap.html
464/// [OrdMap]: ../ordmap/struct.OrdMap.html
465#[macro_export]
466macro_rules! get_in {
467    ($target:expr, $path:expr => $($tail:tt) => * ) => {{
468        $target.get($path).and_then(|v| get_in!(v, $($tail) => *))
469    }};
470
471    ($target:expr, $path:expr) => {
472        $target.get($path)
473    };
474}
475
476#[cfg(test)]
477mod lib_test {
478    #[test]
479    fn update_in() {
480        let vector = vector![1, 2, 3, 4, 5];
481        assert_eq!(vector![1, 2, 23, 4, 5], update_in!(vector, 2, 23));
482        let hashmap = hashmap![1 => 1, 2 => 2, 3 => 3];
483        assert_eq!(
484            hashmap![1 => 1, 2 => 23, 3 => 3],
485            update_in!(hashmap, 2, 23)
486        );
487        let ordmap = ordmap![1 => 1, 2 => 2, 3 => 3];
488        assert_eq!(ordmap![1 => 1, 2 => 23, 3 => 3], update_in!(ordmap, 2, 23));
489
490        let vecs = vector![vector![1, 2, 3], vector![4, 5, 6], vector![7, 8, 9]];
491        let vecs_target = vector![vector![1, 2, 3], vector![4, 5, 23], vector![7, 8, 9]];
492        assert_eq!(vecs_target, update_in!(vecs, 1 => 2, 23));
493    }
494
495    #[test]
496    fn get_in() {
497        let vector = vector![1, 2, 3, 4, 5];
498        assert_eq!(Some(&3), get_in!(vector, 2));
499        let hashmap = hashmap![1 => 1, 2 => 2, 3 => 3];
500        assert_eq!(Some(&2), get_in!(hashmap, &2));
501        let ordmap = ordmap![1 => 1, 2 => 2, 3 => 3];
502        assert_eq!(Some(&2), get_in!(ordmap, &2));
503
504        let vecs = vector![vector![1, 2, 3], vector![4, 5, 6], vector![7, 8, 9]];
505        assert_eq!(Some(&6), get_in!(vecs, 1 => 2));
506    }
507}