/Users/jst/src/grafalgo/cpp/include/StairFunc.h

// Header file for data structure that maintains a staircase function.
// Main operations include testing for the minimum value in a
// specified range and increasing (or decreasing) the value
// across all points in a specified range.
// x values are required to be non-negative.

#ifndef STAIRFUNC_H
#define STAIRFUNC_H

#include "DkBstSet.h"
#include "List.h"

namespace grafalgo {

class StairFunc : public Adt {
public:         StairFunc(int);
                ~StairFunc();

        // common methods
        void    clear();
        void    resize(int);
        void    expand(int);
        void    copyFrom(const StairFunc&);

        static  const int MAXY = Util::BIGINT32-1; // max allowed key2 value
        int     value(int);                 // return y value for given x
        int     findmin(int,int);           // return min value in given range
        void    change(int,int,int);        // change values in range by delta

        string& toString(string&) const;
protected:
        DkBstSet *points;               // data structure for "change points"
        List    *free;                  // list of unused items in points

        void    makeSpace(int);
        void    freeSpace();
};

} // ends namespace

#endif