tiny-counter 0.1.0

/// Core rotating bucket storage for event counts.
use std::collections::VecDeque;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

/// Sanity threshold for per-bucket event counts (50 million).
///
/// This limit ensures that summing up to 72 buckets (the maximum in default config)
/// never exceeds u32::MAX: 72 × 50M = 3.6B < 4.2B
///
/// For on-device tracking, 50M events in a single time bucket is extremely high:
/// - 50M/hour = 13,888 events/second
/// - 50M/day = 578 events/second
/// - 50M/year = 1.6 events/second
const SANITY_THRESHOLD: u32 = 50_000_000;

/// A ring buffer that stores event counts in rotating buckets.
///
/// Bucket 0 is always the current time interval. Higher indices represent
/// older intervals. As time advances, buckets rotate: new buckets are added
/// at index 0, and old buckets beyond bucket_count are discarded.
///
/// Uses u32 for bucket counts (max 4.2 billion events per bucket).
///
/// Serializes as a plain array for compact storage (no "buckets" key overhead).
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "serde", serde(transparent))]
#[derive(Clone)]
pub(crate) struct CountRing {
    buckets: VecDeque<u32>,
}

impl std::fmt::Debug for CountRing {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.buckets.fmt(f)
    }
}

impl CountRing {
    /// Creates a new CountRing with the specified capacity.
    ///
    /// All buckets are eagerly initialized to zero, so len() == bucket_count
    /// immediately after construction. This ensures bucket_count() consistently
    /// returns the configured capacity.
    pub(crate) fn new(bucket_count: usize) -> Self {
        Self {
            buckets: VecDeque::from(vec![0; bucket_count]),
        }
    }

    /// Increments the count at the specified bucket index.
    ///
    /// All buckets are pre-allocated at construction, so this operation is always
    /// safe for valid indices (< bucket_count).
    ///
    /// **Silent dropping**: If bucket_index >= bucket_count, the operation is silently ignored
    /// with no error. This happens when events are too old to fit in the fixed-size rotating
    /// bucket array. This is intentional - the library uses fixed-size storage, and old data
    /// falls off as buckets rotate. This represents a loss of granularity, not complete data loss.
    ///
    /// **Saturation arithmetic**: Uses saturating addition internally. If a bucket count reaches
    /// u32::MAX (4.2 billion), further increments have no effect. This prevents overflow but means
    /// very high-volume events cannot be accurately counted beyond this limit. For most applications
    /// this is not a concern, but if you need to track counts beyond u32::MAX, consider using
    /// multiple counters or a different data structure.
    pub(crate) fn increment(&mut self, bucket_index: usize, count: u32) {
        // Silently ignore events that are too old to fit in the bucket array.
        // This is intentional - fixed-size storage means old data falls off.
        if bucket_index >= self.buckets.len() {
            return;
        }

        // All buckets are pre-allocated, so direct indexing is safe
        self.buckets[bucket_index] = self.buckets[bucket_index].saturating_add(count);

        // Debug mode: warn if bucket exceeds sanity threshold
        #[cfg(debug_assertions)]
        {
            let new_value = self.buckets[bucket_index];
            if new_value > SANITY_THRESHOLD {
                eprintln!(
                    "tiny-counter warning: bucket[{}] has {} events (threshold: {}). \
                     This library is designed for on-device tracking at reasonable scale. \
                     Consider if this is the right tool for your use case.",
                    bucket_index, new_value, SANITY_THRESHOLD
                );
            }
        }
    }

    /// Rotates the ring by pushing n new zero buckets to the front.
    ///
    /// All existing buckets shift to higher indices (older). Buckets beyond
    /// bucket_count are discarded. For large rotations (n > bucket_count),
    /// the rotation is bounded to bucket_count.
    pub(crate) fn rotate(&mut self, rotations: usize) {
        // Bound rotations to bucket_count
        let bucket_count = self.buckets.len();
        let n = rotations.min(bucket_count);

        // Push n new zero buckets to the front
        for _ in 0..n {
            self.buckets.push_front(0);
        }

        // Truncate to bucket_count
        self.buckets.truncate(bucket_count);
    }

    /// Returns the count at the specified index, or None if out of bounds.
    pub(crate) fn get(&self, index: usize) -> Option<u32> {
        self.buckets.get(index).copied()
    }

    /// Returns the number of buckets currently stored.
    pub(crate) fn len(&self) -> usize {
        self.buckets.len()
    }

