--@ Version 2.0.4
--@ Author Luke
--@ Created 2001-1-23


--@ Description
-- Some list functions, implemented as movie script functions. 
-- Note that some functions modify the list passed in as a parameters. Others
-- return new news (leaving the original list untouched).

--@ Version History
-- 2.0.4 Added new pImpode function for 'imploding' propertyLists
-- 2.0.3 Changed the parameter check for implode so that it accepts propertyLists
-- 2.0.2 Fixed a bug with the explode function that would index out of range on empty strings

-- 2.0.1 Some of the utility functions had an unneccesary 'me' parameter in them (left over
-- from a previous version of the script). These were removed in this version

-- MODIFYING LISTS PASSED BY REFERENCE ----------------------------


on Flatten (aList, intoList)
  -- flattens a list into the second list
  mx = aList.count
  repeat with i = 1 to mx
    v = aList[i]
    if v.ilk = #List then Flatten(v, intoList)
    else intoList.add(v)
  end repeat
end

on ReverseSort (aList)
  -- reverse sorts the list passed in by reference
  sort(aList)
  ReverseList(aList)
end


on Randomise (aList)
  -- randomises the list passed in by reference
  mx = aList.count
  rList = []
  repeat with i = 1 to mx
    rList.addAt(random(i), aList[i])
  end repeat
  repeat with i = 1 to mx
    aList[i] = rList[i]
  end repeat 
end

on ReverseList (aList)
  -- Reverse sorts the list passed in by reference
  -- Adapted from some code originally posted online somewhere.
  -- Sorry, but I can't remember the original author (for credit)
  -- 
  mx = aList.count()
  Half = mx/ 2
  HalfPlus1 = mx+1
  ----
  lower = Half
  repeat while lower
    if lower mod 10 then
      upper = HalfPlus1-lower
      tmp = aList[lower]
      aList[lower] = aList[upper]
      aList[upper] = tmp
      lower = lower-1
    else
      repeat while lower
        upper = HalfPlus1-lower
        tmp = aList[lower]
        aList[lower] = aList[upper]
        aList[upper] = tmp
        tmp = aList[lower-1]
        aList[lower-1] = aList[upper+1]
        aList[upper+1] = tmp
        tmp = aList[lower-2]
        aList[lower-2] = aList[upper+2]
        aList[upper+2] = tmp
        tmp = aList[lower-3]
        aList[lower-3] = aList[upper+3]
        aList[upper+3] = tmp
        tmp = aList[lower-4]
        aList[lower-4] = aList[upper+4]
        aList[upper+4] = tmp
        tmp = aList[lower-5]
        aList[lower-5] = aList[upper+5]
        aList[upper+5] = tmp
        tmp = aList[lower-6]
        aList[lower-6] = aList[upper+6]
        aList[upper+6] = tmp
        tmp = aList[lower-7]
        aList[lower-7] = aList[upper+7]
        aList[upper+7] = tmp
        tmp = aList[lower-8]
        aList[lower-8] = aList[upper+8]
        aList[upper+8] = tmp
        tmp = aList[lower-9]
        aList[lower-9] = aList[upper+9]
        aList[upper+9] = tmp
        lower = lower-10
      end repeat
    end if
  end repeat
end


on Splice (aList, startIndx, howMany, elements)
  -- aList: the list to modify
  -- start: index at which to start
  -- howMany: how many items to remove [0 -> n]
  -- elements: new elememts to insert at startPoint
  mx = aList.count
  startIndx = Min(startIndx, mx)
  
  if howMany > 0 then 
    -- remove the old entries
    finishIndx = Min(startIndx + howMany-1, mx)
    repeat with i = finishIndx down to startIndx
      aList.deleteAt(startIndx)
    end repeat
  end if
  --  now add the new
  c = elements.count()
  repeat with t = c down to 1
    aList.addAt(startIndx, elements[t])
  end repeat
  
end

-- GET NEW (MODIFIED) LISTS ----------------------------

