orderedstructs SkipList

https://skiplist.readthedocs.io/en/latest/
Admin
orderedstructs SkipList is a data structure implemented in C++ with Python bindings that behaves as...
Tokens:26,059
Snippets:287
Trust Score:9.6
Update:4 months ago
Show doc for...
Tokens:
Raw
### Install SkipList with GCC

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Install the SkipList package using setup.py when on a platform that uses GCC. This involves setting the USING_GCC environment variable.

```sh
USING_GCC=1 python setup.py develop
```

--------------------------------

### Install SkipList using pip

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Install the SkipList package from PyPi using pip. This is the recommended method for most users.

```sh
pip install orderedstructs
```

--------------------------------

### Install SkipList in development mode

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Install the SkipList package in development mode from a local source. This requires cloning the repository and running setup.py.

```sh
cd <skiplist>
pip install -r requirements.txt
python setup.py develop
```

--------------------------------

### Install SkipList for development

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Install the SkipList package in development mode using pip and setup.py. This is useful when working on the project's codebase.

```bash
cd <skiplist>
pip install -r requirements.txt
python setup.py develop

```

--------------------------------

### Install orderedstructs package

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Install the orderedstructs package using pip. This is the standard way to get the Python version of the SkipList.

```bash
$ pip install orderedstructs

```

--------------------------------

### Python Skip List Constructor Examples

Source: https://skiplist.readthedocs.io/en/latest/api.html

Shows how to instantiate the PySkipList class with different Python types such as int, float, and bytes.

```Python
import cSkipList

sl = cSkipList.PySkipList(int) # Python 3, for Python 2 use PySkipList(long)
sl = cSkipList.PySkipList(float)
sl = cSkipList.PySkipList(bytes) # In Python 2 PySkipList(str) also works
```

--------------------------------

### Set GCC environment variable for setup

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Set the USING_GCC environment variable before running setup.py develop if you are on a GCC platform. This helps fix some compilation warnings.

```bash
USING_GCC=1 python setup.py develop

```

--------------------------------

### Example .dot file structure for a Skip List

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

This is an example of the .dot file content generated by the Python interface, representing the structure of a skip list with inserted elements.

```dot
digraph SkipList {
label = "SkipList."
graph [rankdir = "LR"];
node [fontsize = "12" shape = "ellipse"];
edge [];

subgraph cluster0 {
style=dashed
label="Skip list iteration 0"

"HeadNode0" [
label = "{ 1 | <f2> 0x7f8a68d86280} | { 1 | <f1> 0x7f8a68d86280}"
shape = "record"
];
"HeadNode0":f1 -> "node00x7f8a68d86280":w1 [];
"HeadNode0":f2 -> "node00x7f8a68d86280":w2 [];

"node00x7f8a68d86280" [
label = " { <w2> 2 | <f2> 0x7f8a68d9dcc0 } | { <w1> 1 | <f1> 0x7f8a68d44ec0 } | <f0> 21"
shape = "record"
];
"node00x7f8a68d86280":f1 -> "node00x7f8a68d44ec0":w1 [];
"node00x7f8a68d86280":f2 -> "node00x7f8a68d9dcc0":w2 [];
"node00x7f8a68d44ec0" [
label = " { <w1> 1 | <f1> 0x7f8a68d9dcc0 } | <f0> 42"
shape = "record"
];
"node00x7f8a68d44ec0":f1 -> "node00x7f8a68d9dcc0":w1 [];
"node00x7f8a68d9dcc0" [
label = " { <w2> 1 | <f2> 0x0 } | { <w1> 1 | <f1> 0x0 } | <f0> 84"
shape = "record"
];
"node00x7f8a68d9dcc0":f1 -> "node00x0":w1 [];
"node00x7f8a68d9dcc0":f2 -> "node00x0":w2 [];

"node00x0" [label = "<w2> NULL | <w1> NULL" shape = "record"];
}

node0 [shape=record, label = "<f0> | ", style=invis, width=0.01];
node0:f0 -> HeadNode0 [style=invis];
}
```

--------------------------------

### Generate DOT file for a simple Skip List

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

Use `dotFile` and `dotFileFinalise` to output the current state of a skip list to stdout in DOT format. This example demonstrates creating a skip list and inserting five values.

```cpp
#include "SkipList.h"

void doc_insert_simple() {
   OrderedStructs::SkipList::HeadNode<int> sl;

   sl.insert(42);
   sl.insert(84);
   sl.insert(21);
   sl.insert(100);
   sl.insert(12);

   sl.dotFile(std::cout);
   sl.dotFileFinalise(std::cout);
}
```

