1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

// Copyright 2018 Skylor R. Schermer.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
////////////////////////////////////////////////////////////////////////////////
//!
//! Provides an interval type for doing set selection and iteration.
//!
////////////////////////////////////////////////////////////////////////////////

// Local imports.
use crate::raw_interval::RawInterval;


////////////////////////////////////////////////////////////////////////////////
// Finite
////////////////////////////////////////////////////////////////////////////////
/// Provides the methods needed to iterate over an type's points. Used
/// to [`Normalize`] finite types used in [`Interval`] bounds.
///
/// [`Normalize`]: trait.Normalize.html
/// [`Interval`]: ../interval/struct.Interval.html
pub trait Finite: Sized {
    /// The minimum value of the type.
    const MINIMUM: Self;

    /// The maximum value of the type.
    const MAXIMUM: Self;

    /// Returns the previous element before the given one.
    fn pred(&self) -> Option<Self>;

    /// Returns the next element after the given one.
    fn succ(&self) -> Option<Self>;
}


////////////////////////////////////////////////////////////////////////////////
// Normalize
////////////////////////////////////////////////////////////////////////////////
/// Provides normalization capabilities for an [`Interval`].
/// 
/// [`Interval`]: ../interval/struct.Interval.html
pub trait Normalize {
    /// Normalizes the given interval in place.
    fn normalize(&mut self);

    /// Denormalizes the given interval in place.
    fn denormalize(&mut self);

    /// Returns a normalized copy of the given interval.
    fn normalized(mut self) -> Self where Self: Sized {
        self.normalize();
        self
    }

    /// Returns a denormalized copy of the given interval.
    fn denormalized(mut self) -> Self where Self: Sized {
        self.denormalize();
        self
    }
}


////////////////////////////////////////////////////////////////////////////////
// Normalize implementations
////////////////////////////////////////////////////////////////////////////////
// /// General 'do nothing' implementation for all intervals.
// impl<T> Normalize for RawInterval<T> {
//     default fn normalize(&mut self) {/* Do nothing. */}
//     default fn denormalize(&mut self) {/* Do nothing. */}
// }

/// Specialization for [`Finite`] intervals.
impl<T> Normalize for RawInterval<T> where T: Finite {
    fn normalize(&mut self) {
        use RawInterval::*;
        *self = match std::mem::replace(self, Empty) {
            Empty           => Empty,
            Point(p)        => Point(p),
            Open(l, r)      => match (l.succ(), r.pred()) {
                (Some(l), Some(r)) => Closed(l, r),
                _                  => Empty,
            },
            LeftOpen(l, r)  => l.succ().map_or(Empty, |l| Closed(l, r)),
            RightOpen(l, r) => r.pred().map_or(Empty, |r| Closed(l, r)),
            Closed(l, r)    => Closed(l, r),
            UpTo(r)         => r.pred().map_or(Empty, |r| Closed(T::MINIMUM, r)),
            UpFrom(l)       => l.succ().map_or(Empty, |l| Closed(l, T::MAXIMUM)),
            To(p)           => Closed(T::MINIMUM, p),
            From(p)         => Closed(p, T::MAXIMUM),
            Full            => Closed(T::MINIMUM, T::MAXIMUM),
        }
    }

    fn denormalize(&mut self) {
        use RawInterval::*;
        *self = match std::mem::replace(self, Empty) {
            Empty           => Empty,
            Point(p)        => match (p.pred(), p.succ()) {
                (Some(l), Some(r)) => Open(l, r),
                (Some(l), None)    => UpFrom(l),
                (None, Some(r))    => UpTo(r),
                _                  => Full,
            },
            Open(l, r)      => Open(l, r),
            LeftOpen(l, r)  => match r.succ() {
                Some(r) => Open(l, r),
                None    => UpFrom(l),
            },
            RightOpen(l, r) => match l.pred() {
                Some(l) => Open(l, r),
                None    => UpTo(r),
            },
            Closed(l, r)    => match (l.pred(), r.succ()) {
                (Some(l), Some(r)) => Open(l, r),
                (Some(l), None)    => UpFrom(l),
                (None, Some(r))    => UpTo(r),
                _                  => Full,
            },
            UpTo(r)         => UpTo(r),
            UpFrom(l)       => UpFrom(l),
            To(p)           => p.pred().map_or(Empty, |r| UpTo(r)),
            From(p)         => p.succ().map_or(Empty, |l| UpFrom(l)),
            Full            => Full,
        }
    }
}


////////////////////////////////////////////////////////////////////////////////
// Standard integer Finite implementations
////////////////////////////////////////////////////////////////////////////////

// Implements basic normalization for a single builtin integer type.
macro_rules! std_integer_finite_impl {
    // For each given type...
    ($($t:ident),*) => {
        $(impl Finite for $t {
            const MINIMUM: $t = {std::$t::MIN};
            const MAXIMUM: $t = {std::$t::MAX};

            fn pred(&self) -> Option<Self> {
                if *self != std::$t::MIN {Some(self - 1)} else {None}
            }

            fn succ(&self) -> Option<Self> {
                if *self != std::$t::MAX {Some(self + 1)} else {None}
            }
        })*
    };
}

// Provide implementations of Finite for builtin integer types.
std_integer_finite_impl![
    u8, u16, u32, u64, u128, usize,
    i8, i16, i32, i64, i128, isize
];


// TODO: Use nextUp and nextDown IEEE 754 functions to normalize float values?