00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef MINIMIZER_TABLE_HPP_
00039 #define MINIMIZER_TABLE_HPP_
00040
00041 #include <vector>
00042 #include <iostream>
00043 #include "table_listener.hpp"
00044
00045 using std::vector;
00046 using std::ostream;
00047
00053 template<class Value, class Comparator, typename Listener = table_listener>
00054 class minimizer_table: public vector<Value> {
00055 private:
00056
00057 typedef vector<Value> super;
00058
00059
00060 size_t max_size;
00061 Comparator compare;
00062
00063
00064 Listener& listener;
00065
00066 public:
00067
00069 typedef typename super::iterator iterator;
00070
00072 typedef typename super::const_iterator const_iterator;
00073
00075 explicit minimizer_table(size_t max_size, Comparator compare = Comparator(),
00076 Listener& listener = Listener::DEFAULT) :
00077 super(), max_size(max_size), compare(compare), listener(listener) {
00078 }
00079
00081 bool insertable( const Value& value ) {
00082 return insert(value,true) != super::end();
00083 }
00084
00086 iterator insert(const Value& value, bool simulate = false ) {
00087 iterator iter = super::end();
00088
00089
00090 if (super::size() == 0) {
00091 if (!simulate) super::push_back(value);
00092 iter = super::end()-1;
00093 if (!simulate) listener.on_table( table_listener::insert, *this, iter );
00094 } else
00095
00096
00097 for (iterator i = super::begin(); i != super::end(); i++) {
00098 int cmp = compare(value, *i);
00099 if (cmp < 0) {
00100 if (!simulate) {
00101 iter = super::insert(i, value);
00102 } else
00103 iter = i;
00104 if (!simulate)
00105 listener.on_table( table_listener::insert, *this, iter );
00106 break;
00107 } else
00108 if (cmp == 0) return iter;
00109 }
00110
00111
00112 if (iter == super::end() && super::size() != max_size) {
00113 if (!simulate)
00114 super::push_back(value);
00115 iter = super::end()-1;
00116 if (!simulate) listener.on_table( table_listener::insert, *this, iter );
00117
00118 } else
00119
00120
00121 if (super::size() > max_size) {
00122 if (!simulate) {
00123 listener.on_table( table_listener::remove, *this, super::end()-1 );
00124 super::pop_back();
00125 }
00126 }
00127 return iter;
00128 }
00129
00131 bool remove(const Value& value) {
00132 for (iterator i = super::begin(); i != super::end(); i++)
00133 if (*i == value) {
00134 super::erase(i);
00135 return true;
00136 }
00137 return false;
00138 }
00139
00141 bool contains(const Value& value) const {
00142 for (const_iterator i = super::begin(); i != super::end(); i++)
00143 if (*i == value) return true;
00144 return false;
00145 }
00146
00147 Comparator& get_compare() {
00148 return compare;
00149 }
00150 };
00151
00153 template<class V, class C, class L>
00154 std::ostream& operator<<(std::ostream& s, const minimizer_table<V, C, L>& v) {
00155 typedef minimizer_table<V, C, L> t;
00156 for (typename t::const_iterator i = v.begin(); i != v.end(); i++) {
00157 if (i != v.begin()) s << ",";
00158 s << *i;
00159 }
00160 return s;
00161 }
00162
00163 #endif