--------------------------------

### C++ SkipList Thread Safety Example

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Illustrates how to use a C++ SkipList in a multi-threaded environment by sharing a SkipList head node across threads.

```cpp
#include <thread>
#include <vector>

#include "SkipList.h"

void do_something(OrderedStructs::SkipList::HeadNode<double> *pSkipList) {
    // Insert/remove items into *pSkipList
    // Read items inserted by other threads.
}

OrderedStructs::SkipList::HeadNode<double> sl;
std::vector<std::thread> threads;

for (size_t i = 0; i < thread_count; ++i) {
    threads.push_back(std::thread(do_something, &sl));
}
for (auto &t: threads) {
    t.join();
}
// The SkipList now contains the totality of the thread actions.
```

--------------------------------

### Basic C++ SkipList operations

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Demonstrates basic operations like insertion, checking for existence, getting size, accessing elements by index, and removing elements from a C++ SkipList.

```cpp
#include "SkipList.h"

// Declare with any type that has sane comparison.
OrderedStructs::SkipList::HeadNode<double> sl;

sl.insert(42.0);
sl.insert(21.0);
sl.insert(84.0);

sl.has(42.0) // true
sl.size()    // 3
sl.at(1)     // 42.0, throws OrderedStructs::SkipList::IndexError if index out of range

sl.remove(21.0); // throws OrderedStructs::SkipList::ValueError if value not present

sl.size()    // 2
sl.at(1)     // 84.0

```

--------------------------------

### Python Skip List Basic Operations

Source: https://skiplist.readthedocs.io/en/latest/api.html

Demonstrates basic operations like insertion, checking for existence, getting size, and accessing elements by index using the PySkipList class.

```Python
import cSkipList

sl = cSkipList.PySkipList(float)

sl.insert(42.0)
sl.insert(21.0)
sl.insert(84.0)

sl.has(42.0) # True
sl.size()    # 3
sl.at(1)     # 42.0

sl.has(42.0) # True
sl.size()    # 3
sl.at(1)     # 42.0, raises IndexError if index out of range

sl.remove(21.0); # raises ValueError if value not present

sl.size()    # 2
sl.at(1)     # 84.0
```

--------------------------------

### Python SkipList Testing

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Command to run basic Python SkipList tests using pytest. Requires pytest and hypothesis to be installed.

```sh
cd <skiplist>
pytest tests/
```

--------------------------------

### Basic Python SkipList operations

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Demonstrates basic operations like insertion, checking for existence, getting size, accessing elements by index, and removing elements from a Python SkipList with float values.

```python
import orderedstructs

# Declare with a type. Supported types are long/float/bytes/object.
sl = orderedstructs.SkipList(float)

sl.insert(42.0)
sl.insert(21.0)
sl.insert(84.0)

sl.has(42.0) # True
sl.size()    # 3
sl.at(1)     # 42.0, raises IndexError if index out of range

sl.remove(21.0) # raises ValueError if value not present

sl.size()    # 2
sl.at(1)     # 84.0

```

--------------------------------

### Worst-Case Skip List Example

Source: https://skiplist.readthedocs.io/en/latest/design.html

Depicts a mal-formed skip list that can result from unfortunate coin tosses or adversarial input, leading to degraded search performance (O(n)). This structure shows how connections can become linear.

```text
| 5 E |--| 8 0 |------------------------------------------------------->| NULL |
| 1 A |->| 1 B |--| 1 C |->| 1 D |->| 5 0 |---------------------------->| NULL |
| 1 A |->| 1 B |->| 1 C |->| 1 D |->| 1 E |->| 1 F |->| 1 G |->| 1 0 |->| NULL |
| HED |  |  A  |  |  B  |  |  C  |  |  D  |  |  E  |  |  F  |  |  G  |
```

--------------------------------

### Example Output of Rolling Median Calculation

Source: https://skiplist.readthedocs.io/en/latest/rolling_median.html

Shows the expected output when computing a rolling median with a window size of 3 on a numpy array from 0.0 to 9.0. The output includes initial NaN values corresponding to the window size.

```text
Original: [0. 1. 2. 3. 4. 5. 6. 7. 8. 9.]
  Result: [nan nan  1.  2.  3.  4.  5.  6.  7.  8.]

```

--------------------------------

### HeadNode::at (index, count, dest)

Source: https://skiplist.readthedocs.io/en/latest/api.html

Loads a vector with `count` values starting from the specified index. Throws `IndexError` if the range is out of bounds. Time complexity is O(count * log(n)).

