kirkos 0.1.0

//! A heap-allocated ring buffer targeted for sorted data using only core
//! features.
//!
//! The buffer can retrieve a contiguous slice on demand with no additional
//! copies. It supports slicing and insertion for comparable elements.
//! Insertion only discards older elements when necessary and moves the
//! minimum number of elements. Sorting is also available.

#![no_std]

extern crate alloc;

use alloc::{
    alloc::{alloc, handle_alloc_error, Layout},
    boxed::Box,
};
use core::{
    clone::Clone,
    cmp::{Ord, Ordering},
    fmt::Debug,
    iter::Iterator,
    mem::{transmute, MaybeUninit},
    ops::{FnMut, Range},
    ptr::copy,
    slice,
};

/// The ring buffer.
///
/// Immutable operations such as searching can be performed via `as_slice`.
/// Mutable operations are done on the object directly. Supported operations
/// include appending, prepending, inserting, sorting.
#[derive(Debug)]
pub struct Ring<T>
where
    T: Clone,
{
    /// By maintaining a duplicate of each added element, we can extract a
    /// contiguous slice at all times.
    buf: Box<[MaybeUninit<T>]>,
    /// Index of oldest element. Always [0,N).
    oldest: usize,
    /// Number of elements actually filled. Always <= N.
    fill: usize,
    /// Capacity of one half of the buffer.
    capacity: usize,
}

