core/vbl/vbl_batch_multimap.h
Go to the documentation of this file.
00001 // This is core/vbl/vbl_batch_multimap.h
00002 #ifndef vbl_batch_multimap_h_
00003 #define vbl_batch_multimap_h_
00004 
00005 //:
00006 // \file
00007 // \brief Like a faster vcl_multimap but using only a single block of memory, and no fast insertion or deletion.
00008 // \author Ian Scott, Imorphics 2011
00009 
00010 
00011 #include <vcl_cassert.h>
00012 #include <vcl_vector.h>
00013 #include <vcl_cstddef.h> // for ptrdiff_t and size_t
00014 #include <vcl_functional.h>
00015 #include <vcl_utility.h>
00016 #include <vcl_algorithm.h>
00017 
00018 namespace
00019 {
00020 
00021 }
00022 //: A fast read and batch-write map-style collection.
00023 // This container stores its elements in a single vector, and has fast construction and deletion.
00024 // It has all the const-access map fundtions, but its contents can only be modified all-at-once.
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   //  friend class vbl_batch_multimap<key_type, mapped_type, key_compare>;
00046   // protected:
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   //: Change all the values in the multimap.
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   //: Change all the values in the multimap, to a ready sorted sequence
00080   // The input values must already be sorted on their v.first members.
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 // const vector API  
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 // const map API
00107 
00108   //: Finds the beginning of a subsequence matching given \p key.
00109   // /return iterator to the first element that equals \p key, or the 
00110   //   next greatest element if no match is found.
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   //: Finds the one past the end of a subsequence matching given \p key.
00118   // /return iterator to one past the last element that equals \p key, or to the 
00119   //   next greatest element if no match is found.
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   //: A more efficient  make_pair(lower_bound(...), upper_bound(...))
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   //: Finds the first matching value in the sequence, or returns end() if no match,
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   //: Finds the number of elements with matching \p key,
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_