[RFC] Consider amortized O(1) rolling extrema for AroonOscillator

RFC

Before you proceed

• I've searched existing issues and PRs for an active Aroon performance proposal.
• I have no other RFC open.

Context

I was looking through the Rust AroonOscillator while investigating its window behavior and noticed that once initialized, every update rescans the full observation window twice.

update_raw() calls calculate_aroon() on every subsequent observation:

if self.initialized {
    self.calculate_aroon();
}

calculate_aroon() then scans the complete high window:

let mut periods_since_high = 0_usize;
let mut max_val = f64::MIN;

for (periods_back, &hi) in self.high_inputs.iter().rev().enumerate() {
    if hi > max_val {
        max_val = hi;
        periods_since_high = periods_back;
    }
}

and separately scans the complete low window:

let mut periods_since_low = 0_usize;
let mut min_val = f64::MAX;

for (periods_back, &lo) in self.low_inputs.iter().rev().enumerate() {
    if lo < min_val {
        min_val = lo;
        periods_since_low = periods_back;
    }
}

For period p, each initialized update therefore does two linear scans over roughly p + 1 values.

The current update complexity is:

single initialized update: O(p)
N observations:            O(Np)
storage:                   O(p)

For small Aroon periods this is unlikely to matter. The reason I think it may still be worth considering is that this is an indicator update path which can run continuously across many instruments and observations, and the crate already keeps a bounded rolling window.

I wanted to check whether there is interest in replacing the repeated full scans with maintained rolling extrema.

Proposed direction

A monotonic deque for highs and another for lows could maintain candidates for the maximum and minimum as the window advances.

Each observation would:

1. Expire candidates which have left the period + 1 window.
2. Remove dominated candidates from the back.
3. Insert the new observation and its sequence/window index.
4. Read the current extreme from the front.

Each observation enters a monotonic deque once and leaves at most once, making updates amortized O(1):

single initialized update: O(1) amortized
N observations:            O(N)
storage:                   O(p)

I would not want to change this based on complexity alone. I would benchmark the existing implementation against the proposed implementation at representative periods and only proceed if there is a measurable improvement without a meaningful regression at normal periods.

Correctness requirements

There is one Aroon-specific detail that matters here.

The current implementation deliberately scans from newest to oldest:

// Scan the full window from newest to oldest so the enumeration index
// is the periods-since count directly and ties resolve to the most
// recent occurrence of the extreme.

and only replaces the selected value on a strict comparison:

if hi > max_val {
    ...
}

if lo < min_val {
    ...
}

This means equal highs or lows resolve to the most recent occurrence.

That behavior is now covered by:

#[rstest]
fn test_tie_favors_most_recent_occurrence() {
    let mut aroon = AroonOscillator::new(4);
    let inputs = [
        (110.0, 100.0),
        (110.0, 100.0),
        (105.0, 101.0),
        (105.0, 101.0),
        (105.0, 101.0),
    ];

    for &(h, l) in &inputs {
        aroon.update_raw(h, l);
    }

    assert_eq!(aroon.aroon_up, 25.0);
    assert_eq!(aroon.aroon_down, 25.0);
    assert_eq!(aroon.value, 0.0);
}

Any rolling-extrema implementation would need to preserve that exact behavior.

For example, when inserting a new high equal to an older candidate high, the older equal candidate should not remain authoritative if doing so would change the current "most recent occurrence wins" semantics.

The same applies to lows.

Considerations

Performance

The optimization changes the extrema lookup from a full scan on every observation to incremental maintenance.

The expected asymptotic change is:

Current
update: O(p)
stream: O(Np)

Proposed
update: O(1) amortized
stream: O(N)

I would include Criterion or the existing project-standard benchmarks covering multiple period sizes rather than relying on Big O alone.

Complexity

The current implementation is simple and easy to audit.

A monotonic deque introduces more state and more edge cases around:

• eviction at the exact window boundary
• repeated equal highs
• repeated equal lows
• the newest occurrence tie rule
• reset behavior
• initialization at exactly period + 1
• window rollover

So I think the optimization is only worthwhile if the benchmarks show a useful improvement.

Scope

I would keep this specific to AroonOscillator.

I am not proposing a generic rolling-extrema abstraction or changes to unrelated indicators as part of the same work.

Alternatives

Keep the existing implementation

This is reasonable if realistic Aroon periods make the current O(p) scan effectively irrelevant compared with the added state and complexity of monotonic deques.

Cache only one side

This reduces some work but leaves the same asymptotic behavior for the other extrema scan and adds complexity without getting the full benefit.

Generic rolling min/max utility

A reusable abstraction may make sense if several indicators need identical behavior, but I would avoid widening the scope unless there is already a clear use case elsewhere in the crate.

If maintainers are interested in the monotonic-deque approach, I can benchmark the existing implementation first and use those results to determine whether a PR is justified.