Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.

An implementation of a median calculation of a sliding window along a data stream. More...
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <list>
#include <set>
#include <vector>
Classes  
class  probability::windowed_median::WindowedMedian 
A class to calculate the median of a leading sliding window at the back of a stream of integer values. More...  
Namespaces  
namespace  probability 
Probability algorithms.  
namespace  windowed_median 
Functions for the Windowed Median algorithm implementation.  
Typedefs  
using  probability::windowed_median::Window = std::list<int> 
using  probability::windowed_median::size_type = Window::size_type 
Functions  
static void  test (const std::vector< int > &vals, int windowSize) 
Selftest implementations.  
int  main (int argc, const char *argv[]) 
Main function.  
An implementation of a median calculation of a sliding window along a data stream.
Given a stream of integers, the algorithm calculates the median of a fixed size window at the back of the stream. The leading time complexity of this algorithm is O(log(N), and it is inspired by the known algorithm to [find median from (infinite) data stream](https://www.tutorialcup.com/interview/algorithm/findmedianfromdatastream.htm), with the proper modifications to account for the finite window size for which the median is requested
The sliding window is managed by a list, which guarantees O(1) for both pushing and popping. Each new value is pushed to the window back, while a value from the front of the window is popped. In addition, the algorithm manages a multivalue binary search tree (BST), implemented by std::multiset. For each new value that is inserted into the window, it is also inserted to the BST. When a value is popped from the window, it is also erased from the BST. Both insertion and erasion to/from the BST are O(logN) in time, with N the size of the window. Finally, the algorithm keeps a pointer to the root of the BST, and updates its position whenever values are inserted or erased to/from BST. The root of the tree is the median! Hence, median retrieval is always O(1)
Time complexity: O(logN). Space complexity: O(N). N  size of window
int main  (  int  argc, 
const char *  argv[] ) 
Main function.
argc  command line argument count (ignored) 
argv  command line array of arguments (ignored) 
A few fixed test cases
Array of sorted values; odd window size
Array of sorted values  decreasing; odd window size
Even window size
Array with repeating values
Array with same values except one
Array that includes repeating values including negatives
Array with large values  sum of few pairs exceeds MAX_INT. Window size is even  testing calculation of average median between two middle values
Random test cases
Array size in the range [5, 20]
Window size in the range [3, 10]
Random array values (positive/negative)
Testing randomized test

static 
Selftest implementations.
vals  Stream of values 
windowSize  Size of sliding window 
Comparing medians: efficient function vs. Naive one