```APIDOC
## HeadNode::at(size_t index, size_t count, std::vector<T> &dest) const

### Description
This loads a vector of type `T` with `count` values starting at the given index. This will throw an `IndexError` if the index + count is >= size of the skip list. This is O(count * log(n)) for well formed skip lists.

### Method
`void HeadNode::at(size_t index, size_t count, std::vector<T> &dest) const;`

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
* **index** (size_t) - The starting index.
* **count** (size_t) - The number of elements to retrieve.
* **dest** (std::vector<T>&) - The vector to load the elements into.
```

--------------------------------

### Build All C++ and Python Versions

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Run a build script to execute all C++ and Python tests, and build all currently supported Python versions.

```bash
cd <skiplist>
./build_all.sh

```

--------------------------------

### Build C++ Binary with CMake

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Build the C++ SkipList binary using CMake in release mode with parallel jobs.

```bash
cd <skiplist>
cake --build cmake-build-release --target SkipList -- -j 6

```

--------------------------------

### Run All C++ Tests (Release)

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Execute all C++ functional and performance tests using the Makefile in release mode.

```bash
cd <skiplist>/src/cpp
make release
./SkipList_R.exe

```

--------------------------------

### Build All Tests and Python Versions

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Run all C++ and Python tests and build all supported Python versions using the build script. This process can take a significant amount of time per Python version.

```sh
$ cd <skiplist>
$ ./build_all.sh
```

--------------------------------

### C++ SkipList Testing with Makefile (Release)

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Command to run all C++ functional and performance tests for a SkipList using the Makefile in release mode.

```sh
cd <skiplist>/src/cpp
make release
./SkipList_R.exe
```

--------------------------------

### Python SkipList with Custom Objects

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Shows how to use a Python SkipList with user-defined objects, defining custom ordering based on last name and first name.

```python
import functools

import orderedstructs

@functools.total_ordering
class Person:
    """Simple example of ordering based on last name/first name."""
    def __init__(self, first_name, last_name):
        self.first_name = first_name
        self.last_name = last_name

    def __eq__(self, other):
        try:
            return self.last_name == other.last_name \
                and self.first_name == other.first_name
        except AttributeError:
            return NotImplemented

    def __lt__(self, other):
        try:
            return self.last_name < other.last_name \
                or self.first_name < other.first_name
        except AttributeError:
            return NotImplemented
    
    def __str__(self):
        return '{}, {}'.format(self.last_name, self.first_name)

sl = orderedstructs.SkipList(object)

sl.insert(Person('Peter', 'Pan'))
sl.insert(Person('Alan', 'Pan'))
assert sl.size() == 2
assert str(sl.at(0)) == 'Pan, Alan' 
assert str(sl.at(1)) == 'Pan, Peter'
```

--------------------------------

### C++ SkipList Basic Operations

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Demonstrates basic insertion, checking for existence, size retrieval, and element access in a C++ SkipList.

```cpp
#include "SkipList.h"
        
    // Declare with any type that has sane comparison.
    OrderedStructs::SkipList::HeadNode<double> sl;
    
    sl.insert(42.0);
    sl.insert(21.0);
    sl.insert(84.0);
    
    sl.has(42.0) // true
    sl.size()    // 3
    sl.at(1)     // 42.0, throws OrderedStructs::SkipList::IndexError if index out of range

    sl.remove(21.0); // throws OrderedStructs::SkipList::ValueError if value not present
    
    sl.size()    // 2
    sl.at(1)     // 84.0
```

--------------------------------

### Import necessary libraries and utility function

Source: https://skiplist.readthedocs.io/en/latest/rolling_median.html

Imports required modules for multiprocessing, shared memory, typing, NumPy, and the orderedstructs package. Includes a utility function to get the data pointer of a NumPy array.

```Python
import multiprocessing
# Python 3.8+, need to be specific about importing this.
from multiprocessing import shared_memory
import typing

import numpy as np

import orderedstructs

def np_data_pointer(a: np.ndarray) -> int:
    """The address of the actual data. 'data pointer' in np.info()."""
    return a.__array_interface__["data"][0]
```

--------------------------------

### Run Thread-Safe C++ Tests (Release)

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Execute all C++ functional and performance tests for a thread-safe SkipList using the Makefile in release mode with thread support enabled.

```bash
cd <skiplist>/src/cpp
make release CXXFLAGS=-DSKIPLIST_THREAD_SUPPORT
./SkipList_R.exe

```

--------------------------------

### C++ SkipList Testing with CMake

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Commands to build and run C++ SkipList tests using CMake in release mode.

