views:

86

answers:

2

Is there anything like boost::multi_index but for ruby. Basically taking some container of objects and having it indexed N different ways with N different query methods.

I guess you could use DataMapper with the SQLite in memory database but I was wondering if there is anything pure ruby around.

Below is an imagined example of what this type of class might do. It looks very much like a database.

class Foo
    attr_accessor :a
    attr_accessor :b
    attr_accessor :c
end


class FooIndexer < MultiIndex
    hash_index :a do |o|
        o.a
    end

    ordered_index :b do |x, y|
        x.b <=> y.b
    end
end


index = FooIndexer.new

index.insert( Foo.new ( ... ))
index.insert( Foo.new ( ... ))
index.insert( Foo.new ( ... ))
index.insert( Foo.new ( ... ))
index.insert( Foo.new ( ... ))


index.find ( index.a == 10 )
index.find ( index.b > 10  )
A: 

It sounds like you're after a particular way of implementing this feature. But in terms of a ruby-like interface, I would recommend just using the Enumerable#find method. That way, you can say

foo_container = [FooIndexer.new, ...]
foo_container.find{|x| x.a == 10}

which looks very much like your example, save for braces instead of parentheses!

Later, if you find performance very bad, you may want to have some kind of cached or optimized find. But, based only on your question, if you look for that now, you'll be optimizing too soon.

Enumerable provides lots of these things already, so you have natural extensions like

foo_container.select{|x| x.a == 10}  # Finds all instances.
foo_container.reject{|x| x.a == 10}  # Finds the complementary set.
Peter
Of course find can be used but that is not really the question. Enumerable is great and a core component of any bit of my code but I'm specifically looking for a container that can index by multiple keys.
bradgonesurfing
sure, but why? are you currently suffering performance problems? this will direct the solution...
Peter
Cmon dude! Don't be the guy who warns me off using hashes just because arrays and Enumerable will do the job just fine. If you have 100k elements in an array ( maybe I do maybe I don't ) then a linear search using Enumerable::find vs a hash lookup will kill you. That is why Ruby provides hashes. In general hashes, arrays and Enumerable provide 99% of your algorithm needs. However I asked a specific question. Looks like the answer is no and if I care to I might write my own version, or maybe use DataMapper with the SQLite in memory database like I first suggested.
bradgonesurfing
Actually I ended up writing my own solution for a limited subset of what boost::multi-index can do. Seehttp://stackoverflow.com/questions/3612598/multi-index-container-for-ruby/3616107#3616107
bradgonesurfing
A: 

This is a fully worked solution including spec but only for multiple hash keys.

require 'pp'

class MKey
  def initialize &bk
    @block = bk
    @containers = {}
  end

  def <<(val)
    keys = @block.call(val)
    keys.each do |k,v|
      @containers[k] ||= {}
      @containers[k][v] = val
    end
  end

  def [](key)
    k, v = key.first
    @containers[k][v]
  end

  def delete(key)
    val = self[key]
    keys = @block.call(val)
    keys.each do |k,v|
      @containers[k].delete(v)
    end
  end

  include Enumerable

  def each
    k, c = @containers.first 
    c.each do |k, val|
      yield val
    end
  end

end


describe MKey do 

  class Foo
    def initialize(a,b)
      @a = a
      @b = b
    end
    attr_accessor :a
    attr_accessor :b
  end

  it "should insert" do

    index = MKey.new do |o|
      { :a => o.a,
        :b => o.b
      }
    end

    x = Foo.new("hello", "cat")
    y = Foo.new("goodbye", "code")

    index << x
    index << y

    # Test Enumerable interface
    index.find do |val|
      val.a == "hello"
    end.should == x

    # Test multi key interface
    index[:a => "hello"].should == x
    index[:b => "code"].should == y

    index.delete(:a => "hello")

    index[:a => "hello"].should == nil
    index[:b => "code"].should == y

    index.delete(:b => "code")

    index[:a => "hello"].should == nil
    index[:b => "code"].should == nil


  end

  it "hash lookup should be faster than find" do


    index = MKey.new do |o|
      { :a => o.a,
        :b => o.b
      }
    end

    for i in 1..10000
      index << Foo.new(i, i*100)
    end

    t0 = timer do
      index[:a => 1000]
    end

    t1 = timer do
      index.find {|v| v.a == 10000}
    end

    t0.should < t1 * 100 

  end

end
bradgonesurfing