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

#[cfg(feature = "std")]
use std::ops;
#[cfg(not(feature = "std"))]
use core::ops;

use self::ops::{Index, IndexMut, Range, RangeFrom, RangeFull, RangeTo};

#[cfg(feature = "nightly")]
use self::ops::{RangeInclusive, RangeToInclusive};

/// A collection with a length.
///
/// Obtaining the length of the collection must take O(1) time and space.
pub trait Len {
    /// Returns the length of the collection.
    fn len(&self) -> usize;

    /// Returns whether the collection is empty.
    fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

/// A collection whose length can be set to zero, i.e. a clearable collection.
///
/// Clearing the collection must take O(1) time and space after all elements in the collection are
/// dropped.
pub trait LenZero: Len {
    /// Empties the collection, making its length zero.
    fn clear(&mut self);
}

/// A collection with a "mutable" length, i.e. a truncatable collection.
///
/// Truncating the collection must take O(1) time and space after all of the removed elements in the
/// collection are dropped.
pub trait LenMut: Default + LenZero {
    /// Truncates the collection so that it is no greater than `len` long.
    fn truncate(&mut self, len: usize);
}

/// A collection with a capacity.
///
/// Obtaining the capacity of the collection must take O(1) time and space.
pub trait Capacity {
    /// Returns the capacity of the collection.
    fn capacity(&self) -> usize;
}

/// A collection which can be created with a certain capacity.
///
/// Creating a collection with a given capacity should take O(n) time and space with respect to the
/// requested capacity. A `Default` value must have a capacity of either 0 or `usize::MAX`.
pub trait DefaultCapacity: Capacity + Default {
    /// Creates a value of the given capacity.
    fn default_capacity(capacity: usize) -> Self;
}

/// A collection with a "mutable" capacity.
///
/// Changing the capacity of the collection must take O(n) time and space with respect to the
/// requested capacity.
pub trait CapacityMut: Len + DefaultCapacity {
    /// Ensures that the capacity is at least the current length plus `additional`.
    fn reserve(&mut self, additional: usize);

    /// Similar to `reserve`, providing a strong hint that capacity above the requested amount is
    /// not desired. This strong hint may be ignored completely.
    fn reserve_exact(&mut self, additional: usize);

    /// Reduces the capacity down as close as possible to the current length. Again, this hint be
    /// ignored partially or completely.
    fn shrink_to_fit(&mut self);
}

/// Shorthand for types which allow slicing over `usize`.
#[cfg(feature = "nightly")]
pub trait IndexRanges: Index<Range<usize>, Output = Self>
                     + Index<RangeTo<usize>, Output = Self>
                     + Index<RangeFrom<usize>, Output = Self>
                     + Index<RangeInclusive<usize>, Output = Self>
                     + Index<RangeToInclusive<usize>, Output = Self>
                     + Index<RangeFull, Output = Self> {}
#[cfg(feature = "nightly")]
impl<T: ?Sized> IndexRanges for T
    where T: Index<Range<usize>, Output = Self>
           + Index<RangeTo<usize>, Output = Self>
           + Index<RangeFrom<usize>, Output = Self>
           + Index<RangeInclusive<usize>, Output = Self>
           + Index<RangeToInclusive<usize>, Output = Self>
           + Index<RangeFull, Output = Self>
{}

/// Shorthand for types which allow slicing over `usize`.
#[cfg(not(feature = "nightly"))]
pub trait IndexRanges: Index<Range<usize>, Output = Self>
                     + Index<RangeTo<usize>, Output = Self>
                     + Index<RangeFrom<usize>, Output = Self>
                     + Index<RangeFull, Output = Self> {}
#[cfg(not(feature = "nightly"))]
impl<T: ?Sized> IndexRanges for T
    where T: Index<Range<usize>, Output = Self>
           + Index<RangeTo<usize>, Output = Self>
           + Index<RangeFrom<usize>, Output = Self>
           + Index<RangeFull, Output = Self>
{}

/// Shorthand for types which allow mutable slicing over `usize`.
#[cfg(feature = "nightly")]
pub trait IndexRangesMut: IndexMut<Range<usize>, Output = Self>
                        + IndexMut<RangeTo<usize>, Output = Self>
                        + IndexMut<RangeFrom<usize>, Output = Self>
                        + IndexMut<RangeInclusive<usize>, Output = Self>
                        + IndexMut<RangeToInclusive<usize>, Output = Self>
                        + IndexMut<RangeFull, Output = Self>
                        + IndexRanges {}
#[cfg(feature = "nightly")]
impl<T: ?Sized> IndexRangesMut for T
    where T: IndexMut<Range<usize>, Output = Self>
           + IndexMut<RangeTo<usize>, Output = Self>
           + IndexMut<RangeFrom<usize>, Output = Self>
           + IndexMut<RangeInclusive<usize>, Output = Self>
           + IndexMut<RangeToInclusive<usize>, Output = Self>
           + IndexMut<RangeFull, Output = Self>
{}

/// Shorthand for types which allow mutable slicing over `usize`.
#[cfg(not(feature = "nightly"))]
pub trait IndexRangesMut: IndexMut<Range<usize>, Output = Self>
                        + IndexMut<RangeTo<usize>, Output = Self>
                        + IndexMut<RangeFrom<usize>, Output = Self>
                        + IndexMut<RangeFull, Output = Self>
                        + IndexRanges {}
#[cfg(not(feature = "nightly"))]
impl<T: ?Sized> IndexRangesMut for T
    where T: IndexMut<Range<usize>, Output = Self>
           + IndexMut<RangeTo<usize>, Output = Self>
           + IndexMut<RangeFrom<usize>, Output = Self>
           + IndexMut<RangeFull, Output = Self>
{}

/// A collection which can be split into two parts at a given index.
///
/// Splitting a collection must take O(1) time and space.
pub trait SplitAt: Len + IndexRanges {
    /// Splits the collection into two pieces at the given index.
    ///
    /// Panicks on out-of-bounds errors.
    fn split_at(&self, index: usize) -> (&Self, &Self);

    /// Splits the collection into two mutable pieces at the given index.
    fn split_at_mut(&mut self, index: usize) -> (&mut Self, &mut Self);
}

/// A collection which can be split into two owned parts at a given index.
///
/// Splitting a collection must take O(1) time and space.
pub trait SplitOff: LenMut {
    /// Splits off the collection at the given index, returning the data past the index.
    fn split_off(&mut self, index: usize) -> Self;
}