mapped_vec/

lib.rs

//! This crate is meant to provide an interface for vectors that not only store data, but also its order. This type of vector is called a mapped vector.
//! A mapped vector is suitable for the fast processing of large types, because in the case of large types, it's faster to move around a few numbers specifying 
//! the order of the data than to move around the actual data. The reverse and rotate functions of a mapped vector are O(1), because the reverse function simply
//! changes the function to filter indices with, and the rotate function only has to edit a number offset for each index and possibly swap a few functions.
//! Inserts and removes are also generally faster with this, even for small types. A mapped vector also supports turning into a regular vector, although this can
//! be expensive, so it's recommended to use the get_mapped method to get a vector of references to elements in order instead. This works on no_std with alloc.
//!
//! Example Usage with Random Numbers and Timed Functions:
//!
//! # use mapped_vec::MappedVec;
//! # use rand::prelude::*;
//! #
//! # fn main() {
//! #     let mut rng = rand::thread_rng();
//! #     let mut rgen = (0..100_000).map(|_| rng.gen::<f64>()).collect::<Vec<f64>>();
//! #     
//! #     let mut mapped = MappedVec::new();
//! #     mapped.extend_from_slice(&rgen);
//! #     
//! #     let ind = rng.gen::<u16>() as usize;
//! #     
//! #     let timed = std::time::Instant::now();
//! #     mapped.remove(ind);
//! #     println!("Remove of mapped vector: {:?}", timed.elapsed());
//! #     
//! #     let timed = std::time::Instant::now();
//! #     rgen.remove(ind);
//! #     println!("Remove of regular vector: {:?}", timed.elapsed());
//! # 
//! #     let timed = std::time::Instant::now();
//! #     mapped.insert(ind, 0.0);
//! #     println!("Insert of mapped vector: {:?}", timed.elapsed());
//! #     
//! #     let timed = std::time::Instant::now();
//! #     rgen.insert(ind, 0.0);
//! #     println!("Insert of regular vector: {:?}", timed.elapsed());
//! # 
//! #     let timed = std::time::Instant::now();
//! #     mapped.reverse();
//! #     println!("Time to reverse mapped vector: {:?}", timed.elapsed());
//! # 
//! #     let timed = std::time::Instant::now();
//! #     rgen.reverse();
//! #     println!("Time to reverse regular vector: {:?}", timed.elapsed());
//! # 
//! #     let timed = std::time::Instant::now();
//! #     let rvec = mapped.to_vec();
//! #     println!("Time to convert mapped vector to real vector: {:?}", timed.elapsed());
//! # 
//! #     assert_eq!(rvec, rgen);
//! # }
#![no_std]
#![forbid(unsafe_code)]
extern crate alloc;
use alloc::vec::Vec;
use core::ops::{Index, IndexMut};
mod ring;
use ring::Ring;

/// See the crate-level documentation for the description of this structure, which is all of the public API in this crate, as well as the method documentation for more info.
pub struct MappedVec<T> {
    vector: Vec<T>,
    indices: Ring<usize>,
}

impl<T> MappedVec<T> {
    /// This creates a new mapped vector.
    pub fn new() -> MappedVec<T> {
        MappedVec {
            vector: Vec::new(),
            indices: Ring::new(),
        }
    }

    /// This appends a mapped vector to this one.
    pub fn append(&mut self, v: &mut MappedVec<T>) {
        for x in 0..v.indices.len() {
            v.indices[x] += self.vector.len();
        }
        self.indices.append(&mut v.indices);
        self.vector.append(&mut v.vector);
        *v = MappedVec::new();
    }
    
    /// This gets the length of a mapped vector.
    pub fn len(&self) -> usize {
        self.indices.len()
    }
    
    /// This adds an element to a mapped vector.
    pub fn push(&mut self, value: T) {
        self.indices.push(self.vector.len());
        self.vector.push(value);
    }
    
    /// This quickly swaps elements of the vector.
    pub fn swap(&mut self, x: usize, y: usize) {
        self.indices.swap(x, y);
    }
    
    /// This quickly pops off an element of the vector.
    pub fn pop(&mut self) {
        self.indices.pop();
    }
    
    /// This quickly removes an element of the vector.
    pub fn remove(&mut self, index: usize) {
        self.indices.remove(index);
    }
    
    /// This quickly inserts an element into an index of the vector.
    pub fn insert(&mut self, index: usize, value: T) {
        self.vector.push(value);
        self.indices.insert(index, self.vector.len() - 1);
    }

    /// This quickly reverses the vector.
    pub fn reverse(&mut self) {
        self.indices.reverse();
    }

    /// This quickly rotates the vector's elements.
    pub fn rotate(&mut self, offs: isize) {
        self.indices.rotate(offs);
    }

    /// This clears the vector.
    pub fn clear(&mut self) {
        *self = MappedVec::new();
    }
    
    /// This resizes a vector to a specific size. If the size exceeds the length of the vector, then the remaining elements are filled in by a specified closure.
    pub fn resize_with<F: Fn() -> T>(&mut self, nl: usize, f: F) {
        if nl <= self.len() {
            for _ in nl..self.len() {
                self.indices.pop();
            }
        } else {
            let diff = nl - self.len();
            for _ in 0..diff {
                self.push(f());
            }
        }
    }

    /// This removes an element without caring about ordering.
    pub fn swap_remove(&mut self, index: usize) {
        self.swap(index, self.len() - 1);
        self.indices.pop();
    }

    /// This checks if the vector is empty.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// This changes the layout of the vector and resets the indices while maintaining the same indexing behavior.
    pub fn update_vector(&mut self) {
        for (n, x) in self.indices.iter_mut().enumerate() {
            self.vector.swap(*x, n);
            *x = n;
        }
    }

    /// This extends the vector by an iterator.
    pub fn extend<I: Iterator<Item = T> + Clone>(&mut self, iterator: I) {
        self.indices.extend(0 + self.vector.len()..iterator.clone().count() + self.vector.len());
        self.vector.extend(iterator);
    }
    
    /// This gets an ordered vector of references to the elements of this vector.
    pub fn get_mapped(&self) -> Vec<&T> {
        let mut output = Vec::new();
        for x in 0..self.len() {
            output.push(self.index(x));
        }
        output
    }
}

impl<T> Index<usize> for MappedVec<T> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        self.vector.index(self.indices[index])
    }
}

impl<T> IndexMut<usize> for MappedVec<T> {
    fn index_mut(&mut self, index: usize) -> &mut T {
        self.vector.index_mut(self.indices[index])
    }
}

impl<T: Clone> MappedVec<T> {
    /// This extends the vector.
    pub fn extend_from_slice(&mut self, input: &[T]) {
        self.indices.extend(self.len()..self.len() + input.len());
        self.vector.extend(input.iter().cloned());
    }

    /// This is an expensive operation that turns this mapped vector into a regular one. It is recommended to use get_mapped whenever possible over this.
    pub fn to_vec(&self) -> Vec<T> {
        let mut output = Vec::new();
        for x in 0..self.len() {
            output.push(self.index(x).clone());
        }
        output
    }
    
    /// This resizes the vector. If the size is large than the current size, then the remaining elements are turned into a specified value.
    pub fn resize(&mut self, nl: usize, v: T) {
        if nl <= self.len() {
            for _ in nl..self.len() {
                self.indices.pop();
            }
        } else {
            let diff = nl - self.len();
            for _ in 0..diff {
                self.push(v.clone());
            }
        }
    }
}