00001 #ifndef UTIL_JOINT_SORT_H
00002 #define UTIL_JOINT_SORT_H
00003
00004
00005
00006
00007
00008 #include "util/proxy_iterator.hh"
00009
00010 #include <algorithm>
00011 #include <functional>
00012
00013 namespace util {
00014
00015 namespace detail {
00016
00017 template <class KeyIter, class ValueIter> class JointProxy;
00018
00019 template <class KeyIter, class ValueIter> class JointIter {
00020 public:
00021 JointIter() {}
00022
00023 JointIter(const KeyIter &key_iter, const ValueIter &value_iter) : key_(key_iter), value_(value_iter) {}
00024
00025 bool operator==(const JointIter<KeyIter, ValueIter> &other) const { return key_ == other.key_; }
00026
00027 bool operator<(const JointIter<KeyIter, ValueIter> &other) const { return (key_ < other.key_); }
00028
00029 std::ptrdiff_t operator-(const JointIter<KeyIter, ValueIter> &other) const { return key_ - other.key_; }
00030
00031 JointIter<KeyIter, ValueIter> &operator+=(std::ptrdiff_t amount) {
00032 key_ += amount;
00033 value_ += amount;
00034 return *this;
00035 }
00036
00037 friend void swap(JointIter &first, JointIter &second) {
00038 using std::swap;
00039 swap(first.key_, second.key_);
00040 swap(first.value_, second.value_);
00041 }
00042
00043 void DeepSwap(JointIter &other) {
00044 using std::swap;
00045 swap(*key_, *other.key_);
00046 swap(*value_, *other.value_);
00047 }
00048
00049 private:
00050 friend class JointProxy<KeyIter, ValueIter>;
00051 KeyIter key_;
00052 ValueIter value_;
00053 };
00054
00055 template <class KeyIter, class ValueIter> class JointProxy {
00056 private:
00057 typedef JointIter<KeyIter, ValueIter> InnerIterator;
00058
00059 public:
00060 typedef struct {
00061 typename std::iterator_traits<KeyIter>::value_type key;
00062 typename std::iterator_traits<ValueIter>::value_type value;
00063 const typename std::iterator_traits<KeyIter>::value_type &GetKey() const { return key; }
00064 } value_type;
00065
00066 JointProxy(const KeyIter &key_iter, const ValueIter &value_iter) : inner_(key_iter, value_iter) {}
00067 JointProxy(const JointProxy<KeyIter, ValueIter> &other) : inner_(other.inner_) {}
00068
00069 operator value_type() const {
00070 value_type ret;
00071 ret.key = *inner_.key_;
00072 ret.value = *inner_.value_;
00073 return ret;
00074 }
00075
00076 JointProxy &operator=(const JointProxy &other) {
00077 *inner_.key_ = *other.inner_.key_;
00078 *inner_.value_ = *other.inner_.value_;
00079 return *this;
00080 }
00081
00082 JointProxy &operator=(const value_type &other) {
00083 *inner_.key_ = other.key;
00084 *inner_.value_ = other.value;
00085 return *this;
00086 }
00087
00088 typename std::iterator_traits<KeyIter>::reference GetKey() const {
00089 return *(inner_.key_);
00090 }
00091
00092 friend void swap(JointProxy<KeyIter, ValueIter> first, JointProxy<KeyIter, ValueIter> second) {
00093 first.Inner().DeepSwap(second.Inner());
00094 }
00095
00096 private:
00097 friend class ProxyIterator<JointProxy<KeyIter, ValueIter> >;
00098
00099 InnerIterator &Inner() { return inner_; }
00100 const InnerIterator &Inner() const { return inner_; }
00101 InnerIterator inner_;
00102 };
00103
00104 template <class Proxy, class Less> class LessWrapper : public std::binary_function<const typename Proxy::value_type &, const typename Proxy::value_type &, bool> {
00105 public:
00106 explicit LessWrapper(const Less &less) : less_(less) {}
00107
00108 bool operator()(const Proxy &left, const Proxy &right) const {
00109 return less_(left.GetKey(), right.GetKey());
00110 }
00111 bool operator()(const Proxy &left, const typename Proxy::value_type &right) const {
00112 return less_(left.GetKey(), right.GetKey());
00113 }
00114 bool operator()(const typename Proxy::value_type &left, const Proxy &right) const {
00115 return less_(left.GetKey(), right.GetKey());
00116 }
00117 bool operator()(const typename Proxy::value_type &left, const typename Proxy::value_type &right) const {
00118 return less_(left.GetKey(), right.GetKey());
00119 }
00120
00121 private:
00122 const Less less_;
00123 };
00124
00125 }
00126
00127 template <class KeyIter, class ValueIter> class PairedIterator : public ProxyIterator<detail::JointProxy<KeyIter, ValueIter> > {
00128 public:
00129 PairedIterator(const KeyIter &key, const ValueIter &value) :
00130 ProxyIterator<detail::JointProxy<KeyIter, ValueIter> >(detail::JointProxy<KeyIter, ValueIter>(key, value)) {}
00131 };
00132
00133 template <class KeyIter, class ValueIter, class Less> void JointSort(const KeyIter &key_begin, const KeyIter &key_end, const ValueIter &value_begin, const Less &less) {
00134 ProxyIterator<detail::JointProxy<KeyIter, ValueIter> > full_begin(detail::JointProxy<KeyIter, ValueIter>(key_begin, value_begin));
00135 detail::LessWrapper<detail::JointProxy<KeyIter, ValueIter>, Less> less_wrap(less);
00136 std::sort(full_begin, full_begin + (key_end - key_begin), less_wrap);
00137 }
00138
00139
00140 template <class KeyIter, class ValueIter> void JointSort(const KeyIter &key_begin, const KeyIter &key_end, const ValueIter &value_begin) {
00141 JointSort(key_begin, key_end, value_begin, std::less<typename std::iterator_traits<KeyIter>::value_type>());
00142 }
00143
00144 }
00145
00146 #endif // UTIL_JOINT_SORT_H