// Copyright 2018 Kyle Mayes
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! View extraction.

use core::cmp::{Ordering};
use core::marker::{PhantomData};

use super::{Extract, ExtractResult, Span, Stream};

/// A slice of bytes containing values that span a fixed number of bytes.
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct View<'a, T, P> where T: Extract<'a, P> + Span, P: Copy {
    bytes: &'a [u8],
    values: usize,
    parameter: P,
    _marker: PhantomData<*const T>,
}

impl<'a, T, P> View<'a, T, P> where T: Extract<'a, P> + Span, P: Copy {
    /// Returns the bytes in this slice.
    #[inline]
    pub fn bytes(&self) -> &'a [u8] {
        self.bytes
    }

    /// Returns the number of values in this slice.
    #[inline]
    pub fn len(&self) -> usize {
        self.values
    }

    /// Returns whether there are no values in this slice.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.values == 0
    }

    /// Returns the bytes for the value at the supplied index in this slice.
    #[inline]
    pub fn get(&self, index: usize) -> Option<&'a [u8]> {
        if index < self.values {
            let start = index * T::SPAN;
            let end = start + T::SPAN;
            Some(&self.bytes[start..end])
        } else {
            None
        }
    }

    /// Returns the value at the supplied index in this slice.
    #[inline]
    pub fn extract(&self, index: usize) -> Option<T> {
        self.get(index).map(|b| T::extract(&mut Stream(b), self.parameter).unwrap())
    }

    /// Returns an iterator over the values in this slice.
    #[inline]
    pub fn iter(self) -> ViewIter<'a, T, P> {
        let values = self.values;
        ViewIter { view: self, index: 0, values }
    }

    /// Binary searches the values in this slice for the supplied value.
    #[inline]
    pub fn binary_search(&self, value: &T) -> Option<usize> where T: Ord {
        self.binary_search_by(|v| v.cmp(value)).map(|(i, _)| i)
    }

    /// Binary searches the values in this slice using the supplied comparator function.
    #[inline]
    pub fn binary_search_by<F>(&self, mut f: F) -> Option<(usize, T)> where F: FnMut(&T) -> Ordering {
        if self.values == 0 {
            return None;
        }

        let mut low = 0isize;
        let mut high = self.values as isize - 1;

        while low <= high {
            let middle = low + ((high - low) / 2);
            let value = self.extract(middle as usize).unwrap();
            match f(&value) {
                Ordering::Equal => return Some((middle as usize, value)),
                Ordering::Less => low = middle + 1,
                Ordering::Greater => high = middle - 1,
            }
        }

        None
    }

    /// Binary searches the values in this slice using the supplied key extraction function.
    #[inline]
    pub fn binary_search_by_key<U, F>(&self, key: &U, mut f: F) -> Option<(usize, T)> where U: Ord, F: FnMut(&T) -> U {
        self.binary_search_by(|v| f(v).cmp(key))
    }

    /// Binary searches the value bytes in this slice for the supplied value.
    #[inline]
    pub fn binary_search_bytes(&self, bytes: &[u8]) -> Option<usize> {
        self.binary_search_bytes_by(|b| b.cmp(bytes)).map(|(i, _)| i)
    }

    /// Binary searches the value bytes in this slice using the supplied comparator function.
    #[inline]
    pub fn binary_search_bytes_by<F>(&self, mut f: F) -> Option<(usize, &'a [u8])> where
        F: FnMut(&'a [u8]) -> Ordering
    {
        if self.values == 0 {
            return None;
        }

        let mut low = 0isize;
        let mut high = self.values as isize - 1;

        while low <= high {
            let middle = low + ((high - low) / 2);
            let bytes = self.get(middle as usize).unwrap();
            match f(&bytes) {
                Ordering::Equal => return Some((middle as usize, bytes)),
                Ordering::Less => low = middle + 1,
                Ordering::Greater => high = middle - 1,
            }
        }

        None
    }

    /// Binary searches the value bytes in this slice using the supplied key extraction function.
    #[inline]
    pub fn binary_search_bytes_by_key<U, F>(&self, key: &U, mut f: F) -> Option<(usize, &'a [u8])> where
        U: Ord, F: FnMut(&'a [u8]) -> U
    {
        self.binary_search_bytes_by(|b| f(b).cmp(key))
    }
}

impl<'a, T, P> Extract<'a, (usize, P)> for View<'a, T, P> where T: Extract<'a, P> + Span, P: Copy {
    #[inline]
    fn extract(stream: &mut Stream<'a>, (values, parameter): (usize, P)) -> ExtractResult<'a, Self> {
        Ok(View { bytes: stream.extract(values * T::SPAN)?, values, parameter, _marker: PhantomData })
    }
}

/// An iterator over the values in a [`View`].
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct ViewIter<'a, T, P> where T: Extract<'a, P> + Span, P: Copy {
    view: View<'a, T, P>,
    index: usize,
    values: usize,
}

impl<'a, T, P> Iterator for ViewIter<'a, T, P> where T: Extract<'a, P> + Span, P: Copy {
    type Item = T;

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let size = self.values - self.index;
        (size, Some(size))
    }

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.values {
            let value = self.view.extract(self.index);
            self.index += 1;
            value
        } else {
            None
        }
    }
}

impl<'a, T, P> DoubleEndedIterator for ViewIter<'a, T, P> where T: Extract<'a, P> + Span, P: Copy {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.index < self.values {
            let value = self.view.extract(self.values - 1);
            self.values -= 1;
            value
        } else {
            None
        }
    }
}

