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 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
//! This crate is meant to provide an interface for vectors that not only store data, but also its order. This type of vector is called a mapped vector. //! A mapped vector is suitable for the fast processing of large types, because in the case of large types, it's faster to move around a few numbers specifying //! the order of the data than to move around the actual data. The reverse and rotate functions of a mapped vector are O(1), because the reverse function simply //! changes the function to filter indices with, and the rotate function only has to edit a number offset for each index and possibly swap a few functions. //! Inserts and removes are also generally faster with this, even for small types. A mapped vector also supports turning into a regular vector, although this can //! be expensive, so it's recommended to use the get_mapped method to get a vector of references to elements in order instead. This works on no_std with alloc. //! //! Example Usage with Random Numbers and Timed Functions: //! //! # use mapped_vec::MappedVec; //! # use rand::prelude::*; //! # //! # fn main() { //! # let mut rng = rand::thread_rng(); //! # let mut rgen = (0..100_000).map(|_| rng.gen::<f64>()).collect::<Vec<f64>>(); //! # //! # let mut mapped = MappedVec::new(); //! # mapped.extend_from_slice(&rgen); //! # //! # let ind = rng.gen::<u16>() as usize; //! # //! # let timed = std::time::Instant::now(); //! # mapped.remove(ind); //! # println!("Remove of mapped vector: {:?}", timed.elapsed()); //! # //! # let timed = std::time::Instant::now(); //! # rgen.remove(ind); //! # println!("Remove of regular vector: {:?}", timed.elapsed()); //! # //! # let timed = std::time::Instant::now(); //! # mapped.insert(ind, 0.0); //! # println!("Insert of mapped vector: {:?}", timed.elapsed()); //! # //! # let timed = std::time::Instant::now(); //! # rgen.insert(ind, 0.0); //! # println!("Insert of regular vector: {:?}", timed.elapsed()); //! # //! # let timed = std::time::Instant::now(); //! # mapped.reverse(); //! # println!("Time to reverse mapped vector: {:?}", timed.elapsed()); //! # //! # let timed = std::time::Instant::now(); //! # rgen.reverse(); //! # println!("Time to reverse regular vector: {:?}", timed.elapsed()); //! # //! # let timed = std::time::Instant::now(); //! # let rvec = mapped.to_vec(); //! # println!("Time to convert mapped vector to real vector: {:?}", timed.elapsed()); //! # //! # assert_eq!(rvec, rgen); //! # } #![no_std] #![forbid(unsafe_code)] extern crate alloc; use alloc::vec::Vec; use core::ops::{Index, IndexMut}; mod ring; use ring::Ring; /// See the crate-level documentation for the description of this structure, which is all of the public API in this crate, as well as the method documentation for more info. pub struct MappedVec<T> { vector: Vec<T>, indices: Ring<usize>, } impl<T> MappedVec<T> { /// This creates a new mapped vector. pub fn new() -> MappedVec<T> { MappedVec { vector: Vec::new(), indices: Ring::new(), } } /// This appends a mapped vector to this one. pub fn append(&mut self, v: &mut MappedVec<T>) { for x in 0..v.indices.len() { v.indices[x] += self.vector.len(); } self.indices.append(&mut v.indices); self.vector.append(&mut v.vector); *v = MappedVec::new(); } /// This gets the length of a mapped vector. pub fn len(&self) -> usize { self.indices.len() } /// This adds an element to a mapped vector. pub fn push(&mut self, value: T) { self.indices.push(self.vector.len()); self.vector.push(value); } /// This quickly swaps elements of the vector. pub fn swap(&mut self, x: usize, y: usize) { self.indices.swap(x, y); } /// This quickly pops off an element of the vector. pub fn pop(&mut self) { self.indices.pop(); } /// This quickly removes an element of the vector. pub fn remove(&mut self, index: usize) { self.indices.remove(index); } /// This quickly inserts an element into an index of the vector. pub fn insert(&mut self, index: usize, value: T) { self.vector.push(value); self.indices.insert(index, self.vector.len() - 1); } /// This quickly reverses the vector. pub fn reverse(&mut self) { self.indices.reverse(); } /// This quickly rotates the vector's elements. pub fn rotate(&mut self, offs: isize) { self.indices.rotate(offs); } /// This clears the vector. pub fn clear(&mut self) { *self = MappedVec::new(); } /// This resizes a vector to a specific size. If the size exceeds the length of the vector, then the remaining elements are filled in by a specified closure. pub fn resize_with<F: Fn() -> T>(&mut self, nl: usize, f: F) { if nl <= self.len() { for _ in nl..self.len() { self.indices.pop(); } } else { let diff = nl - self.len(); for _ in 0..diff { self.push(f()); } } } /// This removes an element without caring about ordering. pub fn swap_remove(&mut self, index: usize) { self.swap(index, self.len() - 1); self.indices.pop(); } /// This checks if the vector is empty. pub fn is_empty(&self) -> bool { self.len() == 0 } /// This changes the layout of the vector and resets the indices while maintaining the same indexing behavior. pub fn update_vector(&mut self) { for (n, x) in self.indices.iter_mut().enumerate() { self.vector.swap(*x, n); *x = n; } } /// This extends the vector by an iterator. pub fn extend<I: Iterator<Item = T> + Clone>(&mut self, iterator: I) { self.indices.extend(0 + self.vector.len()..iterator.clone().count() + self.vector.len()); self.vector.extend(iterator); } /// This gets an ordered vector of references to the elements of this vector. pub fn get_mapped(&self) -> Vec<&T> { let mut output = Vec::new(); for x in 0..self.len() { output.push(self.index(x)); } output } } impl<T> Index<usize> for MappedVec<T> { type Output = T; fn index(&self, index: usize) -> &T { self.vector.index(self.indices[index]) } } impl<T> IndexMut<usize> for MappedVec<T> { fn index_mut(&mut self, index: usize) -> &mut T { self.vector.index_mut(self.indices[index]) } } impl<T: Clone> MappedVec<T> { /// This extends the vector. pub fn extend_from_slice(&mut self, input: &[T]) { self.indices.extend(self.len()..self.len() + input.len()); self.vector.extend(input.iter().cloned()); } /// This is an expensive operation that turns this mapped vector into a regular one. It is recommended to use get_mapped whenever possible over this. pub fn to_vec(&self) -> Vec<T> { let mut output = Vec::new(); for x in 0..self.len() { output.push(self.index(x).clone()); } output } /// This resizes the vector. If the size is large than the current size, then the remaining elements are turned into a specified value. pub fn resize(&mut self, nl: usize, v: T) { if nl <= self.len() { for _ in nl..self.len() { self.indices.pop(); } } else { let diff = nl - self.len(); for _ in 0..diff { self.push(v.clone()); } } } }