range/
lib.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5#![deny(unsafe_code)]
6
7use std::cmp::{self, max, min};
8use std::{fmt, ops};
9
10use malloc_size_of_derive::MallocSizeOf;
11use serde::{Deserialize, Serialize};
12
13pub trait Int:
14    Copy + ops::Add<Self, Output = Self> + ops::Sub<Self, Output = Self> + cmp::Ord
15{
16    fn zero() -> Self;
17    fn one() -> Self;
18    fn to_usize(self) -> usize;
19}
20impl Int for isize {
21    #[inline]
22    fn zero() -> isize {
23        0
24    }
25    #[inline]
26    fn one() -> isize {
27        1
28    }
29    #[inline]
30    fn to_usize(self) -> usize {
31        num_traits::NumCast::from(self).unwrap()
32    }
33}
34impl Int for usize {
35    #[inline]
36    fn zero() -> usize {
37        0
38    }
39    #[inline]
40    fn one() -> usize {
41        1
42    }
43    #[inline]
44    fn to_usize(self) -> usize {
45        self
46    }
47}
48
49/// An index type to be used by a `Range`
50pub trait RangeIndex: Int + fmt::Debug {
51    type Index;
52    fn new(x: Self::Index) -> Self;
53    fn get(self) -> Self::Index;
54}
55
56impl RangeIndex for isize {
57    type Index = isize;
58    #[inline]
59    fn new(x: isize) -> isize {
60        x
61    }
62
63    #[inline]
64    fn get(self) -> isize {
65        self
66    }
67}
68
69impl RangeIndex for usize {
70    type Index = usize;
71    #[inline]
72    fn new(x: usize) -> usize {
73        x
74    }
75
76    #[inline]
77    fn get(self) -> usize {
78        self
79    }
80}
81
82/// Implements a range index type with operator overloads
83#[macro_export]
84macro_rules! int_range_index {
85    ($(#[$attr:meta])* struct $Self_:ident($T:ty)) => (
86        #[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
87        $(#[$attr])*
88        pub struct $Self_(pub $T);
89
90        impl $Self_ {
91            #[inline]
92            pub fn to_usize(self) -> usize {
93                self.get() as usize
94            }
95        }
96
97        impl $crate::RangeIndex for $Self_ {
98            type Index = $T;
99            #[inline]
100            fn new(x: $T) -> $Self_ {
101                $Self_(x)
102            }
103
104            #[inline]
105            fn get(self) -> $T {
106                match self { $Self_(x) => x }
107            }
108        }
109
110        impl $crate::Int for $Self_ {
111            #[inline]
112            fn zero() -> $Self_ { $Self_($crate::Int::zero()) }
113            #[inline]
114            fn one() -> $Self_ { $Self_($crate::Int::one()) }
115            #[inline]
116            fn to_usize(self) -> usize { self.to_usize() }
117        }
118
119        impl ::std::ops::Add<$Self_> for $Self_ {
120            type Output = $Self_;
121
122            #[inline]
123            fn add(self, other: $Self_) -> $Self_ {
124                $Self_(self.get() + other.get())
125            }
126        }
127
128        impl ::std::ops::Sub<$Self_> for $Self_ {
129            type Output = $Self_;
130
131            #[inline]
132            fn sub(self, other: $Self_) -> $Self_ {
133                $Self_(self.get() - other.get())
134            }
135        }
136
137        impl ::std::ops::Neg for $Self_ {
138            type Output = $Self_;
139
140            #[inline]
141            fn neg(self) -> $Self_ {
142                $Self_(-self.get())
143            }
144        }
145    )
146}
147
148/// A range of indices
149#[derive(Clone, Copy, Deserialize, MallocSizeOf, Serialize)]
150pub struct Range<I> {
151    begin: I,
152    length: I,
153}
154
155impl<I: RangeIndex> fmt::Debug for Range<I> {
156    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
157        write!(f, "[{:?} .. {:?})", self.begin(), self.end())
158    }
159}
160
161/// An iterator over each index in a range
162pub struct EachIndex<I: RangeIndex> {
163    start: I,
164    stop: I,
165}
166
167pub fn each_index<I: RangeIndex>(start: I, stop: I) -> EachIndex<I> {
168    EachIndex { start, stop }
169}
170
171impl<I: RangeIndex> Iterator for EachIndex<I> {
172    type Item = I;
173
174    #[inline]
175    fn next(&mut self) -> Option<I> {
176        if self.start < self.stop {
177            let next = self.start;
178            self.start = next + I::one();
179            Some(next)
180        } else {
181            None
182        }
183    }
184
185    #[inline]
186    fn size_hint(&self) -> (usize, Option<usize>) {
187        if self.start < self.stop {
188            let len = (self.stop - self.start).to_usize();
189            (len, Some(len))
190        } else {
191            (0, Some(0))
192        }
193    }
194}
195
196impl<I: RangeIndex> DoubleEndedIterator for EachIndex<I> {
197    #[inline]
198    fn next_back(&mut self) -> Option<Self::Item> {
199        if self.start < self.stop {
200            let next = self.stop - I::one();
201            self.stop = next;
202            Some(next)
203        } else {
204            None
205        }
206    }
207}
208
209impl<I: RangeIndex> Range<I> {
210    /// Create a new range from beginning and length offsets. This could be
211    /// denoted as `[begin, begin + length)`.
212    ///
213    /// ~~~ignore
214    ///    |-- begin ->|-- length ->|
215    ///    |           |            |
216    /// <- o - - - - - +============+ - - - ->
217    /// ~~~
218    #[inline]
219    pub fn new(begin: I, length: I) -> Range<I> {
220        Range { begin, length }
221    }
222
223    #[inline]
224    pub fn empty() -> Range<I> {
225        Range::new(Int::zero(), Int::zero())
226    }
227
228    /// The index offset to the beginning of the range.
229    ///
230    /// ~~~ignore
231    ///    |-- begin ->|
232    ///    |           |
233    /// <- o - - - - - +============+ - - - ->
234    /// ~~~
235    #[inline]
236    pub fn begin(&self) -> I {
237        self.begin
238    }
239
240    /// The index offset from the beginning to the end of the range.
241    ///
242    /// ~~~ignore
243    ///                |-- length ->|
244    ///                |            |
245    /// <- o - - - - - +============+ - - - ->
246    /// ~~~
247    #[inline]
248    pub fn length(&self) -> I {
249        self.length
250    }
251
252    /// The index offset to the end of the range.
253    ///
254    /// ~~~ignore
255    ///    |--------- end --------->|
256    ///    |                        |
257    /// <- o - - - - - +============+ - - - ->
258    /// ~~~
259    #[inline]
260    pub fn end(&self) -> I {
261        self.begin + self.length
262    }
263
264    /// `true` if the index is between the beginning and the end of the range.
265    ///
266    /// ~~~ignore
267    ///        false        true      false
268    ///          |           |          |
269    /// <- o - - + - - +=====+======+ - + - ->
270    /// ~~~
271    #[inline]
272    pub fn contains(&self, i: I) -> bool {
273        i >= self.begin() && i < self.end()
274    }
275
276    /// `true` if the offset from the beginning to the end of the range is zero.
277    #[inline]
278    pub fn is_empty(&self) -> bool {
279        self.length() == Int::zero()
280    }
281
282    /// Shift the entire range by the supplied index delta.
283    ///
284    /// ~~~ignore
285    ///                     |-- delta ->|
286    ///                     |           |
287    /// <- o - +============+ - - - - - | - - - ->
288    ///                                 |
289    /// <- o - - - - - - - +============+ - - - ->
290    /// ~~~
291    #[inline]
292    pub fn shift_by(&mut self, delta: I) {
293        self.begin = self.begin + delta;
294    }
295
296    /// Extend the end of the range by the supplied index delta.
297    ///
298    /// ~~~ignore
299    ///                     |-- delta ->|
300    ///                     |           |
301    /// <- o - - - - - +====+ - - - - - | - - - ->
302    ///                                 |
303    /// <- o - - - - - +================+ - - - ->
304    /// ~~~
305    #[inline]
306    pub fn extend_by(&mut self, delta: I) {
307        self.length = self.length + delta;
308    }
309
310    /// Move the end of the range to the target index.
311    ///
312    /// ~~~ignore
313    ///                               target
314    ///                                 |
315    /// <- o - - - - - +====+ - - - - - | - - - ->
316    ///                                 |
317    /// <- o - - - - - +================+ - - - ->
318    /// ~~~
319    #[inline]
320    pub fn extend_to(&mut self, target: I) {
321        self.length = target - self.begin;
322    }
323
324    /// Adjust the beginning offset and the length by the supplied deltas.
325    #[inline]
326    pub fn adjust_by(&mut self, begin_delta: I, length_delta: I) {
327        self.begin = self.begin + begin_delta;
328        self.length = self.length + length_delta;
329    }
330
331    /// Set the begin and length values.
332    #[inline]
333    pub fn reset(&mut self, begin: I, length: I) {
334        self.begin = begin;
335        self.length = length;
336    }
337
338    #[inline]
339    pub fn intersect(&self, other: &Range<I>) -> Range<I> {
340        let begin = max(self.begin(), other.begin());
341        let end = min(self.end(), other.end());
342
343        if end < begin {
344            Range::empty()
345        } else {
346            Range::new(begin, end - begin)
347        }
348    }
349}
350
351/// Methods for `Range`s with indices based on integer values
352impl<I: RangeIndex> Range<I> {
353    /// Returns an iterater that increments over `[begin, end)`.
354    #[inline]
355    pub fn each_index(&self) -> EachIndex<I> {
356        each_index(self.begin(), self.end())
357    }
358}
range/lib.rs

range/
lib.rs
