geo_booleanop/splay/
set.rs

1use super::tree;
2use super::SplayTree;
3use std::cmp::Ordering;
4
5pub struct SplaySet<T, C>
6where
7    C: Fn(&T, &T) -> Ordering,
8{
9    tree: SplayTree<T, (), C>,
10}
11
12impl<T, C> SplaySet<T, C>
13where
14    C: Fn(&T, &T) -> Ordering,
15{
16    pub fn new(comparator: C) -> SplaySet<T, C> {
17        SplaySet {
18            tree: SplayTree::new(comparator),
19        }
20    }
21
22    pub fn len(&self) -> usize {
23        self.tree.len()
24    }
25    pub fn is_empty(&self) -> bool {
26        self.len() == 0
27    }
28    pub fn clear(&mut self) {
29        self.tree.clear()
30    }
31
32    pub fn contains(&self, t: &T) -> bool {
33        self.tree.contains(t)
34    }
35
36    pub fn find(&self, t: &T) -> Option<&T> {
37        self.tree.find_key(t)
38    }
39
40    pub fn next(&self, t: &T) -> Option<&T> {
41        self.tree.next(t).map(|kv| kv.0)
42    }
43
44    pub fn prev(&self, t: &T) -> Option<&T> {
45        self.tree.prev(t).map(|kv| kv.0)
46    }
47
48    pub fn insert(&mut self, t: T) -> bool {
49        self.tree.insert(t, ()).is_none()
50    }
51
52    pub fn remove(&mut self, t: &T) -> bool {
53        self.tree.remove(t).is_some()
54    }
55
56    pub fn min(&self) -> Option<&T> {
57        self.tree.min()
58    }
59
60    pub fn max(&self) -> Option<&T> {
61        self.tree.max()
62    }
63}
64
65impl<T, C> IntoIterator for SplaySet<T, C>
66where
67    C: Fn(&T, &T) -> Ordering,
68{
69    type Item = T;
70    type IntoIter = IntoIter<T>;
71
72    fn into_iter(self) -> Self::IntoIter {
73        IntoIter {
74            inner: self.tree.into_iter(),
75        }
76    }
77}
78
79pub struct IntoIter<T> {
80    inner: tree::IntoIter<T, ()>,
81}
82
83impl<T> Iterator for IntoIter<T> {
84    type Item = T;
85    fn next(&mut self) -> Option<T> {
86        self.inner.next().map(|p| p.0)
87    }
88    fn size_hint(&self) -> (usize, Option<usize>) {
89        self.inner.size_hint()
90    }
91}
92
93impl<T> DoubleEndedIterator for IntoIter<T> {
94    fn next_back(&mut self) -> Option<T> {
95        self.inner.next_back().map(|(k, _)| k)
96    }
97}
98
99impl<T, C> Extend<T> for SplaySet<T, C>
100where
101    C: Fn(&T, &T) -> Ordering,
102{
103    fn extend<I: IntoIterator<Item = T>>(&mut self, i: I) {
104        for t in i {
105            self.insert(t);
106        }
107    }
108}
geo_booleanop/splay/set.rs

geo_booleanop/splay/
set.rs
