[elephant-devel] Start of 0.6.1 Beta Cycle

[Ian Eslick]

Henrik,

I think there's a confusion here because we have not properly  
communicated the semantics we are intending for map-index.  You have  
properly identified a problem in mine (inability to traverse null  
values) which I introduced to solve a problem I anticipated that  
shows up under your proposal.

I implemented map-index by using 'null' values of start and end to  
mean 'first' and 'last'.  Under this contract the current tests are  
correct.  However, this use of null precludes indexing over actual  
null values which is a specification bug.  You've fixed that by  
handling the presence or absence of the start/end keywords.  That  
makes functions that wrap map-index more complex to write.

For example, how do we want to have users specify queries such as:  
"all ages < 20" in get-instances-by-range?  (which is based on map- 
index).  We'd have to add keyword arguments or the 'null' contract to  
it.  The current implementation is:

(defun get-instances-by-range (class slot start end)
   ...
   (map-index #'collector slot-index :start start :end end))

In this case I force the user to use nil to indicate 'first' and  
'last' and we should find an alternative to that in case people want  
to iterate over booleans (although thye could use by-value for nil  
and then for t).  map-index needs a fix to provide get-instances-by- 
value for nulls, but not necessarily the current contract it creates  
in get-instances-by-range.

Under your map-index proposal, if get-instances-by-range wants to  
implement the null contract you would have to do something like the  
following:

(defun get-instances-by-range (class slot start end)
   ...
   (case ((and (null start) (null end))
	 (map-index #'collector slot-index))
         ((null start)
          (map-index #'collector slot-index :end end))
         ((null end)
          (map-index #'collector slot-index :start start))
         (t
          (map-index #'collector slot-index :start start :end end))))

Or something that computes the keyword list and then uses apply,  
which isn't very convenient either.  Users may also write their own  
query functions that utilize map-index and would have to reproduce  
this complex call to map-index syntax.

I propose a third alternative for map-index:

(defun map-index (fn index &key start end first last)
    ...)

Where first and last are booleans that override any values in start  
and end and mean the first value and last value in the ordered  
index.  Thus our implementation becomes:

(defun get-instances-by-range (class slot start end)
   ...
   (map-index #'collector slot-index :start start :end end :first  
(null start) :last (null start)))

or to use :first and :last

(defun get-instances-by-range (class slot start end)
   ...
   (map-index #'collector slot-index :start start :end end :first (eq  
start :first) :last (eq end :last)))

What do you think about the map-index interface and what should we do  
about first and last range queries in get-instances-by-range?

One alternative is to also add :first and :last keywords to get- 
instances-by-range so we don't introduce any special values to the  
arguments start and end.

Ian

On Mar 21, 2007, at 1:58 PM, Henrik Hjelte wrote:

> Great work.
> It seems that one of my changes yesterday introduced a bug, so Ian  
> fixed
> that bug and my change disappeared in the process. It suits me right,
> because I really should have made a testcase showing the bug before
> fixing it. Better later than never though.
>
> I modify the test indexing-basic in testindexing.lisp:
> (get-instances-by-value 'idx-one 'slot1 nil) should return zero
> instances, right? Now it returns three which is wrong.
>
> I had to modify the map-index method in collections.lisp some more to
> get this right without breaking other tests. Get-instances-by-value
> calls collections with start equal to end, so I do a special check for
> this, and that also makes it possible to use the cursor-pset function
> instead of cursor-pset-range which could be a speedup at least in
> theory.
>
> /Henrik Hjelte
>
> Changes:
> {
> hunk ./tests/testindexing.lisp 101
> -               (length (get-instances-by-range 'idx-one 'slot1 n (+ 1
> n))))
> +               (length (get-instances-by-range 'idx-one 'slot1 n (+ 1
> n)))
> +                (length (get-instances-by-value 'idx-one 'slot1  
> nil)))
> hunk ./tests/testindexing.lisp 104
> -  3 2 1 t 3)
> +  3 2 1 t 3 0)
> hunk ./src/elephant/collections.lisp 377
> -                          (next-range))))))
> +                          (next-range)))))
> +                 (same-start-and-end ()
> +                   (when (and start-supplied-p end-supplied-p)
> +                     (or (and (null start) (null end))
> +                         (and start end (lisp-compare<= start end)
> (lisp-compare<= end start))))))
> hunk ./src/elephant/collections.lisp 384
> -             (if (and start-supplied-p (not (null start)))
> -                 (cursor-pset-range cur start)
> -                 (cursor-pfirst cur))
> +              (cond
> +                ((same-start-and-end)
> +                 (cursor-pset cur start))
> +                ((and start-supplied-p (not (null start)))
> +                 (cursor-pset-range cur start))
> +                (t (cursor-pfirst cur)))
> }
>
> The whole new map-index method:
>
> (defmethod map-index (fn (index btree-index) &rest args &key (start  
> nil
> start-supplied-p) (end nil end-supplied-p))
>   "Like map-btree, but takes a function of three arguments key, value
> and primary key
>    if you want to get at the primary key value, otherwise use map- 
> btree"
>   (declare (dynamic-extent args)
> 	   (ignorable args))
>   (let ((sc (get-con index)))
>     (ensure-transaction (:store-controller sc)
>       (with-btree-cursor (cur index)
> 	(labels ((next-range ()
> 		   (multiple-value-bind (exists? skey val pkey) (cursor-pnext-nodup
> cur)
> 		     (if (and exists?
> 			      (or (not end-supplied-p)
> 				  (null end)
> 				  (lisp-compare<= skey end)))
> 		       (progn
> 			 (funcall fn skey val pkey)
> 			 (next-in-range skey))
> 		       (return-from map-index nil))))
> 		 (next-in-range (key)
> 		   (multiple-value-bind (exists? skey val pkey) (cursor-pnext-dup  
> cur)
> 		     (if exists?
> 			 (progn
> 			   (funcall fn skey val pkey)
> 			   (next-in-range key))
> 			 (progn
> 			   (cursor-pset-range cur key)
> 			   (next-range)))))
>                  (same-start-and-end ()
>                    (when (and start-supplied-p end-supplied-p)
>                      (or (and (null start) (null end))
>                          (and start end (lisp-compare<= start end)
> (lisp-compare<= end start))))))
> 	  (declare (dynamic-extent next-range next-in-range))
> 	  (multiple-value-bind (exists? skey val pkey)
>               (cond
>                 ((same-start-and-end)
>                  (cursor-pset cur start))
>                 ((and start-supplied-p (not (null start)))
>                  (cursor-pset-range cur start))
>                 (t (cursor-pfirst cur)))
> 	    (if (and exists?
> 		     (or (not end-supplied-p)
> 			 (null end)
> 			 (lisp-compare<= skey end)))
> 		(progn
> 		  (funcall fn skey val pkey)
> 		  (next-in-range skey))
> 		nil)))))))
>
>
>
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel