/* NetRexx */
options replace format comments java crossref symbols nobinary

import java.util.List
import java.util.ArrayList

-- =============================================================================
/**
 * Permutation Iterator
 * <br />
 * <br />
 * Algorithm by E. W. Dijkstra, "A Discipline of Programming", Prentice-Hall, 1976, p.71
 */
class RPermutationIterator implements Iterator

  -- ---------------------------------------------------------------------------
  properties indirect
    perms = List
    permOrders = int[]
    maxN
    currentN
    first = boolean

  -- ---------------------------------------------------------------------------
  properties constant
    isTrue  = boolean (1 == 1)
    isFalse = boolean (1 \= 1)

  -- ---------------------------------------------------------------------------
  method RPermutationIterator(initial = List) public
    setUp(initial)
    return

  -- ---------------------------------------------------------------------------
  method RPermutationIterator(initial = Object[]) public
    init = ArrayList(initial.length)
    loop elmt over initial
      init.add(elmt)
      end elmt
    setUp(init)
    return

  -- ---------------------------------------------------------------------------
  method RPermutationIterator(initial = Rexx[]) public
    init = ArrayList(initial.length)
    loop elmt over initial
      init.add(elmt)
      end elmt
    setUp(init)
    return

  -- ---------------------------------------------------------------------------
  method setUp(initial = List) private
    setFirst(isTrue)
    setPerms(initial)
    setPermOrders(int[getPerms().size()])
    setMaxN(getPermOrders().length)
    setCurrentN(0)
    po = getPermOrders()
    loop i_ = 0 while i_ < po.length
      po[i_] = i_
      end i_
    return

  -- ---------------------------------------------------------------------------
  method hasNext() public returns boolean
    status = isTrue
    if getCurrentN() == factorial(getMaxN()) then status = isFalse
    setCurrentN(getCurrentN() + 1)
    return status

  -- ---------------------------------------------------------------------------
  method next() public returns Object
    if isFirst() then setFirst(isFalse)
    else do
      po = getPermOrders()
      i_ = getMaxN() - 1
      loop while po[i_ - 1] >= po[i_]
        i_ = i_ - 1
        end

      j_ = getMaxN()
      loop while po[j_ - 1] <= po[i_ - 1]
        j_ = j_ - 1
        end

      swap(i_ - 1, j_ - 1)

      i_ = i_ + 1
      j_ = getMaxN()
      loop while i_ < j_
        swap(i_ - 1, j_ - 1)
        i_ = i_ + 1
        j_ = j_ - 1
        end
      end
    return reorder()

  -- ---------------------------------------------------------------------------
  method remove() public signals UnsupportedOperationException
    signal UnsupportedOperationException()

  -- ---------------------------------------------------------------------------
  method swap(i_, j_) private
    po = getPermOrders()
    save   = po[i_]
    po[i_] = po[j_]
    po[j_] = save
    return

  -- ---------------------------------------------------------------------------
  method reorder() private returns List
    result = ArrayList(getPerms().size())
    loop ix over getPermOrders()
      result.add(getPerms().get(ix))
      end ix
    return result

  -- ---------------------------------------------------------------------------
  /**
   * Calculate n factorial: {@code n! = 1 * 2 * 3 .. * n}
   * @param n
   * @return n!
   */
  method factorial(n) public static
    fact = 1
    if n > 1 then loop i = 1 while i <= n
      fact = fact * i
      end i
    return fact

  -- ---------------------------------------------------------------------------
  method main(args = String[]) public static
    thing02 = RPermutationIterator(['alpha', 'omega'])
    thing03 = RPermutationIterator([String 'one', 'two', 'three'])
    thing04 = RPermutationIterator(Arrays.asList([Integer(1), Integer(2), Integer(3), Integer(4)]))
    things = [thing02, thing03, thing04]
    loop thing over things
      N = thing.getMaxN()
      say 'Permutations:' N'! =' factorial(N)
      loop lineCount = 1 while thing.hasNext()
        prm = thing.next()
        say lineCount.right(8)':' prm.toString()
        end lineCount
      say 'Permutations:' N'! =' factorial(N)
      say
      end thing
    return