[elephant-devel] virtual subtree?

[Ian Eslick]

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