00001
00002 #ifndef vbl_batch_multimap_h_
00003 #define vbl_batch_multimap_h_
00004
00005
00006
00007
00008
00009
00010
00011 #include <vcl_cassert.h>
00012 #include <vcl_vector.h>
00013 #include <vcl_cstddef.h>
00014 #include <vcl_functional.h>
00015 #include <vcl_utility.h>
00016 #include <vcl_algorithm.h>
00017
00018 namespace
00019 {
00020
00021 }
00022
00023
00024
00025 template <typename K, typename T, typename C=vcl_less<K> >
00026 class vbl_batch_multimap
00027 {
00028 public:
00029 typedef K key_type;
00030 typedef T mapped_type;
00031 typedef typename vcl_pair<key_type, mapped_type> value_type;
00032 typedef C key_compare;
00033 typedef typename vcl_vector<value_type> container_type;
00034 typedef typename container_type::allocator_type allocator_type;
00035
00036 typedef typename container_type::const_iterator const_iterator;
00037
00038 typedef typename container_type::const_reference const_reference;
00039
00040
00041
00042 class value_compare_t
00043 : public vcl_binary_function<value_type, value_type, bool>
00044 {
00045
00046
00047 public:
00048 key_compare comp;
00049
00050 value_compare_t(key_compare c)
00051 : comp(c) { }
00052
00053 public:
00054 bool operator()(const value_type& x, const value_type& y) const
00055 { return comp(x.first, y.first); }
00056
00057 bool compare(const value_type& x, const value_type& y) const
00058 { return comp(x.first, y.first); }
00059 };
00060
00061
00062 vbl_batch_multimap() :data_() {}
00063
00064 template <typename CI>
00065 vbl_batch_multimap(CI start, CI finish):
00066 data_(start, finish)
00067 {
00068 vcl_sort(data_.begin(), data_.end(), value_compare_t(key_compare()));
00069 }
00070
00071
00072 template <typename CI>
00073 void assign(CI start, CI finish)
00074 {
00075 data_.assign(start, finish);
00076 vcl_sort(data_.begin(), data_.end(), value_compare_t(key_compare()));
00077 }
00078
00079
00080
00081 template <typename CI>
00082 void assign_sorted(CI start, CI finish)
00083 {
00084 data_.assign(start, finish);
00085 assert(is_sorted(start, finish, value_compare_t(key_compare())));
00086 }
00087
00088 void swap(vbl_batch_multimap& rhs)
00089 {
00090 data_.swap(rhs.data_);
00091 }
00092
00093
00094 bool operator==(const vbl_batch_multimap&rhs)
00095 {
00096 return data_ == rhs.data_;
00097 }
00098
00099
00100
00101 const_iterator begin() const { return data_.begin(); }
00102 const_iterator end() const { return data_.end(); }
00103 bool empty() const { return data_.empty(); }
00104 vcl_size_t size() const { return data_.size(); }
00105
00106
00107
00108
00109
00110
00111 const_iterator lower_bound(const key_type& key) const
00112 {
00113 return vcl_lower_bound(data_.begin(), data_.end(),
00114 make_pair(key, mapped_type()), value_compare_t(key_compare()));
00115 }
00116
00117
00118
00119
00120 const_iterator upper_bound(const key_type& key) const
00121 {
00122 return vcl_upper_bound(data_.begin(), data_.end(),
00123 make_pair(key, mapped_type()), value_compare_t(key_compare()));
00124 }
00125
00126
00127 vcl_pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00128 {
00129 return vcl_equal_range(data_.begin(), data_.end(),
00130 make_pair(key, mapped_type()), value_compare_t(key_compare()));
00131 }
00132
00133
00134 const_iterator find(const key_type& key) const
00135 {
00136 const_iterator it = lower_bound(key);
00137 if (it != end() && it->first != key)
00138 return end();
00139 else
00140 return it;
00141 }
00142
00143
00144 vcl_size_t count(const key_type& key) const
00145 {
00146 vcl_pair<const_iterator, const_iterator> range = equal_range(key);
00147 return range.second - range.first;
00148 }
00149
00150
00151 private:
00152 container_type data_;
00153
00154 template <typename CI, typename CMP>
00155 static bool is_sorted(CI start, CI end, CMP comp)
00156 {
00157 if (start == end) return true;
00158
00159 for (end--; start!=end; ++start)
00160 {
00161 if ( comp(*(start+1), *start)) return false;
00162 }
00163 return true;
00164 }
00165
00166 };
00167
00168 template<typename K, typename T, typename C>
00169 inline void swap(vbl_batch_multimap<K, T, C> &x, vbl_batch_multimap<K, T, C>& y)
00170 {
00171 x.swap(y);
00172 }
00173
00174 #endif // vbl_batch_multimap_h_