logvec 1.1.1

//! `logvec` provides [`LogVec`], a cache-friendly Bentley-Saxe logarithmic array.
//!
//! It stores all elements in one contiguous `Vec<T>` and maintains sorted runs whose
//! sizes follow the binary decomposition of `len()`.
//!
//! # Complexity
//! - `insert`: amortized `O(log n)`
//! - `contains`: `O(log^2 n)` (binary search across sorted runs)
//! - `delete`: `O(n)` worst-case (removal + re-sort)
//!
//! # Example
//! ```rust
//! use logvec::LogVec;
//!
//! let mut arr = LogVec::new();
//! arr.insert(5);
//! arr.insert(3);
//! arr.insert(8);
//!
//! assert!(arr.contains(&5));
//! assert!(!arr.contains(&42));
//! assert_eq!(arr.delete(&3), Some(3));
//! assert!(!arr.contains(&3));
//! ```

/// A Bentley-Saxe logarithmic array backed by a contiguous `Vec<T>`.
#[derive(Debug)]
pub struct LogVec<T> {
    /// Arrays stored sequentially in increasing size 2^i, 2^i-1, ..., 4, 2, 1
    items: Vec<T>,
}

impl<T> LogVec<T> {
    /// Creates an empty [`LogVec`].
    pub fn new() -> Self {
        Self { items: Vec::new() }
    }

    /// Returns the number of elements in the collection.
    pub fn len(&self) -> usize {
        self.items.len()
    }

    /// Returns `true` if the collection contains no elements.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<T> Default for LogVec<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Ord> LogVec<T> {
    /// Inserts a value into the structure.
    ///
    /// The insertion is amortized `O(log n)`.
    pub fn insert(&mut self, value: T) {
        self.items.push(value);

        let z = self.items.len().trailing_zeros();
        let merge_size = 1_usize << z;
        if merge_size > 1 {
            let start = self.items.len() - merge_size;
            let merged = &mut self.items[start..];
            if merge_size <= 8 {
                // Tiny runs happen frequently; use a minimal insertion sort path.
                Self::sort_small_unchecked(merged);
            } else {
                merged.sort_unstable();
            }
        }
    }

    fn sort_small_unchecked(slice: &mut [T]) {
        debug_assert!(slice.len() <= 8);

        for i in 1..slice.len() {
            for j in (1..=i).rev() {
                // SAFETY:
                // - Indices `j - 1` and `j` are in-bounds from the check above.
                // - They are distinct because `j > 0`.
                let [left, right] = unsafe { slice.get_disjoint_unchecked_mut([j - 1, j]) };

                if left <= right {
                    break;
                }

                std::mem::swap(left, right);
            }
        }
    }

    /// Returns `true` if the query exists in the structure.
    ///
    /// This performs binary searches over internal sorted runs.
    pub fn contains(&self, query: &T) -> bool {
        let len = self.items.len();
        if len == 0 {
            return false;
        }

        // Start from the highest power of 2 present in the length
        let mut size = 1 << len.ilog2();

        while size > 0 {
            if len & size != 0 {
                let end = len & !(size - 1);
                let start = end - size;
                let block = &self.items[start..end];

                // SAFETY:
                // - `block` is non-empty because `size > 0` and this arm requires
                //   the corresponding bit to be set in `len`.
                // - So indices `0` and `block.len() - 1` are always in-bounds.
                let (first, last) =
                    unsafe { (block.get_unchecked(0), block.get_unchecked(block.len() - 1)) };

                // Reject blocks whose sorted bounds cannot contain the query.
                if query >= first && query <= last && block.binary_search(query).is_ok() {
                    return true;
                }
            }

            size >>= 1; // Bitshift downwards
        }

        false
    }

    /// Deletes one matching element and returns it.
    ///
    /// Returns `None` if the element was not found.
    pub fn delete(&mut self, query: &T) -> Option<T> {
        let mut size = 1;

        while size <= self.items.len() {
            if self.items.len() & size != 0 {
                let end = self.items.len() & !(size - 1);
                let start = end - size;

                if let Ok(local_idx) = self.items[start..end].binary_search(query) {
                    let absolute_idx = start + local_idx;

                    // 1. Remove the element O(n)
                    let item = self.items.remove(absolute_idx);

                    // 2. The binary representation of the length has changed.
                    // By fully sorting the array, we guarantee that whatever new
                    // block sizes the binary representation demands, they will
                    // inherently be sorted.
                    // Because the array is mostly sorted runs, this is very fast.
                    self.items.sort_unstable();

                    return Some(item);
                }
            }

            size <<= 1;
        }

        None
    }
}

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

    #[test]
    fn test_insert_and_contains() {
        let mut arr = LogVec::new();
        assert!(!arr.contains(&5));

        arr.insert(5);
        assert!(arr.contains(&5));
        assert!(!arr.contains(&3));

        arr.insert(3);
        arr.insert(8);
        arr.insert(1);
        arr.insert(10);

        // Binary length is 5 (101): one block of 4, one block of 1.
        for &val in &[1, 3, 5, 8, 10] {
            assert!(arr.contains(&val), "Should contain {}", val);
        }
        assert!(!arr.contains(&2));
    }

    #[test]
    fn test_deletion() {
        let mut arr = LogVec::new();
        for i in 0..10 {
            arr.insert(i); // Insert 0 through 9
        }

        assert!(arr.contains(&5));

        // Delete a middle element
        assert!(arr.delete(&5).is_some());
        assert!(!arr.contains(&5));

        // Ensure everything else survived the block reshuffling
        for i in 0..10 {
            if i != 5 {
                assert!(arr.contains(&i), "Should still contain {}", i);
            }
        }

        // Deleting a non-existent element
        assert!(arr.delete(&99).is_none());
    }

    #[test]
    fn test_large_fuzz() {
        // Stress test to ensure block boundaries never panic
        let mut arr = LogVec::new();
        for i in 0..1000 {
            arr.insert(i);
        }
        for i in 0..1000 {
            assert!(arr.contains(&i));
        }
        for i in (0..1000).step_by(2) {
            arr.delete(&i); // Delete even numbers
        }
        for i in 0..1000 {
            assert_eq!(arr.contains(&i), i % 2 != 0);
        }
    }

    #[test]
    fn test_small_sort_path_insert() {
        // Exercises many tiny merge sizes (2,4,8) reached during insertion.
        let mut arr = LogVec::new();
        let mut seed = 0x1234_5678_9ABC_DEF0u64;
        for _ in 0..1024 {
            seed = seed
                .wrapping_mul(6364136223846793005)
                .wrapping_add(1442695040888963407);
            arr.insert((seed % 257) as i32);
        }

        for v in -1..260 {
            let expected = arr.items.contains(&v);
            assert_eq!(arr.contains(&v), expected);
        }
    }
}