tunes 1.1.0

/// Generate Recamán's sequence
///
/// Recamán's sequence is a mathematical curiosity that creates beautiful spiraling patterns.
/// It's defined recursively with a simple rule that produces surprisingly complex behavior:
///
/// - Start with 0
/// - At step n: try to go backward by n (a(n) = a(n-1) - n)
/// - If that's negative or already visited, go forward instead (a(n) = a(n-1) + n)
///
/// The sequence: 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62...
///
/// Named after Colombian mathematician Bernardo Recamán Santos. When visualized,
/// it creates beautiful arcs that have been used in art installations and music.
///
/// # Arguments
/// * `n` - Number of terms to generate
///
/// # Returns
/// Vector of values forming Recamán's sequence
///
/// # Typical Values
/// - **n = 10-20**: Good for melodic phrases (interesting contours)
/// - **n = 20-30**: Medium patterns (complete melodies)
/// - **n = 50+**: Long evolving sequences (structural use)
/// - Values grow large (n=100 → 1000s), always normalize!
///
/// # Recipe: Spiraling Bass Line
/// ```
/// use tunes::prelude::*;
/// use tunes::sequences;
///
/// let mut comp = Composition::new(Tempo::new(110.0));
///
/// // Generate Recamán spiral
/// let recaman = sequences::recaman::generate(24);
///
/// // Map to bass range (E2 to E3)
/// let bass_line = sequences::normalize(&recaman, 82.4, 164.8);
///
/// comp.instrument("recaman_bass", &Instrument::sub_bass())
///     .notes(&bass_line, 0.5);
/// ```
///
/// # Examples
/// ```
/// use tunes::sequences;
///
/// let recaman = sequences::recaman::generate(20);
/// // [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62]
///
/// // Use for melodic contours
/// let melody = sequences::normalize(&recaman, 220.0, 880.0);
///
/// // Use for interesting bass lines
/// # use tunes::prelude::*;
/// # let mut comp = Composition::new(Tempo::new(120.0));
/// let bass_recaman = sequences::recaman::generate(16);
/// let bass_freqs = sequences::normalize(&bass_recaman, 55.0, 110.0);
/// comp.instrument("bass", &Instrument::sub_bass())
///     .notes(&bass_freqs, 0.25);
/// ```
///
/// # Musical Applications
/// - **Melodic contours**: Creates interesting back-and-forth pitch movement
/// - **Bass lines**: Unpredictable but structured patterns
/// - **Phrase lengths**: Use values (mod some number) for varying phrase durations
/// - **Rhythmic displacement**: Map to beat positions for syncopation
/// - **Formal structure**: Large-scale sectional organization
/// - **Visual music**: Graph the sequence for performance visuals
///
/// # Why It's Special
/// Recamán's sequence has a unique "memory" - it remembers all previous values
/// and avoids revisiting them when possible. This creates patterns that wander
/// but never quite repeat, perfect for generative music that needs to feel
/// purposeful without being predictable.
pub fn generate(n: usize) -> Vec<u32> {
    if n == 0 {
        return vec![];
    }

    let mut seq = vec![0u32];
    let mut seen = std::collections::HashSet::new();
    seen.insert(0u32);

    for i in 1..n {
        let prev = seq[i - 1];
        let backward = prev.saturating_sub(i as u32);

        // Try backward first: must be > 0 and not previously seen
        if backward > 0 && !seen.contains(&backward) {
            seq.push(backward);
            seen.insert(backward);
        } else {
            // Go forward - standard Recamán just adds without checking duplicates
            let forward = prev + i as u32;
            seq.push(forward);
            seen.insert(forward);
        }
    }

    seq
}

