Monoidal sliding window in c++

slidingmonoid.cpp

#include <iostream>
#include <vector>

using namespace std;

//quick prototype inspired by the haskell version (not battle tested)
//https://byorgey.github.io/blog/posts/2024/11/27/stacks-queues.html
//compile with g++ -std=c++17 slidingmonoid.cpp -o slidingmonoid


//Assume commutative monoid operation

class SumOperation
{
    public:

    static int op(  int a) //Monoids have a neutral element e so op(a) must be equal to op( a, e)
    {
        return a;
    }
    static int op( int a, int b)
    {
        return a + b;
    }

};

class MaxOperation
{
    public:

    static int op(  int a)
    {
        return a;
    }
    static int op( int a, int b)
    {
        return max(a ,b);
    }

};

template<typename T, typename T2, typename GroupOperation>
class AnnotatedStack
{
    public:

    void push( const T& a)
    { 
        data.push_back( make_pair( a, data.size()==0?GroupOperation::op(a):GroupOperation::op(a,data[data.size()-1].second) ));
    }

    pair<T,T2> peek()
    {
        return data[data.size()-1];
    }

    T2 measure()
    {
        return data[data.size()-1].second;
    }

    void pop()
    {
        data.pop_back();
    }

    unsigned int size()
    {
        return data.size();
    }

  

    private:
    vector<pair<T,T2> > data; //we use vector but we can also use raw pointers or lists
};

template<typename T,typename T2, typename GroupOperation>
  void reverseFill(AnnotatedStack<T,T2,GroupOperation>& dst, AnnotatedStack<T,T2,GroupOperation>& src)
    {
        while( src.size() > 0)
        {
            auto asum = src.peek();
            src.pop();
            dst.push(asum.first);
        }
    }

template<typename T, typename T2, typename GroupOperation>
class AnnotatedQueue
{
    public:

    //Add element to the back of the queue
    void push( const T& a)
    {
        back.push(a);
    }

    pair<T,T2> peek( )
    {
        if(  front.size() == 0)
            reverseFill(front, back);
        return front.peek();
    }

    void pop()
    {
        if(  front.size() == 0)
            reverseFill(front, back);
        front.pop();
    }

    unsigned int size()
    {
        return back.size() + front.size();
    }

    //measure is not defined and should not be called when size() == 0
    T2 measure()
    {
        //Because of the assumption we can call back.measure()
        if( front.size() == 0)
            return back.measure();

        //Because of the assumption we can call front.measure()
        if( back.size() == 0)
            return front.measure();
        return GroupOperation::op(back.measure(),front.measure());
    }

    private:
    AnnotatedStack<T,T2,GroupOperation> back;
    AnnotatedStack<T,T2,GroupOperation> front;

};


int main()
{

    cout<< "computing the sliding grouping of a generic monoid operation" << endl;

    vector<int> array;
    array.push_back( 3);
    array.push_back( 7);
    array.push_back( 2);
    array.push_back( 8);
    array.push_back( 8);
    array.push_back( 7);
    array.push_back( 3);
    array.push_back( 1);
    array.push_back( 2);
    array.push_back( 2);
    array.push_back( 2);

    AnnotatedStack<int,int,SumOperation> sumstack;
    
    for( int i = 0 ; i < array.size() ; i++)
    {
        sumstack.push( array[i] );
        auto elsum = sumstack.peek();
        cout << "size: " << sumstack.size() << " last element " <<  array[i] << " cumulative sum " << elsum.second << endl; 
    }
    for( int i = 0 ; i < array.size() ; i++)
    {
       auto elsum = sumstack.peek();
        cout << "size : " << sumstack.size() << " last element " << elsum.first << " cumulative sum " << elsum.second << endl; 
        sumstack.pop();
    }

    cout << endl ;
    AnnotatedStack<int,int,MaxOperation> maxstack;
    
    for( int i = 0 ; i < array.size() ; i++)
    {
        maxstack.push( array[i] );
        auto elmax = maxstack.peek();

        cout << "maxstack.size() : " << maxstack.size() << " last element " << elmax.first << " cumulative max " << elmax.second << endl; 
       
    }

     for( int i = 0 ; i < array.size() ; i++)
    {
        maxstack.pop();
        auto elmax = maxstack.peek( );
        cout << "size : " << maxstack.size() << " last element " << elmax.first << " cumulative max " << elmax.second << endl; 
    }

    int windowsize = 4;
    vector<int> cumsums;
    int cumsum = 0;
    for( int i = 0 ; i < array.size() ; i++)
    {
        cumsum += array[i];
        cumsums.push_back(cumsum);
        int cumsumwindow = cumsum - ((i-windowsize >= 0) ? cumsums[ max( i - windowsize, 0)]:0);
        cout << "cumsums window " << cumsumwindow  << endl; 

    }

    cout << endl;
    AnnotatedQueue<int,int,SumOperation> sumqueue;
    for( int i = 0 ; i < array.size() ; i++)
    {
        sumqueue.push( array[i] );

        cout << "size: " << sumqueue.size() << " last element inserted " << array[i]  << endl ;
    }

    cout << endl;
    while( sumqueue.size() > 0)
    {
        auto elsum = sumqueue.peek();
        sumqueue.pop();
        cout << "size: " << sumqueue.size() << " last element retrieved " << elsum.first << " current sum " << elsum.second << endl ;

    }
    
    cout << endl;
     for( int i = 0 ; i < array.size() ; i++)
    {   
        if( i >= windowsize ) sumqueue.pop();

        sumqueue.push( array[i] );
        cout << "size: " << sumqueue.size() << " last element inserted " << array[i] << " sliding sum " << sumqueue.measure() << endl; 
         
    }
    
    windowsize = 3;
    AnnotatedQueue<int,int,MaxOperation> maxqueue;

    cout << endl;
     for( int i = 0 ; i < array.size() ; i++)
    {   
        if( i >= windowsize ) maxqueue.pop();
        maxqueue.push( array[i] );
        cout << "size: " << maxqueue.size() << " last element inserted " << array[i] << " sliding max " << maxqueue.measure() << endl; 
         
    }

    return 0;
}