bitstring/
bit_string.rs

1use core::cmp::{
2	min,
3	Ordering,
4};
5
6/// A bit string with variable (but possibly limited) length.
7///
8/// The length limit might depend on the current string; that is why
9/// writing a bit might truncate the string (but not the bit that was
10/// just modified).  "Writing" a bit also includes writing without
11/// actually changing it.
12///
13/// This special case is needed to handle variants with different
14/// (maximum) lengths: a small prefix indicates the variant, then
15/// follows the actual data of the variant.
16///
17/// As an example one might want to combine IPv4 and IPv6 cidr
18/// representations into one `BitString` type; the empty bit string
19/// would represent `0.0.0.0/0` + `::/0`.
20///
21/// Apart from this special case writing a bit must not modify any other
22/// bits or change the length.
23///
24/// The required `Eq` implementation must match comparing two bitstrings
25/// by their bits (up to their length); i.e. `BitString`s must not carry
26/// additional data apart from the bits (and mustn't compare unused
27/// bits in the storage if their value isn't fixed).
28#[allow(clippy::len_without_is_empty)]
29pub trait BitString: Eq {
30	/// Get the `ndx`th bit.
31	///
32	/// # Panics
33	///
34	/// Should panic if `ndx >= self.len()`.
35	fn get(&self, ndx: usize) -> bool;
36
37	/// Set the `ndx`th bit to `bit`.
38	///
39	/// Might clip the length to `ndx+1`.
40	///
41	/// # Panics
42	///
43	/// Should panic if `ndx >= self.len()`.
44	fn set(&mut self, ndx: usize, bit: bool);
45
46	/// Flips the `ndx`th bit.
47	///
48	/// # Panics
49	///
50	/// Should panic if `ndx >= self.len()`.
51	fn flip(&mut self, ndx: usize);
52
53	/// Current length of the bit string in bits.
54	#[allow(clippy::len_without_is_empty)]
55	fn len(&self) -> usize;
56
57	/// Set current length to `len`.
58	///
59	/// Does nothing if `len <= self.len()`.
60	///
61	/// If necessary should also zero the underlying storage if `Eq`
62	/// needs it to work properly.
63	fn clip(&mut self, len: usize);
64
65	/// Append a bit.
66	///
67	/// # Panics
68	///
69	/// Might panic if underlying storage can only store a limited
70	/// number of bits.
71	fn append(&mut self, bit: bool);
72
73	/// Create a new zero-length bit string.
74	///
75	/// Underlying storage should be zeroed if `Eq` needs it to work
76	/// properly.
77	fn null() -> Self;
78
79	/// Length of the longest shared prefix of two bit strings.
80	fn shared_prefix_len(&self, other: &Self) -> usize {
81		let max_len = min(self.len(), other.len());
82		for i in 0..max_len {
83			if self.get(i) != other.get(i) {
84				return i;
85			}
86		}
87		max_len
88	}
89
90	/// Longest shared prefix of two bit strings.
91	fn shared_prefix(&self, other: &Self) -> Self
92	where
93		Self: Clone,
94	{
95		let mut a = self.clone();
96		a.clip(self.shared_prefix_len(other));
97		a
98	}
99
100	/// Partial ordering on bit strings.
101	///
102	/// Formal definition:
103	///
104	/// ```text
105	///     `a < b` iff `a != b` and `b` is a prefix of `a`
106	/// ```
107	///
108	/// If you view a bit string as a set including all bit strings
109	/// starting with it, this is the subset relation.
110	fn subset_cmp(&self, other: &Self) -> Option<Ordering> {
111		let spl = self.shared_prefix_len(other);
112		if spl == self.len() {
113			// self is a prefix of other
114			if spl == other.len() {
115				Some(Ordering::Equal)
116			} else {
117				Some(Ordering::Greater)
118			}
119		} else if spl == other.len() {
120			// other is a prefix of self
121			Some(Ordering::Less)
122		} else {
123			// neither is a prefix of the other one
124			None
125		}
126	}
127
128	/// Lexicographic ordering on bit strings.
129	///
130	/// Formal definition:
131	///
132	/// ```text
133	///     `a < b` iff `a != b` and (
134	///         `b` is a prefix of `a`
135	///         or `a[s] < b[s]`
136	///              where s is the smallest index with `a[s] != b[s]`)
137	/// ```
138	///
139	/// Or, if you define `_|_ < false < true`:
140	///
141	/// ```text
142	///     `a < b` iff `a[s] < b[s]`
143	///         where s is the smallest index with `a[s] != b[s]`
144	/// ```
145	fn lexicographic_cmp(&self, other: &Self) -> Ordering {
146		let spl = self.shared_prefix_len(other);
147		if spl == self.len() {
148			// self is a prefix of other
149			if spl == other.len() {
150				Ordering::Equal
151			} else {
152				// self is shorter than other
153				Ordering::Less
154			}
155		} else if spl == other.len() {
156			// other is a prefix of self and shorter
157			Ordering::Greater
158		} else {
159			// both are at least one bit longer than the shared prefix,
160			// and they differ in that bit (otherwise shared prefix
161			// would be longer)
162			if self.get(spl) {
163				Ordering::Greater
164			} else {
165				Ordering::Less
166			}
167		}
168	}
169}
bitstring/bit_string.rs

bitstring/
bit_string.rs