/// Generate Van der Corput sequence (low-discrepancy/quasi-random sequence)
///
/// The Van der Corput sequence is a "quasi-random" sequence that fills space more
/// evenly than pure random numbers. It's used in ray tracing, Monte Carlo integration,
/// and anywhere you want random-looking but well-distributed values.
///
/// The sequence is generated by reversing the binary representation of integers:
/// - 1 (binary: 1) → 0.1 (binary) = 0.5
/// - 2 (binary: 10) → 0.01 (binary) = 0.25
/// - 3 (binary: 11) → 0.11 (binary) = 0.75
/// - 4 (binary: 100) → 0.001 (binary) = 0.125
///
/// This produces values in [0, 1) that are more evenly distributed than random.
///
/// # Arguments
/// * `n` - Number of terms to generate
/// * `base` - Base for the sequence (typically 2 for binary, but can use other bases)
///
/// # Returns
/// Vector of values in range [0.0, 1.0) with quasi-random distribution
///
/// # Examples
/// ```
/// use tunes::sequences;
///
/// // Generate quasi-random values
/// let quasi = sequences::van_der_corput::generate(16, 2);
/// // More evenly distributed than random!
///
/// // Use for note placement that avoids clumping
/// let positions = sequences::van_der_corput::generate(32, 2);
/// let note_times: Vec<f32> = positions.iter()
///     .map(|&x| x * 4.0)  // Spread over 4 seconds
///     .collect();
///
/// // Use for parameter sweeps
/// # use tunes::prelude::*;
/// # let mut comp = Composition::new(Tempo::new(120.0));
/// let cutoff_values = sequences::van_der_corput::generate(64, 2);
/// for (i, &cutoff) in cutoff_values.iter().enumerate() {
///     let freq = 200.0 + cutoff * 600.0;  // 200-800 Hz range
///     comp.instrument("sweep", &Instrument::synth_lead())
///         .at(i as f32 * 0.125)
///         .note(&[freq], 0.1);
/// }
/// ```
///
/// # Musical Applications
/// - **Note distribution**: Place notes evenly without grid-like regularity
/// - **Rhythm generation**: Better than random for avoiding clumps
/// - **Parameter sampling**: Sweep through filter/pan/volume space efficiently
/// - **Chord voicings**: Distribute notes across register evenly
/// - **Polyrhythms**: Create non-periodic but well-distributed patterns
/// - **Microtonal scales**: Sample pitch space quasi-randomly
///
/// # Quasi-Random vs Random
/// Pure random can create clumps and gaps. Van der Corput fills space more evenly:
/// - **Random**: Unpredictable, can cluster
/// - **Quasi-random**: Looks random, mathematically even distribution
/// - **Grid**: Predictable, mechanical
///
/// Perfect middle ground for generative music that needs randomness without chaos.

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

    #[test]
    fn test_recaman_basic() {
        let seq = generate(20);

        // Known Recamán sequence values
        let expected = vec![
            0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62,
        ];
        assert_eq!(seq, expected);
    }

    #[test]
    fn test_recaman_edge_cases() {
        let empty = generate(0);
        assert_eq!(empty, Vec::<u32>::new());

        let single = generate(1);
        assert_eq!(single, vec![0]);

        let two = generate(2);
        assert_eq!(two, vec![0, 1]);
    }

    #[test]
    fn test_recaman_backward_when_possible() {
        let seq = generate(10);

        // At step 1: 0 - 1 would be negative, so go forward: 0 + 1 = 1
        assert_eq!(seq[1], 1);

        // At step 2: 1 + 2 = 3 (can't go backward to -1)
        assert_eq!(seq[2], 3);

        // At step 3: 3 + 3 = 6 (can't go backward to 0, already seen)
        assert_eq!(seq[3], 6);

        // At step 4: 6 - 4 = 2 (can go backward, 2 not seen yet)
        assert_eq!(seq[4], 2);
    }

    #[test]
    fn test_recaman_properties() {
        let seq = generate(50);

        // Recamán CAN have duplicates (when forward step lands on seen value)
        // This is actually part of the sequence's interesting behavior!

        // Check that it follows the rules:
        // - First value is 0
        assert_eq!(seq[0], 0);

        // - Sequence has correct length
        assert_eq!(seq.len(), 50);

        // - All values are non-negative (by construction with u32)
        // No assertion needed, u32 guarantees this
    }
}

// ========== PRESETS ==========

/// Short Recamán (16 terms) - melodic phrase length
pub fn short() -> Vec<u32> {
    generate(16)
}

/// Classic Recamán (32 terms) - medium pattern
pub fn classic() -> Vec<u32> {
    generate(32)
}

/// Long Recamán (64 terms) - extended sequence
pub fn long() -> Vec<u32> {
    generate(64)
}

/// Epic Recamán (100 terms) - long structural use
pub fn epic() -> Vec<u32> {
    generate(100)
}