seadawg 0.1.3

//! Sorted vectors.
//!
//! [Repository](https://gitlab.com/spearman/sorted-vec)
//!
//! - `SortedVec` -- sorted from least to greatest
//! - `ReverseSortedVec` -- sorted from greatest to least
//!
//! The `partial` module provides sorted vectors of types that only implement
//! `PartialOrd` where comparison of incomparable elements results in runtime
//! panic.

use super::u8::VecU8;

//#[cfg(feature = "serde")]
//#[macro_use] extern crate serde;

// pub mod partial;

/// Forward sorted vector
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Clone, Debug)]
pub struct SortedVecU8<T: Ord> {
  vec: VecU8<T>
}

/// Reverse sorted vector
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Clone, Debug)]
pub struct ReverseSortedVecU8<T: Ord> {
  vec: VecU8<T>
}

impl<T: Ord> SortedVecU8<T> {

  #[inline]
  pub fn new() -> Self {
    SortedVecU8 {
      vec: VecU8::new(),
    }
  }

  #[inline]
  pub fn with_capacity(capacity: usize) -> Self {
    SortedVecU8 {
      vec: VecU8::with_capacity(capacity),
    }
  }

  /// Uses `sort_unstable()` to sort in place.
  #[inline]
  pub fn from_unsorted(mut vec: Vec<T>) -> Self {
    vec.sort_unstable();
    SortedVecU8 {
      vec: VecU8::from(vec),
    }
  }

  /// Insert an element into sorted position, returning the order index at which
  /// it was placed.
  ///
  /// If the element was already present, the order index is returned as an
  /// `Err`, otherwise it is returned with `Ok`.
  pub fn insert(&mut self, element: T) -> Result<usize, usize> {
    match &self.vec[..].binary_search(&element) {
      Ok(insert_at) => {
        self.vec.insert(*insert_at, element);
        Err(*insert_at)
      }
      Err(insert_at) => {
        self.vec.insert(*insert_at, element);
        Ok(*insert_at)
      }
    }
  }

  pub fn insert_unique(&mut self, element: T) -> Result<usize, usize> {
    match &self.vec[..].binary_search(&element) {
      Ok(insert_at) => {
        Err(*insert_at)
      }
      Err(insert_at) => {
        self.vec.insert(*insert_at, element);
        Ok(*insert_at)
      }
    }
  }

  #[inline]
  pub fn remove_item(&mut self, item: &T) -> Option<T> {
    match self.vec.binary_search(item) {
      Ok(remove_at) => Some(self.vec.remove(remove_at)),
      Err(_) => None
    }
  }

  #[inline]
  pub fn find<'a, F, K: Ord>(&'a self, key: &K, key_extrqctor: F) -> Option<&T>
  where F: FnMut(&'a T) -> K,
        K: Ord, {
    match self.vec.binary_search_by_key(key, key_extrqctor) {
      Ok(idx) => self.vec.get(idx),
      Err(_) => None
    }
  }

  #[inline]
  pub fn find_mut<'a, F, K: Ord>(&'a mut self, key: &K, key_extrqctor: F) -> Option<&mut T>
  where F: FnMut(&'a T) -> K,
        K: Ord, {

    unsafe {
      // Rust is just complete shit here
      let ptr: *mut VecU8<T> = &mut self.vec;
      match (*ptr).binary_search_by_key(key, key_extrqctor) {
        Ok(idx) => self.vec.get_mut(idx),
        Err(_) => None
      }
    }
  }

  #[inline]
  pub fn remove_by_key<'a, F, K>(&'a mut self, key: &'a K, key_extractor: F) -> Option<T>
  where F: FnMut(&'a T) -> K,
        K: Ord + 'a, {

    unsafe {
      // Rust is just complete shit here
      let ptr: *mut VecU8<T> =  &mut self.vec;
      let remove_at_option = (*ptr).binary_search_by_key(
        key,
        key_extractor
      );

      if remove_at_option.is_err() {
        return None;
      }

      let remove_at = remove_at_option.unwrap();
      let value = self.vec.remove(remove_at);
      Some(value)
    }
  }

  /// Panics if index is out of bounds
  #[inline]
  pub fn remove_index(&mut self, index: usize) -> T {
    self.vec.remove(index)
  }
  #[inline]
  pub fn pop(&mut self) -> Option<T> {
    self.vec.pop()
  }
  #[inline]
  pub fn clear(&mut self) {
    self.vec.clear()
  }
  // #[inline]
  // pub fn dedup (&mut self) {
  //   self.vec.dedup();
  // }
  // #[inline]
  // pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
  //   R : std::ops::RangeBounds <usize>
  // {
  //   self.vec.drain (range)
  // }
  #[inline]
  pub fn into_vec(mut self) -> Vec<T> {
    unsafe {
      let v = Vec::from_raw_parts(self.vec.as_mut_ptr(), self.vec.len(), self.vec.capacity());
      std::mem::forget(self);
      v
    }
  }

  /// Apply a closure mutating the sorted vector and use `sort_unstable()`
  /// to re-sort the mutated vector
  pub fn mutate_vec<F, O>(&mut self, f: F) -> O where
    F: FnOnce(&mut VecU8<T>) -> O
  {
    let res = f(&mut self.vec);
    self.vec.sort_unstable();
    res
  }
}

