rs_graph/collections/
map.rs

1/*
2 * Copyright (c) 2018, 2020, 2021, 2022 Frank Fischer <frank-fischer@shadow-soft.de>
3 *
4 * This program is free software: you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
16 */
17
18use crate::traits::IndexGraph;
19use std::collections::HashMap;
20use std::hash::{BuildHasher, Hash};
21
22/// A (finite) map of items (node or edges) of a graph to some value.
23pub trait ItemMap<K, V>
24where
25    K: Copy,
26{
27    /// Return `true` if this map is empty.
28    fn is_empty(&self) -> bool {
29        self.len() == 0
30    }
31
32    /// Return the number of items in this map.
33    fn len(&self) -> usize;
34
35    /// Remove all items from the map.
36    fn clear(&mut self);
37
38    /// Add one item to the map.
39    ///
40    /// Return `true` iff `u` had not been contained in this map before. Otherwise
41    /// case the value is *not* updated.
42    fn insert(&mut self, key: K, value: V) -> bool;
43
44    /// Add one item to the map.
45    ///
46    /// Return `true` iff `key` had not been contained in this map before. In this
47    /// case the value *is* updated.
48    fn insert_or_replace(&mut self, key: K, value: V) -> bool;
49
50    /// Remove one item from the map.
51    ///
52    /// Returns `true` if the item had been contained in the map, otherwise
53    /// false.
54    fn remove(&mut self, key: K) -> bool;
55
56    /// Return a read-only reference to the element with the given key.
57    fn get(&self, key: K) -> Option<&V>;
58
59    /// Return a mutable reference to the element with the given key.
60    fn get_mut(&mut self, key: K) -> Option<&mut V>;
61
62    /// Return `true` iff item `u` is contained in this map.
63    fn contains(&self, key: K) -> bool;
64}
65
66impl<'a, K, V, S> ItemMap<K, V> for &'a mut S
67where
68    K: Copy,
69    S: ItemMap<K, V>,
70{
71    fn is_empty(&self) -> bool {
72        (**self).is_empty()
73    }
74
75    fn len(&self) -> usize {
76        (**self).len()
77    }
78
79    fn clear(&mut self) {
80        (**self).clear()
81    }
82
83    fn insert(&mut self, key: K, value: V) -> bool {
84        (**self).insert(key, value)
85    }
86
87    fn insert_or_replace(&mut self, key: K, value: V) -> bool {
88        (**self).insert_or_replace(key, value)
89    }
90
91    fn remove(&mut self, key: K) -> bool {
92        (**self).remove(key)
93    }
94
95    fn get(&self, key: K) -> Option<&V> {
96        (**self).get(key)
97    }
98
99    fn get_mut(&mut self, key: K) -> Option<&mut V> {
100        (**self).get_mut(key)
101    }
102
103    fn contains(&self, key: K) -> bool {
104        (**self).contains(key)
105    }
106}
107
108impl<K, V, S> ItemMap<K, V> for HashMap<K, V, S>
109where
110    K: Copy + Eq + Hash,
111    S: BuildHasher,
112{
113    fn is_empty(&self) -> bool {
114        HashMap::is_empty(self)
115    }
116
117    fn len(&self) -> usize {
118        HashMap::len(self)
119    }
120
121    fn clear(&mut self) {
122        HashMap::clear(self)
123    }
124
125    fn insert(&mut self, key: K, value: V) -> bool {
126        let mut new = false;
127        HashMap::entry(self, key).or_insert_with(|| {
128            new = true;
129            value
130        });
131        new
132    }
133
134    fn insert_or_replace(&mut self, key: K, value: V) -> bool {
135        HashMap::insert(self, key, value).is_some()
136    }
137
138    fn remove(&mut self, key: K) -> bool {
139        HashMap::remove(self, &key).is_some()
140    }
141
142    fn get(&self, key: K) -> Option<&V> {
143        HashMap::get(self, &key)
144    }
145
146    fn get_mut(&mut self, key: K) -> Option<&mut V> {
147        HashMap::get_mut(self, &key)
148    }
149
150    fn contains(&self, key: K) -> bool {
151        HashMap::contains_key(self, &key)
152    }
153}
154
155pub struct NodeVecMap<'a, G, V> {
156    graph: &'a G,
157    data: Vec<Option<V>>,
158    nitems: usize,
159}
160
161impl<'a, G, V> NodeVecMap<'a, G, V>
162where
163    G: IndexGraph,
164    V: Clone,
165{
166    pub fn new(g: &'a G) -> Self {
167        NodeVecMap {
168            graph: g,
169            data: vec![None; g.num_nodes()],
170            nitems: 0,
171        }
172    }
173}
174
175impl<'a, G, V> ItemMap<G::Node<'a>, V> for NodeVecMap<'a, G, V>
176where
177    G: IndexGraph,
178    V: Clone,
179{
180    fn is_empty(&self) -> bool {
181        self.nitems == 0
182    }
183
184    fn len(&self) -> usize {
185        self.nitems
186    }
187
188    fn clear(&mut self) {
189        self.nitems = 0;
190        self.data.fill(None)
191    }
192
193    fn insert(&mut self, key: G::Node<'a>, value: V) -> bool {
194        let i = self.graph.node_id(key);
195        if self.data[i].is_none() {
196            self.data[i] = Some(value);
197            true
198        } else {
199            false
200        }
201    }
202
203    fn insert_or_replace(&mut self, key: G::Node<'a>, value: V) -> bool {
204        self.data[self.graph.node_id(key)].replace(value).is_none()
205    }
206
207    fn remove(&mut self, key: G::Node<'a>) -> bool {
208        self.data[self.graph.node_id(key)].take().is_some()
209    }
210
211    fn get(&self, key: G::Node<'a>) -> Option<&V> {
212        self.data[self.graph.node_id(key)].as_ref()
213    }
214
215    fn get_mut(&mut self, key: G::Node<'a>) -> Option<&mut V> {
216        self.data[self.graph.node_id(key)].as_mut()
217    }
218
219    fn contains(&self, key: G::Node<'a>) -> bool {
220        self.data[self.graph.node_id(key)].is_some()
221    }
222}
rs_graph/collections/map.rs

rs_graph/collections/
map.rs
