path: root/tests/benchmarks/fannkuch.nim

import os
import strutils

proc fannkuch (n: int): int =
    var 
        count: seq[int]
        maxFlips = 0
        m        = n-1
        r        = n
        check    = 0
        perm1: seq[int]
        perm:  seq[int]

    newSeq (count, n+1)
    newSeq (perm1, n)
    newSeq (perm, n)
    for i in 0 .. n-1:
        count[i] = i+1
        perm1[i] = i
        perm[i]  = i
    count[n] = n+1

    while True:
        if check < 30:
            for i in items (perm1):
                write (stdout, $(i+1))
            echo ("")
            inc (check)

        while r != 1:
            count[r-1] = r
            dec (r)

        if perm1[0] != 0 and perm1[m] != m:
            # perm = perm1
            # The above line is between 3 and 4 times slower than the loop below!
            for i in 0 .. n-1:
                perm[i] = perm1[i]
            var flipsCount = 0
            var k = perm[0]
            while k != 0:
                for i in 0 .. (k div 2):
                    swap (perm[i], perm[k-i])
                inc (flipsCount)
                k = perm[0]

            if flipsCount > maxFlips:
                maxFlips = flipsCount

        block makePerm:
            while r != n:
                var tmp = perm1[0]
                # # perm1.delete (0)
                # # perm1.insert (tmp, r)
                # # The above is about twice as slow as the following:
                # moveMem (addr (perm1[0]), addr (perm1[1]), r * sizeof (int))
                # The call to moveMem is about 50% slower than the loop below!
                for i in 0 .. r-1:
                    perm1[i] = perm1[i+1]
                perm1[r] = tmp
                
                dec (count[r])
                if count[r] > 0:
                    break makePerm
                inc (r)
            return maxFlips

var n = 10
echo ("Pfannkuchen(" & $n & ") = " & $fannkuch (n))