Generic Segment Tree implementation using C++ Templates

Question

I am trying to make a generic Segment Tree Class for updates and range queries.

Instead of assuming that the elements would just be integers and the operation to be done over a range of elements would be their sum or product, i would want the user to provide the type T of the element and a function, which i named compose.

This function takes in two parameters of type T and returns a value of the same type T. This return value is the result when that desired operation is performed over range of 2 elements which i can use to perform that same operation on a range of any number of elements.

The class is as follows:

#include <functional>

template<class T>
class SegmentTree {

    public:
        class binary_function_unitype: public std::binary_function<T,T,T> {
            public:
                virtual T operator() (T arg1, T arg2) {};
        };

    private:
        class Node {
            public:
                T value;
                int seg_start, seg_end;
                Node* left;
                Node* right;
                Node (T value, int seg_start, int seg_end, Node* left=0, Node* right=0) {
                    this->value = value;
                    this->seg_start = seg_start;
                    this->seg_end = seg_end;
                    this->left = left;
                    this->right = right;
                }
        };

        // Not expecting the compose function to be robust enough.
        T composeUtil (T arg1, T arg2) {
            if (arg1!=0 && arg2!=0)
                return compose(arg1,arg2);
            else if (arg1!=0)
                return arg1;
            else if (arg2!=0)
                return arg2;
        }

        // Creating the Segment Tree.
        Node* createTree (T leaves[], int start, int end) {
            // base case - leaf of tree.
            if (start==end)
                return new Node(leaves[start],start,start,0,0);
            // general case.
            int mid = start + (end-start)/2;
            Node* left = createTree(leaves,start,mid);
            Node* right = createTree(leaves,mid+1,end);
            T retValue = composeUtil(left->value,right->value);
            return new Node(retValue,start,end,left,right);
        }

        // Range Query helper.
        T queryUtil (Node* root, int start, int end) {
            int seg_start = root->seg_start, seg_end = root->seg_end;
            if (seg_start>end || seg_end<start)
                return 0;
            else if (seg_start>=start && seg_end<=end)
                return root->value;
            else
                return compose( queryUtil(root->left,start,end), queryUtil(root->right,start,end));
        }

        // Helper function for Updating the Segment Tree.
        void updateUtil (Node* root, int position, T updatedValue) {
            int seg_start = root->seg_start, seg_end = root->seg_end;
            if(seg_start>position || seg_end<position)
                return;
            else if(seg_start==seg_end)
                root->value = updatedValue;
            else
                root->value = composeUtil(root->left->value,root->right->value);
        }

        // Freeing the memory allocated to the Segment Tree.
        void destroyTree(Node* root) {
            if (root->left!=0)
                destroyTree(root->left);
            if (root->right!=0)
                destroyTree(root->right);
            delete root;
        }

        Node* root;
        binary_function_unitype compose;

    public:
        SegmentTree (T leaves[], binary_function_unitype compose, int start, int end) {
            this->compose = compose;
            this->root = createTree(leaves, start, end);
        }

        T query (int start, int end) {
            return queryUtil(root, start, end);
        }

        void update (int position, T updatedValue) {
            updateUtil(root, position, updatedValue);
        }

        ~SegmentTree () {
            destroyTree(root);
        }
};

When I tried to use this class, it turns out that the compose function, which I took in as a paramater is not being used, on the contrary the one from the class binary_function_unitype is being used.

I expected that the function definition from the user would override the one in class binary_function_unitype and my work would be done. But that did not happen. The program using this class is as follows:

#include <iostream>
#include "SegmentTree.h"

using namespace std;

class Compose: public SegmentTree<int>::binary_function_unitype {
    public:
        int operator() (int arg1, int arg2) {
            return arg1+arg2;
        }
};

int main()
{
    int num;
    cin>>num;
    int arr[num];
    for(int i=0;i<num;i++)
        cin>>arr[i];
    Compose compose;
    SegmentTree<int> segTree(arr, compose, 0, num-1);
    int s,e;
    cin>>s>>e;
    cout<<segTree.query(s-1,e-1);
    return 0;
}

Can somebody tell me whats the flaw in my approach or if I misunderstood some basic concept about using inheritance or templates in C++ ?

Thanks.

Answer 1

The constructor takes a binary_function_unitype by value, so it will slice.