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

Last change on this file since 5926 was 5732, checked in by mies, 15 years ago
File size: 4.8 KB
Line 
1// [License]
2// The Ariba-Underlay Copyright
3//
4// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)
5//
6// Institute of Telematics
7// UniversitÀt Karlsruhe (TH)
8// Zirkel 2, 76128 Karlsruhe
9// Germany
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND
22// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OF TELEMATICS OR
25// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32//
33// The views and conclusions contained in the software and documentation
34// are those of the authors and should not be interpreted as representing
35// official policies, either expressed or implied, of the Institute of
36// Telematics.
37// [License]
38#ifndef MINIMIZER_TABLE_HPP_
39#define MINIMIZER_TABLE_HPP_
40
41#include <vector>
42#include <iostream>
43#include "table_listener.hpp"
44
45using std::vector;
46using std::ostream;
47
48/**
49 * TODO: Doc
50 *
51 * @author Sebastian Mies <mies@tm.uka.de>
52 */
53template<class Value, class Comparator, typename Listener = table_listener>
54class minimizer_table: public vector<Value> {
55private:
56 // define table type
57 typedef vector<Value> super;
58
59 // members
60 size_t max_size;
61 Comparator compare;
62
63 // listener
64 Listener& listener;
65
66public:
67
68 /// delegates from vector<Value>
69 typedef typename super::iterator iterator;
70
71 /// delegates from vector<Value>
72 typedef typename super::const_iterator const_iterator;
73
74 /// explicitly construct a minimizer table
75 explicit minimizer_table(size_t max_size, Comparator compare = Comparator(),
76 Listener& listener = Listener::DEFAULT) :
77 super(), max_size(max_size), compare(compare), listener(listener) {
78 }
79
80 /// returns true, if the value would fit into the table
81 bool insertable( const Value& value ) {
82 return insert(value,true) != super::end();
83 }
84
85 /// inserts a value into an ordered list
86 iterator insert(const Value& value, bool simulate = false ) {
87 iterator iter = super::end();
88
89 // table empty? -> just add entry
90 if (super::size() == 0) {
91 if (!simulate) super::push_back(value);
92 iter = super::end()-1;
93 if (!simulate) listener.on_table( table_listener::insert, *this, iter );
94 } else
95
96 // add at correct position
97 for (iterator i = super::begin(); i != super::end(); i++) {
98 int cmp = compare(value, *i);
99 if (cmp < 0) {
100 if (!simulate) {
101 iter = super::insert(i, value);
102 } else
103 iter = i;
104 if (!simulate)
105 listener.on_table( table_listener::insert, *this, iter );
106 break;
107 } else
108 if (cmp == 0) return iter;
109 }
110
111 // no item smaller than item and table not full? -> append
112 if (iter == super::end() && super::size() != max_size) {
113 if (!simulate)
114 super::push_back(value);
115 iter = super::end()-1;
116 if (!simulate) listener.on_table( table_listener::insert, *this, iter );
117
118 } else
119
120 // drop entries
121 if (super::size() > max_size) {
122 if (!simulate) {
123 listener.on_table( table_listener::remove, *this, super::end()-1 );
124 super::pop_back();
125 }
126 }
127 return iter;
128 }
129
130 /// remove value from ordered list
131 bool remove(const Value& value) {
132 for (iterator i = super::begin(); i != super::end(); i++)
133 if (*i == value) {
134// listener.on_table( table_listener::remove, *this, i );
135 super::erase(i);
136 return true;
137 }
138 return false;
139 }
140
141 /// check whether this list contains a specific value
142 bool contains(const Value& value) const {
143 for (const_iterator i = super::begin(); i != super::end(); i++)
144 if (*i == value) return true;
145 return false;
146 }
147
148 Comparator& get_compare() {
149 return compare;
150 }
151};
152
153/// prints a list of items
154template<class V, class C, class L>
155std::ostream& operator<<(std::ostream& s, const minimizer_table<V, C, L>& v) {
156 typedef minimizer_table<V, C, L> t;
157 for (typename t::const_iterator i = v.begin(); i != v.end(); i++) {
158 if (i != v.begin()) s << ",";
159 s << *i;
160 }
161 return s;
162}
163
164#endif /* MINIMIZER_TABLE_HPP_ */
Note: See TracBrowser for help on using the repository browser.