ADT

hash_cache.rb

require 'forwardable'

module ADT
  class HashCache
    extend Forwardable
    include Enumerable

    attr_reader :max_size, :default_value, :store_default

    def initialize(max_size, default: nil, store_default: true)
      clear
      errors(:size) unless max_size.is_a?(Integer) && max_size > 0
      @max_size = max_size
      @default_value = default
      @store_default = store_default
      @dirty = false
      @without_size_restrictions = false
    end

    def_delegators :@metadata, :has_key?, :key?, :member?, :include?, :keys, :each_key
    def_delegators :@storage, :has_value?, :value?, :values, :each_value
    def_delegators :@storage, :count, :length, :size, :empty?

    def [](key)
      fetch(key, default_value)
    end

    def []=(key,val)
      store(key,val)
    end

    def fetch(key, default = (no_default = true; nil))
      case
      when has_key?(key)
        index = update_metadata(key)
        @storage[index]
      when block_given? then yield key
      when !no_default then default
      else raise KeyError, "key not found: \"#{key}\""
      end
    end

    def store(key,val)
      key = key.dup.freeze if key.is_a?(String)
      if !store_default && val == default_value
        return val.tap{ delete(key) }
      end
      if has_key?(key)
        index = update_metadata(key)
      else
        restrict_to(max_size - 1)
        index = indexer(key)
        @metadata[key] = format_metadata(index)
      end
      @storage[index] = val
    end

    def delete(key)
      case
      when has_key?(key)
        index, _ = @metadata.delete(key)
        @storage.delete(index)
      when block_given? then yield key
      else default_value
      end
    end

    def values_at(*keys)
      keys.map{ |k| self[k] }
    end

    def clear
      @storage = {}
      @metadata = {}
    end

    def consistent?
      Set.new(@metadata.values) == Set.new(@storage.keys)
    end

    def flatten(level = 1)
      self.to_a.flatten(level)
    end

    def to_h
      Hash[self.to_a]
    end
    alias_method :to_hash, :to_h

    def each
      return enum_for(:each) unless block_given?
      @metadata.each do |key, meta|
        value = @storage[meta.first]
        yield [key, value]
      end
    end
    alias_method :each_pair, :each

    def each_timestamped
      return enum_for(:each_timestamped) unless block_given?
      self.each{ |k,v| yield [k, v, @metadata[k].last] }
    end

    def key(value)
      index = @storage.key(value)
      if @storage.key?(index)
        key_forger(index).tap do |key|
          update_metadata(key)
        end
      end
    end

    def shift
      unless self.empty?
        key = @metadata.first.first
        val = delete(key)
        [key, val]
      end
    end

    def merge(other)
      dup.merge!(other)
    end

    def merge!(other)
      iter = [:each_timestamped, :each].find{ |i| other.respond_to?(i) }
      without_size_restrictions do
        other.send(iter) do |k,v,ts|
          ts = resolve_timestamp(k,v,ts)
          store(k,v)
          set_timestamp(k,ts) if ts
        end
        undirty!
      end
      restrict_to(max_size)
      self
    end
    alias_method :update, :merge!

    def ==(other)
      same_by?(other){ |x| x.to_a }
    end

    def eql?(other)
      same_by?(other){ |x| x.each_timestamped.to_a }
    end

    def ===(other)
      self.to_h == other.to_h
    end

    private

    def same_by?(other, &blk)
      return false unless other.is_a?(HashCache)
      [:max_size, :default_value, :store_default].each do |var|
        return false if other.send(var) != self.send(var)
      end
      [other, self].map(&blk).reduce(:==)
    end

    def without_size_restrictions
      @without_size_restrictions = true
      yield
    ensure
      @without_size_restrictions = false
    end

    def indexer(key)
      key # switch to a better storage strategy later
    end

    def key_forger(index)
      index # reverse of indexer
    end

    def update_metadata(key)
      index, _ = @metadata.delete(key)
      @metadata[key] = format_metadata(index)
      index
    end

    def format_metadata(index)
      [index, Time.now.to_f]
    end

    def set_timestamp(k,ts)
      if has_key?(k) && @metadata[k][1] != ts
        @metadata[k][1] = ts
        @dirty = true
      end
    end

    def resolve_timestamp(k,v,ts)
      if ts
        return ts unless self.has_key?(k)
        index = @metadata[k][0]
        current_value = @storage[index]
        return ts if current_value != v
        [ts, @metadata[k][1]].max
      end
    end

    def restrict_to(size)
      return if @without_size_restrictions
      errors(:restrict) if size < 0
      self.clear if size == 0
      while self.count > size do
        delete(@metadata.first.first)
      end
    end

    def undirty!
      return unless @dirty
      new_metadata = {}
      pos = 0
      @metadata.sort_by do |k,md|
        (pos += 1) && [md[1], pos]
      end.each do |k,md|
        new_metadata[k] = md
      end
      @metadata = new_metadata
      @dirty = false
    end

    def initialize_copy(orig)
      super
      clear
      merge!(orig)
    end

    def errors(type)
      case type
      when :size
        raise ArgumentError, "need a positive integer value for maximum size!"
      when :restrict
        cs = "consistent? == #{consistent?}"
        raise RuntimeError, "trying to restrict to negative size??? #{cs}"
      end
    end
  end
