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

//! `SmallVector` is a
//! [`std::vec::Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html) that
//! does not allocate if it contains one ore no element.

use crate::{
    memory::{assert_in_bounds, Vector},
    output::unreachable,
};
use std::{
    iter::FromIterator,
    ops::{Index, IndexMut},
};

/// A [`Vector`](../vector/struct.Vector.html) with small-buffer-optimization
#[derive(Debug, PartialEq, Clone)]
pub enum SmallVector<T> {
    /// Empty variant, no need to allocate anything (same as `Vector`)
    Empty,
    /// A `SmallVector` with a single element that is stored in place
    One(T),
    /// Fallback to a plain `Vector`, for two or more elements
    Many(Vector<T>),
}

impl<T> SmallVector<T> {
    /// See [`Vec::len()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.len).
    pub fn len(&self) -> usize {
        match self {
            SmallVector::Empty => 0,
            SmallVector::One(_value) => 1,
            SmallVector::Many(vector) => vector.len(),
        }
    }
    /// See [`Vec::is_empty()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.is_empty).
    pub fn is_empty(&self) -> bool {
        match &self {
            SmallVector::Empty => true,
            SmallVector::One(_value) => false,
            SmallVector::Many(vector) => vector.is_empty(),
        }
    }
}

impl<T: Copy + Default> Default for SmallVector<T> {
    fn default() -> SmallVector<T> {
        SmallVector::Empty
    }
}

impl<T: Copy + Default> SmallVector<T> {
    /// Constructs a new `SmallVector` containing a single element.
    #[allow(dead_code)]
    pub fn singleton(value: T) -> SmallVector<T> {
        SmallVector::One(value)
    }
    /// Convert a `Vector` to a `SmallVector`.
    pub fn from_vector(vector: Vector<T>) -> SmallVector<T> {
        SmallVector::Many(vector)
    }
    /// See [`Vec::first()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.first).
    pub fn first(&self) -> Option<T> {
        match self {
            SmallVector::Empty => None,
            &SmallVector::One(value) => Some(value),
            SmallVector::Many(vector) => vector.get(0).cloned(),
        }
    }
    /// See [`Vec::push()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push).
    pub fn push(&mut self, new_value: T) {
        if let SmallVector::Empty = self {
            *self = SmallVector::One(new_value);
            return;
        }
        if let SmallVector::One(value) = *self {
            *self = SmallVector::Many(vector!(value));
        }
        if let SmallVector::Many(vector) = self {
            vector.push(new_value);
            return;
        }
        unreachable();
    }
    /// See [`Vec::swap_remove()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap_remove).
    ///
    /// *Note*: this currently only supports being called with index=0 because that's all we need for parsing.
    pub fn swap_remove(&mut self, index: usize) -> T {
        requires!(index == 0);
        if let SmallVector::One(value) = *self {
            *self = SmallVector::Empty;
            value
        } else if let SmallVector::Many(vector) = self {
            vector.swap_remove(0)
        } else {
            unreachable()
        }
    }
}

impl<T: Copy + Default> FromIterator<T> for SmallVector<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> SmallVector<T> {
        SmallVector::from_vector(Vector::from_iter(iter))
    }
}
impl<T> Index<usize> for SmallVector<T> {
    type Output = T;
    fn index(&self, index: usize) -> &Self::Output {
        assert_in_bounds(0..self.len(), index);
        match self {
            SmallVector::Empty => unreachable(),
            SmallVector::One(value) => value,
            SmallVector::Many(vector) => &vector[index],
        }
    }
}

impl<T> IndexMut<usize> for SmallVector<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        assert_in_bounds(0..self.len(), index);
        match self {
            SmallVector::Empty => unreachable(),
            SmallVector::One(value) => value,
            SmallVector::Many(vector) => &mut vector[index],
        }
    }
}