// histogram.h

/**
*    Copyright (C) 2008 10gen Inc.
*
*    This program is free software: you can redistribute it and/or  modify
*    it under the terms of the GNU Affero General Public License, version 3,
*    as published by the Free Software Foundation.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU Affero General Public License for more details.
*
*    You should have received a copy of the GNU Affero General Public License
*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef UTIL_HISTOGRAM_HEADER
#define UTIL_HISTOGRAM_HEADER

#include "../pch.h"

#include <string>

namespace mongo {

    using std::string;

    /**
     * A histogram for a 32-bit integer range.
     */
    class Histogram {
    public:
        /**
         * Construct a histogram with 'numBuckets' buckets, optionally
         * having the first bucket start at 'initialValue' rather than
         * 0. By default, the histogram buckets will be 'bucketSize' wide.
         *
         * Usage example:
         *   Histogram::Options opts;
         *   opts.numBuckets = 3;
         *   opts.bucketSize = 10;
         *   Histogram h( opts );
         *
         *   Generates the bucket ranges [0..10],[11..20],[21..max_int]
         *
         * Alternatively, the flag 'exponential' could be turned on, in
         * which case a bucket's maximum value will be
         *    initialValue + bucketSize * 2 ^ [0..numBuckets-1]
         *
         * Usage example:
         *   Histogram::Options opts;
         *   opts.numBuckets = 4;
         *   opts.bucketSize = 125;
         *   opts.exponential = true;
         *   Histogram h( opts );
         *
         *   Generates the bucket ranges [0..125],[126..250],[251..500],[501..max_int]
         */
        struct Options {
            boost::uint32_t numBuckets;
            boost::uint32_t bucketSize;
            boost::uint32_t initialValue;

            // use exponential buckets?
            bool            exponential;
            
            Options() 
                : numBuckets(0)
                , bucketSize(0)
                , initialValue(0)
                , exponential(false){}
        };
        explicit Histogram( const Options& opts );
        ~Histogram();

        /**
         * Find the bucket that 'element' falls into and increment its count.
         */
        void insert( boost::uint32_t element );

        /**
         * Render the histogram as string that can be used inside an
         * HTML doc.
         */
        string toHTML() const;

        // testing interface below -- consider it private

        /**
         * Return the count for the 'bucket'-th bucket.
         */
        boost::uint64_t getCount( boost::uint32_t bucket ) const;

        /**
         * Return the maximum element that would fall in the
         * 'bucket'-th bucket.
         */
        boost::uint32_t getBoundary( boost::uint32_t bucket ) const;

        /**
         * Return the number of buckets in this histogram.
         */
        boost::uint32_t getBucketsNum() const;
        
    private:
        /**
         * Returns the bucket where 'element' should fall
         * into. Currently assumes that 'element' is greater than the
         * minimum 'inialValue'.
         */
        boost::uint32_t _findBucket( boost::uint32_t element ) const;

        boost::uint32_t  _initialValue;  // no value lower than it is recorded
        boost::uint32_t  _numBuckets;    // total buckets in the histogram

        // all below owned here
        boost::uint32_t* _boundaries;    // maximum element of each bucket
        boost::uint64_t* _buckets;       // current count of each bucket

        Histogram( const Histogram& );
        Histogram& operator=( const Histogram& );
    };

}  // namespace mongo

#endif  //  UTIL_HISTOGRAM_HEADER