Determining if a list is sorted

Date: Wed, 12 Nov 1997 11:24:47 -0800
From: "Terry R. Schussler" 
Subject: Determining if a particular list is sorted (sortP)

>Yes, I was referring to the "sorted" flag that Director evidently keeps - it
>is of course possible to have a list that is in fact arranged in ascending
>order, but is not flagged as "sorted".  This is especially important for
>functions like findposnear(), which only works correctly for a "sorted"
>list.  As noted, the add() function is another example of a function whose
>workings are altered by the "sorted" flag.
>
>I have experimented by timing successive sort commands on the same list, by
>the way, and it appears that sorting a list that is already sorted takes
>near-zero time - I guess Director is using it's "sorted" flag intelligently
>here.  (so if you need to guarantee that a list is sorted - such as to use
>findposnear(), just issue a sort command anyway - the time penalty is next
>to nothing if the list is already sorted.)
>
>And speaking of findposnear(), why is there no similar command for linear
>lists?  I've encountered many situations where I could've used that - I once
>implemented a modified binary search in lingo for just that purpose.
>
>[note that findposnear() works slightly differently than is documented in
>the manuals, returning the position of the equal or next greater value, not
>the "closest" value - this has been noted on direct-l before.  I actually
>find this more useful than the documented workings would be.]
>
>Jason Ettinger's idea of appending to a sorted list to toggle off the
>"sorted" flag is good, and of course sort() sets the flag - but I still
>think it would be nice to be able to test the flag.  Mind you, since sort()
>uses the flag intelligently, I can't think of a practical use for it at the
>moment...

-- this Lingo handler function examines a passed linear or property list
-- and return a boolean result as to whether the list is in a sorted state
-- written by Terry R. Schussler on 11/12/97
-- NOTE: Lists must have at least one value.
-- Empty lists will be considered sorted.

on sortP listArg
  -- we assume that ASCII 0 will always be sorted into the first position
  put numToChar(0) into firstPositionToken
  -- check the list type
  case (ilk(listArg)) of
    #list :  -- check a linear list's sorted state
      add listArg, firstPositionToken
      put getAt(listArg, 1) into firstEntry
    #propList : -- check a property list's sorted state
      addProp listArg, firstPositionToken, firstPositionToken
      put getPropAt(listArg, 1) into firstEntry
    otherwise
      -- the passed argument was NOT a list value
      return #ERR
  end case
  -- where our entry was added determines sort state
  if firstEntry = firstPositionToken then
    deleteAt listArg, 1
    return TRUE
  else
    deleteAt listArg, count(listArg)
    return FALSE
  end if
end sortP