Multi-Index Containers

[Avdi Grimm]

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_indexprefix) {|val| val[0,3]}
mi.add_indexsize)

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

 

[ara.t.howard]

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/

 

[Avdi Grimm]

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

 

[Robert Klemme]

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_indexprefix) {|val| val[0,3]}
mi.add_indexsize)

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?

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