sort_hierarchy.nim

import game_types, registry, storage

# proc `>`(game: var Game; x, y: Entity): bool =
#    template hierX: untyped = game.hierarchy[x]
#    template hierY: untyped = game.hierarchy[y]
#
#    hierY.parent == x or hierX.next == y or
#       (hierX.parent != y and hierY.next != x) and
#       (hierX.parent < hierY.parent or (hierX.parent == hierY.parent and hierX < hierY)))

proc less(game: Game; x, y: Entity): bool

proc less(game: Game; x, y: Hierarchy): bool =
   less(game, x.head, y.head) and less(game, x.next, y.next) and less(game, x.parent, y.parent)

proc less(game: Game; x, y: Entity): bool =
   template hierX: untyped = game.hierarchy[x]
   template hierY: untyped = game.hierarchy[y]

   hierX.parent == y or hierY.next == x or (hierY.parent != x and hierX.next != y and
         (less(game, hierY.parent, hierX.parent) or (hierY.parent == hierX.parent and less(game, hierY, hierX))))

# proc swap*[T](s: var Storage[T], x, y: Entity) =
#    let xIndex = x.index
#    let packedXIndex = s.sparseToPacked[xIndex]
#    let yIndex = y.index
#    let packedYIndex = s.sparseToPacked[yIndex]
#    if packedXIndex != invalidId.EntityImpl and
#          packedYIndex != invalidId.EntityImpl:
#       s.sparseToPacked[xIndex] = packedYIndex
#       s.sparseToPacked[yIndex] = packedXIndex
#       swap(s.packed[packedXIndex], s.packed[packedYIndex])
#       swap(s.packedToSparse[packedXIndex], s.packedToSparse[packedYIndex])

proc sort[T](game: Game; s: var Storage[T]) =
   for i in 1 ..< len(s):
      let x = s.packedToSparse[i]
      var j = i - 1
      while j >= 0 and less(game, x, s.packedToSparse[j]):
         let jIndex = s.packedToSparse[j]
         s.sparseToPacked[s.packedToSparse[j + 1]] = s.sparseToPacked[jIndex]
         s.packedToSparse[j + 1] = s.packedToSparse[j]
         s.packed[j + 1] = s.packed[j]
         dec(j)
      s.sparseToPacked[s.packedToSparse[j + 1]] = x
      s.packedToSparse[j + 1] = x
      s.packed[j + 1] = s.packed[i]