windowed_median.cpp

/**
 * @file
 * @brief An implementation of a median calculation of a sliding window along a
 * data stream
 *
 * @details
 * 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/find-median-from-data-stream.htm),
 * with the proper modifications to account for the finite window size for which
 * the median is requested
 *
 * ### Algorithm
 * 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 multi-value 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
 * @author [Yaniv Hollander](https://github.com/YanivHollander)
 */
#include <cassert>  /// for assert
#include <cstdlib>  /// for std::rand - needed in testing
#include <ctime>    /// for std::time - needed in testing
#include <list>     /// for std::list - used to manage sliding window
#include <set>  /// for std::multiset - used to manage multi-value sorted sliding window values
#include <vector>  /// for std::vector - needed in testing

/**
 * @namespace probability
 * @brief Probability algorithms
 */
namespace probability {
/**
 * @namespace windowed_median
 * @brief Functions for the Windowed Median algorithm implementation
 */
namespace windowed_median {
using Window = std::list<int>;
using size_type = Window::size_type;

/**
 * @class WindowedMedian
 * @brief A class to calculate the median of a leading sliding window at the
 * back of a stream of integer values.
 */
class WindowedMedian {
    const size_type _windowSize;  ///< sliding window size
    Window _window;  ///< a sliding window of values along the stream
    std::multiset<int> _sortedValues;  ///< a DS to represent a balanced
                                       /// multi-value binary search tree (BST)
    std::multiset<int>::const_iterator
        _itMedian;  ///< an iterator that points to the root of the multi-value
                    /// BST

    /**
     * @brief Inserts a value to a sorted multi-value BST
     * @param value Value to insert
     */
    void insertToSorted(int value) {
        _sortedValues.insert(value);  /// Insert value to BST - O(logN)
        const auto sz = _sortedValues.size();
        if (sz == 1) {  /// For the first value, set median iterator to BST root
            _itMedian = _sortedValues.begin();
            return;
        }

        /// If new value goes to left tree branch, and number of elements is
        /// even, the new median in the balanced tree is the left child of the
        /// median before the insertion
        if (value < *_itMedian && sz % 2 == 0) {
            --_itMedian;  // O(1) - traversing one step to the left child
        }

        /// However, if the new value goes to the right branch, the previous
        /// median's right child is the new median in the balanced tree
        else if (value >= *_itMedian && sz % 2 != 0) {
            ++_itMedian;  /// O(1) - traversing one step to the right child
        }
    }

    /**
     * @brief Erases a value from a sorted multi-value BST
     * @param value Value to insert
     */
    void eraseFromSorted(int value) {
        const auto sz = _sortedValues.size();

        /// If the erased value is on the left branch or the median itself and
        /// the number of elements is even, the new median will be the right
        /// child of the current one
        if (value <= *_itMedian && sz % 2 == 0) {
            ++_itMedian;  /// O(1) - traversing one step to the right child
        }

        /// However, if the erased value is on the right branch or the median
        /// itself, and the number of elements is odd, the new median will be
        /// the left child of the current one
        else if (value >= *_itMedian && sz % 2 != 0) {
            --_itMedian;  // O(1) - traversing one step to the left child
        }

        /// Find the (first) position of the value we want to erase, and erase
        /// it
        const auto it = _sortedValues.find(value);  // O(logN)
        _sortedValues.erase(it);                    // O(logN)
    }

 public:
    /**
     * @brief Constructs a WindowedMedian object
     * @param windowSize Sliding window size
     */
    explicit WindowedMedian(size_type windowSize) : _windowSize(windowSize){};

    /**
     * @brief Insert a new value to the stream
     * @param value New value to insert
     */
    void insert(int value) {
        /// Push new value to the back of the sliding window - O(1)
        _window.push_back(value);
        insertToSorted(value);  // Insert value to the multi-value BST - O(logN)
        if (_window.size() > _windowSize) {  /// If exceeding size of window,
                                             /// pop from its left side
            eraseFromSorted(
                _window.front());  /// Erase from the multi-value BST
                                   /// the window left side value
            _window.pop_front();   /// Pop the left side value from the window -
                                   /// O(1)
        }
    }

    /**
     * @brief Gets the median of the values in the sliding window
     * @return Median of sliding window. For even window size return the average
     * between the two values in the middle
     */
    float getMedian() const {
        if (_sortedValues.size() % 2 != 0) {
            return *_itMedian;  // O(1)
        }
        return 0.5f * *_itMedian + 0.5f * *next(_itMedian);  /// O(1)
    }

    /**
     * @brief A naive and inefficient method to obtain the median of the sliding
     * window. Used for testing!
     * @return Median of sliding window. For even window size return the average
     * between the two values in the middle
     */
    float getMedianNaive() const {
        auto window = _window;
        window.sort();  /// Sort window - O(NlogN)
        auto median =
            *next(window.begin(),
                  window.size() / 2);  /// Find value in the middle - O(N)
        if (window.size() % 2 != 0) {
            return median;
        }
        return 0.5f * median +
               0.5f * *next(window.begin(), window.size() / 2 - 1);  /// O(N)
    }
};
}  // namespace windowed_median
}  // namespace probability

/**
 * @brief Self-test implementations
 * @param vals Stream of values
 * @param windowSize Size of sliding window
 */
static void test(const std::vector<int> &vals, int windowSize) {
    probability::windowed_median::WindowedMedian windowedMedian(windowSize);
    for (const auto val : vals) {
        windowedMedian.insert(val);

        /// Comparing medians: efficient function vs. Naive one
        assert(windowedMedian.getMedian() == windowedMedian.getMedianNaive());
    }
}

/**
 * @brief Main function
 * @param argc command line argument count (ignored)
 * @param argv command line array of arguments (ignored)
 * @returns 0 on exit
 */
int main(int argc, const char *argv[]) {
    /// A few fixed test cases
    test({1, 2, 3, 4, 5, 6, 7, 8, 9},
         3);  /// Array of sorted values; odd window size
    test({9, 8, 7, 6, 5, 4, 3, 2, 1},
         3);  /// Array of sorted values - decreasing; odd window size
    test({9, 8, 7, 6, 5, 4, 5, 6}, 4);     /// Even window size
    test({3, 3, 3, 3, 3, 3, 3, 3, 3}, 3);  /// Array with repeating values
    test({3, 3, 3, 3, 7, 3, 3, 3, 3}, 3);  /// Array with same values except one
    test({4, 3, 3, -5, -5, 1, 3, 4, 5},
         5);  /// 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
    test({470211272, 101027544, 1457850878, 1458777923, 2007237709, 823564440,
          1115438165, 1784484492, 74243042, 114807987},
         6);

    /// Random test cases
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    std::vector<int> vals;
    for (int i = 8; i < 100; i++) {
        const auto n =
            1 + std::rand() /
                    ((RAND_MAX + 5u) / 20);  /// Array size in the range [5, 20]
        auto windowSize =
            1 + std::rand() / ((RAND_MAX + 3u) /
                               10);  /// Window size in the range [3, 10]
        vals.clear();
        vals.reserve(n);
        for (int i = 0; i < n; i++) {
            vals.push_back(
                rand() - RAND_MAX);  /// Random array values (positive/negative)
        }
        test(vals, windowSize);  /// Testing randomized test
    }
    return 0;
}