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@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