end

indexer.rb

require 'adt/sorted_set'

module ADT
  class Indexer
    attr_reader :max, :last

    def initialize(limit)
      @max = Integer(limit) - 1
      @last = -1
    end

    def checkout
      from_released = remove_max_released
      return from_released if from_released
      return if @last >= @max
      @last += 1
    end

    def release(index)
      return unless index.is_a?(Integer)
      return if index > @last || index < 0
      return if !released.add?(-1 * index)
      trim_released
      index
    end

    def count
      @last + 1 - released.size
    end

    private

    def released
      @released ||= ADT::SortedSet::Wrapper.new
    end

    def remove_max_released
      return if released.empty?
      return if !(ele = released.shift)
      (-1 * ele).tap do |index|
        @last -= 1 if index == @last
      end
    end

    def trim_released
      while released.first == (val = -1 * @last)
        break if !released.delete?(val)
        @last -= 1
      end
    end

  end
end

requirements.rb

module Util
  module Requirements
    extend self

    def available?(name)
      require name
      true
    rescue LoadError
      false
    end

    def find(*choices)
      choices.find{ |c| available?(c) }
    end

  end
end

sorted_set.rb

require 'util/requirements'
require 'set'

module ADT
  module SortedSet
    Wrapper = case Util::Requirements.find('rb_lovely', 'rbtree')
    when 'rb_lovely'
      Class.new(RbLovely::SortedSet) do
        def self.name; super + "(RbLovely)"; end
        alias_method :size, :length
        alias_method :delete_and_return, :delete
        def delete(o); delete_and_return(o); self; end
        def delete?(o); include?(o) ? delete(o) : nil; end
        def add?(o); include?(o) ? nil : add(o); end
      end
    when 'rbtree'
      Class.new(Set) do
        def self.name; super + "(RBTree)"; end
        def initialize(*args, &block); @hash = RBTree.new; super; end
        def add(o); cmp_err if !o.respond_to?(:<=>); super; end
        alias_method :<<, :add
        [:first, :last, :shift, :pop].each do |m|
          define_method(m){ @hash.send(m).try(:first) }
        end
        private
        def cmp_err; raise ArgumentError "value must respond to <=>"; end
      end
    else
      Class.new(SortedSet) do
        def self.name; super + "(Naive)"; end
        def last; self.to_a.last; end
        def delete_and_return(o); delete?(o) ? o : nil; end
        def shift; delete_and_return(self.first); end
        def pop; delete_and_return(self.last); end
      end
    end
  end
end