haar_lib/ds/
ordered_set.rs

1//! 順序付き集合
2use crate::ds::ordered_map::*;
3
4/// 順序付き集合
5#[derive(Default)]
6pub struct OrderedSet<K: Ord> {
7    map: OrderedMap<K, ()>,
8}
9
10impl<K: Ord> OrderedSet<K> {
11    /// 空の`OrderedSet`を返す。
12    pub fn new() -> Self {
13        Self {
14            map: OrderedMap::new(),
15        }
16    }
17
18    /// 要素数を返す。
19    pub fn len(&self) -> usize {
20        self.map.len()
21    }
22
23    /// 要素数が`0`ならば`true`を返す。
24    pub fn is_empty(&self) -> bool {
25        self.map.is_empty()
26    }
27
28    /// `key`が存在するとき、それが何番目のキーであるかを`Ok`で返す。
29    /// そうでないとき、仮に`key`があったとき何番目のキーであったか、を`Err`で返す。
30    pub fn binary_search(&self, key: &K) -> Result<usize, usize> {
31        self.map.binary_search(key).map(|(k, _)| k)
32    }
33
34    /// `l`以上`r`未満の値の個数を返す。
35    pub fn count(&self, l: &K, r: &K) -> usize {
36        let r = match self.binary_search(r) {
37            Ok(i) | Err(i) => i,
38        };
39        let l = match self.binary_search(l) {
40            Ok(i) | Err(i) => i,
41        };
42        r.saturating_sub(l)
43    }
44
45    /// `key`以下の最大のキーをもつキーを返す。
46    pub fn max_le<'a>(&'a self, key: &'a K) -> Option<&'a K> {
47        self.map.max_le(key).map(|(k, _)| k)
48    }
49
50    /// `key`以上の最小のキーをもつキーを返す。
51    pub fn min_ge<'a>(&'a self, key: &'a K) -> Option<&'a K> {
52        self.map.min_ge(key).map(|(k, _)| k)
53    }
54
55    /// `key`をキーとして持つならば`true`を返す。
56    pub fn contains(&self, key: &K) -> bool {
57        self.map.contains(key)
58    }
59
60    /// `key`が存在するとき、`key`を挿入して、`true`を返す。
61    pub fn insert(&mut self, key: K) -> bool {
62        self.map.insert(key, ()).is_some()
63    }
64
65    /// キー`key`があれば、そのキーを削除して、`true`を返す。
66    pub fn remove(&mut self, key: &K) -> bool {
67        self.map.remove(key).is_some()
68    }
69
70    /// `i`番目のキーへの参照を返す。
71    pub fn get_by_index(&self, i: usize) -> Option<&K> {
72        self.map.get_by_index(i).map(|(k, _)| k)
73    }
74
75    /// `i`番目の要素を削除して、そのキーを返す。
76    pub fn remove_by_index(&mut self, i: usize) -> Option<K> {
77        self.map.remove_by_index(i).map(|(k, _)| k)
78    }
79
80    /// 順序付き辞書のすべての要素を順番に`f`に渡す。
81    pub fn for_each(&self, mut f: impl FnMut(&K)) {
82        self.map.for_each(|k, _| f(k));
83    }
84
85    /// 先頭の要素を削除して返す。
86    pub fn pop_first(&mut self) -> Option<K> {
87        self.map.pop_first().map(|(k, _)| k)
88    }
89    /// 末尾の要素を削除して返す。
90    pub fn pop_last(&mut self) -> Option<K> {
91        self.map.pop_last().map(|(k, _)| k)
92    }
93    /// 先頭の要素の参照を返す。
94    pub fn first(&self) -> Option<&K> {
95        self.map.first().map(|(k, _)| k)
96    }
97    /// 末尾の要素の参照を返す。
98    pub fn last(&self) -> Option<&K> {
99        self.map.last().map(|(k, _)| k)
100    }
101}
haar_lib/ds/ordered_set.rs

haar_lib/ds/
ordered_set.rs
