seadawg 0.1.3

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

pub mod u8;
pub mod sorted;
pub mod sorted_u8;

#[repr(packed)]
pub struct VecU32<T> {
  ptr: *mut T,
  len: u32,
  cap: u32,
}

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

impl<T> VecU32<T> {
  /// Get the number of elements in the vector
  pub fn len(&self) -> usize {
    self.len as usize
  }

  pub fn is_empty(&self) -> bool {
    self.len == 0
  }

  /// Create a new, empty vector
  pub fn new() -> VecU32<T> {
    VecU32 {
      ptr: ptr::null_mut(),
      len: 0,
      cap: 0
    }
  }

  /// Create a new, empty vector with a given capacity
  pub fn with_capacity(cap: usize) -> VecU32<T> {
    unsafe {
      let layout = Layout::from_size_align_unchecked(
        (cap as usize) * size_of::<T>(),
        align_of::<T>()
      );
      let vec = VecU32 {
        ptr: alloc(layout) as *mut T,
        len: 0,
        cap: cap as u32,
      };

      vec
    }
  }

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

  /// Maximum to hold before expansion
  pub fn capacity(&self) -> usize {
    self.cap as usize
  }

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

      let mut new_cap = 1;
      if self.cap == 0 {

        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 {
        new_cap = self.cap * 2;

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

      self.cap = new_cap;
    }
  }

  /// Push an item into the vector
  #[inline]
  pub fn push(&mut self, value: T) {
    if self.len == self.cap {
      self.double_buf();
    }

    unsafe {
      let end = self.as_mut_ptr().offset(self.len as isize);
      ptr::write(end, value);
      self.len += 1;
    }
  }

  /// push at position
  pub fn push_at(&mut self, _: usize, value: T) {
    if self.len == self.cap {
      self.double_buf();
    }

    unsafe {
      let end = self.as_mut_ptr().offset(self.len as isize);
      ptr::write(end, value);
      self.len += 1;
    }
  }

  /// Extend from a copyable slice
  pub fn extend_from_copy_slice(&mut self, other: &[T])
  where
    T: Copy,
  {
    while self.len + other.len() as u32 > self.cap {
      self.double_buf();
    }

    let old_len = self.len as usize;
    self.len += other.len() as u32;
    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.len == 0 {
      None
    } else {
      unsafe {
        self.len -= 1;
        Some(ptr::read(self.get_unchecked(self.len())))
      }
    }
  }

  /// Insert a value at `index`, copying the elements after `index` upwards
  pub fn insert(&mut self, index: usize, value: T) {
    if self.len == self.cap {
      self.double_buf();
    }

    unsafe {

      let p = self.as_mut_ptr().add(index);
      // Shift everything over to make space. (Duplicating the
      // `index`th element into two consecutive places.)
      ptr::copy(p, p.offset(1), self.len as usize - index);
      // Write it in, overwriting the first copy of the `index`th
      // element.
      ptr::write(p, value);

      self.len += 1;
    }
  }

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

        // Shift everything down to fill in that spot.
        ptr::copy(ptr.offset(1), ptr, len - index - 1);
      }
      self.len -= 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 as usize;
      let hole: *mut T = &mut self[index];
      let last = ptr::read(self.get_unchecked(len - 1));
      self.len -= 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 as usize;
    {
      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 {
      while desired_len < self.len as usize {
        self.len -= 1;
        let len = self.len;
        ptr::drop_in_place(self.get_unchecked_mut(len as usize));
      }
    }
  }

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

      other.len = 0;
    }
  }

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

    while self.len + count as u32 > self.cap {
      self.double_buf();
    }

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

    self.len += count as u32;
  }

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

impl<T> From<Vec<T>> for VecU32<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 VecU32<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 VecU32<T> {
  type Target = [T];

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

impl<T> DerefMut for VecU32<T> {
  fn deref_mut(&mut self) -> &mut [T] {
    if self.ptr.is_null() {
      unsafe { ::std::slice::from_raw_parts_mut(0x1 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 VecU32<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 as usize,
      // cap: self.cap as usize,
      index: 0,
    };
    ::std::mem::forget(self);
    iter
  }
}

impl<'a, T> IntoIterator for &'a VecU32<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 VecU32<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 VecU32<T> {
  fn clone(&self) -> VecU32<T> {
    VecU32::from(self.iter().cloned().collect::<Vec<_>>())
  }
}

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

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

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

impl<T: ::std::fmt::Debug> ::std::fmt::Debug for VecU32<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};

#[cfg(feature = "serde-serialization")]
impl<T> ::serde::ser::Serialize for VecU32<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 VecU32Visitor<T> {
  marker: PhantomData<fn() -> VecU32<T>>
}

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

#[cfg(feature = "serde-serialization")]
impl<'de, T> ::serde::de::Visitor<'de> for VecU32Visitor<T>
where
  T: ::serde::de::Deserialize<'de>
{
  type Value = VecU32<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 = VecU32::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 VecU32<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(VecU32Visitor::new())
  }
}

#[cfg(test)]
mod test {

  use std::sync::Arc;
  use super::VecU32;

  #[test]
  fn test_assure_passing_to_threads() {

    let shared_vec = Arc::new(VecU32::<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();
    });
  }
}