Test Run: a simple example

Problem description

This TestRun problem was designed to be as simple as possible while being able to simulate any stack behavior. Its purpose was mainly to experimentally evaluate the time and space efficiency of the Compressed Stack structure. However, it also provides a good starting point for all users.

It is an artificial stack algorithm that executes push and pop operations for debugging purposes. Each data in the input is a pair of positive integers separated by a comma (say, 5,2). The first number indicates the value to store, if and only if it is at least 1. The second number indicates the value used to update the context (note that the data type and the contexts are both integers). We use the context as an auxiliary variable to count the number of pops to execute (while the context is strictly positive, popCondition will return true and decrement the context by one).

Instance generator

An instance generator is provided as examples/testrun/generateInputTestRun.cpp. If the provided CMake file CMakeLists.txt is used as described in the Installation (Build) page, an executable to generate TestRun instances will be built.

The generateInputTestRun executable can be called as follows.

path_to_executable/generateInputTestRun path_to_file/file_name instancetype stacktype size space rand_min rand_max pop_probability

Specific examples can be generated as follows. The first is general example with a given probability of pop. The second is a "hard" scenario for the compressed stack that is called Chrismas Tree. More explanation can be found in "TODO: link to the arxiv article"

// Push everything and pop with probablity 10% (n=1000, p=50)
// Random integers are generated between 11 and 732
path_to_executable/generateInputTestRun path_to_file/file_name 1 1 1000 50 11 732 0.1

// Christmas tree with step and cycle 8 and pop 4, (n=1000, p=50)
path_to_executable/generateInputTestRun path_to_file/file_name 3 1 1000 50 8 8 4

Basic usage

If we suppose the path to the previous generated instance is stored in the variable filePath, then a simple utilization of the library would be as such:

// Create the StackAlgo object and its associated stack to execute a TestRun
Instance testRun(filePath);
// Actually run the TestRun instance
testRun.run();
// Print the actual state of the stack at the end of the algorithm
testRun.println();

Example with command line

Two instances are available in this repository for the TestRun problem. They can be executed as easily as

// We assume the user is at the root directory of the library
build_directory/testrun8 examples/testrun/instances/testFilePushProbablility10p50n1000.txt
build_directory/testrun8 examples/testrun/instances/testFileChristmasTreeCycle8Step8Pop4n1000p50.txt

Experimental results

Tables containing results for a best case and worst case scenarii are available on Numerical-results-(tables). In Baffier et al, those results are interpreted.