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)
32    }
33
34    /// `key`以下の最大のキーをもつキーを返す。
35    pub fn max_le(&self, key: &K) -> Option<&K> {
36        self.map.max_le(key).map(|(k, _)| k)
37    }
38
39    /// `key`以上の最小のキーをもつキーを返す。
40    pub fn min_ge(&self, key: &K) -> Option<&K> {
41        self.map.min_ge(key).map(|(k, _)| k)
42    }
43
44    /// `key`をキーとして持つならば`true`を返す。
45    pub fn contains(&self, key: &K) -> bool {
46        self.map.contains(key)
47    }
48
49    /// `key`が存在するとき、`key`を挿入して、`true`を返す。
50    pub fn insert(&mut self, key: K) -> bool {
51        self.map.insert(key, ()).is_some()
52    }
53
54    /// キー`key`があれば、そのキーを削除して、`true`を返す。
55    pub fn remove(&mut self, key: &K) -> bool {
56        self.map.remove(key).is_some()
57    }
58
59    /// `i`番目のキーへの参照を返す。
60    pub fn get_by_index(&self, i: usize) -> Option<&K> {
61        self.map.get_by_index(i).map(|(k, _)| k)
62    }
63
64    /// `i`番目の要素を削除して、そのキーを返す。
65    pub fn remove_by_index(&mut self, i: usize) -> Option<K> {
66        self.map.remove_by_index(i).map(|(k, _)| k)
67    }
68
69    /// 順序付き辞書のすべての要素を順番に`f`に渡す。
70    pub fn for_each(&self, mut f: impl FnMut(&K)) {
71        self.map.for_each(|k, _| f(k));
72    }
73
74    // pub fn pop_first(&mut self) -> Option<K>
75    // pub fn pop_last(&mut self) -> Option<K>
76    // pub fn first(&self) -> Option<&K>
77    // pub fn last(&self) -> Option<&K>
78}
haar_lib/ds/ordered_set.rs

haar_lib/ds/
ordered_set.rs
