source: source/ariba/overlay/modules/chord/detail/minimizer_table.hpp@ 5504

// [License]

// The Ariba-Underlay Copyright

//

// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)

//

// Institute of Telematics

// UniversitÀt Karlsruhe (TH)

// Zirkel 2, 76128 Karlsruhe

// Germany

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

// 1. Redistributions of source code must retain the above copyright

// notice, this list of conditions and the following disclaimer.

// 2. 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.

//

// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``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 THE INSTITUTE OF TELEMATICS OR

// CONTRIBUTORS 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.

//

// The views and conclusions contained in the software and documentation

// are those of the authors and should not be interpreted as representing

// official policies, either expressed or implied, of the Institute of

// Telematics.

// [License]

#ifndef MINIMIZER_TABLE_HPP_

#define MINIMIZER_TABLE_HPP_



#include <vector>

#include <iostream>

#include "table_listener.hpp"



using std::vector;

using std::ostream;



/**

 * TODO: Doc

 *

 * @author Sebastian Mies <mies@tm.uka.de>

 */

template<class Value, class Comparator, typename Listener = table_listener>

class minimizer_table: public vector<Value> {

private:

        // define table type

        typedef vector<Value> super;



        // members

        size_t max_size;

        Comparator compare;



        // listener

        Listener& listener;



public:



        /// delegates from vector<Value>

        typedef typename super::iterator iterator;



        /// delegates from vector<Value>

        typedef typename super::const_iterator const_iterator;



        /// explicitly construct a minimizer table

        explicit minimizer_table(size_t max_size, Comparator compare = Comparator(),

                        Listener& listener = Listener::DEFAULT) :

                        super(), max_size(max_size), compare(compare), listener(listener) {

        }



        /// returns true, if the value would fit into the table

        bool insertable( const Value& value ) {

                return insert(value,true) != super::end();

        }



        /// inserts a value into an ordered list

        iterator insert(const Value& value, bool simulate = false ) {

                iterator iter = super::end();



                // table empty? -> just add entry

                if (super::size() == 0) {

                        if (!simulate) super::push_back(value);

                        iter = super::end()-1;

                        if (!simulate) listener.on_table( table_listener::insert, *this, iter );

                } else



                // add at correct position

                for (iterator i = super::begin(); i != super::end(); i++) {

                        int cmp = compare(value, *i);

                        if (cmp < 0) {

                                if (!simulate) {

                                        iter = super::insert(i, value);

                                } else

                                        iter = i;

                                if (!simulate)

                                        listener.on_table( table_listener::insert, *this, iter );

                                break;

                        } else

                        if (cmp == 0) return iter;

                }



                // no item smaller than item and table not full? -> append

                if (iter == super::end() && super::size() != max_size) {

                        if (!simulate)

                        super::push_back(value);

                        iter = super::end()-1;

                        if (!simulate) listener.on_table( table_listener::insert, *this, iter );



                } else



                // drop entries

                if (super::size() > max_size) {

                        if (!simulate) {

                                listener.on_table( table_listener::remove, *this, super::end()-1 );

                                super::pop_back();

                        }

                }

                return iter;

        }



        /// remove value from ordered list

        bool remove(const Value& value) {

                for (iterator i = super::begin(); i != super::end(); i++)

                if (*i == value) {

                        super::erase(i);

                        return true;

                }

                return false;

        }



        /// check whether this list contains a specific value

        bool contains(const Value& value) const {

                for (const_iterator i = super::begin(); i != super::end(); i++)

                if (*i == value) return true;

                return false;

        }



        Comparator& get_compare() {

                return compare;

        }

};



/// prints a list of items

template<class V, class C, class L>

std::ostream& operator<<(std::ostream& s, const minimizer_table<V, C, L>& v) {

        typedef minimizer_table<V, C, L> t;

        for (typename t::const_iterator i = v.begin(); i != v.end(); i++) {

                if (i != v.begin()) s << ",";

                s << *i;

        }

        return s;

}



#endif /* MINIMIZER_TABLE_HPP_ */