use std::cmp::{self, Ordering};
use std::hash::{Hash, Hasher};
use std::fmt::{self, Debug};
use crate::index_error::IndexingError;
use crate::index_error::index_error;
use std;
use crate::proof::*;
use crate::{Id, Index, Range};
impl<'id, P> Index<'id, P> {
#[inline]
pub fn integer(&self) -> usize { self.index }
}
impl<'id> Index<'id, NonEmpty> {
pub fn after(self) -> Index<'id, Unknown> {
unsafe {
Index::new(self.index + 1)
}
}
}
impl<'id, P> Debug for Index<'id, P> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Index({})", self.index)
}
}
impl<'id, P, Q> PartialEq<Index<'id, Q>> for Index<'id, P> {
#[inline(always)]
fn eq(&self, rhs: &Index<'id, Q>) -> bool {
self.index == rhs.index
}
}
impl<'id, P> Eq for Index<'id, P> { }
impl<'id, P, Q> PartialOrd<Index<'id, Q>> for Index<'id, P> {
fn partial_cmp(&self, rhs: &Index<'id, Q>) -> Option<Ordering> {
Some(self.index.cmp(&rhs.index))
}
fn lt(&self, rhs: &Index<'id, Q>) -> bool {
self.index < rhs.index
}
}
impl<'id, P> Ord for Index<'id, P> {
fn cmp(&self, rhs: &Self) -> Ordering {
self.index.cmp(&rhs.index)
}
}
impl<'id, P> Hash for Index<'id, P> {
fn hash<H: Hasher>(&self, h: &mut H) {
self.index.hash(h)
}
}
impl<'id, P, Q> PartialEq<Range<'id, Q>> for Range<'id, P> {
fn eq(&self, other: &Range<'id, Q>) -> bool {
self.start == other.start && self.end == other.end
}
}
impl<'id, P> Eq for Range<'id, P> { }
impl<'id, P> Hash for Range<'id, P> {
fn hash<H: Hasher>(&self, h: &mut H) {
self.order_key().hash(h);
}
}
impl<'id, P> Range<'id, P> {
pub(crate) fn order_key(self) -> (usize, usize) { (self.start, self.end) }
}
impl<'id, P, Q> PartialOrd<Range<'id, Q>> for Range<'id, P> {
fn partial_cmp(&self, rhs: &Range<'id, Q>) -> Option<Ordering> {
Some(Ord::cmp(&self.order_key(), &rhs.order_key()))
}
fn lt(&self, rhs: &Range<'id, Q>) -> bool {
PartialOrd::lt(&self.order_key(), &rhs.order_key())
}
}
impl<'id, P> Ord for Range<'id, P> {
fn cmp(&self, rhs: &Self) -> Ordering {
Ord::cmp(&self.order_key(), &rhs.order_key())
}
}
impl<'id, P> Range<'id, P> {
#[inline]
pub fn len(&self) -> usize { self.end - self.start }
#[inline]
pub fn is_empty(&self) -> bool { self.start >= self.end }
#[inline]
pub fn nonempty(&self) -> Result<Range<'id, NonEmpty>, IndexingError> {
unsafe {
if !self.is_empty() {
Ok(Range::assume_nonempty_range(*self))
} else {
Err(index_error())
}
}
}
#[inline]
pub fn start(&self) -> usize { self.start }
#[inline]
pub fn end(&self) -> usize { self.end }
#[inline]
pub fn split_in_half(self) -> (Range<'id>, Range<'id, P>) {
let mid = (self.end - self.start) / 2 + self.start;
unsafe {
(Range::from(self.start, mid), Range::from_any(mid, self.end))
}
}
#[inline]
pub fn split_at(&self, index: usize) -> (Range<'id>, Range<'id>, bool) {
let mid = if index > self.len() {
self.end
} else { self.start + index };
unsafe {
(Range::from(self.start, mid), Range::from(mid, self.end),
index <= self.len())
}
}
#[inline]
pub fn contains(&self, abs_index: usize) -> Option<Index<'id>> {
unsafe {
if abs_index >= self.start && abs_index < self.end {
Some(Index::new(abs_index))
} else { None }
}
}
#[inline]
pub fn subdivide(&self, n: usize) -> Subdivide<'id> {
unsafe {
Subdivide {
fs: FracStep::new(self.start, self.end, n),
range: Range::from(self.start, self.end),
}
}
}
pub fn join<Q>(&self, other: Range<'id, Q>) -> Result<Range<'id, <(P, Q) as ProofAdd>::Sum>, IndexingError>
where (P, Q): ProofAdd
{
if self.end == other.start {
unsafe {
Ok(Range::from_any(self.start, other.end))
}
} else {
Err(index_error())
}
}
pub fn join_cover<Q>(&self, other: Range<'id, Q>) -> Range<'id, P>
where (P, Q): ProofAdd,
{
let end = cmp::max(self.end, other.end);
unsafe {
Range::from_any(self.start, end)
}
}
pub fn join_cover_both<Q>(&self, other: Range<'id, Q>) -> Range<'id, <(P, Q) as ProofAdd>::Sum>
where (P, Q): ProofAdd,
{
let start = cmp::min(self.start, other.start);
let end = cmp::max(self.end, other.end);
unsafe {
Range::from_any(start, end)
}
}
#[inline]
pub fn as_range(&self) -> std::ops::Range<usize> { self.start..self.end }
#[inline]
pub fn frontiers(&self) -> (Range<'id>, Range<'id>) {
let s = self.start;
let e = self.end;
unsafe {
(Range::from(s, s), Range::from(e, e))
}
}
#[inline]
pub fn forward_by(&self, index: &mut Index<'id>, offset: usize) -> bool {
let i = index.index + offset;
if i < self.end {
index.index = i;
true
} else { false }
}
#[inline]
pub fn forward_range_by<Q>(&self, r: Range<'id, Q>, offset: usize) -> Range<'id> {
let max = self.end;
let start = cmp::min(r.start.saturating_add(offset), max);
let end = cmp::min(r.end.saturating_add(offset), max);
unsafe {
Range::from(start, end)
}
}
#[inline]
pub fn no_proof(&self) -> Range<'id> {
unsafe {
Range::assume_any_range(*self)
}
}
}
impl<'id, P> Debug for Range<'id, P> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Range({}, {})", self.start, self.end)
}
}
pub trait IntoCheckedRange<'id> : Sized {
fn into(self) -> Result<Range<'id, NonEmpty>, IndexingError>;
}
impl<'id> IntoCheckedRange<'id> for Range<'id> {
#[inline]
fn into(self) -> Result<Range<'id, NonEmpty>, IndexingError> {
self.nonempty()
}
}
impl<'id> IntoCheckedRange<'id> for Range<'id, NonEmpty> {
#[inline]
fn into(self) -> Result<Range<'id, NonEmpty>, IndexingError> {
Ok(self)
}
}
impl<'id, P> Range<'id, P> {
#[inline(always)]
pub fn first(&self) -> Index<'id, P> {
unsafe {
Index::new(self.start)
}
}
#[inline]
pub fn upper_middle(&self) -> Index<'id, P> {
let mid = self.len() / 2 + self.start;
unsafe {
Index::new(mid)
}
}
#[inline]
pub fn past_the_end(self) -> Index<'id, Unknown> {
unsafe {
Index::new(self.end)
}
}
}
impl<'id> Range<'id, NonEmpty> {
#[inline]
pub fn lower_middle(&self) -> Index<'id> {
let mid = (self.len() - 1) / 2 + self.start;
unsafe {
Index::new(mid)
}
}
#[inline]
pub fn last(&self) -> Index<'id> {
unsafe {
Index::new(self.end - 1)
}
}
#[inline]
pub fn tail(self) -> Range<'id> {
unsafe {
Range::from(self.start + 1, self.end)
}
}
#[inline]
pub fn init(&self) -> Range<'id> {
unsafe {
Range::from(self.start, self.end - 1)
}
}
#[inline]
pub fn advance_(&self) -> Result<Range<'id, NonEmpty>, IndexingError>
{
let mut next = *self;
next.start += 1;
if next.start < next.end {
Ok(next)
} else {
Err(index_error())
}
}
#[inline]
pub fn advance(&mut self) -> bool
{
let mut next = *self;
next.start += 1;
if next.start < next.end {
*self = next;
true
} else {
false
}
}
#[inline]
pub fn advance_by(&mut self, offset: usize) -> bool
{
let mut next = *self;
next.start = next.start.saturating_add(offset);
if next.start < next.end {
*self = next;
true
} else {
false
}
}
#[inline]
pub fn advance_back(&mut self) -> bool
{
let mut next = *self;
next.end -= 1;
if next.start < next.end {
*self = next;
true
} else {
false
}
}
}
impl<'id, P> IntoIterator for Range<'id, P> {
type Item = Index<'id>;
type IntoIter = RangeIter<'id>;
#[inline]
fn into_iter(self) -> RangeIter<'id> {
RangeIter {
id: self.id,
start: self.start,
end: self.end,
}
}
}
#[derive(Copy, Clone, Debug)]
pub struct RangeIter<'id> {
id: Id<'id>,
start: usize,
end: usize,
}
impl<'id> RangeIter<'id> {
#[inline]
pub fn into_range(&self) -> Range<'id> {
unsafe {
Range::from(self.start, self.end)
}
}
}
impl<'id> Iterator for RangeIter<'id> {
type Item = Index<'id>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if self.start < self.end {
let index = self.start;
self.start += 1;
unsafe {
Some(Index::new(index))
}
} else {
None
}
}
}
impl<'id> DoubleEndedIterator for RangeIter<'id> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
if self.start < self.end {
self.end -= 1;
unsafe {
Some(Index::new(self.end))
}
} else {
None
}
}
}
#[derive(Copy, Clone, Debug, PartialOrd, PartialEq)]
struct Frac(usize, usize, usize);
impl Frac {
#[inline]
fn next_interval(&mut self, dec: usize, frac: usize) -> (usize, usize) {
let start = self.0;
self.0 += dec;
self.1 += frac;
if self.1 >= self.2 {
self.1 -= self.2;
self.0 += 1;
}
(start, self.0)
}
}
#[derive(Copy, Clone, Debug, PartialOrd, PartialEq)]
struct FracStep {
f: Frac,
frac_step: usize,
decimal_step: usize,
start: usize,
end: usize,
}
impl FracStep {
#[inline]
fn new(start: usize, mut end: usize, divisor: usize) -> Self {
debug_assert!(start <= end);
let len = end - start;
let decimal_step = len / divisor;
let frac_step = len % divisor;
if decimal_step == 0 {
end = start;
}
FracStep {
f: Frac(start, 0, divisor),
frac_step: frac_step,
decimal_step: decimal_step,
start: start,
end: end,
}
}
#[inline]
fn next(&mut self) -> Option<(usize, usize)> {
if self.f.0 >= self.end {
None
} else {
let (ds, fs) = (self.decimal_step, self.frac_step);
Some(self.f.next_interval(ds, fs))
}
}
}
#[derive(Copy, Clone, Debug)]
pub struct Subdivide<'id> {
range: Range<'id>,
fs: FracStep,
}
impl<'id> Iterator for Subdivide<'id> {
type Item = Range<'id, NonEmpty>;
#[inline]
fn next(&mut self) -> Option<Range<'id, NonEmpty>> {
self.fs.next().map(|(i, j)| {
debug_assert!(self.range.contains(i).is_some());
debug_assert!(self.range.contains(j).is_some() || j == self.range.end);
debug_assert!(i != j);
unsafe {
Range::from_ne(i, j)
}
})
}
}
#[test]
fn test_frac_step() {
let mut f = FracStep::new(0, 8, 3);
assert_eq!(f.next(), Some((0, 2)));
assert_eq!(f.next(), Some((2, 5)));
assert_eq!(f.next(), Some((5, 8)));
assert_eq!(f.next(), None);
let mut f = FracStep::new(1, 9, 3);
assert_eq!(f.next(), Some((1, 3)));
assert_eq!(f.next(), Some((3, 6)));
assert_eq!(f.next(), Some((6, 9)));
assert_eq!(f.next(), None);
let mut f = FracStep::new(0, 7, 8);
assert_eq!(f.next(), None);
assert_eq!(f.next(), None);
let mut f = FracStep::new(0, 3, 1);
assert_eq!(f.next(), Some((0, 3)));
assert_eq!(f.next(), None);
}
#[test]
fn test_join_cover() {
use crate::scope;
let array = [0, 1, 2, 3, 4, 5];
scope(&array[..], |arr| {
let left = arr.vet_range(0..2).unwrap();
let left = left.nonempty().unwrap();
let (_, right) = arr.range().frontiers();
let joined = right.join_cover(left);
let ix = joined.first();
assert!(!ix.nonempty_proof());
ix.integer()
});
}