tarrasque 0.10.0

// 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<'s, T, P> where T: Extract<'s, P> + Span, P: Copy {
    bytes: &'s [u8],
    values: usize,
    parameter: P,
    _marker: PhantomData<*const T>,
}

impl<'s, T, P> View<'s, T, P> where T: Extract<'s, P> + Span, P: Copy {
    /// Returns the bytes in this slice.
    #[inline]
    pub fn bytes(&self) -> &'s [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<&'s [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> {
        Some(Stream(self.get(index)?).extract(self.parameter).unwrap())
    }

    /// Returns the value at the supplied index in this slice.
    #[inline]
    pub fn try_extract(&self, index: usize) -> Option<ExtractResult<'s, T>> {
        Some(Stream(self.get(index)?).extract(self.parameter))
    }

    /// Returns an iterator over the values in this slice.
    #[inline]
    pub fn iter(self) -> ViewIter<'s, 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, &'s [u8])> where
        F: FnMut(&'s [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, &'s [u8])> where
        U: Ord, F: FnMut(&'s [u8]) -> U
    {
        self.binary_search_bytes_by(|b| f(b).cmp(key))
    }
}

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

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

impl<'s, T, P> Iterator for ViewIter<'s, T, P> where
    T: Extract<'s, 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<'s, T, P> DoubleEndedIterator for ViewIter<'s, T, P> where
    T: Extract<'s, 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<'s, T, P> ExactSizeIterator for ViewIter<'s, T, P> where
    T: Extract<'s, P> + Span,
    P: Copy { }

#[cfg(test)]
mod test {
    use super::*;
    use super::super::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, 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);
    }
}