00001
00002 #ifndef vbl_batch_compact_multimap_h_
00003 #define vbl_batch_compact_multimap_h_
00004
00005
00006
00007
00008
00009 #include <vcl_cassert.h>
00010 #include <vcl_vector.h>
00011 #include <vcl_cstddef.h>
00012 #include <vcl_functional.h>
00013 #include <vcl_utility.h>
00014 #include <vcl_algorithm.h>
00015 #include <vcl_iterator.h>
00016
00017
00018
00019
00020
00021
00022
00023 template <typename K, typename T, typename C=vcl_less<K> >
00024 class vbl_batch_compact_multimap
00025 {
00026 public:
00027 typedef K key_type;
00028 typedef T value_type;
00029
00030 typedef typename vcl_pair<key_type, value_type> input_type;
00031 typedef C key_compare;
00032 typedef unsigned index_type;
00033 typedef typename vcl_vector<key_type> key_container_type;
00034 typedef typename vcl_vector<index_type> index_container_type;
00035 typedef typename vcl_vector<value_type> value_container_type;
00036
00037 typedef typename key_container_type::const_iterator const_key_iterator;
00038 typedef typename value_container_type::const_iterator const_value_iterator;
00039
00040 protected:
00041
00042 typedef typename vcl_vector<input_type> input_container_type;
00043
00044 public:
00045
00046 class input_compare
00047 : public vcl_binary_function<input_type, input_type, bool>
00048 {
00049 public:
00050 friend class vbl_batch_compact_multimap<key_type, value_type, key_compare>;
00051
00052 key_compare comp;
00053
00054 input_compare(key_compare c): comp(c) { }
00055
00056 bool operator()(const input_type& x, const input_type& y) const
00057 { return comp(x.first, y.first); }
00058 };
00059
00060 vbl_batch_compact_multimap() {}
00061
00062 template <typename CI>
00063 vbl_batch_compact_multimap(CI start, CI finish)
00064 {
00065 input_container_type in(start, finish);
00066 vcl_sort(in.begin(), in.end(), input_compare(key_compare()));
00067 assign_sorted(in.begin(), in.end());
00068 }
00069
00070
00071 template <typename CI>
00072 void assign(CI start, CI finish)
00073 {
00074 input_container_type in(start, finish);
00075 vcl_sort(in.begin(), in.end(), input_compare(key_compare()));
00076 assign_sorted(in.begin(), in.end());
00077 }
00078
00079
00080
00081 template <typename CI>
00082 void assign_sorted(CI start, CI finish)
00083 {
00084 keys_.clear();
00085 indices_.clear();
00086 values_.clear();
00087 assert(is_sorted(start, finish, input_compare(key_compare())));
00088 while (start != finish)
00089 {
00090 typename vcl_iterator_traits<CI>::value_type::first_type const & last_start_val = start->first;
00091 keys_.push_back(start->first);
00092 indices_.push_back(values_.size());
00093 values_.push_back(start->second);
00094 while(++start != finish && start->first == last_start_val)
00095 {
00096 values_.push_back(start->second);
00097 }
00098 }
00099 indices_.push_back(values_.size());
00100 }
00101
00102 void swap(vbl_batch_compact_multimap& x)
00103 {
00104 keys_.swap(x.keys_);
00105 indices_.swap(x.indices_);
00106 values_.swap(x.values_);
00107 }
00108
00109 bool operator==(const vbl_batch_compact_multimap& rhs)
00110 {
00111 return keys_ == rhs.keys_ &&
00112 indices_ == rhs.indices_ &&
00113 values_ == rhs.values_;
00114 }
00115
00116
00117
00118 const_key_iterator keys_begin() const { return keys_.begin(); }
00119 const_key_iterator keys_end() const { return keys_.end(); }
00120 const_value_iterator values_begin() const { return values_.begin(); }
00121 const_value_iterator values_end() const { return values_.end(); }
00122 bool empty() const { return values_.empty(); }
00123 vcl_size_t size() const { return values_.size(); }
00124
00125
00126
00127
00128
00129
00130 const_value_iterator lower_bound(const key_type& x) const
00131 {
00132 const_key_iterator k_it = vcl_lower_bound(keys_.begin(), keys_.end(),
00133 x, key_compare() );
00134
00135 return values_.begin() + indices_[k_it - keys_.begin()];
00136 }
00137
00138
00139
00140
00141 const_value_iterator upper_bound(const key_type& x) const
00142 {
00143 const_key_iterator k_it = vcl_upper_bound(keys_.begin(), keys_.end(),
00144 x, key_compare() );
00145
00146 return values_.begin() + indices_[k_it - keys_.begin()];
00147 }
00148
00149
00150 vcl_pair<const_value_iterator, const_value_iterator> equal_range(const key_type& x) const
00151 {
00152
00153
00154 const_key_iterator k_it = vcl_lower_bound(keys_.begin(), keys_.end(),
00155 x, key_compare() );
00156
00157 if (k_it == keys_end() || *k_it != x)
00158 {
00159 const_value_iterator v_it=values_.begin() + indices_[k_it - keys_.begin()];
00160 return vcl_make_pair(v_it, v_it);
00161 }
00162 else
00163 {
00164 return vcl_make_pair(values_.begin() + indices_[k_it - keys_.begin()],
00165 values_.begin() + indices_[k_it - keys_.begin() + 1u] );
00166 }
00167 }
00168
00169
00170 const_value_iterator find(const key_type& x) const
00171 {
00172 const_key_iterator k_it = vcl_lower_bound(keys_.begin(), keys_.end(),
00173 x, key_compare() );
00174
00175 if (k_it == keys_end() || *k_it != x)
00176 return values_end();
00177 else
00178 return values_.begin() + indices_[k_it - keys_.begin()];
00179 }
00180
00181
00182 vcl_size_t count(const key_type& x) const
00183 {
00184 const_key_iterator k_it = vcl_lower_bound(keys_.begin(), keys_.end(),
00185 x, key_compare() );
00186
00187 if (k_it == keys_end() || *k_it != x)
00188 return 0;
00189 else
00190 return indices_[k_it - keys_.begin() + 1u] - indices_[k_it - keys_.begin()];
00191 }
00192
00193 private:
00194 key_container_type keys_;
00195 index_container_type indices_;
00196 value_container_type values_;
00197
00198 template <typename CI, typename CMP>
00199 bool is_sorted(CI start, CI end, CMP comp)
00200 {
00201 if (start == end) return true;
00202
00203 for (--end; start!=end; ++start)
00204 {
00205
00206 if (comp(*(start+1), *start)) return false;
00207 }
00208 return true;
00209 }
00210 };
00211
00212 template<typename K, typename T, typename C>
00213 inline void swap(vbl_batch_compact_multimap<K, T, C> &x, vbl_batch_compact_multimap<K, T, C>& y)
00214 {
00215 x.swap(y);
00216 }
00217
00218 #endif // vbl_batch_compact_multimap_h_