core/vbl/vbl_batch_compact_multimap.h
Go to the documentation of this file.
00001 // This is core/vbl/vbl_batch_compact_multimap.h
00002 #ifndef vbl_batch_compact_multimap_h_
00003 #define vbl_batch_compact_multimap_h_
00004 //:
00005 // \file
00006 // \brief Like a smaller and slightly faster vcl_batch_multimap but without the pair<key, value> sequence
00007 // \author Ian Scott, Imorphics 2011
00008 
00009 #include <vcl_cassert.h>
00010 #include <vcl_vector.h>
00011 #include <vcl_cstddef.h> // for ptrdiff_t and size_t
00012 #include <vcl_functional.h>
00013 #include <vcl_utility.h>
00014 #include <vcl_algorithm.h>
00015 #include <vcl_iterator.h>
00016 
00017 
00018 //: A fast read and batch-write map-style collection.
00019 // This container stores its keys separately from its values, and has fast construction and deletion.
00020 // It has all the const-access map fundtions, but its contents can only be modified all-at-once.
00021 // You can not get a key,value pair, but you can get access to all the compactly-stored values for
00022 // a given key.
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   //: The type of data in the inputted sequence.
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   //: The type of container used internally to process inputted data.
00042   typedef typename vcl_vector<input_type> input_container_type;
00043 
00044  public:
00045   //: A comparator to sort input data, by ignoring the value in pair<key, value>
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   //: Change all the values in the multimap.
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   //: 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     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()); // always one more index than key.
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   // const vector API
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   // const map API
00126 
00127   //: Finds the beginning of a subsequence of values whose key matches given \p x.
00128   // \return iterator to the first value whose key matches \p x, or the
00129   //   next greatest element if no match is found.
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   //: Finds the one past the end of a subsequence of values whose key matches given \p x.
00139   // \return iterator to one past the last value whose key that matches \p key, or to the
00140   //   next greatest element if no match is found.
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   //: A more efficient  make_pair(lower_bound(...), upper_bound(...))
00150   vcl_pair<const_value_iterator, const_value_iterator> equal_range(const key_type& x) const
00151   {
00152     // This appears particularly slow in MSVC10 with no optimisation. In particular it appears slower
00153     // than vcl_map dereference.
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   //: Finds the first value with key matching \p x, or returns values_end() if no match,
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   //: Finds the number of values matching key \p x,
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       // if cmp(a,b) is the sorting criteria, then !cmp(b,a) is the testing criteria for is_sorted.
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_