fera_graph/sets/
mod.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//! Edge and vertex sets.
6
7use prelude::*;
8
9use std::iter;
10use std::ops::IndexMut;
11use std::slice;
12use std::vec;
13
14use rand::Rng;
15
16// TODO: use OptionalMax
17const NONE: usize = ::std::usize::MAX;
18
19pub struct FastVecSet<T, P>
20where
21    P: IndexMut<T, Output = usize>,
22    T: Copy,
23{
24    index: P,
25    values: Vec<T>,
26}
27
28impl<T, P> FastVecSet<T, P>
29where
30    P: IndexMut<T, Output = usize>,
31    T: Copy,
32{
33    pub fn insert(&mut self, item: T) -> bool {
34        if self.index(item) == None {
35            let i = self.values.len();
36            self.values.push(item);
37            self.set_index(item, i);
38            true
39        } else {
40            false
41        }
42    }
43
44    pub fn remove(&mut self, item: T) -> bool {
45        if let Some(i) = self.index(item) {
46            let last = self.values.last().cloned();
47            self.values.swap_remove(i);
48            if let Some(last) = last {
49                self.set_index(last, i);
50            }
51            self.set_index(item, NONE);
52            true
53        } else {
54            false
55        }
56    }
57
58    pub fn clear(&mut self) {
59        for &v in &self.values {
60            self.index[v] = NONE;
61        }
62        self.values.clear();
63    }
64
65    #[inline]
66    pub fn contains(&self, item: T) -> bool {
67        self.index(item).is_some()
68    }
69
70    #[inline]
71    pub fn iter(&self) -> iter::Cloned<slice::Iter<T>> {
72        self.values.iter().cloned()
73    }
74
75    #[inline]
76    pub fn len(&self) -> usize {
77        self.values.len()
78    }
79
80    #[inline]
81    pub fn is_empty(&self) -> bool {
82        self.values.is_empty()
83    }
84
85    #[inline]
86    pub fn choose<R: Rng>(&self, mut rng: R) -> Option<&T> {
87        rng.choose(&self.values)
88    }
89
90    #[inline]
91    fn index(&self, item: T) -> Option<usize> {
92        let i = self.index[item];
93        if i == NONE {
94            None
95        } else {
96            Some(i)
97        }
98    }
99
100    #[inline]
101    fn set_index(&mut self, item: T, i: usize) {
102        self.index[item] = i;
103    }
104}
105
106impl<T, P> IntoIterator for FastVecSet<T, P>
107where
108    P: IndexMut<T, Output = usize>,
109    T: Copy,
110{
111    type Item = T;
112    type IntoIter = vec::IntoIter<T>;
113
114    fn into_iter(self) -> Self::IntoIter {
115        self.values.into_iter()
116    }
117}
118
119impl<'a, T, P> IntoIterator for &'a FastVecSet<T, P>
120where
121    P: IndexMut<T, Output = usize>,
122    T: Copy,
123{
124    type Item = T;
125    type IntoIter = iter::Cloned<slice::Iter<'a, T>>;
126
127    fn into_iter(self) -> Self::IntoIter {
128        self.values.iter().cloned()
129    }
130}
131
132impl<'a, T, P> Extend<T> for FastVecSet<T, P>
133where
134    P: IndexMut<T, Output = usize>,
135    T: Copy,
136{
137    fn extend<I>(&mut self, iter: I)
138    where
139        I: IntoIterator<Item = T>,
140    {
141        for item in iter {
142            self.insert(item);
143        }
144    }
145}
146
147// FIXME: how to rewrite this without using fake type parameters?
148impl FastVecSet<usize, Vec<usize>> {
149    pub fn new_vertex_set<G>(g: &G) -> FastVecSet<Vertex<G>, DefaultVertexPropMut<G, usize>>
150    where
151        G: WithVertexProp<usize>,
152    {
153        FastVecSet {
154            index: g.vertex_prop(NONE),
155            values: vec![],
156        }
157    }
158
159    pub fn new_edge_set<G>(g: &G) -> FastVecSet<Edge<G>, DefaultEdgePropMut<G, usize>>
160    where
161        G: WithEdgeProp<usize>,
162    {
163        FastVecSet {
164            index: g.edge_prop(NONE),
165            values: vec![],
166        }
167    }
168}
fera_graph/sets/mod.rs

fera_graph/sets/
mod.rs
