-- UNIQUE KEY --
--
-- © June 2004 - October 2005, OpenSpark Interactive Ltd
--  <james.newton@openspark.com>
--
----------------------------------------------------------------------
-- 051023 JN: Script now accepts list with negative number key values
--
----------------------------------------------------------------------
-- This movie script allows you to traverse a list of property lists
-- where all the sub lists contain an key property whose value is a
-- positive integer.  It returns the lowest value for the key property
-- which is currently unused.
--
-- If negative numbers are used as keys, these will be converted to
-- positive numbers by adding the maxInteger + 1.  To create a unique
-- negative key, subtract (the maxInteger + 1) from the output.
-- Negative keys will start at -the maxInteger.
--
-- NOTE: The handlers contain no error checking.  Script errors will
-- occur if invalid argmuments are used.
--
-- SAMPLE:
-- put UniqueKey([[[#a:3],[#a:5],[#a:7]],[[#a:2],[#a:6],[#a:1]]],#a,1)
-- -- 4
----------------------------------------------------------------------



on UniqueKey(aNestedList, aKeyProp, aLevel) --------------------------
  -- INPUT: <aNestedList> must be a list of property lists.  At least
  --         one sublist must contain a property named <aKeyProp>,
  --         whose value must be an integer.
  --        <aKeyProp> must be the name of one of the properties in
  --         the sublists of aNestedList, whose value is an integer.
  --        <aLevel> must be a non-negative integer or VOID.
  -- OUTPUT: Returns an unused integer value of aKeyProp.  If aLevel
  --         is a positive integer, the search for values of aKeyProp
  --         will occur at that level of nesting.  If negative numbers
  --         are used, the maxInteger + 1 will be added.  To create
  --         a unique negative key, subtract (the maxInteger + 1) from
  --         the output.  Negative keys will start at -the maxInteger.
  --------------------------------------------------------------------
  
  tKeyList = []
  tTotal   = CountNestedItems(aNestedList, aLevel)
  
  if not tTotal then
    return 1
  end if
  
  AddPropValuesToList(aNestedList, aKeyProp, aLevel, tKeyList, tTotal)
  
  -- Find the first unclaimed value in tKeyList...
  tKey = tKeyList.getPos(0)
  if not tKey then
    -- ... or use the next available value
    tKey = tKeyList.count + 1
  end if
  
  return tKey
end UniqueKey



on CountNestedItems(aNestedList, aLevel) -----------------------------
  -- CALLED by UniqueKey() and recursively
  -- INPUT: <aNestedList> must be a list
  --        <aLevel> must be a non-negative integer, less than the
  --         minimum number of nested levels in aNestedList
  -- OUTPUT: Returns the number of items at aLevel in aNestedList
  --------------------------------------------------------------------
  
  i = aNestedList.count()
  
  if not aLevel then
    return i
  end if
  
  tTotal = 0 -- must be declared or Director will crash
  
  repeat while i
    tSubList = aNestedList[i]
    tTotal   = tTotal + CountNestedItems(tSubList, aLevel - 1)
    i = i - 1
  end repeat
  
  return tTotal
end CountNestedItems



on AddPropValuesToList(aNestedList,aKeyProp,aLevel,aKeyList,aTotal) --
  -- SENT BY UniqueKey() and recursively
  -- INPUT: <aNestedList> must be a list of lists.  If aLevel = 0 then
  --         the sub-list must be property lists, each of which must
  --         contain a property <aKeyProp>, whose value must be a
  --         non-zero integer.
  --        <aKeyProp> must be the name of one of the properties in
  --         the sublists of aNestedList, whose value is an integer.
  --        <aLevel> must be a non-negative integer, indicating how
  --         much deeper to go before checking for aKeyProp
  --         properties.
  --        <aKeyList> must be a linear list.  It will either be 
  --         empty or contain entries whose values are either 1 or 0.
  -- ACTION: Adds the value 1 to aKeyList at the position defined by
  --         value of the aKeyProp property in each of the property
  --         list at the given level... unless that value is greater
  --         than the total number of items.
  -- SAMPLE: [[#a: 3], [#a: 11], [#a: 7], [#a: 2], [#a: 5], [#a: 1]]
  --         => [1, 1, 1, 0, 1] --, 0, 1, 0, 0, 0, 1, 0, 1]
  --                2  3     5         7          11    13
  -- OUTPUT: Returns a list of 1s and 0s, with no more than aTotal
  --         items.
  --------------------------------------------------------------------
  
  tCount = aNestedList.count
  
  repeat with i = 1 to tCount
    tSubList = aNestedList[i]
    
    if aLevel then
      AddPropValuesToList(tSubList,aKeyProp,aLevel-1,aKeyList,aTotal)
      
    else
      -- We've tunneled down to the level we are interested in
      tKey = tSubList[aKeyProp]
      
      if stringP(tKey) then
        tKey = value(tKey)
      end if
      
      if integerP(tKey) then
        if tKey < 0 then
          -- Convert to a (non-unique) positive number
          tKey = tKey + the maxInteger + 1
        end if
        
        -- Indicate that this key value is taken
        if tKey > aTotal then
          -- There is no need to add tKey to aKeylist, since there is
          -- bound to be a lower value which has not been adopted.
        else
          aKeyList[tKey] = 1
        end if
      end if
    end if
  end repeat
end AddPropValuesToList