tlists.nim

discard """
  matrix: "--mm:refc; --mm:orc"
  targets: "c js"
"""

import std/[lists, sequtils]
import std/assertions

const
  data = [1, 2, 3, 4, 5, 6]


template main =
  block SinglyLinkedListTest1:
    var L: SinglyLinkedList[int]
    for d in items(data): L.prepend(d)
    for d in items(data): L.add(d)
    doAssert($L == "[6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6]")

    doAssert(4 in L)

  block SinglyLinkedListTest2:
    var L: SinglyLinkedList[string]
    for d in items(data): L.prepend($d)
    doAssert($L == """["6", "5", "4", "3", "2", "1"]""")

    doAssert("4" in L)


  block DoublyLinkedListTest1:
    var L: DoublyLinkedList[int]
    for d in items(data): L.prepend(d)
    for d in items(data): L.add(d)
    L.remove(L.find(1))
    doAssert($L == "[6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6]")

    doAssert(4 in L)

  block SinglyLinkedRingTest1:
    var L: SinglyLinkedRing[int]
    L.prepend(4)
    doAssert($L == "[4]")
    L.prepend(4)

    doAssert($L == "[4, 4]")
    doAssert(4 in L)


  block DoublyLinkedRingTest1:
    var L: DoublyLinkedRing[int]
    L.prepend(4)
    doAssert($L == "[4]")
    L.prepend(4)

    doAssert($L == "[4, 4]")
    doAssert(4 in L)

    L.add(3)
    L.add(5)
    doAssert($L == "[4, 4, 3, 5]")

    L.remove(L.find(3))
    L.remove(L.find(5))
    L.remove(L.find(4))
    L.remove(L.find(4))
    doAssert($L == "[]")
    doAssert(4 notin L)

  block tlistsToString:
    block:
      var l = initDoublyLinkedList[int]()
      l.add(1)
      l.add(2)
      l.add(3)
      doAssert $l == "[1, 2, 3]"
    block:
      var l = initDoublyLinkedList[string]()
      l.add("1")
      l.add("2")
      l.add("3")
      doAssert $l == """["1", "2", "3"]"""
    block:
      var l = initDoublyLinkedList[char]()
      l.add('1')
      l.add('2')
      l.add('3')
      doAssert $l == """['1', '2', '3']"""

  # Copied here until it is merged into sequtils
  template take(a: untyped, max: int): untyped =
    type T = typeof(block: (for ai in a: ai))
    var ret: seq[T]
    var i = 0
    if max > 0:
      for ai in a:
        ret.add ai
        i.inc
        if i >= max: break
    ret

  template testCommon(initList, toList) =

    block: # toSinglyLinkedList, toDoublyLinkedList
      let l = seq[int].default
      doAssert l.toList.toSeq == []
      doAssert [1].toList.toSeq == [1]
      doAssert [1, 2, 3].toList.toSeq == [1, 2, 3]

    block copy:
      doAssert array[0, int].default.toList.copy.toSeq == []
      doAssert [1].toList.copy.toSeq == [1]
      doAssert [1, 2].toList.copy.toSeq == [1, 2]
      doAssert [1, 2, 3].toList.copy.toSeq == [1, 2, 3]
      type Foo = ref object
        x: int
      var f0 = Foo(x: 0)
      let f1 = Foo(x: 1)
      var a = [f0].toList
      var b = a.copy
      b.add f1
      doAssert a.toSeq == [f0]
      doAssert b.toSeq == [f0, f1]
      f0.x = 42
      doAssert a.head.value.x == 42
      doAssert b.head.value.x == 42

    block: # add, addMoved
      block:
        var
          l0 = initList[int]()
          l1 = [1].toList
          l2 = [2, 3].toList
          l3 = [4, 5, 6].toList
        l0.add l3
        l1.add l3
        l2.addMoved l3
        doAssert l0.toSeq == [4, 5, 6]
        doAssert l1.toSeq == [1, 4, 5, 6]
        doAssert l2.toSeq == [2, 3, 4, 5, 6]
        doAssert l3.toSeq == []
        l2.add l3 # re-adding l3 that was destroyed is now a no-op
        doAssert l2.toSeq == [2, 3, 4, 5, 6]
        doAssert l3.toSeq == []
      block:
        var
          l0 = initList[int]()
          l1 = [1].toList
          l2 = [2, 3].toList
          l3 = [4, 5, 6].toList
        l3.addMoved l0
        l2.addMoved l1
        doAssert l3.toSeq == [4, 5, 6]
        doAssert l2.toSeq == [2, 3, 1]
        l3.add l0
        doAssert l3.toSeq == [4, 5, 6]
      block:
        var c = [0, 1].toList
        c.addMoved c
        doAssert c.take(6) == [0, 1, 0, 1, 0, 1]

    block: # prepend, prependMoved
      block:
        var
          l0 = initList[int]()
          l1 = [1].toList
          l2 = [2, 3].toList
          l3 = [4, 5, 6].toList
        l0.prepend l3
        l1.prepend l3
        doAssert l3.toSeq == [4, 5, 6]
        l2.prependMoved l3
        doAssert l0.toSeq == [4, 5, 6]
        doAssert l1.toSeq == [4, 5, 6, 1]
        doAssert l2.toSeq == [4, 5, 6, 2, 3]
        doAssert l3.toSeq == []
        l2.prepend l3 # re-prepending l3 that was destroyed is now a no-op
        doAssert l2.toSeq == [4, 5, 6, 2, 3]
        doAssert l3.toSeq == []
      block:
        var
          l0 = initList[int]()
          l1 = [1].toList
          l2 = [2, 3].toList
          l3 = [4, 5, 6].toList
        l3.prependMoved l0
        l2.prependMoved l1
        doAssert l3.toSeq == [4, 5, 6]
        doAssert l2.toSeq == [1, 2, 3]
        l3.prepend l0
        doAssert l3.toSeq == [4, 5, 6]
      block:
        var c = [0, 1].toList
        c.prependMoved c
        doAssert c.take(6) == [0, 1, 0, 1, 0, 1]

    block remove:
      var l = [0, 1, 2, 3].toList
      let
        l0 = l.head
        l1 = l0.next
        l2 = l1.next
        l3 = l2.next
      l.remove l0
      doAssert l.toSeq == [1, 2, 3]
      l.remove l2
      doAssert l.toSeq == [1, 3]
      l.remove l2
      doAssert l.toSeq == [1, 3]
      l.remove l3
      doAssert l.toSeq == [1]
      l.remove l1
      doAssert l.toSeq == []
      # Cycle preservation
      var a = [10, 11, 12].toList
      a.addMoved a
      doAssert a.take(6) == @[10, 11, 12, 10, 11, 12]
      a.remove a.head.next
      doAssert a.take(6) == @[10, 12, 10, 12, 10, 12]
      a.remove a.head
      doAssert a.take(6) == @[12, 12, 12, 12, 12, 12]

  testCommon initSinglyLinkedList, toSinglyLinkedList
  testCommon initDoublyLinkedList, toDoublyLinkedList

  block remove: # return value check
    var l = [0, 1, 2, 3].toSinglyLinkedList
    let n = l.head.next.next
    doAssert l.remove(n) == true
    doAssert l.toSeq == [0, 1, 3]
    doAssert l.remove(n) == false
    doAssert l.toSeq == [0, 1, 3]
    doAssert l.remove(l.head) == true
    doAssert l.toSeq == [1, 3]
    doAssert l.remove(l.head.next) == true
    doAssert l.toSeq == [1]
    doAssert l.remove(l.head) == true
    doAssert l.toSeq == []
  
  block issue19297: # add (appends a shallow copy)
    var a: SinglyLinkedList[int]
    var b: SinglyLinkedList[int]

    doAssert a.toSeq == @[]
    a.add(1)
    doAssert a.toSeq == @[1]
    a.add(b)
    doAssert a.toSeq == @[1]
    a.add(2)
    doAssert a.toSeq == @[1, 2]
  
  block issue19314: # add (appends a shallow copy)
    var a: DoublyLinkedList[int]
    var b: DoublyLinkedList[int]

    doAssert a.toSeq == @[]
    a.add(1)
    doAssert a.toSeq == @[1]
    a.add(b)
    doAssert a.toSeq == @[1]
    a.add(2)
    doAssert a.toSeq == @[1, 2]

  block RemoveLastNodeFromSinglyLinkedList:
    var list = initSinglyLinkedList[string]()
    let n1 = newSinglyLinkedNode("sonic")
    let n2 = newSinglyLinkedNode("the")
    let n3 = newSinglyLinkedNode("tiger")
    let n4 = newSinglyLinkedNode("hedgehog")
    list.add(n1)
    list.add(n2)
    list.add(n3)
    list.remove(n3)
    list.add(n4)
    doAssert list.toSeq == @["sonic", "the", "hedgehog"]

static: main()
main()