1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
/* This file is part of rpds. * * rpds is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published * by the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * rpds is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with rpds. If not, see <http://www.gnu.org/licenses/>. */ #![cfg_attr(feature = "fatal-warnings", deny(warnings))] // Note: Keep this in sync with `README.md`. Note that the doc links must be removed. //! # Rust Persistent Data Structures //! //! Rust Persistent Data Structures provides [fully persistent data structures](https://en.wikipedia.org/wiki/Persistent_data_structure) //! with structural sharing. //! //! # Data Structures //! //! This crate implements the following data structures: //! //! 1. [`List`](#list) //! 2. [`Vector`](#vector) //! 3. [`Stack`](#stack) //! 4. [`Queue`](#queue) //! 5. [`HashTrieMap`](#hashtriemap) //! 6. [`HashTrieSet`](#hashtrieset) //! //! ## `List` //! [](sequence/list/struct.List.html) //! //! Your classic functional list. //! //! ### Example //! //! ```rust //! use rpds::List; //! //! let list = List::new().push_front("list"); //! //! assert_eq!(list.first(), Some(&"list")); //! //! let a_list = list.push_front("a"); //! //! assert_eq!(a_list.first(), Some(&"a")); //! //! let list_dropped = a_list.drop_first().unwrap(); //! //! assert_eq!(list_dropped, list); //! ``` //! //! ## `Vector` //! [](sequence/vector/struct.Vector.html) //! //! An sequence that can be indexed. The implementation is described in //! [Understanding Persistent Vector Part 1](http://hypirion.com/musings/understanding-persistent-vector-pt-1) //! and [Understanding Persistent Vector Part 2](http://hypirion.com/musings/understanding-persistent-vector-pt-2). //! //! ### Example //! //! ```rust //! use rpds::Vector; //! //! let vector = Vector::new() //! .push_back("I'm") //! .push_back("a") //! .push_back("vector"); //! //! assert_eq!(vector[1], "a"); //! //! let screaming_vector = vector //! .drop_last().unwrap() //! .push_back("VECTOR!!!"); //! //! assert_eq!(screaming_vector[2], "VECTOR!!!"); //! ``` //! //! ## `Stack` //! [](stack/struct.Stack.html) //! //! A LIFO (last in, first out) data structure. This is just a [`List`](#list) on disguise. //! //! ### Example //! //! ```rust //! use rpds::Stack; //! //! let stack = Stack::new().push("stack"); //! //! assert_eq!(stack.peek(), Some(&"stack")); //! //! let a_stack = stack.push("a"); //! //! assert_eq!(a_stack.peek(), Some(&"a")); //! //! let stack_popped = a_stack.pop().unwrap(); //! //! assert_eq!(stack_popped, stack); //! ``` //! //! ## `Queue` //! [](queue/struct.Queue.html) //! //! A FIFO (first in, first out) data structure. //! //! ### Example //! //! ```rust //! use rpds::Queue; //! //! let queue = Queue::new() //! .enqueue("um") //! .enqueue("dois") //! .enqueue("tres"); //! //! assert_eq!(queue.peek(), Some(&"um")); //! //! let queue_dequeued = queue.dequeue().unwrap(); //! //! assert_eq!(queue_dequeued.peek(), Some(&"dois")); //! ``` //! //! ## `HashTrieMap` //! [](map/hash_trie_map/struct.HashTrieMap.html) //! //! A map implemented with a hash array mapped trie. See //! [Ideal Hash Trees](https://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf) for //! details. //! //! ### Example //! //! ```rust //! use rpds::HashTrieMap; //! //! let map_en = HashTrieMap::new() //! .insert(0, "zero") //! .insert(1, "one"); //! //! assert_eq!(map_en.get(&1), Some(&"one")); //! //! let map_pt = map_en //! .insert(1, "um") //! .insert(2, "dois"); //! //! assert_eq!(map_pt.get(&2), Some(&"dois")); //! //! let map_pt_binary = map_pt.remove(&2); //! //! assert_eq!(map_pt_binary.get(&2), None); //! ``` //! //! ## `HashTrieSet` //! [](set/hash_trie_set/struct.HashTrieSet.html) //! //! A set implemented with a [`HashTrieMap`](#hashtriemap). //! //! ### Example //! //! ```rust //! use rpds::HashTrieSet; //! //! let set = HashTrieSet::new() //! .insert("zero") //! .insert("one"); //! //! assert!(set.contains(&"one")); //! //! let set_extended = set.insert("two"); //! //! assert!(set_extended.contains(&"two")); //! //! let set_positive = set_extended.remove(&"zero"); //! //! assert!(!set_positive.contains(&"zero")); //! ``` pub mod sequence; pub mod stack; pub mod queue; pub mod map; pub mod set; pub use sequence::list::List; pub use sequence::vector::Vector; pub use stack::Stack; pub use queue::Queue; pub use map::hash_trie_map::HashTrieMap; pub use set::hash_trie_set::HashTrieSet;