WRR.h

/*
** libutil++
** $Id: WRR.h 1653 2016-02-28 19:54:59Z sella $
** Copyright (c) 2011-2016 Digital Genesis, LLC. All Rights Reserved.
** Released under the LGPL Version 2.1 License.
** http://www.digitalgenesis.com
*/

#ifndef __libutilxx__sella__algo__WRR_H__
#define __libutilxx__sella__algo__WRR_H__

#include "../../common.h"

#include <stdio.h>
#include <string>
#include <map>

namespace sella {
        namespace algo {
                template <class T> class WRR;

                template <class T> class WRRNode {
                        friend class WRR<T>;
                
                        public:
                                WRRNode(const T & data, double weight = 1.0) throw ();
                
                        private:
                                double  weight;
                
                                double  points;
                                double  rate;
                
                                T                       data;
                };

                template <class T> class WRR {
                        public:
                                WRR() throw ();
                
                                void insert(const std::string & identifier, const T & node, double weight = 1.0) throw ();
                                void remove(const std::string & identifier) throw ();
                                void update(const std::string & identifier, double weight = 1.0) throw ();
                
                                T & next() throw ();
                
                        private:
                                double  total;
                
                                typename std::map<std::string, WRRNode<T> >                             node;
                                typename std::map<std::string, WRRNode<T> >::iterator   iter;
                };
        }
}

template <class T> sella::algo::WRR<T>::WRR() throw () :
        total(0.0),

        node(),
        iter(node.end())
{ }

template <class T> sella::algo::WRRNode<T>::WRRNode(const T & data, double weight) throw () :
        weight(weight),

        points(0.0),
        rate(0.0),

        data(data)
{ }

template <class T> void sella::algo::WRR<T>::insert(const std::string & identifier, const T & node, double weight) throw () {
        this->node.insert(std::make_pair(identifier, WRRNode<T>(node, weight)));
        this->total += weight;

        for (auto iter = this->node.begin(); iter != this->node.end(); ++iter) {
                iter->second.rate = iter->second.weight / this->total;
        }
}

template <class T> void sella::algo::WRR<T>::remove(const std::string & identifier) throw () {
        auto    iter = this->node.find(identifier);

        if (iter != this->node.end()) {
                this->total -= iter->second.weight;

                this->node.erase(iter);
        }

        for (iter = this->node.begin(); iter != this->node.end(); ++iter) {
                iter->second.rate = iter->second.weight / this->total;
        }
}

template <class T> void sella::algo::WRR<T>::update(const std::string & identifier, double weight) throw () {
        auto    iter = this->node.find(identifier);

        if (iter != this->node.end()) {
                iter->weight = weight;

                this->total -= iter->second.weight;
                this->total += weight;
        }

        for (iter = this->node.begin(); iter != this->node.end(); ++iter) {
                iter->second.rate = iter->second.weight / this->total;
        }
}

template <class T> T & sella::algo::WRR<T>::next() throw () {
        while (true) {
                while (this->iter != this->node.end()) {
                        auto    item = this->iter;

                        ++(this->iter);

                        item->second.points += item->second.rate;

                        if (item->second.points >= 1.0) {
                                item->second.points -= 1.0;

                                return item->second.data;
                        }
                }
                this->iter = this->node.begin();
        }
}

#endif

/*
** vim: noet ts=3 sw=3
*/