[elephant-devel] virtual subtree?

[Ian Eslick]

Joe,

The easiest thing I can think of is to create a derived index on the  
classes of
elements in your btree and then use map-index to map over the instances.

ELE-TESTS> (setf my-things (make-indexed-btree))

ELE-TESTS> (add-index my-things :index-name 'thing-type
		      :key-form '(lambda (index k v)
				  (values t (type-of v))))

ELE-TESTS> (map-index (lambda (sk v pk) (print v))
		      (get-index my-things 'thing-type) :value 'symbol)

TEST1
TEST2
NIL

ELE-TESTS> (map-index (lambda (sk v pk) (print v))
		      (get-index my-things 'thing-type) :value 'fixnum)

10
20
NIL

Or better, you can mix this in with an efficient search for your  
triples, such as:

ELE-TESTS> (add-index my-things :index-name 'triples-first
                       :key-form '(lambda (index k v)
                                     (if (subtypep (type-of v)  
'triple) t)
                                         (values t (triple-first v))
                                         (values nil nil)))
                       :populate t)

This will create an index 'triples-first which only indexes triples  
and does so by the value of the first element.  Thus you can easily  
retrieve all triples with the first element eq to 5.

ELE-TESTS> (map-index (lambda (sk v pk) (print v)) (get-index my- 
things 'triples-first :value 5)))

The index will be automatically populated if there are already  
elements.  Otherwise all new elements will automatically be added to  
the new index.

This does create a parallel 'index' which is its own btree.  There  
isn't a good way to do this using only a single btree as we don't  
expose the sort order constraints or allow the user to create partial  
keys so they can use cursors to iterate over a subset of the btree.   
Now if you indexed your things by typename, then you could do this  
with a single tree, although you'd have to go over indexes

Cheers,
Ian


A brief aside:

One of the major issues on queue for v 0.9.1 is how do we  
automatically do something similar
for class heirarchies.  If I want an index to go over all elements of  
a base class,
but a restricted index to go over all elements of some subtype, how  
do we implement and
specify this.

For example, if we had base class 'people and subclasses 'employee,  
'manager, 'consultant, etc.
What if we wanted to retrieve all 'employees and 'managers named  
"Bob"?  Today you'd have to map
over each class index separately.  I'd like to be able to map over  
'people if people has a slotname
for "Name" that is common to the subclasses and get back all objects  
of any subclass with that name.


On Apr 15, 2007, at 12:39 PM, Joe Corneli wrote:

> I am wondering whether it is possible to efficiently treat a subset of
> a given btree as its own tree.  Specifically: if I have a collection
> of miscellaneous data, which I'll call Things, some of which are
> Triples, can I specifically examine all of the Triples in my
> collection, and from that sub-set, find those Triples whose first slot
> is, say, equal to 5?
>
> Or must I do what seems to be the expected thing, and treat Things and
> Triples as a separate btrees if I want to efficiently search through
> the slots of my Triples?
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel