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
[EMAIL PROTECTED]
http://common-lisp.net/mailman/listinfo/elephant-devel
_______________________________________________
elephant-devel site list
[EMAIL PROTECTED]
http://common-lisp.net/mailman/listinfo/elephant-devel
