Multi-Index Containers


#1

Does anyone know of a multi-index container library for Ruby? I just
want to check before I put it on my personal TODO list.

By multi-index, I mean a container which will index its contained
objects by more than one attribute. E.g. something along these lines:

mi = MultiIndex.new
mi.add_index(:prefix) {|val| val[0,3]}
mi.add_index(:size)

mi << “foobar”
mi << “foobaz”
mi << “fuzz”
mi << “fuzzbizz”

mi.by_prefix(“foo”) # => [“foobar”, “foobaz”]
mi.by_prefix(“fuz”) # => [“fuzz”, “fuzzbizz”]
mi.by_size(4) # => [“fuzz”]
mi.by_size(8) #= [“fuzzbizz”]

Yes, I know I can just uses #select on Ruby’s existing containers, but
the idea here is that a MultiIndex would index each attribute on
insert, making lookups faster than using a #select.

So: does this exist?


Avdi

Home: http://avdi.org
Developer Blog: http://avdi.org/devblog/
Twitter: http://twitter.com/avdi
Journal: http://avdi.livejournal.com


#2

On Dec 1, 2008, at 8:53 AM, Avdi G. wrote:

By multi-index, I mean a container which will index its contained
objects by more than one attribute. E.g. something along these lines:

gem install rbtree

a @ http://codeforpeople.com/


#3

On Mon, Dec 1, 2008 at 11:59 AM, ara.t.howard removed_email_address@domain.invalid
wrote:

gem install rbtree

I’m not sure I understand how a Red/Black Tree covers indexing by
multiple, arbitrary, potentially dynamic attributes.


Avdi

Home: http://avdi.org
Developer Blog: http://avdi.org/devblog/
Twitter: http://twitter.com/avdi
Journal: http://avdi.livejournal.com


#4

On 01.12.2008 16:53, Avdi G. wrote:

mi << “foobar”
the idea here is that a MultiIndex would index each attribute on
insert, making lookups faster than using a #select.

So: does this exist?

I haven’t seen it so far. Basically this would mimic what a relational
DB does in memory.

Not difficult to write though.

class Table
def initialize(index_keys)
@indexes =
index_keys.inject({}) do |idx,key|
idx[key]= Hash.new {|h,k| h[k]=[]}
idx
end
end

def add(o)
@indexes.each do |key,idx|
if Array === key
idx[o.send(key)] << o
else
idx[key.map{|k| o.send(k)}] << o
end
end
self
end
end

Kind regards

robert