.. highlight:: python
    :linenothreshold: 10

.. highlight:: c
    :linenothreshold: 10

.. toctree::
    :maxdepth: 2

.. _skiplist-test-notes-label:

===============================================
Some Notes on Testing
===============================================

-----------------------------------------------
Test Code
-----------------------------------------------

There are several areas of test code:

* C++ functional tests.
* C++ performance tests.
* Python functional tests.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
C++ Functional Tests.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The functional tests are run with a debug build of the C++ binary. In a debug build every operation on a skip list is checked before and afterwards with an integrity check. These integrity checks are thorough but expensive, see ``template <typename T> IntegrityCheck HeadNode<T>::lacksIntegrity() const`` in *HeadNode.h* for what checks are done.

Running these tests is as follows:

.. code-block:: sh

    $ cd src/cpp
    $ make debug
    $ ./SkipList_D.exe
    Running skip list tests...
                     test_very_simple_insert(): PASS
                          test_simple_insert(): PASS
                 test_insert_and_remove_same(): PASS
                 test_insert_remove_multiple(): PASS
                           test_ins_rem_rand(): PASS
                  test_insert_n_numbers_same(): PASS
                                     test_at(): PASS
    ...
                    doc_insert_remove_repeat(): PASS
    Final result: PASS
    Exec time: 19.5811 (s)
    Bye, bye!

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
C++ Performance Tests.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Running the release version of the C++ code introduces some performance tests where the results are sent to stdout.

.. code-block:: sh

    $ cd src/cpp
    $ make release
    $ ./SkipList_R.exe
    Running skip list tests...
                     test_very_simple_insert(): PASS
                          test_simple_insert(): PASS
                 test_insert_and_remove_same(): PASS
                 test_insert_remove_multiple(): PASS
                           test_ins_rem_rand(): PASS
                  test_insert_n_numbers_same(): PASS
                                     test_at(): PASS
                   perf_single_insert_remove(): 451.554 (ms) rate x.xe+06 /s
                                                        ...
                perf_roll_med_odd_index_wins(): vectors length:  1000000 window width: 524288 time: x.x (ms)
                                perf_size_of(): size_of(       1):      216 bytes ratio:      216 /sizeof(T):       x
    ...
                    doc_insert_remove_repeat(): PASS
    Final result: PASS
    Exec time: 127.5 (s)
    Bye, bye!

This data is scraped from stdout to describe the :ref:`performance-label`


^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Python Functional Tests.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

There are some tests for the Python API in *tests/*. One of the reasons for creating a Python API was to use the most excellent `Hypothesis <https://github.com/HypothesisWorks/hypothesis-python>`_ to test the underlying C++ code.

.. _testing_a_probabilistic_structure:

-----------------------------------------------
Testing a Probabilistic Structure
-----------------------------------------------

One problem with probabilistic data structures like a skip list is deterministic testing. Along the way you discover particular corner cases that are worthy of testing the implementation against. Each case is completely prescribed by the order of insertion and the order of head/tail results generated by the virtual coin toss function. Whilst the former can be controlled by the test case the latter depends on the state of the pseudo random number generator and there lies the problem.

In this project this is solved in a novel way by seeding the random number generator with a value and seeing what head/tail sequence results. The random number generator is then brute forced with different seeds until every possible head/tail sequence of a certain length is obtained. A map is constructed that has ``{sequence : seed, ...}`` which can be use by any test to find the seed that will create the desired sequence. The random number generator is seeded with that value and the test is now deterministic.

The function that creates a dictionary is ``find_seeds_for_sequences()`` in *tests/unit/seed_tree.py*. It is tested in *tests/unit/test_seed_tree.py*. You can see it at work in *tests/unit/test_cSkipList.py* where ``SEED_DICT`` is created using the C ``rand()`` function exposed through ``cSkipList.seed_rand()`` and ``cSkipList.toss_coin()``. There are various tests in there that specify a sequence of coin tosses and inject nodes that require that sequence.