```sh
cd <skiplist>
cmake --build cmake-build-release --target SkipList -- -j 6
./cmake-build-release/SkipList
```

--------------------------------

### Compute Rolling Median (2D MP)

Source: https://skiplist.readthedocs.io/en/latest/rolling_median.html

Computes a rolling median for a 2D NumPy array using multiprocessing and shared memory. This function is intended for the parent process and handles the setup, task distribution, and result collection.

```python
def compute_rolling_median_2d_mp(
        read_array: np.ndarray,
        window_length: int, num_processes: int,
) -> np.ndarray:
    """Compute a rolling median of a numpy 2D array using
    multiprocessing and shared memory.
    This is the top level call and is run within the parent process.

    This returns a np.ndarray of the same shape as the input with the
    rolling medians.
    Rows of this up to the window_length will be NaN.
    """
    # Limit number of processes if the number of columns is small.
    if read_array.shape[1] < num_processes:
        num_processes = read_array.shape[1]
    with create_shared_memory_array_spec_close_unlink(
            read_array, copy_array=True,
    ) as read_array_spec:
        with create_shared_memory_array_spec_close_unlink(
                read_array, copy_array=False,
        ) as write_array_spec:
            # Create the tasks.
            tasks = []
            for column_index in range(read_array.shape[1]):
                tasks.append(
                    (read_array_spec, window_length, column_index, write_array_spec)
                )
            # Create the pool and apply the tasks.
            mp_pool = multiprocessing.Pool(processes=num_processes)
            pool_apply = [
                mp_pool.apply_async(
                    compute_rolling_median_2d_from_index, t
                ) for t in tasks
            ]
            _write_counts = [r.get() for r in pool_apply]
            write_array = copy_shared_memory_into_new_numpy_array(write_array_spec)
    return write_array
```

--------------------------------

### PySkipList.at_seq(index, count)

Source: https://skiplist.readthedocs.io/en/latest/api.html

Retrieves a tuple of `count` values starting from the specified `index`. Supports negative indices and requires `count` to be positive. Raises `IndexError` if the range is out of bounds. Time complexity is O(count * log(n)).

```APIDOC
## PySkipList.at_seq(index, count)

### Description
Retrieves a tuple of `count` values starting from the specified `index`. Supports negative indices and requires `count` to be positive. Raises `IndexError` if the range is out of bounds. Time complexity is O(count * log(n)) for well-formed skip lists.

### Method
GET (conceptual)

### Endpoint
N/A (Method call)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Parameters
- **index** (long) - Required - The starting index for retrieval. Negative indices are supported.
- **count** (long) - Required - The number of elements to retrieve. Must be positive.
```

--------------------------------

### Render .dot file to PNG using Graphviz

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

Use the `dot` command-line tool from Graphviz to convert a .dot file into a PNG image, visualizing the skip list structure.

```bash
dot -odoc_simple_py.png -Tpng doc_simple_py.dot
```

--------------------------------

### Generate DOT file for multiple Skip List snapshots during insertion

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

This C++ code demonstrates how to capture multiple snapshots of a skip list as values are inserted. It iterates from 0 to 7, inserting each value and writing the skip list's state to stdout after each insertion.

```cpp
#include "SkipList.h"

void doc_insert() {
   OrderedStructs::SkipList::HeadNode<int> sl;

   // Write out the empty head node
   sl.dotFile(std::cout);
   // Now insert a value and add the current representation to the DOT file
   for (int i = 0; i < 8; ++i) {
       sl.insert(i);
       sl.dotFile(std::cout);
   }
   // Finalise the dot file containing the snapshots.
   // This updates the internal references.
   sl.dotFileFinalise(std::cout);
}
```

--------------------------------

### Python SkipList Basic Operations with Floats

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Demonstrates basic insertion, checking for existence, size retrieval, and element access in a Python SkipList with float values.

```python
import orderedstructs

# Declare with a type. Supported types are long/float/bytes/object.
sl = orderedstructs.SkipList(float)

sl.insert(42.0)
sl.insert(21.0)
sl.insert(84.0)

sl.has(42.0) # True
sl.size()    # 3
sl.at(1)     # 42.0, raises IndexError if index out of range

sl.remove(21.0) # raises ValueError if value not present

sl.size()    # 2
sl.at(1)     # 84.0
```

--------------------------------

### Python SkipList with reverse object ordering

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Demonstrates how to create a reverse-ordered Python SkipList of custom objects by providing a custom comparison function to the SkipList constructor.

