dsa_rust/associative/
sorted_map.rs

1/*! Safe sorted map using Vec
2
3# About
4
5 ```rust
6    use dsa_rust::associative::sorted_map::SortedMap;
7
8    // Establishes a baseline map
9    let list = vec![
10        ("Bobson", 29),
11        ("Brain", 39),
12        ("Dangus", 34),
13        ("Dingus", 34),
14        ("Peter", 41),
15        ("Pingus", 45),
16        ("Remus", 27),
17        ("Romulus", 28),
18    ];
19    let mut map = SortedMap::new();
20
21    assert_eq!(map.cap(), 0);
22    assert_eq!(map.entries(), 0);
23    for e in list {
24        eprintln!("Inserting {}", &e.0);
25        map.put(e.0, e.1);
26    }
27    assert_eq!(map.cap(), 8);
28    assert_eq!(map.entries(), 8);
29
30    // Tests the get function
31    let age = map.get("Peter");
32    assert!(age.is_some());
33    assert_eq!(age.unwrap(), &41);
34
35    // Tests replacing a value for an existing key
36    let old = map.put("Peter", 42);
37    assert_eq!(*old.unwrap().value(), 41);
38    let age = map.get("Peter");
39    assert!(age.is_some());
40    assert_eq!(age.unwrap(), &42);
41    assert_eq!(map.entries(), 8);
42
43    // Tests the remove function
44    let removed = map.remove("Pingus");
45    assert!(removed.is_some());
46    assert_eq!(*removed.unwrap().value(), 45);
47    assert_eq!(map.entries(), 7);
48
49 ```
50*/
51
52//use std::cmp::Ordering::{Equal, Greater, Less};
53
54use std::fmt::Debug;
55
56#[derive(Debug, PartialEq)]
57pub struct Entry<K, V> {
58    key: K,
59    value: V,
60}
61impl<K, V> Entry<K, V>
62where
63    K: Debug + PartialEq,
64    V: PartialEq,
65{
66    /// Constructs a new Entry
67    fn new(key: K, value: V) -> Entry<K, V> {
68        Entry { key, value }
69    }
70
71    /// Returns the key for an Entry
72    pub fn key(&self) -> &K {
73        &self.key
74    }
75
76    /// Returns the value for an Entry
77    pub fn value(&self) -> &V {
78        &self.value
79    }
80}
81#[derive(Debug)]
82pub struct SortedMap<K, V> {
83    data: Vec<Option<Entry<K, V>>>,
84    size: usize,
85}
86impl<K, V> Default for SortedMap<K, V>
87where
88    K: Debug + PartialEq + Ord,
89    V: PartialEq,
90{
91    fn default() -> Self {
92        Self::new()
93    }
94}
95impl<K, V> SortedMap<K, V>
96where
97    K: Debug + PartialEq + Ord,
98    V: PartialEq,
99{
100    /** Every structure needs a constructor */
101    pub fn new() -> SortedMap<K, V> {
102        SortedMap {
103            data: Vec::new(),
104            size: 0,
105        }
106    }
107
108    /// Returns the capacity of the map
109    pub fn cap(&self) -> usize {
110        self.data.len()
111    }
112
113    /// Returns the number of entries in the map
114    pub fn entries(&self) -> usize {
115        self.size
116    }
117
118    /// Convenience wrapper for busy recursive signature method that does all the real work.
119    /// Uses a binary search algorithm to find indexes in `O(log(n))` time.
120    /// NOTE: Calling function must handle case of entering first entry into empty list
121    fn find_index(&self, target: &K) -> usize {
122        let right: usize = self.data.len() - 1;
123        Self::find_index_rec(&self.data, target, 0, right)
124    }
125    /** If the tarket is in the list the function returns the index,
126    if the target is not in the list the function returns the next appropriate index */
127    fn find_index_rec(
128        data: &Vec<Option<Entry<K, V>>>,
129        key: &K,
130        left: usize,
131        right: usize,
132    ) -> usize {
133        // Recursive base case returns next viable index when the key is not found
134        if left > right {
135            left
136        } else {
137            let mid = (left + right) / 2;
138            if data[mid].is_some() && *key == data[mid].as_ref().unwrap().key {
139                mid
140            } else if data[mid].is_some() && *key < data[mid].as_ref().unwrap().key {
141                Self::find_index_rec(data, key, left, mid - 1)
142            } else {
143                Self::find_index_rec(data, key, mid + 1, right)
144            }
145        }
146    }
147
148    ///  Gets the value associated with the provided key in `O(log(n))` time, if it exists in the map.
149    pub fn get(&self, key: K) -> Option<&V> {
150        let j: usize = self.find_index(&key);
151        if self.data[j].is_some() && self.data[j].as_ref().unwrap().key == key {
152            return Some(&self.data[j].as_ref().unwrap().value);
153        }
154        None
155    }
156
157    /// Inserts an entry into the map while maintaining sorted order by key in _O(n)_ (_n/2_ average) time.
158    pub fn put(&mut self, key: K, value: V) -> Option<Entry<K, V>> {
159        // First entry
160        if self.data.is_empty() {
161            let new: Entry<K, V> = Entry::new(key, value);
162            self.data.insert(0, Some(new)); // Results in O(n) resize operations
163            self.size += 1;
164            return None;
165        }
166
167        // Searches for existing entry
168        let index = self.find_index(&key);
169        // The key already exists
170        if index < self.data.len() && self.data[index].as_ref().unwrap().key == key {
171            // The location has a previous value
172            let old: Entry<K, V> = self.data[index].take().unwrap();
173            let new: Entry<K, V> = Entry::new(key, value);
174            self.data[index] = Some(new);
175            Some(old)
176        } else {
177            let new: Entry<K, V> = Entry::new(key, value);
178            self.data.insert(index, Some(new)); // Results in O(n) resize operations
179            self.size += 1;
180            None
181        }
182    }
183
184    /// Removes and returns the entry associated with a given key in _O(log(n))_ time.
185    /// TODO: The take() operation leaves None, which prevents _O(n)_ shifts, but isn't very clean.
186    pub fn remove(&mut self, key: K) -> Option<Entry<K, V>> {
187        let j: usize = self.find_index(&key);
188        if self.data[j].is_some() && self.data[j].as_ref().unwrap().key == key {
189            self.size -= 1;
190            return self.data[j].take();
191        }
192        None
193    }
194}
195
196#[test]
197fn find_index_test() {
198    let list = vec![
199        Some(Entry {
200            key: "Bobson",
201            value: 29,
202        }),
203        Some(Entry {
204            key: "Brain",
205            value: 39,
206        }),
207        Some(Entry {
208            key: "Dangus",
209            value: 34,
210        }),
211        Some(Entry {
212            key: "Dingus",
213            value: 34,
214        }),
215        Some(Entry {
216            key: "Peter",
217            value: 41,
218        }),
219        Some(Entry {
220            key: "Pingus",
221            value: 45,
222        }),
223        Some(Entry {
224            key: "Remus",
225            value: 27,
226        }),
227        Some(Entry {
228            key: "Romulus",
229            value: 28,
230        }),
231    ];
232    // Key exists
233    let index = SortedMap::find_index_rec(&list, &"Brain", 0, list.len() - 1);
234    assert_eq!(index, 1);
235    // Key exists
236    let index = SortedMap::find_index_rec(&list, &"Pingus", 0, list.len() - 1);
237    assert_eq!(index, 5);
238    // Key does not exist
239    let index = SortedMap::find_index_rec(&list, &"Florbus", 0, list.len() - 1);
240    assert_eq!(index, 4);
241}
242
243#[test]
244fn general_test() {
245    // Establishes a baseline map
246    let list = vec![
247        ("Bobson", 29),
248        ("Brain", 39),
249        ("Dangus", 34),
250        ("Dingus", 34),
251        ("Peter", 41),
252        ("Pingus", 45),
253        ("Remus", 27),
254        ("Romulus", 28),
255    ];
256    let mut map = SortedMap::new();
257    assert_eq!(map.data.len(), 0);
258    assert_eq!(map.size, 0);
259    for e in list {
260        eprintln!("Inserting {}", &e.0);
261        map.put(e.0, e.1);
262    }
263    assert_eq!(map.data.len(), 8);
264    assert_eq!(map.size, 8);
265
266    // Tests the get function
267    let age = map.get("Peter");
268    assert!(age.is_some());
269    assert_eq!(age.unwrap(), &41);
270
271    // Tests replacing a value for an existing key
272    let old = map.put("Peter", 42);
273    assert_eq!(old.unwrap().value, 41);
274    let age = map.get("Peter");
275    assert!(age.is_some());
276    assert_eq!(age.unwrap(), &42);
277    assert_eq!(map.size, 8);
278
279    // Tests the remove function
280    let removed = map.remove("Pingus");
281    assert!(removed.is_some());
282    assert_eq!(removed.unwrap().value, 45);
283    assert_eq!(map.size, 7);
284}
dsa_rust/associative/sorted_map.rs

dsa_rust/associative/
sorted_map.rs
