seadawg 0.1.3

use std::ptr;
use std::ops::{Deref, DerefMut};
use std::iter::FromIterator;

#[repr(packed)]
pub struct VecU8<T> {
  ptr: *mut T,
  len_idx: u8,
  cap_idx: u8,
}

unsafe impl<T> Send for VecU8<T> {}
unsafe impl<T> Sync for VecU8<T> {}

impl<T> VecU8<T> {
  /// Get the number of elements in the vector
  pub fn len(&self) -> usize {
    
    if self.is_empty() {
      return 0;
    }

    return self.len_idx as usize + 1;
  }

  pub fn is_empty(&self) -> bool {
    self.ptr.is_null()
  }

  /// Create a new, empty vector
  pub fn new() -> VecU8<T> {
    VecU8 {
      ptr: ptr::null_mut(),
      len_idx: 0,
      cap_idx: 0
    }
  }

  /// Create a new, empty vector with a given capacity
  pub fn with_capacity(cap: usize) -> VecU8<T> {
    
    let mut cap_idx: u8 =  0;
    if cap > 1 {
      cap_idx = (cap - 1) as u8;
    }

    return VecU8 {
      ptr: ptr::null_mut(),
      len_idx: 0,
      cap_idx,
    };
  }

  /// Create a new vector from raw parts
  pub unsafe fn from_raw_parts(ptr: *mut T, len: usize, cap: usize) -> VecU8<T> {

    let mut cap_idx: u8 =  0;
    if cap > 1 {
      cap_idx = (cap - 1) as u8;
    }

    let mut len_idx: u8 =  0;
    if !ptr.is_null() {
      len_idx = (len - 1) as u8;
    }

    return VecU8 {
      ptr,
      len_idx,
      cap_idx,
    };
  }

  /// Maximum to hold before expansion
  pub fn capacity(&self) -> usize {
    return (self.cap_idx as usize) + 1;
  }

  /// Double the capacity of the vector by spilling onto the heap
  fn double_buf(&mut self) {

    if self.cap_idx == u8::MAX {
      panic!("Cannot double the buffer further");
    }

    let was_empty = self.is_empty();

    unsafe {

      let mut new_cap: usize = 1;
      if was_empty {

        if self.cap_idx > 0 {
          new_cap = self.cap_idx as usize + 1;
        }

        let layout = Layout::from_size_align_unchecked(
          (new_cap as usize) * size_of::<T>(),
          align_of::<T>()
        );
        self.ptr = alloc(layout) as *mut T;
      } else {

        if self.cap_idx < 127 {
          new_cap = (self.cap_idx as usize + 1) * 2;
        } else {
          new_cap = 255;
        }

        let layout = Layout::from_size_align_unchecked(
          (self.cap_idx as usize) * size_of::<T>(),
          align_of::<T>()
        );
        self.ptr = realloc(self.ptr as *mut u8, layout, new_cap * size_of::<T>()) as *mut T;

        self.cap_idx = (new_cap - 1) as u8;
      }
    }
  }

  /// Push an item into the vector
  #[inline]
  pub fn push(&mut self, value: T) {

    let was_empty = self.is_empty();

    if was_empty || self.len_idx == self.cap_idx {
      self.double_buf();
    }

    let mut offset: isize = 0;

    if !was_empty {
      offset = self.len_idx as isize + 1;
    }

    unsafe {
      let end = self.as_mut_ptr().offset(offset);
      ptr::write(end, value);
    }

    if !was_empty {
      self.len_idx += 1;
    }
  }

  /// push at position
  pub fn push_at(&mut self, _: usize, value: T) {

    let was_empty = self.is_empty();
    
    if was_empty || self.len_idx == self.cap_idx {
      self.double_buf();
    }

    let mut offset: isize = 0;

    if !was_empty {
      offset = self.len_idx as isize + 1;
    }

    unsafe {
      let end = self.as_mut_ptr().offset(offset);
      ptr::write(end, value);
    }

    self.len_idx += 1;
  }

  /// Extend from a copyable slice
  pub fn extend_from_copy_slice(&mut self, other: &[T])
  where
    T: Copy,
  {
    if other.is_empty() {
      return;
    }

    while self.is_empty() || self.len_idx as usize + other.len() > self.cap_idx as usize {
      self.double_buf();
    }

    let old_len = self.len_idx as usize;
    self.len_idx += (other.len() - 1)  as u8;
    self[old_len..].copy_from_slice(other);
  }

  /// Pop and return the last element, if the vector wasn't empty
  #[inline]
  pub fn pop(&mut self) -> Option<T> {
    if self.is_empty() {
      return None;
    }

    let len_idx = self.len_idx as usize;
    if len_idx > 0 {
      self.len_idx -= 1;
    }
    unsafe {
      Some(ptr::read(self.get_unchecked(len_idx)))
    }
  }

