cstree/
utility_types.rs

1use std::fmt;
2
3/// Convenience type to represent tree elements which may either be a node or a token.
4///
5/// Used for both red and green tree, references to elements, ...
6#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
7pub enum NodeOrToken<N, T> {
8    Node(N),
9    Token(T),
10}
11
12impl<N, T> NodeOrToken<N, T> {
13    pub fn into_node(self) -> Option<N> {
14        match self {
15            NodeOrToken::Node(node) => Some(node),
16            NodeOrToken::Token(_) => None,
17        }
18    }
19
20    pub fn into_token(self) -> Option<T> {
21        match self {
22            NodeOrToken::Node(_) => None,
23            NodeOrToken::Token(token) => Some(token),
24        }
25    }
26
27    pub fn as_node(&self) -> Option<&N> {
28        match self {
29            NodeOrToken::Node(node) => Some(node),
30            NodeOrToken::Token(_) => None,
31        }
32    }
33
34    pub fn as_token(&self) -> Option<&T> {
35        match self {
36            NodeOrToken::Node(_) => None,
37            NodeOrToken::Token(token) => Some(token),
38        }
39    }
40
41    pub(crate) fn as_ref(&self) -> NodeOrToken<&N, &T> {
42        match self {
43            NodeOrToken::Node(node) => NodeOrToken::Node(node),
44            NodeOrToken::Token(token) => NodeOrToken::Token(token),
45        }
46    }
47}
48
49impl<N: Clone, T: Clone> NodeOrToken<&N, &T> {
50    pub(crate) fn cloned(&self) -> NodeOrToken<N, T> {
51        match *self {
52            NodeOrToken::Node(node) => NodeOrToken::Node(node.clone()),
53            NodeOrToken::Token(token) => NodeOrToken::Token(token.clone()),
54        }
55    }
56}
57
58impl<N: fmt::Display, T: fmt::Display> fmt::Display for NodeOrToken<N, T> {
59    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
60        match self {
61            NodeOrToken::Node(node) => node.fmt(f),
62            NodeOrToken::Token(token) => token.fmt(f),
63        }
64    }
65}
66
67#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
68pub enum Direction {
69    Next,
70    Prev,
71}
72
73/// `WalkEvent` describes tree walking process.
74#[derive(Debug, Copy, Clone)]
75pub enum WalkEvent<T> {
76    /// Fired before traversing the node.
77    Enter(T),
78    /// Fired after the node is traversed.
79    Leave(T),
80}
81
82impl<T> WalkEvent<T> {
83    pub fn map<F: FnOnce(T) -> U, U>(self, f: F) -> WalkEvent<U> {
84        match self {
85            WalkEvent::Enter(it) => WalkEvent::Enter(f(it)),
86            WalkEvent::Leave(it) => WalkEvent::Leave(f(it)),
87        }
88    }
89}
90
91#[derive(Debug)]
92pub(crate) enum MaybeOwned<'a, T> {
93    Owned(T),
94    Borrowed(&'a mut T),
95}
96
97impl<T> MaybeOwned<'_, T> {
98    pub(crate) fn into_owned(self) -> Option<T> {
99        match self {
100            MaybeOwned::Owned(owned) => Some(owned),
101            MaybeOwned::Borrowed(_) => None,
102        }
103    }
104}
105
106impl<T> std::ops::Deref for MaybeOwned<'_, T> {
107    type Target = T;
108
109    fn deref(&self) -> &T {
110        match self {
111            MaybeOwned::Owned(it) => it,
112            MaybeOwned::Borrowed(it) => it,
113        }
114    }
115}
116
117impl<T> std::ops::DerefMut for MaybeOwned<'_, T> {
118    fn deref_mut(&mut self) -> &mut T {
119        match self {
120            MaybeOwned::Owned(it) => it,
121            MaybeOwned::Borrowed(it) => it,
122        }
123    }
124}
125
126impl<T: Default> Default for MaybeOwned<'_, T> {
127    fn default() -> Self {
128        MaybeOwned::Owned(T::default())
129    }
130}
131
132/// There might be zero, one or two leaves at a given offset.
133#[derive(Clone, Debug)]
134pub enum TokenAtOffset<T> {
135    /// No leaves at offset -- possible for the empty file.
136    None,
137    /// Only a single leaf at offset.
138    Single(T),
139    /// Offset is exactly between two leaves.
140    Between(T, T),
141}
142
143impl<T> TokenAtOffset<T> {
144    pub fn map<F: Fn(T) -> U, U>(self, f: F) -> TokenAtOffset<U> {
145        match self {
146            TokenAtOffset::None => TokenAtOffset::None,
147            TokenAtOffset::Single(it) => TokenAtOffset::Single(f(it)),
148            TokenAtOffset::Between(l, r) => TokenAtOffset::Between(f(l), f(r)),
149        }
150    }
151
152    /// Convert to option, preferring the right leaf in case of a tie.
153    pub fn right_biased(self) -> Option<T> {
154        match self {
155            TokenAtOffset::None => None,
156            TokenAtOffset::Single(node) => Some(node),
157            TokenAtOffset::Between(_, right) => Some(right),
158        }
159    }
160
161    /// Convert to option, preferring the left leaf in case of a tie.
162    pub fn left_biased(self) -> Option<T> {
163        match self {
164            TokenAtOffset::None => None,
165            TokenAtOffset::Single(node) => Some(node),
166            TokenAtOffset::Between(left, _) => Some(left),
167        }
168    }
169}
170
171impl<T> Iterator for TokenAtOffset<T> {
172    type Item = T;
173
174    fn next(&mut self) -> Option<T> {
175        match std::mem::replace(self, TokenAtOffset::None) {
176            TokenAtOffset::None => None,
177            TokenAtOffset::Single(node) => {
178                *self = TokenAtOffset::None;
179                Some(node)
180            }
181            TokenAtOffset::Between(left, right) => {
182                *self = TokenAtOffset::Single(right);
183                Some(left)
184            }
185        }
186    }
187
188    fn size_hint(&self) -> (usize, Option<usize>) {
189        match self {
190            TokenAtOffset::None => (0, Some(0)),
191            TokenAtOffset::Single(_) => (1, Some(1)),
192            TokenAtOffset::Between(_, _) => (2, Some(2)),
193        }
194    }
195}
196
197impl<T> ExactSizeIterator for TokenAtOffset<T> {}
cstree/utility_types.rs

cstree/
utility_types.rs
