nimdeque/tests/linked.nim

# Copyright 2022 Mattia Giambirtone
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#    http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
import stats
import times
import random
import strformat
import ../src/nimdeque


when isMainModule:
    const size = 5000
    const benchSize = 50000

    echo &"Running tests with queue of size {size}"
    var deque = newLinkedDeque[int]()
    var testStart = cpuTime()
    echo &"\t- Testing add()"
    for i in countup(0, size - 1, 1):
        deque.add(i)
    doAssert deque.len() == size

    echo "\t- Testing iteration"
    for i in countup(0, size - 1, 1):
        doAssert deque[i] == i
    for i, e in deque:
        doAssert i == e
    var j = 0
    for e in deque.reversed():
        doAssert size - j - 1 == e
        inc(j)
    for i, e in deque.reversedPairs():
        doAssert size - i - 1 == e

    echo "\t- Testing contains()"
    for i in countup(0, size - 1, 1):
        doAssert i in deque
    doAssert 48574857 notin deque
    doAssert -0xfffffff notin deque
    echo "\t- Testing pop(0)"
    doAssert deque.pop() == 0
    doAssert deque.len() == size - 1
    doAssert deque[0] == 1

    echo "\t- Testing pop(^1)"
    doAssert deque.pop(deque.high()) == size - 1
    doAssert deque.len() == size - 2
    doAssert deque[deque.high()] == size - 2

    echo "\t- Re-checking values"
    for i in countup(0, size - 3, 1):
        doAssert deque[i] == i + 1

    echo "\t- Testing addLeft()"
    deque.addLeft(0)
    doAssert deque.len() == size - 1
    doAssert deque[0] == 0

    echo "\t- Re-checking values"
    for i in countup(0, size - 2, 1):
        doAssert deque[i] == i

    echo "\t- Testing insert(3)"
    var oldLen = deque.len()
    deque.insert(3, 69420)
    doAssert oldLen + 1 == deque.len()
    doAssert deque.pop(3) == 69420
    doAssert deque.len() == oldLen

    echo &"\t- Testing insert({size - 2})"
    oldLen = deque.len()
    deque.insert(size - 2, 0x42362)
    doAssert oldLen + 1 == deque.len()
    doAssert deque.pop(size - 2) == 0x42362
    doAssert deque.len() == oldLen

    echo &"\t- Testing insert({size div 2})"
    oldLen = deque.len()
    deque.insert(size div 2, 0xf7102)
    doAssert oldLen + 1 == deque.len()
    doAssert deque.pop(size div 2) == 0xf7102
    doAssert deque.len() == oldLen

    randomize()
    let idx = rand(size - 1)
    echo &"\t- Testing insert({idx})"
    oldLen = deque.len()
    deque.insert(idx, 0xff)
    doAssert oldLen + 1 == deque.len()
    doAssert deque.pop(idx) == 0xff
    doAssert deque.len() == oldLen

    echo "\t- Testing backwards indeces"
    for i in countdown(deque.high(), 1):
        doAssert deque[^i] == deque[deque.len() - i]
    deque.add(deque.pop(^1))
    doAssert deque[deque.high()] == deque[^1]

    echo &"\t- Testing queue with maxSize {size div 2}"
    var queue = newLinkedDeque[int](size div 2)
    for i in countup(0, (size div 2) - 1):
        queue.add(i)
    doAssert queue.len() == size div 2
    var temp = queue[0]
    queue.add((size div 2) + 1)
    doAssert queue.len() == size div 2
    doAssert queue[^1] == (size div 2) + 1
    doAssert queue[0] == temp + 1
    queue.addLeft(0)
    doAssert queue.len() == size div 2
    doAssert queue[0] == 0
    doAssert queue[^1] == (size div 2) - 1

    echo "\t- Testing extend()"
    var old = deque.len()
    var s = @[1, 2, 3, 4, 5, 6]
    deque.extend(s)
    for i in countup(size + 5, deque.high()):
        doAssert deque[i] == s[i]
    doAssert old + len(s) == deque.len()

    echo "\t- Testing extendLeft()"
    old = deque.len()
    deque.extendLeft(s)
    for i in countup(0, 5):
        doAssert deque[i] == s[5 - i]

    echo "\t- Testing clear()"
    deque.clear()
    doAssert deque.len() == 0
    doAssertRaises(IndexDefect, echo deque[0])

    echo "\t- Testing equality"
    var 
        a = newLinkedDeque[int]()
        b = newLinkedDeque[int]()
    for i in countup(0, size - 1):
        a.add(i)
    # I could add to both a and b together
    # but ¯\_(ツ)_/¯ who cares
    b.extend(a)
    doAssert a == b

    echo "\t- Testing find()"
    for i in countup(0, size - 1):
        deque.add(i)
    doAssert deque.find(size - 1) == size - 1
    doAssert deque.find(0) == 0
    doAssert deque.find(size) == -1
    doAssert deque.find(size div 2) == size div 2
    echo &"Tests completed in {cpuTime() - testStart} seconds"