A final clarification:
map-index is a feature of the upcoming 0.9 release. The same
effective functionality can be achieved on version 0.6.0 using cursor
operations cursor-pset and cursor-pnext-dup.
Ian
On Apr 15, 2007, at 2:52 PM, Ian Eslick wrote:
I should clarify two points from my last e-mail.
I added to the first btree the elements:
k: 1 v:'test1
k: 2 v:'test
k 10 v:10
k 20 v:20
That generated the test result.
The final index, 'triple-first, only indexes triples and no other
types. It accomplishes this by returning an 'index-p' value. The
first value returned by the :key-form is whether or not to index
the value provided to get-value. The second value is the secondary-
key to use to create the index entry that is used to find the value
in the main indexed-btree, in this case the triple with the first
value equal to the generated secondary key.
Sorry if that is wordy - please ask questions if any of this is
unclear.
Cheers,
Ian
On Apr 15, 2007, at 2:34 PM, Ian Eslick wrote:
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@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
