use std::{
cmp::Ordering,
ops::{Index, IndexMut},
};
pub trait HasLength {
fn len(&self) -> usize;
fn is_empty(&self) -> bool {
self.len() == 0
}
}
pub trait Array: HasLength + Index<usize> {
fn get(&self, index: usize) -> Option<&<Self as Index<usize>>::Output> {
if index >= self.len() {
None
} else {
Some(&self[index])
}
}
fn first(&self) -> Option<&<Self as Index<usize>>::Output> {
self.get(0)
}
fn last(&self) -> Option<&<Self as Index<usize>>::Output> {
if self.is_empty() {
None
} else {
self.get(self.len() - 1)
}
}
fn contains(&self, target: &<Self as Index<usize>>::Output) -> bool
where
<Self as Index<usize>>::Output: PartialEq,
{
for index in 0..self.len() {
if &self[index] == target {
return true;
}
}
false
}
fn binary_search(&self, target: &<Self as Index<usize>>::Output) -> Result<usize, usize>
where
<Self as Index<usize>>::Output: Ord,
{
self.binary_search_by(|value| value.cmp(target))
}
fn binary_search_by<F>(&self, mut compare: F) -> Result<usize, usize>
where
F: FnMut(&<Self as Index<usize>>::Output) -> Ordering,
{
let s = self;
let mut size = s.len();
if size == 0 {
return Err(0);
}
let mut base = 0usize;
while size > 1 {
let half = size / 2;
let mid = base + half;
let cmp = compare(&s[mid]);
base = if cmp == Ordering::Greater { base } else { mid };
size -= half;
}
let cmp = compare(&s[base]);
if cmp == Ordering::Equal {
Ok(base)
} else {
Err(base + (cmp == Ordering::Less) as usize)
}
}
fn binary_search_by_key<K, F>(&self, key: &K, mut extract: F) -> Result<usize, usize>
where
F: FnMut(&<Self as Index<usize>>::Output) -> K,
K: Ord,
{
self.binary_search_by(|i| extract(i).cmp(key))
}
fn is_sorted(&self) -> bool
where
<Self as Index<usize>>::Output: PartialOrd,
{
self.is_sorted_by(|l, r| l.partial_cmp(r))
}
fn is_sorted_by<F>(&self, mut compare: F) -> bool
where
F: FnMut(
&<Self as Index<usize>>::Output,
&<Self as Index<usize>>::Output,
) -> Option<Ordering>,
{
if self.len() < 2 {
true
} else {
for i in 1..self.len() {
if compare(&self[i - 1], &self[i]) == Some(Ordering::Greater) {
return false;
}
}
true
}
}
fn is_sorted_by_key<K, F>(&self, mut extract: F) -> bool
where
F: FnMut(&<Self as Index<usize>>::Output) -> K,
K: PartialOrd<K>,
{
self.is_sorted_by(|l, r| extract(l).partial_cmp(&extract(r)))
}
fn starts_with(&self, slice: &[<Self as Index<usize>>::Output]) -> bool
where
<Self as Index<usize>>::Output: PartialEq + Sized,
{
if slice.len() > self.len() {
return false;
}
for i in 0..slice.len() {
if self[i] != slice[i] {
return false;
}
}
true
}
fn ends_with(&self, slice: &[<Self as Index<usize>>::Output]) -> bool
where
<Self as Index<usize>>::Output: PartialEq + Sized,
{
if slice.len() > self.len() {
return false;
}
let offset = self.len() - slice.len();
for i in 0..slice.len() {
if self[offset + i] != slice[i] {
return false;
}
}
true
}
}
pub trait ArrayMut: Array + IndexMut<usize> {
fn get_mut(&mut self, index: usize) -> Option<&mut <Self as Index<usize>>::Output> {
if index >= self.len() {
None
} else {
Some(&mut self[index])
}
}
fn first_mut(&mut self) -> Option<&mut <Self as Index<usize>>::Output> {
self.get_mut(0)
}
fn last_mut(&mut self) -> Option<&mut <Self as Index<usize>>::Output> {
if self.is_empty() {
None
} else {
self.get_mut(self.len() - 1)
}
}
fn set(
&mut self,
index: usize,
value: <Self as Index<usize>>::Output,
) -> Option<<Self as Index<usize>>::Output>
where
<Self as Index<usize>>::Output: Sized,
{
self.get_mut(index).map(|p| std::mem::replace(p, value))
}
fn swap(&mut self, index1: usize, index2: usize)
where
<Self as Index<usize>>::Output: Sized,
{
if index1 != index2 {
let ptr1: *mut <Self as Index<usize>>::Output = &mut self[index1];
let ptr2: *mut <Self as Index<usize>>::Output = &mut self[index2];
unsafe { std::ptr::swap(ptr1, ptr2) };
}
}
fn map_pair<F, A>(&mut self, index1: usize, index2: usize, mut f: F) -> A
where
F: FnMut(&mut <Self as Index<usize>>::Output, &mut <Self as Index<usize>>::Output) -> A,
{
if index1 == index2 {
panic!("ArrayMut::map_pair: indices cannot be equal!");
}
let pa: *mut <Self as Index<usize>>::Output = self.index_mut(index1);
let pb: *mut <Self as Index<usize>>::Output = self.index_mut(index2);
unsafe { f(&mut *pa, &mut *pb) }
}
fn sort_unstable(&mut self)
where
<Self as Index<usize>>::Output: Ord + Sized,
{
self.sort_unstable_by(|l, r| l.cmp(r))
}
fn sort_unstable_by<F>(&mut self, mut compare: F)
where
<Self as Index<usize>>::Output: Sized,
F: FnMut(&<Self as Index<usize>>::Output, &<Self as Index<usize>>::Output) -> Ordering,
{
crate::sort::quicksort(self, 0, self.len() - 1, |a, b| compare(a, b));
}
fn sort_unstable_by_key<F, K>(&mut self, mut extract: F)
where
F: FnMut(&<Self as Index<usize>>::Output) -> K,
K: Ord,
<Self as Index<usize>>::Output: Sized,
{
self.sort_unstable_by(|l, r| extract(l).cmp(&extract(r)))
}
}
#[cfg(test)]
mod test {
use super::*;
use std::iter::FromIterator;
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct TestVec<A>(Vec<A>);
impl<A> HasLength for TestVec<A> {
fn len(&self) -> usize {
self.0.len()
}
}
impl<A> Index<usize> for TestVec<A> {
type Output = A;
fn index(&self, index: usize) -> &A {
&self.0[index]
}
}
impl<A> IndexMut<usize> for TestVec<A> {
fn index_mut(&mut self, index: usize) -> &mut A {
&mut self.0[index]
}
}
impl<A> Array for TestVec<A> {}
impl<A> ArrayMut for TestVec<A> {}
impl<A> FromIterator<A> for TestVec<A> {
fn from_iter<I>(iter: I) -> Self
where
I: IntoIterator<Item = A>,
{
Self(Vec::from_iter(iter))
}
}
impl<A> From<Vec<A>> for TestVec<A> {
fn from(vec: Vec<A>) -> Self {
Self(vec)
}
}
#[test]
fn ops() {
let mut vec = TestVec::from_iter(1..=3);
assert_eq!(3, vec.len());
assert_eq!(Some(&1), vec.first());
assert_eq!(Some(&2), vec.get(1));
assert_eq!(Some(&3), vec.last());
*vec.first_mut().unwrap() = 3;
*vec.last_mut().unwrap() = 1;
*vec.get_mut(1).unwrap() = 5;
vec.swap(0, 1);
assert_eq!(TestVec::from(vec![5, 3, 1]), vec);
assert!(!vec.is_sorted());
vec.sort_unstable();
assert_eq!(TestVec::from(vec![1, 3, 5]), vec);
assert!(vec.is_sorted());
assert_eq!(Ok(1), vec.binary_search(&3));
assert_eq!(Err(1), vec.binary_search(&2));
assert_eq!(Err(0), vec.binary_search(&0));
assert_eq!(Err(3), vec.binary_search(&1337));
assert!(vec.contains(&1));
assert!(!vec.contains(&2));
assert!(vec.contains(&3));
assert!(!vec.contains(&4));
assert!(vec.contains(&5));
assert!(vec.starts_with(&[1, 3]));
assert!(!vec.starts_with(&[1, 2, 3]));
assert!(vec.ends_with(&[3, 5]));
assert!(!vec.ends_with(&[3, 4, 5]));
}
}