    /// Returns true if the ring contains no buckets.
    #[allow(dead_code)]
    pub(crate) fn is_empty(&self) -> bool {
        self.buckets.is_empty()
    }

    /// Returns a reference to the underlying bucket storage.
    #[allow(dead_code)]
    pub(crate) fn buckets(&self) -> &VecDeque<u32> {
        &self.buckets
    }

    /// Sums the counts in the specified range [start, end).
    ///
    /// If indices are out of bounds, sums only the valid range.
    /// Uses saturating addition to prevent overflow.
    pub(crate) fn sum_range(&self, start: usize, end: usize) -> u32 {
        let actual_end = end.min(self.buckets.len());
        let actual_start = start.min(actual_end);

        self.buckets
            .range(actual_start..actual_end)
            .fold(0u32, |acc, &val| acc.saturating_add(val))
    }

    pub fn into_buckets(self) -> Vec<u32> {
        self.buckets.into()
    }
}

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

    #[test]
    #[cfg(feature = "serde-json")]
    fn test_transparent_serialization_is_compact() {
        // Verify that transparent serialization produces a plain array
        let ring = CountRing::new(5);
        let json = serde_json::to_string(&ring).unwrap();

        // Should be just [0,0,0,0,0], not {"buckets":[0,0,0,0,0]}
        assert_eq!(json, "[0,0,0,0,0]");

        // Verify deserialization still works
        let deserialized: CountRing = serde_json::from_str(&json).unwrap();
        assert_eq!(deserialized.len(), 5);
    }

    #[test]
    fn test_new_creates_ring_with_zero_buckets() {
        let ring = CountRing::new(10);
        assert_eq!(ring.len(), 10);
        assert!(!ring.is_empty());
        // All buckets should be initialized to zero
        for i in 0..10 {
            assert_eq!(ring.get(i), Some(0));
        }
    }

    #[test]
    fn test_increment_bucket_0() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 5);
        assert_eq!(ring.len(), 10); // All buckets pre-allocated
        assert_eq!(ring.get(0), Some(5));
    }

    #[test]
    fn test_increment_past_buckets() {
        let mut ring = CountRing::new(20);
        ring.increment(5, 10);
        assert_eq!(ring.len(), 20); // All buckets pre-allocated
        assert_eq!(ring.get(0), Some(0)); // Bucket 0 is zero
        assert_eq!(ring.get(5), Some(10)); // Bucket 5 has the count
    }

    #[test]
    fn test_increment_multiple_times() {
        let mut ring = CountRing::new(10);
        ring.increment(2, 5);
        ring.increment(2, 3);
        assert_eq!(ring.get(2), Some(8));
    }

    #[test]
    fn test_increment_beyond_bucket_count() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 5);
        ring.increment(15, 100); // Should be ignored
        assert_eq!(ring.len(), 10); // All buckets pre-allocated
        assert_eq!(ring.get(0), Some(5));
    }

    #[test]
    fn test_rotate_single() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 5);
        ring.increment(1, 3);

        ring.rotate(1);

        assert_eq!(ring.get(0), Some(0)); // New bucket at 0
        assert_eq!(ring.get(1), Some(5)); // Old bucket 0 shifted to 1
        assert_eq!(ring.get(2), Some(3)); // Old bucket 1 shifted to 2
    }

    #[test]
    fn test_rotate_multiple() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 5);

        ring.rotate(5);

        assert_eq!(ring.len(), 10); // Truncated to bucket_count
        assert_eq!(ring.get(0), Some(0));
        assert_eq!(ring.get(5), Some(5)); // Original bucket shifted by 5
    }

    #[test]
    fn test_rotate_at_bucket_count() {
        let mut ring = CountRing::new(5);
        ring.increment(0, 10);
        ring.increment(1, 20);

        ring.rotate(5);

        // After rotating by bucket_count, original buckets are beyond limit
        assert_eq!(ring.len(), 5);
        assert_eq!(ring.get(0), Some(0));
        assert_eq!(ring.get(4), Some(0));
    }

    #[test]
    fn test_rotate_beyond_bucket_count() {
        let mut ring = CountRing::new(5);
        ring.increment(0, 10);

        ring.rotate(100); // Should be bounded to bucket_count

        assert_eq!(ring.len(), 5);
        // All buckets should be zero (original data rotated out)
        assert_eq!(ring.sum_range(0, 5), 0);
    }

    #[test]
    fn test_truncate_maintains_invariant() {
        let mut ring = CountRing::new(5);
        for i in 0..10 {
            ring.increment(i, i as u32 + 1);
        }

        // Only first 5 buckets should exist
        assert_eq!(ring.len(), 5);
    }

    #[test]
    fn test_get_out_of_bounds() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 5);

        assert_eq!(ring.get(10), None);
        assert_eq!(ring.get(100), None);
    }

    #[test]
    fn test_sum_range_full() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 10);
        ring.increment(1, 20);
        ring.increment(2, 30);

        assert_eq!(ring.sum_range(0, 3), 60);
    }

    #[test]
    fn test_sum_range_partial() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 10);
        ring.increment(1, 20);
        ring.increment(2, 30);

        assert_eq!(ring.sum_range(1, 3), 50);
    }

    #[test]
    fn test_sum_range_out_of_bounds() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 10);
        ring.increment(1, 20);

        // Should sum only valid range
        assert_eq!(ring.sum_range(0, 100), 30);
        assert_eq!(ring.sum_range(5, 100), 0);
    }

    #[test]
    fn test_sum_range_empty() {
        let ring = CountRing::new(10);
        assert_eq!(ring.sum_range(0, 10), 0);
    }

    #[test]
    fn test_buckets_reference() {
        let mut ring = CountRing::new(10);
        ring.increment(0, 5);
        ring.increment(1, 10);

        let buckets = ring.buckets();
        assert_eq!(buckets.len(), 10); // All buckets pre-allocated
        assert_eq!(buckets[0], 5);
        assert_eq!(buckets[1], 10);
        // Remaining buckets should be zero
        for i in buckets.iter().take(10).skip(2) {
            assert_eq!(*i, 0);
        }
    }

    // Property test: buckets.len() <= bucket_count always
    #[test]
    fn test_invariant_bucket_count() {
        let mut ring = CountRing::new(5);

        // Test various operations
        ring.increment(0, 1);
        assert!(ring.len() <= 5);

        ring.increment(3, 2);
        assert!(ring.len() <= 5);

        ring.rotate(2);
        assert!(ring.len() <= 5);

        ring.increment(10, 100); // Beyond limit
        assert!(ring.len() <= 5);

        ring.rotate(100); // Large rotation
        assert!(ring.len() <= 5);
    }

    // Property test: sum_range is additive
    #[test]
    fn test_property_sum_range_additive() {
        let mut ring = CountRing::new(20);
        for i in 0..10 {
            ring.increment(i, (i + 1) as u32 * 10);
        }

        let sum_0_5 = ring.sum_range(0, 5);
        let sum_5_10 = ring.sum_range(5, 10);
        let sum_0_10 = ring.sum_range(0, 10);

        assert_eq!(sum_0_10, sum_0_5 + sum_5_10);
    }

    #[test]
    fn test_complex_workflow() {
        let mut ring = CountRing::new(10);

        // Record some events
        ring.increment(0, 5);
        ring.increment(1, 10);
        ring.increment(2, 15);

        // Advance time (rotate)
        ring.rotate(2);

        // Old buckets shifted
        assert_eq!(ring.get(2), Some(5)); // Was at 0
        assert_eq!(ring.get(3), Some(10)); // Was at 1
        assert_eq!(ring.get(4), Some(15)); // Was at 2

        // Record new events
        ring.increment(0, 20);
        ring.increment(1, 25);

        // Verify total: 20 + 25 + 5 + 10 + 15 = 75
        // (The two new zero buckets from rotation don't add to the sum)
        assert_eq!(ring.sum_range(0, 10), 75);
    }

    #[test]
    fn test_increment_overflow_saturates() {
        let mut ring = CountRing::new(10);

        // Set bucket to near max value
        ring.increment(0, u32::MAX - 100);
        assert_eq!(ring.get(0), Some(u32::MAX - 100));

        // Try to overflow by adding more than available space
        ring.increment(0, 200);

        // Should saturate at u32::MAX instead of wrapping
        assert_eq!(ring.get(0), Some(u32::MAX));
    }

    #[test]
    fn test_sum_range_saturates_at_u32_max() {
        let mut ring = CountRing::new(10);

        // Add multiple buckets with max u32 values
        ring.increment(0, u32::MAX);
        ring.increment(1, u32::MAX);
        ring.increment(2, u32::MAX);

        // sum_range saturates at u32::MAX
        let sum = ring.sum_range(0, 3);
        assert_eq!(sum, u32::MAX);
    }
}