view release on metacpan or  search on metacpan

lib/Algorithm/SlidingWindow/Dynamic.pm  view on Meta::CPAN

=head2 slide($item)

Advances the window by one position.

If the window is non-empty, removes the oldest item and appends C<$item> as
the newest item. The window size remains unchanged. The removed item is
returned.

If the window is empty, behaves like C<push($item)> and returns C<undef>.

=head2 size

Returns the number of items currently stored in the window.

=head2 is_empty

Returns true if the window is empty, false otherwise.

=head2 oldest

Returns the oldest item without removing it, or C<undef> if the window is
empty.

=head2 newest

Returns the newest item without removing it, or C<undef> if the window is
empty.

=head2 get($index)

Returns the item at logical index C<$index>, where index C<0> refers to the
oldest item and C<size - 1> refers to the newest item.

Returns C<undef> if the index is out of range.

=head2 values

Returns all items currently in the window, ordered from oldest to newest.

=head2 clear

Removes all items from the window. After this call, the window size is zero.

=head1 EXAMPLES

=head2 Shortest Subarray With Sum >= K (Non-Negative Values)

This example demonstrates the classic sliding-window technique for finding the
length of the shortest contiguous subarray whose sum is at least C<K>.

B<Important:> This algorithm assumes that all input values are non-negative.
If negative values are present, a different approach is required.

  use Algorithm::SlidingWindow::Dynamic;

  sub shortest_subarray_at_least_k {
      my ($nums, $k) = @_;

      my $w   = Algorithm::SlidingWindow::Dynamic->new;
      my $sum = 0;
      my $best;

      for my $x (@$nums) {
          die "negative values not supported" if $x < 0;

          $w->push($x);
          $sum += $x;

          while ($w->size > 0 && $sum >= $k) {
              my $len = $w->size;
              $best = $len if !defined($best) || $len < $best;

              my $removed = $w->shift;
              $sum -= $removed;
          }
      }

      return defined($best) ? $best : -1;
  }

  print shortest_subarray_at_least_k([2, 3, 1, 2, 4, 3], 7), "\n";  # prints 2

=head2 Fixed-Length Rolling Window Using slide()

  my $w = Algorithm::SlidingWindow::Dynamic->new;

  $w->push(10);
  $w->push(20);
  $w->push(30);

  my $evicted = $w->slide(40);
  my @vals    = $w->values;   # (20, 30, 40)

=head2 Removing Elements From Either End

  my $w = Algorithm::SlidingWindow::Dynamic->new;
  $w->push(qw(a b c d));

  my $left  = $w->shift;  # removes 'a'
  my $right = $w->pop;    # removes 'd'

  my @vals = $w->values;  # (b, c)

=head1 LIMITATIONS

=over 4

=item *

This module implements a count-based sliding window only. It does not provide
time-based expiration or automatic removal based on timestamps.

=item *

The module does not perform any aggregation, comparison, or ordering of values.
Such logic must be implemented by the caller.

=item *

Algorithms that require handling of negative values may require additional
data structures beyond a simple sliding window.

=back

=head1 SEE ALSO

L<Algorithm::SlidingWindow>

=head1 AUTHOR

Joshua Day

=head1 LICENSE

This library is free software; you may redistribute it and/or modify it under
the same terms as Perl itself.

=cut