impl<T: Ord> Default for SortedVecU8<T> {
  fn default() -> Self {
    Self::new()
  }
}

impl<T: Ord> std::ops::Deref for SortedVecU8<T> {
  type Target = VecU8<T>;
  fn deref(&self) -> &Self::Target {
    &self.vec
  }
}

impl<T: Ord> std::ops::DerefMut for SortedVecU8<T> {

  fn deref_mut(&mut self) -> &mut Self::Target {
    &mut self.vec
  }
}

impl<T: Ord> Extend<T> for SortedVecU8<T> {
  fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
    for t in iter {
      let _ = self.insert(t);
    }
  }
}

impl<T: Ord> ReverseSortedVecU8<T> {
  #[inline]
  pub fn new() -> Self {
    ReverseSortedVecU8 { vec: VecU8::new() }
  }
  #[inline]
  pub fn with_capacity(capacity: usize) -> Self {
    ReverseSortedVecU8 { vec: VecU8::with_capacity(capacity) }
  }
  /// Uses `sort_unstable_by()` to sort in place.
  #[inline]
  pub fn from_unsorted(mut vec: Vec<T>) -> Self {
    vec.sort_unstable_by(|x, y| x.cmp(y).reverse());
    ReverseSortedVecU8 { vec: VecU8::from(vec) }
  }
  /// Insert an element into (reverse) sorted position, returning the order
/// index at which it was placed.
///
/// If the element was already present, the order index is returned as an
/// `Err`, otherwise it is returned with `Ok`.
  pub fn insert(&mut self, element: T) -> Result<usize, usize> {
    match &self.vec[..].binary_search_by(
      |other_element| other_element.cmp(&element).reverse()
    ) {
      Ok(insert_at) => {
        self.vec.insert(*insert_at, element);
        Err(*insert_at)
      }
      Err(insert_at) => {
        self.vec.insert(*insert_at, element);
        Ok(*insert_at)
      }
    }
  }
  #[inline]
  pub fn remove_item(&mut self, item: &T) -> Option<T> {
    match self.vec.binary_search_by(
      |other_item| other_item.cmp(&item).reverse()
    ) {
      Ok(remove_at) => Some(self.vec.remove(remove_at)),
      Err(_) => None
    }
  }
  /// Panics if index is out of bounds
  #[inline]
  pub fn remove_index(&mut self, index: usize) -> T {
    self.vec.remove(index)
  }
  #[inline]
  pub fn binary_search(&self, x: &T) -> Result<usize, usize> {
    self.vec.binary_search_by(|y| y.cmp(&x).reverse())
  }
  #[inline]
  pub fn pop(&mut self) -> Option<T> {
    self.vec.pop()
  }
  #[inline]
  pub fn clear(&mut self) {
    self.vec.clear()
  }
  // #[inline]
  // pub fn dedup (&mut self) {
  //   self.vec.dedup();
  // }
  // #[inline]
  // pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
  //   R : std::ops::RangeBounds <usize>
  // {
  //   self.vec.drain (range)
  // }
  #[inline]
  pub fn into_vec(mut self) -> Vec<T> {
    unsafe {
      let v = Vec::from_raw_parts(self.vec.as_mut_ptr(), self.vec.len(), self.vec.capacity());
      std::mem::forget(self);
      v
    }
  }
  /// Apply a closure mutating the reverse-sorted vector and use
/// `sort_unstable_by()` to re-sort the mutated vector
  pub fn mutate_vec<F, O>(&mut self, f: F) -> O where
    F: FnOnce(&mut VecU8<T>) -> O
  {
    let res = f(&mut self.vec);
    self.vec.sort_unstable_by(|x, y| x.cmp(y).reverse());
    res
  }
}

impl<T: Ord> Default for ReverseSortedVecU8<T> {
  fn default() -> Self {
    Self::new()
  }
}

impl<T: Ord> std::ops::Deref for ReverseSortedVecU8<T> {
  type Target = VecU8<T>;
  fn deref(&self) -> &VecU8<T> {
    &self.vec
  }
}

impl<T: Ord> std::ops::DerefMut for ReverseSortedVecU8<T> {

  fn deref_mut(&mut self) -> &mut Self::Target {
    &mut self.vec
  }
}

impl<T: Ord> Extend<T> for ReverseSortedVecU8<T> {
  fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
    for t in iter {
      let _ = self.insert(t);
    }
  }
}