```python
# As above

sl = orderedstructs.SkipList(object, lambda x, y: y < x)

sl.insert(Person('Peter', 'Pan'))
sl.insert(Person('Alan', 'Pan'))
assert sl.size() == 2
assert str(sl.at(0)) == 'Pan, Peter'
assert str(sl.at(1)) == 'Pan, Alan'

```

--------------------------------

### Convert DOT file to PNG using dot command

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

This command-line instruction shows how to convert a DOT file generated by the skip list visualization methods into a PNG image using the GraphViz `dot` utility.

```bash
dot -odoc_simple.png -Tpng doc_simple.dot
```

--------------------------------

### C++ SkipList Testing with Makefile (Thread Safe)

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Command to run all C++ functional and performance tests for a thread-safe SkipList using the Makefile.

```sh
cd <skiplist>/src/cpp
make release CXXFLAGS=-DSKIPLIST_THREAD_SUPPORT
./SkipList_R.exe
```

--------------------------------

### Convert DOT file to PNG for multiple snapshots

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

This command-line instruction shows how to convert a DOT file containing multiple skip list snapshots into a PNG image using the GraphViz `dot` utility.

```bash
dot -odoc_insert.png -Tpng doc_insert.dot
```

--------------------------------

### Run Basic Python Tests

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Execute basic tests for the Python SkipList implementation using pytest.

```bash
cd <skiplist>
pytest tests/

```

--------------------------------

### Python SkipList with Custom Reverse Ordering

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Demonstrates how to achieve reverse ordering in a Python SkipList for custom objects by providing a custom comparison function.

```python
# As above

sl = orderedstructs.SkipList(object, lambda x, y: y < x)

sl.insert(Person('Peter', 'Pan'))
sl.insert(Person('Alan', 'Pan'))
assert sl.size() == 2
assert str(sl.at(0)) == 'Pan, Peter'
assert str(sl.at(1)) == 'Pan, Alan'
```

--------------------------------

### Skip List Structure Visualization

Source: https://skiplist.readthedocs.io/en/latest/design.html

Illustrates the multi-level linked list structure of a skip list, including head node, data nodes, and NULL termination. Shows node widths and references at different levels.

```text
| 5 E |------------------------------------->| 4 0 |------------------->| NULL |
| 1 A |->| 2 C |---------->| 2 E |---------->| 2 G |---------->| 2 0 |->| NULL |
| 1 A |->| 1 B |->| 1 C |->| 1 D |->| 1 E |->| 1 F |->| 1 G |->| 1 0 |->| NULL |
| HED |  |  A  |  |  B  |  |  C  |  |  D  |  |  E  |  |  F  |  |  G  |
```

--------------------------------

### Run C++ Performance Tests

Source: https://skiplist.readthedocs.io/en/latest/test_notes.html

Execute the C++ performance tests using a release build. This involves compiling the release version and running the executable to measure performance metrics and verify test results.

```bash
1$ cd src/cpp
2$ make release
3$ ./SkipList_R.exe
4Running skip list tests...
5                 test_very_simple_insert(): PASS
6                      test_simple_insert(): PASS
7             test_insert_and_remove_same(): PASS
8             test_insert_remove_multiple(): PASS
9                       test_ins_rem_rand(): PASS
10              test_insert_n_numbers_same(): PASS
11                                 test_at(): PASS
12               perf_single_insert_remove(): 451.554 (ms) rate x.xe+06 /s
13                                                    ...
14            perf_roll_med_odd_index_wins(): vectors length:  1000000 window width: 524288 time: x.x (ms)
15                            perf_size_of(): size_of(       1):      216 bytes ratio:      216 /sizeof(T):       x
16...
17                doc_insert_remove_repeat(): PASS
18Final result: PASS
19Exec time: 127.5 (s)
20Bye, bye!
```

--------------------------------

### Python SkipList with custom objects

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Shows how to use a Python SkipList with user-defined objects, defining a custom ordering based on last name and then first name. Requires the functools.total_ordering decorator.

```python
import functools

import orderedstructs

@functools.total_ordering
class Person:
    """Simple example of ordering based on last name/first name."""
    def __init__(self, first_name, last_name):
        self.first_name = first_name
        self.last_name = last_name

    def __eq__(self, other):
        try:
            return self.last_name == other.last_name \
                and self.first_name == other.first_name
        except AttributeError:
            return NotImplemented

    def __lt__(self, other):
        try:
            return self.last_name < other.last_name \
                or self.first_name < other.first_name
        except AttributeError:
            return NotImplemented

    def __str__(self):
        return '{}, {}'.format(self.last_name, self.first_name)

sl = orderedstructs.SkipList(object)

sl.insert(Person('Peter', 'Pan'))
sl.insert(Person('Alan', 'Pan'))
assert sl.size() == 2
assert str(sl.at(0)) == 'Pan, Alan'
assert str(sl.at(1)) == 'Pan, Peter'

```