impl<T> Ring<T>
where
    T: Clone,
{
    /// Initialize a new empty buffer.
    pub fn new(n: usize) -> Self {
        Self {
            buf: Self::new_buf(n),
            oldest: 0,
            fill: 0,
            capacity: n,
        }
    }

    /// Number of elements in the buffer. Will never exceed capacity, but can
    /// be lower.
    pub fn len(&self) -> usize {
        self.fill
    }

    /// True if the ring contains zero elements.
    pub fn is_empty(&self) -> bool {
        self.fill == 0
    }

    /// True if capacity and length are equal.
    pub fn is_full(&self) -> bool {
        self.fill == self.capacity
    }

    /// Max number of elements the ring can hold before discarding old ones.
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// View the data in the buffer from oldest to newest as a contiguous
    /// slice.
    ///
    /// This operation is fast since it does not require copying data.
    pub fn as_slice(&self) -> &[T] {
        unsafe {
            transmute::<&[MaybeUninit<T>], &[T]>(&self.buf[self.oldest..self.oldest + self.fill])
        }
    }

    /// Append a value to the end of the buffer, discarding the oldest element
    /// if necessary.
    pub fn append(&mut self, value: T) {
        if self.capacity == 0 {
            return;
        }
        let newest = (self.oldest + self.fill) % self.capacity;
        if self.fill == self.capacity {
            unsafe {
                self.buf[self.oldest].assume_init_drop();
                self.buf[self.oldest + self.capacity].assume_init_drop();
            }
            self.oldest = (self.oldest + 1) % self.capacity;
        } else {
            self.fill += 1;
        }
        self.buf[newest].write(value.clone());
        self.buf[newest + self.capacity].write(value);
    }

    /// Prepend a value to the beginning of the buffer, discarding the newest
    /// element if necessary.
    ///
    /// To prepend without the possiblity of discarding the latest element,
    /// use `insert_at(0, value)` instead.
    pub fn prepend(&mut self, value: T) {
        if self.capacity == 0 {
            return;
        }
        self.oldest = (self.oldest + self.capacity - 1) % self.capacity;
        if self.fill == self.capacity {
            unsafe {
                self.buf[self.oldest].assume_init_drop();
                self.buf[self.oldest + self.capacity].assume_init_drop();
            }
        } else {
            self.fill += 1;
        }
        self.buf[self.oldest].write(value.clone());
        self.buf[self.oldest + self.capacity].write(value);
    }

    /// Sort elements in the buffer with a comparator.
    ///
    /// The position of the data within the ring will be maintained. Sorting
    /// is unstable and requires making a clone of the data.
    pub fn sort_by<F>(&mut self, compare: F)
    where
        F: FnMut(&T, &T) -> Ordering,
    {
        self.as_slice_mut().sort_unstable_by(compare);
        self.duplicate();
    }

    /// Sort elements in the buffer by key.
    ///
    /// The position of the data within the ring will be maintained. Sorting
    /// is unstable and requires making a clone of the data.
    pub fn sort_by_key<K, F>(&mut self, key: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
        self.as_slice_mut().sort_unstable_by_key(key);
        self.duplicate();
    }

    /// Insert an element at a specified index, moving the minimum number of
    /// elements.
    ///
    /// Indices are relative to the full slice: zero is oldest, `len() - 1` is
    /// newest. If the buffer is full, the oldest element will be dropped.
    /// Specifying `0` for `index` is equivalent to `prepend` except that the
    /// newest element will not be overwritten. Specifying `len()` for `index`
    /// is equivalent to `append`, and anything greater will panic.
    pub fn insert_at(&mut self, index: usize, value: T) {
        if index > self.fill {
            panic!("Invalid index {index} for buffer with size {}", self.fill);
        }
        // Drop prior or expand buffer
        if self.fill == self.capacity {
            if index == 0 {
                return;
            }
            unsafe {
                self.buf[self.oldest].assume_init_drop();
                self.buf[self.oldest + self.capacity].assume_init_drop();
            }
        }

        // Compute move indices for contiguous inner elements and outer swaps
        let src;     // Start index of contiguous segment. May be > capacity.
        let dst;     // Destination index of contiguous segment (src +/- 1).
        let n;       // Number of elements to move <= fill/2.
        let insert;  // One index to insert value into. May be > capacity.
        // Affected region is the moved elements. Its position relative to
        // capacity controls how the invariant around the edges is maintained.
        let lower;   // Lower bound of affected region, either src or dst
        let upper;   // Upper (exclusive) index of affected region

        if index > self.fill / 2 {
            // Advantageous to move elements forward
            src = self.oldest + index;
            dst = src + 1;
            n = self.fill - index;
            insert = src;
            if self.capacity == self.fill {
                self.oldest = (self.oldest + 1) % self.capacity;
            } else {
                self.fill += 1;
            }
            lower = src;
            upper = dst + n;
        } else {
            // Moving elements back. In case of tie, this option wins.
            // If buffer is full, one fewer elements needs to be moved.
            if self.capacity == self.fill {
                src = self.oldest + 1;
                n = index - 1;
            } else {
                // If self.oldest is zero, the contiguous segment starts at
                // self.capacity, not at zero.
                // src = (self.oldest + self.capacity - 1) % self.capacity + 1;
                src = if self.oldest == 0 {
                    self.capacity
                } else {
                    self.oldest
                };
                n = index;
                self.fill += 1;
                self.oldest = (self.oldest + self.capacity - 1) % self.capacity;
            }
            dst = src - 1;
            insert = dst + n;
            lower = dst;
            upper = src + n;
        }
        if n > 0 {
            // Move the contiguous segment
            unsafe { copy::<MaybeUninit<T>>(&self.buf[src], &mut self.buf[dst], n) };

            // Preserve buffer invariants by moving the duplicate portions as efficiently as possible
            if self.capacity <= lower {
                // Replciate end on left
                unsafe {
                    copy::<MaybeUninit<T>>(
                        &self.buf[src - self.capacity],
                        &mut self.buf[dst - self.capacity],
                        n,
                    )
                };
            } else if self.capacity >= upper {
                unsafe {
                    copy::<MaybeUninit<T>>(
                        &self.buf[src + self.capacity],
                        &mut self.buf[dst + self.capacity],
                        n,
                    )
                };
            } else {
                let suffix = upper - self.capacity - 1;
                let prefix = self.capacity - lower - 1;
                let end = self.buf.len() - 1;
                if dst > src {
                    unsafe {
                        // Replicate move of end on left first
                        copy::<MaybeUninit<T>>(&self.buf[0], &mut self.buf[1], suffix);
                        // Then swap last element to start
                        copy::<MaybeUninit<T>>(&self.buf[end], &mut self.buf[0], 1);
                        // Finally replicate move on right
                        copy::<MaybeUninit<T>>(
                            &self.buf[end - prefix],
                            &mut self.buf[end - prefix + 1],
                            prefix,
                        );
                    }
                } else {
                    unsafe {
                        // Finally replicate move on right
                        copy::<MaybeUninit<T>>(
                            &self.buf[end - prefix + 1],
                            &mut self.buf[end - prefix],
                            prefix,
                        );
                        // Then swap last element to start
                        copy::<MaybeUninit<T>>(&self.buf[0], &mut self.buf[end], 1);
                        // Replicate move of end on left first
                        copy::<MaybeUninit<T>>(&self.buf[1], &mut self.buf[0], suffix);
                    }
                }
            }
        }

        // Insert element to unoccupied space, clone vs original order is not guaranteed
        self.buf[insert].write(value.clone());
        self.buf[(insert + self.capacity) % self.buf.len()].write(value);
    }

    /// Insert an object into the buffer, assuming it it sorted by a
    /// comparator, dropping old elements unless there is room for them.
    pub fn insert_by<F>(&mut self, value: T, mut compare: F)
    where
        F: FnMut(&T, &T) -> Ordering,
    {
        let idx = self
            .as_slice()
            .partition_point(|x| compare(x, &value) == Ordering::Less);
        self.insert_at(idx, value);
    }

    /// Insert an object into the buffer, assuming it it sorted by key,
    /// dropping old elements unless there is room for them.
    pub fn insert_by_key<K, F>(&mut self, value: T, mut key: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
        let k = key(&value);
        let idx = self.as_slice().partition_point(|x| key(x) < k);
        self.insert_at(idx, value);
    }

    /// Allocate a new buffer.
    ///
    /// Useful for construction and cloning.
    fn new_buf(n: usize) -> Box<[MaybeUninit<T>]> {
        unsafe {
            // Technically only 2N-1 elements are required since oldest is [0, N-1],
            // but special-casing the element at index 2N-1 is likely not worth the savings
            let layout = Layout::array::<T>(2 * n).expect("Invalid memory layout requested");
            let ptr = alloc(layout);
            if ptr.is_null() {
                handle_alloc_error(layout);
            }
            Box::from_raw(slice::from_raw_parts_mut(
                ptr.cast::<MaybeUninit<T>>(),
                2 * n,
            ))
        }
    }

    /// Get a mutable slice of the entire buffer.
    ///
    /// Not available to the public since modifying the slice contents
    /// violates assumed invariants that allow it to exist in the first place.
    fn as_slice_mut(&mut self) -> &mut [T] {
        unsafe {
            transmute::<&mut [MaybeUninit<T>], &mut [T]>(
                &mut self.buf[self.oldest..self.oldest + self.fill],
            )
        }
    }

    /// Drop a range from the buffer, replacing elements with clones of the
    /// source data.
    ///
    /// Range values are [0, 2*N]. Destination elements *must* be initialized
    /// at start!
    #[inline]
    fn drop_and_replace_range(&mut self, src: Range<usize>, dst: Range<usize>) {
        for (s, d) in Iterator::zip(src, dst) {
            unsafe {
                // It might be faster to do these two operations separately
                self.buf[d].assume_init_drop();
                // TODO: this loop can be a memcopy if T: Copy.
                self.buf[d].write(self.buf[s].assume_init_ref().clone());
            }
        }
    }

    /// Duplicates the main slice properly after it's been modified, e.g. by
    /// sorting.
    #[inline]
    fn duplicate(&mut self) {
        if self.oldest + self.fill <= self.capacity {
            // Single contiguous block
            self.drop_and_replace_range(
                self.oldest..self.oldest + self.fill,
                self.oldest + self.capacity..self.oldest + self.fill + self.capacity,
            );
        } else {
            // Two disparate chunks
            self.drop_and_replace_range(
                self.oldest..self.capacity,
                self.oldest + self.capacity..2 * self.capacity,
            );
            let newest = (self.oldest + self.fill) % self.capacity;
            self.drop_and_replace_range(self.capacity..self.oldest + self.fill, 0..newest);
        }
    }
}

