From: Kent M Pitman
Subject: Re: newbie Q: insertion into sorted list
Date: 
Message-ID: <sfwu24t919w.fsf@world.std.com>
"James Goodzeit" <········@email.msn.com> writes:

> Is there any Lisp primitives or nifty functions for inserting a key to the
> right place in a sorted list---using something like (sort (cons x l)) seems
> it will be extravagantly wasteful. also what would how would i do something
> like
> 
> (position-if 4 '(1 3 5 7) :test #'<) ; bogus
> ==>2
> 
> in Allegro Common Lisp?

I'd worry that this was a classroom exercise, but since my reply
contains heavy use of LOOP and since teachers mostly reject LOOP, I
won't fret too much.  For small generic problems of this kind, it's
best to identify clearly that it either is or is not homework,
though...

These aren't heavily tested.  Note, btw, that if you're inserting into a
sorted vector, the way you'd do it is quite different since you can use
binary search to get there, but you have to shuffle a whole line of elements
down the row if you need to do an insert.  (The reason I mention this is that
POSITION is a function that takes either lists or vectors, interchangeably,
but the function you're asking about really oughtn't.)

(defun sorted-position (item list &key (less-test #'<) (equal-test #'=))
  ;; Primary value is the position the new item belongs at.
  ;; Secondary value is the tail whose cdr contains the position, or NIL
  ;; if no such position.
   (loop with prev = nil
         for position from 0
         for tail on list
         for elt = (first tail)
         when (or (funcall less-test item elt) (funcall equal-test item elt))
           do (return (values position prev))
         do (setq prev tail)
       finally (return (values position prev))))

(defun insert-sorted (item list &key (less-test #'<) (equal-test #'=))
  ;; Don't call this function on anything where anyone points into the
  ;; backbone of the argument LIST, since this will recycle the individual
  ;; vertebrae during splicing.
  (multiple-value-bind (position prev)
     (sorted-position item list :less-test less-test :equal-test equal-test)
    (let ((tail (cdr prev)))
      (if tail
          (destructuring-bind (first . rest) tail
             (unless (funcall equal-test item first) ;already present?
               (setf (car tail) item)
               (setf (cdr tail) (cons first rest))))
         ;; no tail means this is going at the end
         (if prev ; there IS something before us
             (setf (cdr prev) (cons item '()))
             ;; otherwise - nothing before us so this goes first
             (setq list (cons item list)))))) ;i.e., (push item list)
    ;; Return the given list, whose value OR structure may have been modified
    list)

I did some light testing on these, but the rest is up to you.
Note that this is subject to the "delete bug" (see the www.alu.org faq
page if you don't know what that is); you have to call insert-sorted
for value, never just for effect, in case the list is empty.

I guess Java would do this with a class argument instead of two keys, since
both keys have to change in lockstep (i.e., either you want < and =, or 
string-lessp and string-equal, or string< and string=).  We should think
about coming up with a similar concept to that for Lisp.

From: Chris Riesbeck
Subject: Re: newbie Q: insertion into sorted list
Date: 
Message-ID: <riesbeck-E76E78.11110116032001@news.acns.nwu.edu>
In article <···············@world.std.com>, Kent M Pitman 
<······@world.std.com> wrote:

>I guess Java would do this with a class argument instead of two keys, since
>both keys have to change in lockstep (i.e., either you want < and =, or 
>string-lessp and string-equal, or string< and string=).  We should think
>about coming up with a similar concept to that for Lisp

Why not just use < and define x = y as not x < y and not y < x ?
From: James Goodzeit
Subject: Re: newbie Q: insertion into sorted list
Date: 
Message-ID: <emMIAIkrAHA.295@cpmsnbbsa09>
"Kent M Pitman" <······@world.std.com> wrote ...
> I'd worry that this was a classroom exercise, but since my reply
> contains heavy use of LOOP and since teachers mostly reject LOOP, I
> won't fret too much.  For small generic problems of this kind, it's
> best to identify clearly that it either is or is not homework,
> though...


Not part of an exercise. I decided to be a maverick and take an AI course
ignoring the Lisp prerequisite -- and am now paying the price. Anyway my
university (SUNY/Buffalo) has a pretty stringent Academic dishonesty policy
so it would be pretty stupid to attempt to pull something off in a public
forum--not that I would ever consider cheating in the first place. This (and
the other hitherto unanswered format) question are simply about information
I cannot find (or am unable to figure out) in any of my reference materials.

Thanks for your help and best regards
James Goodzeit