  /// Insert a value at `index`, copying the elements after `index` upwards
  pub fn insert(&mut self, index: usize, value: T) {

    let was_empty = self.is_empty();
    if was_empty || self.len_idx == self.cap_idx {
      self.double_buf();
    }

    unsafe {

      let p = self.as_mut_ptr().add(index);

      let len_idx = self.len_idx as usize;
      if !was_empty && len_idx >= index {
        // Shift everything over to make space. (Duplicating the
        // `index`th element into two consecutive places.)
        ptr::copy(p, p.offset(1), len_idx - index + 1);
      }

      // Write it in, overwriting the first copy of the `index`th
      // element.
      ptr::write(p, value);

      if !was_empty {
        self.len_idx += 1;
      }
    }
  }

  /// Remove the element at `index`, copying the elements after `index` downwards
  pub fn remove(&mut self, index: usize) -> T {
    let len = self.len();
    assert!(index < len);

    unsafe {
      // infallible
      let ret;
      {
        // the place we are taking from.
        let ptr = self.as_mut_ptr().add(index);
        // copy it out, unsafely having a copy of the value on
        // the stack and in the vector at the same time.
        ret = ptr::read(ptr);

        if self.len_idx as usize == index {
          ptr::copy(ptr::null(), ptr, 1);
        } else {
          // Shift everything down to fill in that spot.
          ptr::copy(ptr.offset(1), ptr, len - index);
        }
      }
      let was_empty = self.is_empty();

      if !was_empty {
        self.len_idx -= 1;
      }
      ret
    }
  }

  /// Removes an element from the vector and returns it.
  ///
  /// The removed element is replaced by the last element of the vector.
  ///
  /// This does not preserve ordering, but is O(1).
  #[inline]
  pub fn swap_remove(&mut self, index: usize) -> T {
    unsafe {
      let len = self.len_idx as usize;
      let hole: *mut T = &mut self[index];
      let last = ptr::read(self.get_unchecked(len));
      self.len_idx -= 1;
      ptr::replace(hole, last)
    }
  }

  /// Take a function which returns whether an element should be kept,
  /// and mutably removes all elements from the vector which are not kept
  pub fn retain<F: FnMut(&T) -> bool>(&mut self, mut keep: F) {
    let mut del = 0;
    let len = self.len();

    {
      let v = &mut **self;

      for i in 0..len {
        if !keep(&v[i]) {
          del += 1;
        } else {
          v.swap(i - del, i);
        }
      }
    }

    if del > 0 {
      self.truncate(len - del);
    }
  }

  /// Truncate the vector to the given length
  pub fn truncate(&mut self, desired_len: usize) {
    unsafe {

      if desired_len == 0 {
        ptr::drop_in_place(&mut self[..]);
        self.len_idx = 0;
        return;
      }

      let len = self.len();
      ptr::drop_in_place(&mut self[desired_len..len]);

      self.len_idx = (desired_len - 1) as u8;
    }
  }

  #[inline]
  pub fn append(&mut self, other: &mut Self) {
    unsafe {
      self.append_elements(&other[..] as _);

      other.len_idx = 0;
      //TODO: maybe assert other's ptr is null
    }
  }

  /// Appends elements to `Self` from other buffer.
  #[inline]
  unsafe fn append_elements(&mut self, other: *const [T]) {

    if (*other).is_empty() {
      return;
    }
    
    let other_len = (*other).len();

    if self.len() + other_len > 255 {
      panic!("Cannot append elements because resulting vector is too big");
    }

    while self.is_empty() || self.len_idx as usize + other_len > self.cap_idx as usize {
      self.double_buf();
    }

    let self_len = self.len();
    ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(self_len), other_len);

    self.len_idx += other_len as u8;
  }

  /// Clear the vector
  #[inline]
  pub fn clear(&mut self) {
    self.truncate(0);
  }
}

impl<T> From<Vec<T>> for VecU8<T> {
  /// Create a `VecU32` from a normal `Vec`,
  /// directly using the backing storage as free heap storage
  fn from(mut vec: Vec<T>) -> Self {
    let cvec = unsafe { Self::from_raw_parts(vec.as_mut_ptr(), vec.len(), vec.capacity()) };
    ::std::mem::forget(vec);
    cvec
  }
}

impl<T> Drop for VecU8<T> {
  /// Drop elements and deallocate free heap storage, if any is allocated
  fn drop(&mut self) {
    unsafe {
      ptr::drop_in_place(&mut self[..]);
    };
  }
}

impl<T> Deref for VecU8<T> {
  type Target = [T];

  fn deref(&self) -> &[T] {
    if self.is_empty() {
      unsafe { ::std::slice::from_raw_parts(ptr::null() as *const T, 0) }
    } else {
      unsafe { ::std::slice::from_raw_parts(self.ptr, self.len() as usize) }
    }
  }
}

impl<T> DerefMut for VecU8<T> {
  fn deref_mut(&mut self) -> &mut [T] {
    if self.is_empty() {
      unsafe { ::std::slice::from_raw_parts_mut(ptr::null_mut() as *mut T, 0) }
    } else {
      unsafe { ::std::slice::from_raw_parts_mut(self.ptr, self.len() as usize) }
    }
  }
}

