How to find the nearest interval of two items in a collection? about fset HOT 6 CLOSED

Here is an attempt (I'm still interested in your expertise!).

(defun interval-search (seq value &key (key #'identity))
  "Search members of SEQ for an interval containing VALUE. Return two
values being the boundary elements of the interval found, one value on
an exact match, or NIL otherwise."
  (labels ((rec (low high)
             (cond
              ((eq (- low high) 1)
               (values (fset:@ seq high)
                       (fset:@ seq low)))
              ((< high low)
               nil)
              (t
               (let* ((mid (floor (/ (+ low high) 2)))
                      (mid-value (funcall key (fset:@ seq mid))))
                  (case (fset:compare mid-value value)
                    (:greater (rec low (- mid 1)))
                    (:less    (rec (+ mid 1) high))
                    (t        (fset:@ seq mid))))))))
    (unless (fset:empty? seq)
      (rec 0 (- (fset:size seq) 1)))))

from fset.

There's an existing operation 'rank' that will do what you need. Put your
values in a map, and then call 'rank' to find the nearest key. Use
'at-rank' to extract the key/value pairs of that and the previous rank, as
appropriate.

(It annoys me that I defined 'rank' to return the higher index rather than
the lower one in the case of a miss; returning the lower one would have
been more natural. But I don't think I should risk breaking users' code by
changing it now.)

-- Scott

On Fri, Mar 21, 2014 at 2:59 AM, Camille Troillard <[email protected]

wrote:

Here is an attempt (I'm still interested in your expertise!).

(defun interval-search (seq value &key (key #'identity))
"Search members of SEQ for an interval containing VALUE. Return twovalues being the boundary elements of the interval found, one value onan exact match, or NIL otherwise."
(labels ((rec (low high)
(cond
((eq (- low high) 1)
(values (fset:@ seq high)
(fset:@ seq low)))
((< high low)
nil)
(t
(let* ((mid (floor (/ (+ low high) 2)))
(mid-value (funcall key (fset:@ seq mid))))
(case (fset:compare mid-value value)
(:greater (rec low (- mid 1)))
(:less (rec (+ mid 1) high))
(t (fset:@ seq mid))))))))
(unless (fset:empty? seq)
(rec 0 (- (fset:size seq) 1)))))

Reply to this email directly or view it on GitHubhttps://github.com//issues/5#issuecomment-38261919
.

from fset.

Thanks Scott!
I will have a look at RANK.

from fset.

Just an additional comment:
RANK is internal to the FSET package, so I don't believe it is much used.
I guess you could change it in a future release, don't you think?

from fset.

Ah, I never exported RANK or AT-RANK; alas, that probably means I never
tested them very much either. If you could code-review and/or test them,
that would be great.

Nonetheless, since RANK wasn't exported, as you suggest I feel free to
tweak its interface. I have done so, and exported both symbols.

-- Scott

On Fri, Mar 21, 2014 at 1:23 PM, Camille Troillard <[email protected]

wrote:

Just an additional comment:
RANK is internal to the FSET package, so I don't believe it is much used.
I guess you could change it in a future release, don't you think?

Reply to this email directly or view it on GitHubhttps://github.com//issues/5#issuecomment-38319850
.

from fset.

The updated version works fine, thank you for making this adjustment!

from fset.