use std::cmp;
use std::ops;
use std::ptr;
use std::mem;
use std::fmt::{self, Debug};
use std::marker::PhantomData;
use crate::index_error::IndexingError;
use crate::index_error::index_error;
use crate::proof::*;
use std;
use crate::container_traits::*;
use crate::indexing::{IntoCheckedRange};
use crate::{Id, Index, Range};
use crate::ContainerPrivate;
pub struct Container<'id, Array, Mode = ()> {
id: Id<'id>,
arr: Array,
mode: PhantomData<Mode>,
}
#[derive(Debug, Copy, Clone)]
pub enum OnlyIndex { }
impl<'id, Array, Mode> Debug for Container<'id, Array, Mode>
where Array: Debug
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.arr.fmt(f)
}
}
impl<'id, Array, Mode> Clone for Container<'id, Array, Mode>
where Array: Clone + FixedLength
{
fn clone(&self) -> Self {
Container {
id: self.id,
arr: self.arr.clone(),
mode: self.mode,
}
}
}
impl<'id, Array, Mode> ContainerPrivate for Container<'id, Array, Mode> {
type Array = Array;
#[inline(always)]
fn array(&self) -> &Self::Array {
&self.arr
}
#[inline(always)]
fn array_mut(&mut self) -> &mut Self::Array {
&mut self.arr
}
}
impl<'id, Array, T, Mode> Container<'id, Array, Mode>
where Array: Trustworthy<Item=T>,
{
#[inline]
pub fn len(&self) -> usize {
self.arr.base_len()
}
pub fn only_index(self) -> Container<'id, Array, OnlyIndex> {
Container {
id: self.id,
arr: self.arr,
mode: PhantomData,
}
}
#[inline]
pub fn empty_range(&self) -> Range<'id> {
unsafe {
Range::from(0, 0)
}
}
#[inline]
pub fn range(&self) -> Range<'id> {
unsafe {
Range::from(0, self.len())
}
}
#[inline]
pub fn vet(&self, index: usize) -> Result<Index<'id>, IndexingError> {
if index < self.len() {
unsafe {
Ok(Index::new(index))
}
} else {
Err(index_error())
}
}
#[inline]
pub fn vet_range(&self, r: ops::Range<usize>) -> Result<Range<'id>, IndexingError> {
if r.start <= r.end && r.end <= self.len() {
unsafe {
Ok(Range::from(r.start, r.end))
}
} else {
Err(index_error())
}
}
#[inline]
pub fn split_at<P>(&self, index: Index<'id, P>) -> (Range<'id>, Range<'id, P>) {
unsafe {
(Range::from(0, index.index), Range::from_any(index.index, self.len()))
}
}
#[inline]
pub fn split_after(&self, index: Index<'id>) -> (Range<'id, NonEmpty>, Range<'id>) {
let mid = index.index + 1;
unsafe {
(Range::from_ne(0, mid), Range::from(mid, self.len()))
}
}
#[inline]
pub fn split_around<P>(&self, r: Range<'id, P>) -> (Range<'id>, Range<'id>) {
unsafe {
(Range::from(0, r.start), Range::from(r.end, self.len()))
}
}
#[inline]
pub fn before<P>(&self, index: Index<'id, P>) -> Range<'id> {
self.range_of(..index)
}
#[inline]
pub fn after(&self, index: Index<'id>) -> Range<'id> {
self.range_of(index.after()..)
}
#[inline]
pub fn range_of<P, R>(&self, r: R) -> Range<'id>
where R: OnePointRange<Index<'id, P>>,
{
debug_assert!(!(r.start().is_some() && r.end().is_some()));
unsafe {
let start = r.start().map(|i| i.index).unwrap_or(0);
let end = r.end().map(|i| i.index).unwrap_or(self.len());
debug_assert!(start <= end && end <= self.len());
Range::from(start, end)
}
}
#[inline]
pub fn forward(&self, index: &mut Index<'id>) -> bool {
let i = index.index + 1;
if i < self.len() {
index.index = i;
true
} else { false }
}
#[inline]
pub fn forward_by(&self, index: &mut Index<'id>, offset: usize) -> bool {
let i = index.index + offset;
if i < self.len() {
index.index = i;
true
} else { false }
}
#[inline]
pub fn forward_range_by<P>(&self, r: Range<'id, P>, offset: usize) -> Range<'id> {
let start = r.start.saturating_add(offset);
let end = r.end.saturating_add(offset);
let len = self.len();
unsafe {
Range::from(cmp::min(len, start), cmp::min(len, end))
}
}
#[inline]
pub fn backward(&self, index: &mut Index<'id>) -> bool {
let i = index.index;
if i > 0 {
index.index = i - 1;
true
} else { false }
}
#[inline]
pub fn scan_from<'b, F>(&'b self, index: Index<'id>, mut f: F) -> Range<'id, NonEmpty>
where F: FnMut(&'b T) -> bool, T: 'b,
Array: Contiguous<Item=T>,
{
let mut end = index;
for elt in &self[self.after(index)] {
if !f(elt) {
break;
}
end.index += 1;
}
end.index += 1;
unsafe {
Range::from_ne(index.index, end.index)
}
}
#[inline]
pub fn scan_from_rev<'b, F>(&'b self, index: Index<'id>, mut f: F) -> Range<'id, NonEmpty>
where F: FnMut(&'b T) -> bool, T: 'b,
Array: Contiguous<Item=T>,
{
unsafe {
let mut start = index;
for elt in self[..index].iter().rev() {
if !f(elt) {
break;
}
start.index -= 1;
}
Range::from_ne(start.index, index.index + 1)
}
}
#[inline]
pub fn scan_range<'b, F, P>(&'b self, range: Range<'id, P>, mut f: F)
-> (Range<'id>, Range<'id>)
where F: FnMut(&'b T) -> bool, T: 'b,
Array: Contiguous<Item=T>,
{
let mut end = range.start;
for elt in &self[range] {
if !f(elt) {
break;
}
end += 1;
}
unsafe {
(Range::from(range.start, end),
Range::from(end, range.end))
}
}
#[inline]
pub fn swap(&mut self, i: Index<'id>, j: Index<'id>)
where Array: GetUncheckedMut
{
unsafe {
let self_mut = self as *mut Self;
let pi: *mut _ = &mut (*self_mut)[i];
let pj: *mut _ = &mut (*self_mut)[j];
ptr::swap(pi, pj);
}
}
#[inline]
pub fn rotate1_up<R>(&mut self, r: R)
where Array: Contiguous + GetUncheckedMut,
R: IntoCheckedRange<'id>
{
if let Ok(r) = r.into() {
if r.first() != r.last() {
unsafe {
let last_ptr = &self[r.last()] as *const Array::Item;
let first_ptr = &mut self[r.first()] as *mut Array::Item;
let tmp = ptr::read(last_ptr);
ptr::copy(first_ptr,
first_ptr.offset(1),
r.len() - 1);
ptr::copy_nonoverlapping(&tmp, first_ptr, 1);
mem::forget(tmp);
}
}
}
}
#[inline]
pub fn rotate1_down<R>(&mut self, r: R)
where Array: Contiguous + GetUncheckedMut,
R: IntoCheckedRange<'id>
{
if let Ok(r) = r.into() {
if r.first() != r.last() {
unsafe {
let last_ptr = &mut self[r.last()] as *mut Array::Item;
let first_ptr = &mut self[r.first()] as *mut Array::Item;
let tmp = ptr::read(first_ptr);
ptr::copy(first_ptr.offset(1),
first_ptr,
r.len() - 1);
ptr::copy_nonoverlapping(&tmp, last_ptr, 1);
mem::forget(tmp);
}
}
}
}
#[inline]
pub fn index_twice<P, Q>(&mut self, r: Range<'id, P>, s: Range<'id, Q>)
-> Result<(&mut [T], &mut [T]), IndexingError>
where Array: ContiguousMut
{
if r.end <= s.start {
let self_mut = self as *mut Self;
unsafe {
Ok((&mut (*self_mut)[r], &mut (*self_mut)[s]))
}
} else {
Err(index_error())
}
}
pub fn zip_mut_raw<P, Q, F>(&mut self, r: Range<'id, P>, s: Range<'id, Q>, mut f: F)
where F: FnMut(*mut T, *mut T),
Array: GetUncheckedMut,
{
let len = cmp::min(r.len(), s.len());
for i in 0..len {
unsafe {
f(
self.arr.xget_unchecked_mut(r.start + i),
self.arr.xget_unchecked_mut(s.start + i)
)
}
}
}
}
impl<'id, Array, T> Container<'id, Array, OnlyIndex>
where Array: Pushable<Item=T>,
{
pub fn push(&mut self, element: T) -> Index<'id> {
let i = self.arr.push(element);
debug_assert!(i < self.arr.base_len());
unsafe {
Index::new(i)
}
}
pub fn insert<Q>(&mut self, index: Index<'id, Q>, element: T) {
debug_assert!(index.index <= self.arr.base_len());
unsafe {
self.arr.insert_unchecked(index.index, element);
}
}
}
impl<'id, Array, T, Mode> Container<'id, Array, Mode>
where Array: Trustworthy<Item=T> + FixedLength
{
pub fn make_twin<Array2>(&self, arr: Array2) -> Result<Container<'id, Array2, OnlyIndex>, IndexingError>
where Array2: Trustworthy + FixedLength
{
if self.len() != arr.base_len() {
Err(index_error())
} else {
Ok(Container { id: self.id, arr: arr, mode: PhantomData })
}
}
}
impl<'id, Array, M> ops::Index<Index<'id>> for Container<'id, Array, M>
where Array: GetUnchecked
{
type Output = Array::Item;
#[inline(always)]
fn index(&self, index: Index<'id>) -> &Self::Output {
unsafe {
self.arr.xget_unchecked(index.index)
}
}
}
impl<'id, Array, M> ops::IndexMut<Index<'id>> for Container<'id, Array, M>
where Array: GetUncheckedMut
{
#[inline(always)]
fn index_mut(&mut self, index: Index<'id>) -> &mut Self::Output {
unsafe {
self.arr.xget_unchecked_mut(index.index)
}
}
}
impl<'id, T, Array, P, M> ops::Index<Range<'id, P>> for Container<'id, Array, M>
where Array: Contiguous<Item=T>,
{
type Output = [T];
#[inline(always)]
fn index(&self, r: Range<'id, P>) -> &Self::Output {
unsafe {
std::slice::from_raw_parts(
self.arr.begin().offset(r.start as isize),
r.len())
}
}
}
impl<'id, Array, P, M> ops::IndexMut<Range<'id, P>> for Container<'id, Array, M>
where Array: ContiguousMut,
{
#[inline(always)]
fn index_mut(&mut self, r: Range<'id, P>) -> &mut Self::Output {
unsafe {
std::slice::from_raw_parts_mut(
self.arr.begin_mut().offset(r.start as isize),
r.len())
}
}
}
impl<'id, T, P, Array, M> ops::Index<ops::RangeFrom<Index<'id, P>>> for Container<'id, Array, M>
where Array: Contiguous<Item=T>,
{
type Output = [T];
#[inline(always)]
fn index(&self, r: ops::RangeFrom<Index<'id, P>>) -> &[T] {
let i = r.start.index;
unsafe {
std::slice::from_raw_parts(
self.arr.begin().offset(i as isize),
self.len() - i)
}
}
}
impl<'id, T, P, Array, M> ops::IndexMut<ops::RangeFrom<Index<'id, P>>> for Container<'id, Array, M>
where Array: ContiguousMut<Item=T>,
{
#[inline(always)]
fn index_mut(&mut self, r: ops::RangeFrom<Index<'id, P>>) -> &mut [T] {
let i = r.start.index;
unsafe {
std::slice::from_raw_parts_mut(
self.arr.begin_mut().offset(i as isize),
self.len() - i)
}
}
}
impl<'id, T, P, Array, M> ops::Index<ops::RangeTo<Index<'id, P>>> for Container<'id, Array, M>
where Array: Contiguous<Item=T>,
{
type Output = [T];
#[inline(always)]
fn index(&self, r: ops::RangeTo<Index<'id, P>>) -> &[T] {
let i = r.end.index;
unsafe {
std::slice::from_raw_parts(self.arr.begin(), i)
}
}
}
impl<'id, T, P, Array, M> ops::IndexMut<ops::RangeTo<Index<'id, P>>> for Container<'id, Array, M>
where Array: ContiguousMut<Item=T>,
{
#[inline(always)]
fn index_mut(&mut self, r: ops::RangeTo<Index<'id, P>>) -> &mut [T] {
let i = r.end.index;
unsafe {
std::slice::from_raw_parts_mut(self.arr.begin_mut(), i)
}
}
}
impl<'id, T, Array, M> ops::Index<ops::RangeFull> for Container<'id, Array, M>
where Array: Contiguous<Item=T>,
{
type Output = [T];
#[inline(always)]
fn index(&self, _: ops::RangeFull) -> &[T] {
self.arr.as_slice()
}
}
impl<'id, T, Array> ops::IndexMut<ops::RangeFull> for Container<'id, Array>
where Array: ContiguousMut<Item=T>,
{
#[inline(always)]
fn index_mut(&mut self, _: ops::RangeFull) -> &mut [T] {
self.arr.as_mut_slice()
}
}
pub fn scope<Array, F, Out>(arr: Array, f: F) -> Out
where F: for<'id> FnOnce(Container<'id, Array>) -> Out,
Array: Trustworthy,
{
f(Container { id: Id::default(), arr: arr, mode: PhantomData })
}
#[test]
fn test_intervals() {
let mut data = [0; 8];
scope(&mut data[..], |mut data| {
let r = data.range();
for (index, part) in r.subdivide(3).enumerate() {
for elt in &mut data[part] {
*elt = index;
}
}
});
assert_eq!(&data[..], &[0, 0, 1, 1, 1, 2, 2, 2]);
}
#[test]
fn intervals() {
let mut data = [0; 16];
scope(&mut data[..], |mut arr| {
let r = arr.range();
for elt in &mut arr[r] {
*elt += 1;
}
});
}
#[test]
fn test_scan() {
let mut data = [0, 0, 0, 1, 2];
scope(&mut data[..], |data| {
let r = data.range().nonempty().unwrap();
let range = data.scan_from(r.first(), |elt| *elt == 0);
assert_eq!(&data[range], &[0, 0, 0]);
let range = data.scan_from(range.last(), |elt| *elt != 0);
assert_eq!(&data[range], &[0, 1, 2]);
});
}
#[test]
fn test_nonempty() {
let mut data = [0, 1, 2, 3, 4, 5];
scope(&mut data[..], |data| {
let mut r = data.range().nonempty().unwrap();
assert_eq!(data[r.first()], 0);
assert_eq!(data[r.lower_middle()], 2);
assert_eq!(data[r.upper_middle()], 3);
assert_eq!(data[r.last()], 5);
assert!(r.advance());
assert_eq!(data[r.first()], 1);
assert_eq!(data[r.lower_middle()], 3);
assert_eq!(data[r.upper_middle()], 3);
assert_eq!(data[r.last()], 5);
assert!(r.advance());
assert_eq!(data[r.first()], 2);
assert_eq!(data[r.lower_middle()], 3);
assert_eq!(data[r.upper_middle()], 4);
assert_eq!(data[r.last()], 5);
while r.advance() { }
assert_eq!(data[r.first()], 5);
assert_eq!(data[r.lower_middle()], 5);
assert_eq!(data[r.upper_middle()], 5);
assert_eq!(data[r.last()], 5);
});
}
#[test]
fn test_contains() {
let mut data = [0, 1, 2, 3, 4, 5];
scope(&mut data[..], |data| {
let r = data.range();
for i in 0..data.len() {
assert!(r.contains(i).is_some());
assert_eq!(r.contains(i).unwrap(), data.vet(i).unwrap());
}
assert!(r.contains(r.len()).is_none());
assert!(data.vet(r.len()).is_err());
});
}
#[test]
fn test_is_send_sync() {
fn _is_send_sync<T: Send + Sync>() { }
fn _test<'id>() {
_is_send_sync::<Id<'id>>();
_is_send_sync::<Index<'id>>();
_is_send_sync::<Range<'id>>();
}
}