on GrepList (aList, aFilter, controlObj)
  -- Returns a new list derived by filtering an existing one.
  -- If controlObj is specified, the filter is assumed to be a 
  -- method name. Otherwise the filter is assumed to be either 
  -- a built in lingo function or movieScript function that 
  -- returns a boolean result.
  --
  -- Example 1:
  --
  --   aList = [#a, 3.00, #foo, "1", #bar, VOID]
  --   put GrepList(aList, #SymbolP)
  --   -- [#a, #foo, #bar]
  --
  -- Example 2:
  -- 
  --   testObj = script("testObj").new()
  --   put GrepList(aList, #IsValid, testObj)
  --   -- where IsValid(v) is a method in testObj that does any
  --   -- test that returns true or false
  --
  --* aList - can be either a list or a PropertyList
  --* aFilter - is either a built in lingo function or movieScript function that returns a boolean result
  --* controlObj - object containing the filter method {optional}
  
  
  
  
  
  If aList.ilk = #PropList then 
    rList = [:]
    mx = aList.count 
    
    if controlObj.ilk = #Instance then 
      aFilter = symbol(aFilter)
      repeat with i = 1 to mx
        v = aList[i]
        f = call(aFilter, [controlObj], v)
        if (f = TRUE) then rList.addProp(aList.getPropAt(i), v)
      end repeat
    else
      f = 1
      repeat with i = 1 to mx
        ____v = aList[i]
        do ("f = " & aFilter & "(____v)")
        if (f = TRUE) then rList.addProp(aList.getPropAt(i),____v)
      end repeat
    end if
    
    
  else if aList.ilk = #List then 
    rList = []
    mx = aList.count 
    
    if controlObj.ilk = #Instance then 
      aFilter = symbol(aFilter)
      repeat with i = 1 to mx
        v = aList[i]
        f = call(aFilter, [controlObj], v)
        if (f = TRUE) then rList.add(v)
      end repeat
    else
      f = 1
      repeat with i = 1 to mx
        ____v = aList[i]
        do ("f = " & aFilter & "(____v)")
        if (f = TRUE) then rList.add(____v)
      end repeat
    end if
  end if
  return rList
end




on GetPropToList (aPropList)
  -- 'flattens' the property list into a linear list
  -- in the form [Prop, Value, Prop, Value ...]
  rList = []
  mx = aPropList.count
  repeat with i =1 to mx 
    rList.append(aPropList.getPropAt(i))
    rList.append(aPropList[i])
  end repeat
  return rList
end

on GetFlattened (aList)
  -- 'flattens' a list of lists into a single list, returning
  -- a new list
  mx = aList.count
  rList = []
  repeat with i = 1 to mx
    v = aList[i]
    if v.ilk = #List then Flatten(v, rList)
    else rList.add(v)
  end repeat
  return rList
end

on GetReverseSort (aList)
  -- returns a new reverse sorted copy of list
  rList = aList.duplicate()
  sort(rList)
  ReverseList(rList)
  return rList
end

on GetRandomised (aList)
  -- returns a new randomised copy of the list
  rList = []
  mx = aList.count
  repeat with i = 1 to mx
    rList.addAt(random(i), aList[i])
  end repeat
  return rList  
end


on GetSorted (aPropList)
  -- returns a new list sorted by value, maintaining prop/value pairs
  -- (lingo's sort() function sorts by property)
  tmp = [:]
  sort(tmp)
  mx = aProplist.count
  repeat with i = 1 to mx
    tmp.addProp(aProplist[i], aProplist.getPropAt(i))
  end repeat
  rList = [:]
  repeat with i = 1 to mx
    rList.addProp(tmp[i], tmp.getPropAt(i))
  end repeat
  return rList
end

on Slice (aList, startIndx, finishIndx)
  -- returns a 'slice' of the list, taken from the 
  -- start index to (and including) then last index
  mx = aList.count
  if voidP(finishIndx) then finishIndx = mx
  else finishIndx = Min(finishIndx, mx)
  startIndx = Min(startIndx, mx)
  if ilk(aList) = #propList then
    t = [:]
    repeat with t = startIndx to finishIndx
      t.addProp(aList.getPropAt(t), aList[t])
    end repeat
  else
    t = []
    repeat with t = startIndx to finishIndx
      t.add(aList[t])
    end repeat
  end if
  return t
end



-- OTHER USEFUL FUNCTIONS ----------------------------

on ListContains (aList, aStr)
  -- like 'getOne', but not case sensitive
  mx = aList.count
  repeat with i = 1 to mx
    if aList[i] = aStr then return i
  end repeat
  return 0
end

on Push (aList, aVal)
  -- push a value onto a list
  aList.append(aVal)
end


on CountAtoms (aList)
  --* returns the number of atoms contained within a list of lists
  flatList = []
  Flatten( aList, flatList )
  return (flatList.count)
end

on Pop (aList)
  -- pop the last value off the list
  --* returns the last value in a list, or VOID if the list is empty
  mx = aList.count()
  if mx then 
    lastVal = aList[mx]
    lastVal.deleteAt(mx)
    return lastVal
  end if
end

on GetRandomSequence (n, z, s)
  -- returns a list of numbers in a random order
  --* n is the number of numbers to generate (positive integer)
  --* z is the sequence step (default is 1)
  --* s is the starting value (default is 1)
  
  if voidP(z) then z = 1
  if voidp(s) then s = 1
  
  rList = []
  v = s
  repeat with i = 1 to n
    rList.addAt(random(i), v)
    v = v + z
  end repeat
  return rList  
end	

on Explode (aSeparator, aString)
  -- converts the string into a list, splitting the string
  -- using the supplied delimiter (the "delimiter" can be more 
  -- that one-char long)
  
  if aSeparator.ilk <> #String then aSeparator = RETURN
  if aString.ilk <> #String then return []
  
  rList = []
  delLength=length(aSeparator)
  if delLength = 0 then 
    return [aString]
  end if
  mx = aString.length
  if mx = 0 then 
    return []
  else
    p = offset(aSeparator, aString)
    repeat while p
      subStr = aString.char[1..p]
      delete the last char of subStr
      rList.add(subStr)
      aString = aString.char[p + delLength..length(aString)]
      p = offset(aSeparator, aString)
    end repeat
    if aString.length > 0 then 
      rList.add(aString.char[1..length(aString)])
    end if
    return rList
  end if
  
end

on Implode (glue, aList)
  -- Joins the list into a string, using the 'glue' as a separator
  
  if glue.ilk <> #string then glue = ""
  if NOT listP(aList) then return ""
  
  mx = aList.count - 1
  if mx < 0 then return ""
  rStr = ""
  repeat with i = 1 to mx
    if aList[i].ilk = #List then rStr = rStr & Implode(glue, aList[i]) &  glue
    else rStr = rStr & aList[i] & glue
  end repeat
  
  if aList[aList.count].ilk = #List then rStr = rStr & Implode(glue, aList[i])
  else rStr = rStr & aList[aList.count]
  return rStr
end	

on pImplode (glue, aListOrSecondGlue, aList)
  -- Joins the list into a string, using the 'glue' as a separator
  -- Optional second glue to join property - value pairs (default is ":")
  
  
  if glue.ilk <> #string then glue = ""
  if aListOrSecondGlue.ilk = #String then 
    -- second param is a glue, so use the third param
    glue2 = aListOrSecondGlue
    if (aList.ilk <> #propList) then return ""
    
  else 
    -- assume second param is the list
    glue2 = ":"
    if (aListOrSecondGlue.ilk = #propList) then aList = aListOrSecondGlue
    else return ""
    
  end if
  
  
  mx = aList.count - 1
  if mx < 0 then return ""
  rStr = ""
  repeat with i = 1 to mx
    p = aList.getPropAt(i)
    if aList[i].ilk = #List then rStr = rStr &  p & ":" & Implode(glue, aList[i]) &  glue
    else rStr = rStr  &  p & glue2 & aList[i] & glue
  end repeat
  p = aList.getPropAt(aList.count)
  if aList[aList.count].ilk = #List then rStr = rStr & Implode(glue, aList[i])
  else rStr = rStr  &  p & glue2 & aList[aList.count]
  return rStr
end	


on FindFirstPos (srcList, aVal)
  -- Returns the position in the srcList with the lowest value that is
  -- greater than the specified value (or return the last position in the
  -- list if the specified value is greater than the last value in 
  -- the list). Assumes the list is sorted.
  --
  -- eg FindFirstPos([1,22,33], 12) --> returns 2
  
  
  -- fast track 
  if srcList.count < 2 then return 1
  if aVal < srcList[1] then return 1
  if aVal > srcList[srcList.count] then return (srcList.count)
  
  -- otherwise search the list by repeatedly splitting the list in half 
  mx = srcList.count()
  midPos = mx / 2
  Prune = [1,MX]
  repeat while true
    -- prune the search
    if aVal >= srcList[midPos] then
      -- its in the right half
      Prune[1] = midPos
    else
      -- its in the left half
      Prune[2] = midPos
    end if
    srange = prune[2]-prune[1]
    if srange > 10 then 
      -- continue pruning
      midPos =  prune[1]+srange/2
    else
      -- search this group
      repeat with i = prune[1] to prune[2]
        if aVal < srcList[i] then return i
      end repeat
      return i
    end if
  end repeat
end

on  MergeLists (target, src)
  -- adds the src list into the targetList
  if (src.ilk =#PropList) and (target.ilk = #PropList) then 
    repeat with i = 1 to src.count
      k= src.getPropAt(i)
      target[k]= src[i]
    end repeat
  end if
end