impl<'a, T, P> ExactSizeIterator for ViewIter<'a, T, P> where T: Extract<'a, P> + Span, P: Copy { }

#[cfg(test)]
mod test {
    use super::*;
    use super::super::number::{Endianness};

    #[test]
    fn test_extract_view() {
        let mut stream = Stream(&[1, 2, 3, 4, 5, 6, 7, 8]);
        let view: View<u16, _> = stream.extract((4, Endianness::Little)).unwrap();
        assert_eq!(view.extract(0), Some(0x0201));
        assert_eq!(view.extract(1), Some(0x0403));
        assert_eq!(view.extract(2), Some(0x0605));
        assert_eq!(view.extract(3), Some(0x0807));
        assert_eq!(view.extract(4), None);

        let mut iterator = view.iter();
        assert_eq!(iterator.len(), 4);
        assert_eq!(iterator.next_back(), Some(0x0807));
        assert_eq!(iterator.len(), 3);
        assert_eq!(iterator.next(), Some(0x0201));
        assert_eq!(iterator.len(), 2);
        assert_eq!(iterator.next_back(), Some(0x0605));
        assert_eq!(iterator.len(), 1);
        assert_eq!(iterator.next(), Some(0x0403));
        assert_eq!(iterator.len(), 0);
        assert_eq!(iterator.next_back(), None);

        assert_eq!(view.binary_search(&0x0000), None);
        assert_eq!(view.binary_search(&0x0201), Some(0));
        assert_eq!(view.binary_search(&0x0403), Some(1));
        assert_eq!(view.binary_search(&0x0605), Some(2));
        assert_eq!(view.binary_search(&0x0807), Some(3));
        assert_eq!(view.binary_search(&0xFFFF), None);

        assert_eq!(view.binary_search_bytes(&[0, 0]), None);
        assert_eq!(view.binary_search_bytes(&[1, 2]), Some(0));
        assert_eq!(view.binary_search_bytes(&[3, 4]), Some(1));
        assert_eq!(view.binary_search_bytes(&[5, 6]), Some(2));
        assert_eq!(view.binary_search_bytes(&[7, 8]), Some(3));
        assert_eq!(view.binary_search_bytes(&[255, 255]), None);
    }
}