--------------------------------

### cSkipList Module Functions

Source: https://skiplist.readthedocs.io/en/latest/api.html

Provides utility functions for the skip list module, including random number generation seeding and retrieving minimum/maximum long values.

```APIDOC
## Module Functions

### `toss_coin()`

Returns the result of a virtual coin toss.

### `seed_rand(long)`

Seeds the random number generator with a long integer.

### `min_long()`

The minimum storable value of a `PySkipList(long)`.

### `max_long()`

The maximum storable value of a `PySkipList(long)`.
```

--------------------------------

### Run C++ SkipList Executable

Source: https://skiplist.readthedocs.io/en/latest/performance.html

Execute the compiled C++ SkipList program. This command is used after building the release version with thread support enabled.

```bash
./SkipList_R.exe
```

--------------------------------

### PySkipList.dot_file()

Source: https://skiplist.readthedocs.io/en/latest/api.html

Returns a DOT file representation of the skip list's current state as a bytes object. Requires a specific macro to be defined during compilation.

```APIDOC
## PySkipList.dot_file()

### Description
Returns a representation of the current state of the skip list as a bytes object that represents a DOT file. This method requires the macro `INCLUDE_METHODS_THAT_USE_STREAMS` to be defined.

### Method
Python method call

### Endpoint
N/A (Python method)

### Parameters
None

### Request Example
```python
dot_representation = skip_list.dot_file()
```

### Response
#### Success Response
- **dot_file_bytes** (bytes) - A bytes object representing the DOT file content.
```

--------------------------------

### Run C++ Tests with CMake

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Execute the C++ SkipList tests after building with CMake.

```bash
cd <skiplist>
./cmake-build-release/SkipList

```

--------------------------------

### C++ Skip List Performance Test Execution

Source: https://skiplist.readthedocs.io/en/latest/performance.html

This snippet shows the command-line execution of the C++ Skip List performance tests. It includes compilation and running the test executable.

```bash
1$ cd src/cpp
2$ make release
3$ ./SkipList_R.exe
4                 test_very_simple_insert(): PASS
5                                                    ...
6                 test_roll_med_even_mean(): PASS
7               perf_single_insert_remove(): 451.554 (ms) rate x.xe+06 /s
8                                                    ...
9            perf_roll_med_odd_index_wins(): vectors length:  1000000 window width: 524288 time: x.x (ms)
10                            perf_size_of(): size_of(       1):      216 bytes ratio:      216 /sizeof(T):       x
11                                                    ...
12Final result: PASS
13Exec time: x.x (s)
14Bye, bye!
```

--------------------------------

### C++ API

Source: https://skiplist.readthedocs.io/en/latest/index.html

Documentation for the C++ Skip List API, including constructors and core operations.

```APIDOC
## C++ API

### Description
Provides the interface for using the Skip List in C++ applications.

### Constructors
Details on how to instantiate a Skip List object.

### `HeadNode::insert(const T &val)`

### Description
Inserts a value into the Skip List.

### Method
`HeadNode::insert`

### Parameters
- **val** (T) - The value to insert.

### `HeadNode::remove(const T &val)`

### Description
Removes a value from the Skip List.

### Method
`HeadNode::remove`

### Parameters
- **val** (T) - The value to remove.

### `HeadNode::has(const T &val) const;`

### Description
Checks if a value exists in the Skip List.

### Method
`HeadNode::has`

### Parameters
- **val** (T) - The value to check for.

### `HeadNode::at(size_t index) const;`

### Description
Retrieves the value at a specific index.

### Method
`HeadNode::at`

### Parameters
- **index** (size_t) - The index of the element to retrieve.

### `HeadNode::at(size_t index, size_t count, std::vector<T> &dest) const;`

### Description
Retrieves a range of values from the Skip List into a destination vector.

### Method
`HeadNode::at`

### Parameters
- **index** (size_t) - The starting index.
- **count** (size_t) - The number of elements to retrieve.
- **dest** (std::vector<T>&) - The vector to store the retrieved elements.

### `HeadNode::index(const T &value) const;`

### Description
Finds the index of a given value.

### Method
`HeadNode::index`

### Parameters
- **value** (T) - The value to find the index of.

### `HeadNode::size() const`

### Description
Returns the number of elements in the Skip List.

### Method
`HeadNode::size`

### Specialised APIs
Additional specialized functions for C++ Skip List.
```

