class VArray
  DefaultSize = 4
  GrowthFactor = 1.5
 
  def initialize(size = DefaultSize)
    @capacity = DefaultSize
    @total = 0
    @top = Buffer.new(DefaultSize)
    @base = @top
    @start = 0
    grow(:top) until @capacity >= size
  end
 
  def size
    @total
  end
  alias_method :length, :size
  attr_reader :capacity
 
  def empty?
    @total == 0
  end
 
  class Buffer
    attr_accessor :prev
 
    def initialize(size)
      @prev = nil
      @data = Array.new(size)
    end
 
    def size
      @data.size
    end
 
    def get(index)
      @data[index]
    end
 
    def set(index,value)
      @data[index] = value
    end
  end
 
  def find_buffer_for_index(index)
    grow(:top) until(index < @capacity)
 
    offset = @capacity - @top.size
 
    current = @top
    while(index < offset && current.prev != nil)
      current = current.prev
      offset -= current.size
    end
    return current,index - offset
  end
  private :find_buffer_for_index
 
  def grow(side)
    if(side == :top)
      buffer = Buffer.new(@top.size * GrowthFactor)
      buffer.prev = @top
      @top = buffer
      @capacity += buffer.size
    else
      buffer = Buffer.new(@base.size * GrowthFactor)
      @base.prev = buffer
      @base = buffer
      @start += buffer.size
      @capacity += buffer.size
    end
  end
  private :grow
 
  def shrink(side)
    return self if @top == @base
    if(side == :top)
      @capacity -= @top.size
      @top = @top.prev
    else
      current = @top
      until(current.prev == @base)
        current = current.prev
      end
      @capacity -= @base.size
      @start -= @base.size
      @base = current
      current.prev = nil
    end
    return self
  end
  private :shrink
 
  def at(index)
    current,offset = find_buffer_for_index(index+@start)
    return current.get(offset)
  end
 
  def put(index,elem)
    @total = index+1 if(index >= @total)
    current,offset = find_buffer_for_index(index+@start)
    return current.set(offset,elem)
  end
 
  def <<(elem)
    self.put(@total,elem)
  end
 
  def pop
    if empty?
      return nil
    else
      elem = self.at(@total-1)
      self.put(@total-1,nil)
      @total -= 1
      shrink(:top) if @capacity - @top.size >= @total
      return elem
    end
  end
 
  def each(&block)
    i = 0
    while(i < @total)
      yield at(i)
      i+=1
    end
    self
  end
 
  def map!(&block)
    i = 0
    while(i < @total)
      val = yield at(i)
      put(i,val)
      i+=1
    end
    self
  end
 
  def map(&block)
    arr = self.class.new()
    i = 0
    while(i < @total)
      val = yield at(i)
      arr.put(i,val)
      i+=1
    end
    arr
  end
 
  def push(*args)
    args.each { |elem| self << elem }
    self
  end
 
  def shift
    if empty?
      return nil
    else
      elem = self.at(0)
      self.put(0,nil)
      @start += 1
      @total -= 1
      shrink(:base) if @start > @base.size
      return elem
    end
  end
 
  def unshift(elem)
    grow(:base) unless(@start > 0)
    @start -= 1
    current,offset = find_buffer_for_index(@start)
    current.set(offset,elem)
    @total += 1
    self
  end
 
  def +(other)
    self.class.new().concat(self).concat(other)
  end
 
  def concat(other)
    other.each {|elem| self << elem }
    self
  end
 
  def dup
    self.class.new().concat self
  end
 
  def reverse
    dup.reverse!
  end
 
  def reverse!()
    return self unless @total > 1
    i = @start
    j = @start + @total - 1
    while(i < (@start+@total/2))
      temp = at(i)
      put(i,at(j))
      put(j,temp)
      i += 1
      j -= 1
    end
    self
  end
 
  alias_method :real_inspect, :inspect
  def inspect
    arr = self.map {|x| x.inspect}
    "["+arr.join(",")+"]"
  end
 
  def join(separator)
    return "" if @total == 0
 
    str = ""
    i = 0
    while(i < @total)
      elem = at(i)
      str << separator unless i == 0
      str << elem.to_s
      i += 1
    end
    str
  end
end
 
arr = VArray.new(3)
10.times do |i|
  arr << i
  p [:<<, i, arr, arr.capacity]
end
 
8.times do
  p [:pop,arr.pop,arr, arr.capacity]
end
 
5.times do |i|
  i += 2
  arr << i
  p [:<<, i, arr, arr.capacity]
end
 
6.times do
  p [:shift, arr.shift, arr, arr.capacity]
end
 
5.times do |i|
  p [:ushft, 4-i, arr.unshift(4-i), arr.capacity]
end
 
5.times do |i|
  i += 7
  arr << i
  p [:<<, i, arr, arr.capacity]
end
puts arr.real_inspect
 
p arr.dup
p arr.reverse