// Functions for objects that have inherent sort order
impl<T> Ring<T>
where
    T: Clone + Ord,
{
    /// Sort comparable elements in the buffer.
    ///
    /// The position of the data within the ring will be maintained. Sorting
    /// is unstable and requires making a clone of the data.
    pub fn sort(&mut self) {
        self.as_slice_mut().sort_unstable();
        self.duplicate();
    }

    /// Insert an object into the buffer, assuming it it sorted, dropping old
    /// elements unless there is room for them.
    pub fn insert(&mut self, value: T) {
        let idx = self.as_slice().partition_point(|x| x < &value);
        self.insert_at(idx, value);
    }
}

impl<T> Clone for Ring<T>
where
    T: Clone,
{
    /// Construct a copy of the buffer and underlying data.
    fn clone(&self) -> Self {
        let mut buf = Self::new_buf(self.capacity);
        // Only clone the initialized elements
        for idx in self.oldest..self.oldest + self.capacity {
            let idx = idx % self.capacity;
            unsafe {
                buf[idx].write(self.buf[idx].assume_init_ref().clone());
                buf[idx + self.capacity].write(self.buf[idx].assume_init_ref().clone());
            }
        }

        Self {
            buf,
            oldest: self.oldest,
            capacity: self.capacity,
            fill: self.fill,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::Ring;

    #[test]
    fn test_new() {
        let h = Ring::<u32>::new(3);
        assert_eq!(h.oldest, 0);
        assert_eq!(h.fill, 0);
        assert_eq!(h.capacity, 3);
        assert_eq!(h.buf.len(), 6);
    }

    #[test]
    fn test_clone() {
        let mut h = Ring::<i32>::new(3);
        h.append(1);
        h.prepend(2);
        let h2 = h.clone();
        assert_eq!(h2.oldest, 2);
        assert_eq!(h2.fill, 2);
        assert_eq!(h2.capacity, 3);
        assert_eq!(unsafe { h2.buf[0].assume_init_ref() }, &1);
        assert_eq!(unsafe { h2.buf[2].assume_init_ref() }, &2);
        assert_eq!(unsafe { h2.buf[3].assume_init_ref() }, &1);
        assert_eq!(unsafe { h2.buf[5].assume_init_ref() }, &2);
    }

    #[test]
    fn test_len() {
        let mut h = Ring::<i32>::new(3);
        assert_eq!(h.len(), 0);

        h.append(1);
        assert_eq!(h.len(), 1);

        h.prepend(2);
        assert_eq!(h.len(), 2);

        h.insert_at(0, 3);
        assert_eq!(h.len(), 3);

        h.insert(2);
        assert_eq!(h.len(), 3);
    }

    #[test]
    fn test_is_empty() {
        assert!(Ring::<i32>::new(0).is_empty());
        assert!(Ring::<[&str; 3]>::new(1).is_empty());
        assert!(Ring::<&[f64]>::new(3).is_empty());

        let mut h = Ring::<&[f64]>::new(3);
        h.append(&[0.0, 1.0]);
        assert!(!h.is_empty());
    }

    #[test]
    fn test_is_full() {
        assert!(Ring::<&[f64]>::new(0).is_full());

        let mut h = Ring::<[&str; 3]>::new(1);
        assert!(!h.is_full());
        h.append(["a", "b", "c"]);
        assert!(h.is_full());

        let mut h = Ring::<i32>::new(3);
        assert!(!h.is_full());
        h.append(0);
        assert!(!h.is_full());
        h.append(1);
        assert!(!h.is_full());
        h.append(2);
        assert!(h.is_full());
    }

    #[test]
    fn test_append() {
        let mut h = Ring::<u32>::new(3);
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), &[]);

        h.append(10);
        assert_eq!(h.len(), 1);
        assert_eq!(h.as_slice(), &[10]);

        h.append(20);
        assert_eq!(h.len(), 2);
        assert_eq!(h.as_slice(), &[10, 20]);

        h.append(30);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[10, 20, 30]);

        h.append(40);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[20, 30, 40]);
    }

    #[test]
    fn test_prepend() {
        let mut h = Ring::<u32>::new(3);
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), &[]);
        assert_eq!(h.oldest, 0);

        h.prepend(10);
        assert_eq!(h.len(), 1);
        assert_eq!(h.as_slice(), &[10]);
        assert_eq!(h.oldest, 2);

        h.prepend(20);
        assert_eq!(h.len(), 2);
        assert_eq!(h.as_slice(), &[20, 10]);
        assert_eq!(h.oldest, 1);

        h.prepend(30);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[30, 20, 10]);
        assert_eq!(h.oldest, 0);

        h.prepend(40);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[40, 30, 20]);
        assert_eq!(h.oldest, 2);
    }

    #[test]
    fn test_sort() {
        let mut h = Ring::<u32>::new(5);
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), &[]);

        h.sort();
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), &[]);
        assert_eq!(h.oldest, 0);

        h.append(20);
        h.append(10);
        h.append(30);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[20, 10, 30]);

        h.sort();
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[10, 20, 30]);
        assert_eq!(h.oldest, 0);

        h.prepend(40);
        h.append(0);
        assert_eq!(h.len(), 5);
        assert_eq!(h.as_slice(), &[40, 10, 20, 30, 0]);

        h.sort();
        assert_eq!(h.len(), 5);
        assert_eq!(h.as_slice(), &[0, 10, 20, 30, 40]);
        assert_eq!(h.oldest, 4);
    }

    #[test]
    fn test_sort_by() {
        let cmp = |a: &&str, b: &&str| a.len().cmp(&b.len());
        let empty: &[&str] = &[];

        let mut h = Ring::<&str>::new(5);
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), empty);

        h.sort_by(cmp);
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), empty);
        assert_eq!(h.oldest, 0);

        h.append("abc");
        h.append("d");
        h.append("ef");
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["abc", "d", "ef"]);

        h.sort_by(cmp);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["d", "ef", "abc"]);
        assert_eq!(h.oldest, 0);

        h.prepend("aaaa");
        h.append("");
        assert_eq!(h.len(), 5);
        assert_eq!(h.as_slice(), &["aaaa", "d", "ef", "abc", ""]);

        h.sort_by(cmp);
        assert_eq!(h.len(), 5);
        assert_eq!(h.as_slice(), &["", "d", "ef", "abc", "aaaa"]);
        assert_eq!(h.oldest, 4);
    }

    #[test]
    fn test_sort_by_key() {
        let key = |a: &&str| a.len();
        let empty: &[&str] = &[];

        let mut h = Ring::<&str>::new(5);
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), empty);

        h.sort_by_key(key);
        assert_eq!(h.len(), 0);
        assert_eq!(h.as_slice(), empty);
        assert_eq!(h.oldest, 0);

        h.append("abc");
        h.append("d");
        h.append("ef");
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["abc", "d", "ef"]);

        h.sort_by_key(key);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["d", "ef", "abc"]);
        assert_eq!(h.oldest, 0);

        h.prepend("aaaa");
        h.append("");
        assert_eq!(h.len(), 5);
        assert_eq!(h.as_slice(), &["aaaa", "d", "ef", "abc", ""]);

        h.sort_by_key(key);
        assert_eq!(h.len(), 5);
        assert_eq!(h.as_slice(), &["", "d", "ef", "abc", "aaaa"]);
        assert_eq!(h.oldest, 4);
    }

    #[test]
    fn test_insert() {
        let mut h = Ring::<i32>::new(3);

        h.insert(2);
        assert_eq!(h.len(), 1);
        assert_eq!(h.as_slice(), &[2]);
        assert_eq!(h.oldest, 2);

        h.insert(4);
        assert_eq!(h.len(), 2);
        assert_eq!(h.as_slice(), &[2, 4]);
        assert_eq!(h.oldest, 2);

        h.insert(1);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[1, 2, 4]);
        assert_eq!(h.oldest, 1);

        h.insert(0);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[1, 2, 4]);
        assert_eq!(h.oldest, 1);

        h.insert(5);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[2, 4, 5]);
        assert_eq!(h.oldest, 2);

        h.insert(3);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &[3, 4, 5]);
        assert_eq!(h.oldest, 2);
    }

    #[test]
    fn test_insert_by() {
        let mut h = Ring::<&str>::new(3);
        let cmp = |a: &&str, b: &&str| a.len().cmp(&b.len());

        h.insert_by("wx", cmp);
        assert_eq!(h.len(), 1);
        assert_eq!(h.as_slice(), &["wx"]);
        assert_eq!(h.oldest, 2);

        h.insert_by("snarf", cmp);
        assert_eq!(h.len(), 2);
        assert_eq!(h.as_slice(), &["wx", "snarf"]);
        assert_eq!(h.oldest, 2);

        h.insert_by("z", cmp);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["z", "wx", "snarf"]);
        assert_eq!(h.oldest, 1);

        h.insert_by("", cmp);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["z", "wx", "snarf"]);
        assert_eq!(h.oldest, 1);

        h.insert_by("foobar", cmp);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["wx", "snarf", "foobar"]);
        assert_eq!(h.oldest, 2);

        h.insert_by("abc", cmp);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["abc", "snarf", "foobar"]);
        assert_eq!(h.oldest, 2);
    }

    #[test]
    fn test_insert_by_key() {
        let mut h = Ring::<&str>::new(3);
        let key = |a: &&str| a.len();

        h.insert_by_key("wx", key);
        assert_eq!(h.len(), 1);
        assert_eq!(h.as_slice(), &["wx"]);
        assert_eq!(h.oldest, 2);

        h.insert_by_key("snarf", key);
        assert_eq!(h.len(), 2);
        assert_eq!(h.as_slice(), &["wx", "snarf"]);
        assert_eq!(h.oldest, 2);

        h.insert_by_key("z", key);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["z", "wx", "snarf"]);
        assert_eq!(h.oldest, 1);

        h.insert_by_key("", key);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["z", "wx", "snarf"]);
        assert_eq!(h.oldest, 1);

        h.insert_by_key("foobar", key);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["wx", "snarf", "foobar"]);
        assert_eq!(h.oldest, 2);

        h.insert_by_key("abc", key);
        assert_eq!(h.len(), 3);
        assert_eq!(h.as_slice(), &["abc", "snarf", "foobar"]);
        assert_eq!(h.oldest, 2);
    }

    #[test]
    fn test_insert_at_start() {
        let mut h = Ring::<i32>::new(3);
        h.insert_at(0, 1);
        assert_eq!(h.as_slice(), &[1]);
        assert_eq!(h.oldest, 2);
        // Move forward breaks tie
        h.insert_at(0, 2);
        assert_eq!(h.as_slice(), &[2, 1]);
        assert_eq!(h.oldest, 1);
        h.insert_at(0, 3);
        assert_eq!(h.as_slice(), &[3, 2, 1]);
        assert_eq!(h.oldest, 0);

        // Doesn't overwrite when full
        h.insert_at(0, 4);
        assert_eq!(h.as_slice(), &[3, 2, 1]);
        assert_eq!(h.oldest, 0);
    }

    #[test]
    fn test_insert_at_end() {
        let mut h = Ring::<i32>::new(3);
        h.insert_at(0, 1);
        assert_eq!(h.as_slice(), &[1]);
        assert_eq!(h.oldest, 2);
        h.insert_at(1, 2);
        assert_eq!(h.as_slice(), &[1, 2]);
        assert_eq!(h.oldest, 2);
        h.insert_at(2, 3);
        assert_eq!(h.as_slice(), &[1, 2, 3]);
        assert_eq!(h.oldest, 2);

        // Does overwrite when full
        h.insert_at(3, 4);
        assert_eq!(h.as_slice(), &[2, 3, 4]);
        assert_eq!(h.oldest, 0);
    }

    #[test]
    fn test_insert_at_edge() {
        let mut h = Ring::new(7);
        h.append(5);
        h.prepend(3);
        h.prepend(2);
        h.prepend(1);
        assert_eq!(h.oldest, 4);
        assert_eq!(h.fill, 4);
        assert_eq!(h.as_slice(), &[1, 2, 3, 5]);

        h.insert_at(3, 4);
        assert_eq!(h.oldest, 4);
        assert_eq!(h.fill, 5);
        assert_eq!(h.as_slice(), &[1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_insert_not_full() {
        let mut h = Ring::<i32>::new(7);
        h.append(2);
        h.append(3);
        h.prepend(1);
        h.prepend(0);
        assert_eq!(h.oldest, 5);
        assert_eq!(h.fill, 4);
        assert_eq!(h.as_slice(), &[0, 1, 2, 3]);

        // Zero, move start back
        let mut h2 = h.clone();
        h2.insert_at(0, -1);
        assert_eq!(h2.oldest, 4);
        assert_eq!(h2.fill, 5);
        assert_eq!(h2.as_slice(), &[-1, 0, 1, 2, 3]);

        // 1, move start back
        let mut h2 = h.clone();
        h2.insert_at(1, -1);
        assert_eq!(h2.oldest, 4);
        assert_eq!(h2.fill, 5);
        assert_eq!(h2.as_slice(), &[0, -1, 1, 2, 3]);

        // 2, break tie, move back
        let mut h2 = h.clone();
        h2.insert_at(2, -1);
        assert_eq!(h2.oldest, 4);
        assert_eq!(h2.fill, 5);
        assert_eq!(h2.as_slice(), &[0, 1, -1, 2, 3]);

        // 3, move forward
        let mut h2 = h.clone();
        h2.insert_at(3, -1);
        assert_eq!(h2.oldest, 5);
        assert_eq!(h2.fill, 5);
        assert_eq!(h2.as_slice(), &[0, 1, 2, -1, 3]);

        // 4, append
        let mut h2 = h.clone();
        h2.insert_at(4, -1);
        assert_eq!(h2.oldest, 5);
        assert_eq!(h2.fill, 5);
        assert_eq!(h2.as_slice(), &[0, 1, 2, 3, -1]);
    }

    #[test]
    fn test_insert_at_full() {
        let mut h = Ring::new(4);
        h.append(2);
        h.append(4);
        h.append(6);
        h.append(8);
        assert_eq!(h.oldest, 0);
        assert_eq!(h.fill, 4);
        assert_eq!(h.as_slice(), &[2, 4, 6, 8]);

        // 0, skip
        h.insert_at(0, 1);
        assert_eq!(h.oldest, 0);
        assert_eq!(h.fill, 4);
        assert_eq!(h.as_slice(), &[2, 4, 6, 8]);

        // 1, move back
        h.insert_at(1, 3);
        assert_eq!(h.oldest, 0);
        assert_eq!(h.fill, 4);
        assert_eq!(h.as_slice(), &[3, 4, 6, 8]);

        // 2, move back
        h.insert_at(2, 5);
        assert_eq!(h.oldest, 0);
        assert_eq!(h.fill, 4);
        assert_eq!(h.as_slice(), &[4, 5, 6, 8]);
    }

    /// Ensure that nothing breaks when operating with an empty ring.
    #[test]
    fn empty() {
        let mut h = Ring::<&str>::new(0);

        assert_eq!(h.fill, 0);
        assert_eq!(h.capacity, 0);
        assert_eq!(h.oldest, 0);
        assert_eq!(h.buf.len(), 0);

        assert!(h.is_empty());
        assert!(h.is_full());

        assert_eq!(h.len(), 0);
        assert_eq!(h.capacity(), 0);
        assert_eq!(h.as_slice(), &[] as &[&str]);

        h.append("a");
        assert!(h.is_empty());
        h.prepend("a");
        assert!(h.is_empty());

        h.insert("a");
        assert!(h.is_empty());
        h.insert_at(0, "a");
        assert!(h.is_empty());
        h.insert_by("a", |a, b| a.len().cmp(&b.len()));
        assert!(h.is_empty());
        h.insert_by_key("a", |a| a.len());
        assert!(h.is_empty());

        h.sort();
        assert!(h.is_empty());
        h.sort_by(|a, b| a.len().cmp(&b.len()));
        assert!(h.is_empty());
        h.sort_by_key(|a| a.len());
        assert!(h.is_empty());
    }
}