distribution.h

Go to the documentation of this file.

/*
 * distribution.h
 *
 * Copyright (C) 2007   Thomas A. Vaughan
 * All rights reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Distribution collection.
 */

#ifndef WAVEPACKET_UTIL_DISTRIBUTION_H__
#define WAVEPACKET_UTIL_DISTRIBUTION_H__


/// \ingroup util
/// Basic distribution template.
/// You can add samples, then query to find percentiles etc.
template <class T>
class distribution_t {
public:
        distribution_t(void) throw() { this->clear(); }

        void clear(void) throw() {
                        m_count = 0;
                        m_map.clear();
                }

        void addSample(IN T x) {
                        m_count++;
                        typename map_t::iterator i = m_map.find(x);
                        if (m_map.end() == i) {
                                m_map[x] = 1;
                                return;
                        }
                        // m_map[x] = m_map[x] + 1;
                        i->second = i->second + 1;
                }

        long size(void) const throw() { return m_count; }

        /// note that 0 < p < 1
        T getValueAtPercentile(IN float p) const throw() {
                        ASSERT(p > 0.0 && p < 1.0, "Bad p: %f", p);

                        // This is the most important line in the file!
                        //      (idx = p * m_count)
                        // There is a temptation to worry about rounding, and
                        //   add additional fudge factors like 0.00001 or 0.5
                        // Don't!
                        //
                        // Imagine a distribution with only 3 entries.
                        // The 33% value is the first entry!
                        // The 34-66% value is the second
                        // The 67+% value is the third
                        long idx = (long) (p * m_count);

                        return getValueAtIndex(idx);
                }

        /// given a sample index, return its value.  Samples are ordered by
        ///     size, so the smallest will have idx = 0.
        T getValueAtIndex(IN int idx) const throw() {
                        ASSERT(idx >= 0 && idx < m_count,
                            "Bad index: %d", idx);

                        long j = 0;
                        for (typename map_t::const_iterator i = m_map.begin();
                             i != m_map.end(); ++i) {
                                j += i->second;
                                if (j > idx) {
//                                      DPRINTF("    Using sample %ld", j);
                                        return i->first;
                                }
                        }
                        ASSERT(false, "should never get here!");
                        return 0;
                }

        float getPercentileAtValue(IN T x) const throw() {
                        long j = 0;
                        for (typename map_t::const_iterator i = m_map.begin();
                             i != m_map.end(); ++i) {
                                if (i->first >= x) {
                                        return ((1.0 * j) / (1.0 * m_count));
                                }
                                j += i->second;
                        }
                        return 1.0;     // must be past end
                }

private:
        typedef std::map<T, int> map_t;

        map_t           m_map;          // value --> count
        long            m_count;        // total number of samples in distribut
};


#endif  // WAVEPACKET_UTIL_DISTRIBUTION_H__