one_stack_vec/

lib.rs

//! OneStackVec is simple data structure which contains any number of items.
//! If there is one or zero item, ALO does not heap allocate.
//! If there is more than one items, ALO does heap allocate.
//!
//! # Examples
//!
//! ```
//! use one_stack_vec::OneStackVec;
//!
//! let mut items = OneStackVec::new();
//!
//! // Adding
//! items.push(42);
//!
//! // Getting
//! assert_eq!(Some(&42), items.get(0));
//!
//! // Removing
//! assert_eq!(Some(42), items.pop());
//! assert_eq!(None, items.pop());
//! ```

use std::cmp::Ordering;
use std::fmt::{Debug, Formatter, Error};
use std::mem;

extern crate serde;
use serde::ser::{Serialize, Serializer, SerializeSeq};
use serde::de::{Deserialize, Deserializer};

mod iter;
pub use self::iter::Iter;


#[derive(Clone)]
pub struct OneStackVec<T>(Option<(T, Vec<T>)>);

impl<T> OneStackVec<T> {
    pub fn new() -> OneStackVec<T> {
        OneStackVec(None)
    }

    pub fn is_zero(&self) -> bool {
        self.0.is_none()
    }


    pub fn push(&mut self, item: T) {
        match &mut self.0 {
            inner @ &mut None => {
                mem::replace(inner, Some((item, Vec::new())));
            }
            &mut Some((_, ref mut vec)) => {
                vec.push(item);
            }
        }
    }

    pub fn get(&self, index: usize) -> Option<&T> {
        match &self.0 {
            &None => None,
            &Some((ref one, ref vec)) => {
                if index == 0 {
                    Some(one)
                } else {
                    vec.get(index - 1)
                }
            }
        }
    }

    /// Removes the last element from a vector and returns it, or `None` if it is empty.
    pub fn pop(&mut self) -> Option<T> {
        match &mut self.0 {
            &mut None => None,
            &mut Some((_, ref mut vec)) if vec.len() > 0 => vec.pop(),
            inner => {
                // "inner" contains only one item.
                let old_inner = mem::replace(inner, None);
                Some(old_inner.unwrap().0)
            }
        }
    }

    pub fn len(&self) -> usize {
        match &self.0 {
            &None => 0,
            &Some((_, ref vec)) => vec.len() + 1,
        }
    }


    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter::with(self.0.as_ref().map(|&(ref first, ref vec)| (first, vec.iter())))
    }


    pub fn contains(&self, x: &T) -> bool
        where T: PartialEq<T>
    {
        match &self.0 {
            &None => false,
            &Some((ref first, ref vec)) => first.eq(x) || vec.contains(x),
        }
    }
}


impl<T> Debug for OneStackVec<T>
    where T: Debug
{
    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        match &self.0 {
            &None => write!(f, "OneStackVec ()"),
            &Some((ref first, ref another)) => {
                write!(f, "OneStackVec ( {:?}, {:?} )", first, another)
            }
        }
    }
}



impl<T> PartialEq for OneStackVec<T>
    where T: PartialEq
{
    fn eq(&self, other: &OneStackVec<T>) -> bool {
        self.0.eq(&other.0)
    }
}


impl<T> Eq for OneStackVec<T> where T: Eq {}


impl<T> PartialOrd for OneStackVec<T>
    where T: PartialOrd<T>
{
    fn partial_cmp(&self, other: &OneStackVec<T>) -> Option<Ordering> {
        self.0.partial_cmp(&other.0)
    }
}


impl<T> Ord for OneStackVec<T>
    where T: Ord
{
    fn cmp(&self, other: &OneStackVec<T>) -> Ordering {
        self.0.cmp(&other.0)
    }
}


impl<T> Serialize for OneStackVec<T>
    where T: Serialize
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where S: Serializer
    {
        let mut seq = serializer.serialize_seq(Some(self.len()))?;
        for item in self.iter() {
            seq.serialize_element(item)?;
        }
        seq.end()
    }
}


impl<'de, T> Deserialize<'de> for OneStackVec<T>
    where T: Deserialize<'de>
{
    fn deserialize<D>(deserializer: D) -> Result<OneStackVec<T>, D::Error>
        where D: Deserializer<'de>
    {
        deserializer.deserialize_seq(OneStackVecVisitor::new())
    }
}

struct OneStackVecVisitor<T>(::std::marker::PhantomData<T>);

impl<T> OneStackVecVisitor<T> {
    fn new() -> OneStackVecVisitor<T> {
        OneStackVecVisitor(::std::marker::PhantomData)
    }
}

impl<'de, T> ::serde::de::Visitor<'de> for OneStackVecVisitor<T>
    where T: ::serde::Deserialize<'de>
{
    type Value = OneStackVec<T>;
    fn expecting(&self, formatter: &mut ::std::fmt::Formatter) -> std::fmt::Result {
        formatter.write_str("one-stack-vec sequense")
    }

    fn visit_none<E>(self) -> Result<OneStackVec<T>, E>
        where E: ::serde::de::Error
    {
        Ok(OneStackVec::new())
    }

    fn visit_seq<A>(self, mut seq: A) -> Result<OneStackVec<T>, A::Error>
        where A: ::serde::de::SeqAccess<'de>
    {
        let mut vec = OneStackVec::new();
        while let Some(item) = seq.next_element()? {
            vec.push(item);
        }
        Ok(vec)
    }
}


#[macro_export]
macro_rules! one_stack_vec {
    ( $( $x:expr ),* ) => {
        {
            let mut tmp_vec = $crate::OneStackVec::new();
            $(
                tmp_vec.push($x);
            )*
            tmp_vec
        }
    };
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn ord() {
        let item1: OneStackVec<isize> = one_stack_vec![];
        let item2: OneStackVec<isize> = one_stack_vec![];
        assert!(item1 == item2);

        let item1 = one_stack_vec![1];
        let item2 = one_stack_vec![];
        assert!(item1 > item2);

        let item1 = one_stack_vec![1];
        let item2 = one_stack_vec![2];
        assert!(item1 < item2);

        let item1 = one_stack_vec![1, 2];
        let item2 = one_stack_vec![2];
        assert!(item1 < item2);

        let item1 = one_stack_vec![1, 2, 3, 4];
        let item2 = one_stack_vec![1, 2, 3];
        assert!(item1 > item2);
    }

    extern crate serde_json;

    #[test]
    fn serde_json() {
        let vec = one_stack_vec![1, 2, 3, 4, 5, 42_u32];
        let serialized_str = serde_json::to_string(&vec).unwrap();
        assert_eq!(vec, serde_json::from_str(serialized_str.as_str()).unwrap());

        let vec: OneStackVec<u32> = one_stack_vec![];
        let serialized_str = serde_json::to_string(&vec).unwrap();
        assert_eq!(vec, serde_json::from_str(serialized_str.as_str()).unwrap());
    }
}