--------------------------------

### Run Slow Tests and Benchmarks

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Execute extensive tests and generate benchmarks. Ensure you are in the skiplist directory. This command uses pytest with specific benchmark options.

```sh
$ cd <skiplist>
$ pytest tests/ --runslow --benchmark-sort=name \
  --benchmark-autosave --benchmark-histogram
```

--------------------------------

### Python API

Source: https://skiplist.readthedocs.io/en/latest/index.html

Documentation for the Python Skip List API, including class methods and their usage.

```APIDOC
## Python API

### Description
Provides the interface for using the Skip List in Python applications.

### Module `cSkipList`

### Class `cSkipList.PySkipList`

### Constructor
Initializes a new `PySkipList` object.

### `PySkipList.has(val)`

### Description
Checks if a value exists in the Skip List.

### Method
`PySkipList.has`

### Parameters
- **val** - The value to check for.

### `PySkipList.at(index)`

### Description
Retrieves the value at a specific index.

### Method
`PySkipList.at`

### Parameters
- **index** (int) - The index of the element to retrieve.

### `PySkipList.at_seq(index, count)`

### Description
Retrieves a sequence of values from the Skip List.

### Method
`PySkipList.at_seq`

### Parameters
- **index** (int) - The starting index.
- **count** (int) - The number of elements to retrieve.

### `PySkipList.index(value)`

### Description
Finds the index of a given value.

### Method
`PySkipList.index`

### Parameters
- **value** - The value to find the index of.

### `PySkipList.size()`

### Description
Returns the number of elements in the Skip List.

### Method
`PySkipList.size`

### `PySkipList.insert(value)`

### Description
Inserts a value into the Skip List.

### Method
`PySkipList.insert`

### Parameters
- **value** - The value to insert.

### `PySkipList.remove(value)`

### Description
Removes a value from the Skip List.

### Method
`PySkipList.remove`

### Parameters
- **value** - The value to remove.

### Specialised APIs
Additional specialized functions for Python Skip List.
```

--------------------------------

### Run Extensive Python Tests and Benchmarks

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Execute more extensive and slow tests for the Python SkipList implementation, generating benchmarks with specific pytest flags.

```bash
cd <skiplist>
pytest tests/ --runslow --benchmark-sort=name \
  --benchmark-autosave --benchmark-histogram

```

--------------------------------

### HeadNode::dotFile(std::ostream &os) const

Source: https://skiplist.readthedocs.io/en/latest/api.html

Writes a DOT file representation of the skip list's current state to the provided output stream. Requires the INCLUDE_METHODS_THAT_USE_STREAMS macro to be defined.

```APIDOC
## HeadNode::dotFile(std::ostream &os) const

### Description
Writes a representation of the current state of the skip is as a fragment of a DOT file to the stream `os` as a `subgraph`. Internally the `HeadNode` keeps a count of how many times this has been called. The first time this function is called writes the preamble of DOT file as well as the subgraph. Writing to `os` before or between `dotFile()` calls may produce undefined DOT format files.

### Method
CONST

### Signature
void dotFile(std::ostream &os) const;

### Requirements
Requires the macro `INCLUDE_METHODS_THAT_USE_STREAMS` to be defined.
```

--------------------------------

### Compile C++ SkipList with Thread Support

Source: https://skiplist.readthedocs.io/en/latest/performance.html

Compile the C++ SkipList with the SKIPLIST_THREAD_SUPPORT macro defined to enable multi-threading. This command is used to build the release version.

```bash
cd src/cpp
make release CXXFLAGS=-DSKIPLIST_THREAD_SUPPORT
```

--------------------------------

### C++ SkipList Testing with Makefile (Debug)

Source: https://skiplist.readthedocs.io/en/latest/_sources/introduction.rst.txt

Command to run C++ functional tests with aggressive internal integrity checks, excluding performance tests, using the Makefile in debug mode.

```sh
cd <skiplist>/src/cpp
make debug
./SkipList_D.exe
```

--------------------------------

### Generate DOT file for repeated insert and remove operations

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

This C++ code visualizes a skip list undergoing repeated insertions and removals. It inserts values 0 to 3, writes the state, removes them, writes the state again, and repeats this process multiple times before finalising the DOT output.