pub struct IntoIter<T> {
  ptr: *mut T,
  len: usize,
  // cap: usize,
  index: usize
}

impl<T> Iterator for IntoIter<T> {
  type Item = T;

  fn next(&mut self) -> Option<T> {
    if self.index < self.len {
      let item = unsafe { ptr::read(self.ptr.offset(self.index as isize)) };
      self.index += 1;
      Some(item)
    } else {
      None
    }
  }
}

impl<T> Drop for IntoIter<T> {
  fn drop(&mut self) {
    // drop all remaining elements
    unsafe {
      ptr::drop_in_place(&mut ::std::slice::from_raw_parts(
        self.ptr.offset(self.index as isize),
        self.len,
      ));
    };
  }
}

impl<T> IntoIterator for VecU8<T> {
  type Item = T;
  type IntoIter = IntoIter<T>;

  fn into_iter(self) -> Self::IntoIter {
    let iter = IntoIter {
      ptr: unsafe { &mut ptr::read(self.ptr) },
      len: self.len(),
      // cap: self.cap as usize,
      index: 0,
    };
    ::std::mem::forget(self);
    iter
  }
}

impl<'a, T> IntoIterator for &'a VecU8<T> {
  type Item = &'a T;
  type IntoIter = ::std::slice::Iter<'a, T>;

  fn into_iter(self) -> Self::IntoIter {
    self.iter()
  }
}

impl<'a, T> IntoIterator for &'a mut VecU8<T> {
  type Item = &'a mut T;
  type IntoIter = ::std::slice::IterMut<'a, T>;

  fn into_iter(self) -> Self::IntoIter {
    self.iter_mut()
  }
}

impl<T: Clone> Clone for VecU8<T> {
  fn clone(&self) -> VecU8<T> {
    VecU8::from(self.iter().cloned().collect::<Vec<_>>())
  }
}

impl<T> FromIterator<T> for VecU8<T> {
  fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
    let into_iter = iter.into_iter();
    let mut vec = VecU8::with_capacity(into_iter.size_hint().0);
    for item in into_iter {
      vec.push(item);
    }
    vec
  }
}

impl<T> Extend<T> for VecU8<T> {
  fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
    for item in iter {
      self.push(item);
    }
  }
}

impl<T> Default for VecU8<T> {
  fn default() -> VecU8<T> {
    VecU8::new()
  }
}

impl<T: ::std::fmt::Debug> ::std::fmt::Debug for VecU8<T> {
  fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
    (self.deref()).fmt(f)
  }
}

#[cfg(feature = "serde-serialization")]
use ::serde::ser::SerializeSeq;
use std::alloc::{alloc, Layout, realloc};
use std::mem::{size_of, align_of};
use std::panic;

#[cfg(feature = "serde-serialization")]
impl<T> ::serde::ser::Serialize for VecU8<T>
where
  T: ::serde::ser::Serialize
{
  fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
  where
    S: ::serde::ser::Serializer,
  {
    let mut seq = serializer.serialize_seq(Some(self.len()))?;
    for e in self {
      seq.serialize_element(e)?;
    }
    seq.end()
  }
}

#[cfg(feature = "serde-serialization")]
struct VecU8Visitor<T> {
  marker: PhantomData<fn() -> VecU8<T>>
}

#[cfg(feature = "serde-serialization")]
impl<T> VecU8Visitor<T> {
  fn new() -> Self {
    VecU8Visitor {
      marker: PhantomData
    }
  }
}

#[cfg(feature = "serde-serialization")]
impl<'de, T> ::serde::de::Visitor<'de> for VecU8Visitor<T>
where
  T: ::serde::de::Deserialize<'de>
{
  type Value = VecU8<T>;

  fn expecting(&self, formatter: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
    formatter.write_str("A Compact Vector")
  }

  fn visit_seq<S>(self, mut access: S) -> Result<Self::Value, S::Error>
  where
    S: ::serde::de::SeqAccess<'de>,
  {
    let mut vector = VecU8::with_capacity(access.size_hint().unwrap_or(0));

    while let Some(element) = access.next_element()? {
      vector.push(element);
    }

    Ok(vector)
  }
}

#[cfg(feature = "serde-serialization")]
impl<'de, T> ::serde::de::Deserialize<'de> for VecU8<T>
where
  T: ::serde::de::Deserialize<'de>
{
  fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
  where
    D: ::serde::de::Deserializer<'de>,
  {
    deserializer.deserialize_map(VecU8Visitor::new())
  }
}

#[cfg(test)]
mod test {

  use std::sync::Arc;
  use super::VecU8;

  #[test]
  fn test_assure_passing_to_threads() {

    let shared_vec = Arc::new(VecU8::<u32>::new());

    let shared_vec_clone = shared_vec.clone();
    std::thread::spawn(move || {
      shared_vec_clone.clone();
    });
    
    let shared_vec_clone = shared_vec.clone();
    std::thread::spawn(move || {
      shared_vec_clone.clone();
    });
  }
}