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

use std::{
    ops::{Bound, RangeBounds},
    sync::Arc,
};

use btree::Tree;
use tap::Tap;

mod btree;

/// A persistent, efficiently concatenable and sliceable vector. The const-generic type parameter ORD is the maximum fanout factor; a value from 32 to 128 usually works well.
#[derive(Clone)]
pub struct CatVec<T: Clone, const ORD: usize> {
    inner: Box<Tree<T, ORD>>,
}

// impl<T: Clone, const ORD: usize> From<Vec<T>> for CatVec<T, ORD> {
//     fn from(v: Vec<T>) -> Self {
//         v.into_iter()
//             .fold(CatVec::new(), |a, b| a.tap_mut(|a| a.push_back(b)))
//     }
// }

impl<T: Clone, V: AsRef<[T]>, const ORD: usize> From<V> for CatVec<T, ORD> {
    fn from(v: V) -> Self {
        v.as_ref()
            .iter()
            .fold(CatVec::new(), |a, b| a.tap_mut(|a| a.push_back(b.clone())))
    }
}

impl<T: Clone, const ORD: usize> From<CatVec<T, ORD>> for Vec<T> {
    fn from(cv: CatVec<T, ORD>) -> Self {
        let mut result = Vec::with_capacity(cv.len());
        for i in 0..cv.len() {
            result.push(cv.get(i).unwrap().clone());
        }
        result
    }
}

impl<T: Clone + std::fmt::Debug, const ORD: usize> std::fmt::Debug for CatVec<T, ORD> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let v: Vec<_> = self.clone().into();
        std::fmt::Debug::fmt(&v, f)
    }
}

impl<T: Clone + std::fmt::Debug, const ORD: usize> CatVec<T, ORD> {
    /// Debug graphviz.
    pub fn debug_graphviz(&self) {
        Arc::new(*self.inner.clone()).eprint_graphviz();
    }
}

impl<T: Clone, const ORD: usize> CatVec<T, ORD> {
    /// Creates a new empty CatVec.
    pub fn new() -> Self {
        Self {
            inner: Tree::new().into(),
        }
    }

    /// Gets a reference to the element at a particular position.
    pub fn get(&self, i: usize) -> Option<&T> {
        self.inner.get(i)
    }

    /// Gets a mutable reference to the element at a particular position.
    pub fn get_mut(&mut self, i: usize) -> Option<&mut T> {
        self.inner.get_mut(i)
    }

    /// Slices a subset of the vector. "Zooms into" a part of the vector.
    pub fn slice_into(&mut self, range: impl RangeBounds<usize>) {
        let start = match range.start_bound() {
            Bound::Excluded(i) => Some(*i + 1),
            Bound::Included(i) => Some(*i),
            Bound::Unbounded => None,
        };
        let end = match range.end_bound() {
            Bound::Excluded(i) => Some(*i),
            Bound::Included(i) => Some(*i + 1),
            Bound::Unbounded => None,
        };
        if let Some(end) = end {
            self.inner.take_head(end)
        }
        if let Some(start) = start {
            self.inner.drop_head(start)
        }
    }

    /// Concatenates this vector with another one. Consumes the other vector.
    pub fn append(&mut self, other: Self) {
        self.inner.concat(*other.inner)
    }

    /// Inserts the given element at the given position, shifting all elements after that rightwards.
    pub fn insert(&mut self, idx: usize, val: T) {
        self.inner.insert(idx, val);
    }

    /// Pushes to the back of the vector.
    pub fn push_back(&mut self, val: T) {
        let len = self.len();
        self.insert(len, val)
    }

    /// Length of vector.
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Check invariant.
    pub fn check_invariants(&self) {
        self.inner.check_invariants();
    }
}

impl<T: Clone, const ORD: usize> Default for CatVec<T, ORD> {
    fn default() -> Self {
        Self::new()
    }
}