```cpp
#include "SkipList.h"

void doc_insert_remove_repeat() {
   int NUM = 4;
   int REPEAT_COUNT = 4;

   OrderedStructs::SkipList::HeadNode<int> sl;

   sl.dotFile(std::cout);
   for (int c = 0; c < REPEAT_COUNT; ++c) {
       for (int i = 0; i < NUM; ++i) {
           sl.insert(i);
           sl.dotFile(std::cout);
       }
       for (int i = 0; i < NUM; ++i) {
           sl.remove(i);
           sl.dotFile(std::cout);
       }
   }
   sl.dotFileFinalise(std::cout);
}
```

--------------------------------

### Calling the Python Rolling Median Function

Source: https://skiplist.readthedocs.io/en/latest/rolling_median.html

Demonstrates how to call the `simple_python_rolling_median` function with a sample numpy array and window size, then prints the original array and the computed rolling median result.

```python
np_array = np.arange(10.0)
print('Original:', np_array)
result = simple_python_rolling_median(np_array, 3)
print('  Result:', result)

```

--------------------------------

### Thread-safe C++ SkipList usage

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Illustrates how to use a C++ SkipList in a multi-threaded environment when compiled with the SKIPLIST_THREAD_SUPPORT macro. Multiple threads can safely insert and remove items.

```cpp
#include <thread>
#include <vector>

#include "SkipList.h"

void do_something(OrderedStructs::SkipList::HeadNode<double> *pSkipList) {
    // Insert/remove items into *pSkipList
    // Read items inserted by other threads.
}

OrderedStructs::SkipList::HeadNode<double> sl;
std::vector<std::thread> threads;

for (size_t i = 0; i < thread_count; ++i) {
    threads.push_back(std::thread(do_something, &sl));
}
for (auto &t: threads) {
    t.join();
}
// The SkipList now contains the totality of the thread actions.

```

--------------------------------

### Generate .dot file from Python Skip List

Source: https://skiplist.readthedocs.io/en/latest/visualisations.html

Use the `.dot_file()` method to obtain a bytes object representing the skip list structure. This can then be decoded and written to a .dot file for visualization.

```Python
import cSkipList

sl = cSkipList.PySkipList(float)

sl.insert(42.0)
sl.insert(21.0)
sl.insert(84.0)

dot_bytes = sl.dot_file()

with open('doc_simple_py.dot', 'w') as dot_file:
    dot_file.write(dot_bytes.decode('ascii'))
```

--------------------------------

### Skip List State Before Insertion

Source: https://skiplist.readthedocs.io/en/latest/design.html

Visual representation of a skip list before inserting a new node 'E'. This helps in understanding the structure that will be modified.

```text
| 1 A |->| 2 C |---------->| 3 G |------------------->| 2 0 |->| NULL |
| 1 A |->| 1 B |->| 1 C |->| 1 D |->| 1 F |->| 1 G |->| 1 0 |->| NULL |
| HED |  |  A  |  |  B  |  |  C  |  |  D  |  |  F  |  |  G  |

```

--------------------------------

### cSkipList.PySkipList Constructor

Source: https://skiplist.readthedocs.io/en/latest/api.html

Constructs a new PySkipList object. The constructor takes a Python type (e.g., int, float, bytes) to specify the data type of elements the skip list will store.

```APIDOC
## cSkipList.PySkipList Constructor

### Description
Constructs a new PySkipList object. The constructor takes a Python type (e.g., int, float, bytes) to specify the data type of elements the skip list will store.

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Parameters
- **type** (type) - Required - The Python type for elements (e.g., int, float, bytes).
```

--------------------------------

### Run C++ Functional Tests

Source: https://skiplist.readthedocs.io/en/latest/test_notes.html

Execute the C++ functional tests using a debug build. This process involves navigating to the source directory, compiling a debug version, and running the executable to verify skip list operations.

```bash
1$ cd src/cpp
2$ make debug
3$ ./SkipList_D.exe
4Running skip list tests...
5                 test_very_simple_insert(): PASS
6                      test_simple_insert(): PASS
7             test_insert_and_remove_same(): PASS
8             test_insert_remove_multiple(): PASS
9                       test_ins_rem_rand(): PASS
10              test_insert_n_numbers_same(): PASS
11                                 test_at(): PASS
12...
13                doc_insert_remove_repeat(): PASS
14Final result: PASS
15Exec time: 19.5811 (s)
16Bye, bye!
```

--------------------------------

### Run C++ Functional Tests (Debug)

Source: https://skiplist.readthedocs.io/en/latest/introduction.html

Execute C++ functional tests with aggressive internal integrity checks, excluding performance tests, using the Makefile in debug mode.

```bash
cd <skiplist>/src/cpp
make debug
./SkipList_D.exe

```
Tokens:
Raw