A bounded deque that holds at most N items and tracks min and max as values are shifted and shoveled.

quant_period.cr

class QuantPeriod(T)

  property max_size : Int32
  property max : T = T.new(0)
  property min : T = T.new(0)

  def initialize(@max_size : Int32)
    raise "max_size (#{@max_size}) must be > 1" if @max_size < 1
    @deque = Deque(T).new(@max_size)
  end

  def to_a
    @deque.to_a
  end

  def to_json(io)
    @deque.to_json(io)
  end

  def initialize(pull : JSON::PullParser)
    @deque = Deque(T).new(pull)
    @max_size = @deque.size
    @max = @deque.max
    @min = @deque.min
  end

  delegate :each, :each_cons, :each_with_index, :sum, :reduce, :size, :empty?, to: @deque

  def map(&block : T -> U) forall U
    ary = [] of U
    @deque.each { |e| ary << yield e }
    ary
  end

  def mean
    return 0.0 if @deque.empty?
    @deque.reduce(0.0){ |sum, e| sum + e } / @deque.size
  end

  # WARNING: Expensive operation
  def slice(a : Int32, b : Int32)
    puts "WARNING: expensive QuantDeque#slice(#{a}, #{b}) #{self}"
    a = 0 if a < 0 && a.abs >= @deque.size
    @deque.to_a[a, b]
  end

  def [](a : Int32, b : Int32)
    slice(a, b)
  end

  def [](index)
    index = 0 if index < 0 && index.abs >= @deque.size
    @deque[index]
  end

  def <<(value : T)
    if @deque.size >= @max_size
      v = @deque.shift
      @max = @deque.max if v == @max
      @min = @deque.min if v == @min
    end
    @max = value if value > @max || @deque.empty?
    @min = value if @min > value || @deque.empty?
    @deque << value
  end
end

quant_period_spec.cr

require "../../spec_helper"

def preloaded(count)
  q = QuantPeriod(Int32).new(count)
  count.times{|i| q << i}
  return q
end

describe "QuantPeriod" do
  it "instantiates" do
    q = QuantPeriod(Int32).new(5)
    q << 1
    q.to_a.should eq [1]
    q.min.should eq 1
    q.max.should eq 1
  end

  it "is bounded" do
    q = preloaded(5)
    q.to_a.should eq [0,1,2,3,4]
    q.min.should eq 0
    q.max.should eq 4
    5.times{|i| q << i + 5}
    q.to_a.should eq [5,6,7,8,9]
    q.min.should eq 5
    q.max.should eq 9
  end

  it "reduces" do
    q = preloaded(5)
    q.reduce(0){|sum, i| sum + i}.should eq 10
  end

  it "maps" do
    q = preloaded(5)
    q.map{|i| i}.should eq [0,1,2,3,4]
  end

  it "last item is the zeroth item" do
    q = preloaded(5)
    [q[4], q[-1]].uniq.should eq [4]
    [q[3], q[-2]].uniq.should eq [3]
    [q[2], q[-3]].uniq.should eq [2]
    [q[1], q[-4]].uniq.should eq [1]
    [q[0], q[-5]].uniq.should eq [0]
    [q[0], q[-6]].uniq.should eq [0]
  end

  it "#safe_slice" do
    q = preloaded(5)
    q.slice(0, 5).should eq [0,1,2,3,4]
    q.slice(-5, 5).should eq [0,1,2,3,4]
    q[-4, 5].should eq [1,2,3,4]
    q[-15, 5].should eq [0,1,2,3,4]
  end
end