00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #ifndef RANKER_H
00028 #define RANKER_H
00029
00030 #include <vector>
00031 #include <string>
00032 #include <algorithm>
00033
00034 using std::vector;
00035 using std::string;
00036
00037 #ifndef uint
00038 typedef unsigned int uint;
00039 #endif
00040
00041 template <class T>
00042 class lt { public: static int compare(T a, T b) { return(a < b); } };
00043 template <class T>
00044 class gt { public: static int compare(T a, T b) { return(a > b); } };
00045
00046 template <class T, class C>
00047 class ranker
00048 {
00049 private:
00050 const T* p;
00051 uint sz;
00052
00053 public:
00054 ranker(const vector<T>& v) : p(&v[0]), sz(v.size()) { }
00055 ranker(const T* tp, uint s) : p(tp), sz(s) { }
00056
00057 int operator()(uint i1, uint i2) const { return(C::compare(p[i1],p[i2])); }
00058
00059 template <class S>
00060 void get_orders(vector<S>& w) const {
00061 w.resize(sz);
00062 w.front() = 0;
00063 for (typename vector<S>::iterator i = w.begin(); i != w.end() - 1; ++i)
00064 *(i + 1) = *i + 1;
00065 std::sort(w.begin(), w.end(), *this);
00066 }
00067
00068 template <class S>
00069 void get_partial_orders(vector<S>& w, uint num) const {
00070 if (num > sz) num = sz;
00071 w.resize(sz);
00072 w.front() = 0;
00073 for (typename vector<S>::iterator i = w.begin(); i != w.end() - 1; ++i)
00074 *(i + 1) = *i + 1;
00075 std::partial_sort(w.begin(), w.begin() + num, w.end(), *this);
00076 w.resize(num);
00077 }
00078
00079 template <class S>
00080 void get_ranks(vector<S>& w, const string& method) const {
00081 w.resize(sz);
00082 vector<uint> tmp(w.size());
00083 get_orders(tmp);
00084 if (method == "average") {
00085 for (uint c = 0, reps; c < w.size(); c += reps) { reps = 1;
00086 while (c + reps < w.size() && p[tmp[c]] == p[tmp[c + reps]]) ++reps;
00087 for (uint k = 0; k < reps; ++k)
00088 w[tmp[c + k]] = S(2 * c + reps - 1) / 2 + 1;
00089 }
00090 } else if (method == "min") {
00091 for (uint c = 0, reps; c < w.size(); c += reps) { reps = 1;
00092 while (c + reps < w.size() && p[tmp[c]] == p[tmp[c + reps]]) ++reps;
00093 for (uint k = 0; k < reps; ++k) w[tmp[c + k]] = c + 1;
00094 }
00095 } else if (method == "max") {
00096 for (uint c = 0, reps; c < w.size(); c += reps) { reps = 1;
00097 while (c + reps < w.size() && p[tmp[c]] == p[tmp[c + reps]]) ++reps;
00098 for (uint k = 0; k < reps; ++k) w[tmp[c + k]] = c + reps;
00099 }
00100 } else
00101 for (uint c = 0; c < w.size(); ++c) w[tmp[c]] = c + 1;
00102 }
00103
00104 template <class S>
00105 void get_partial_ranks(vector<S>& w, const string& method, size_t num) const {
00106 if (num > sz) num = sz;
00107 vector<uint> tmp(sz);
00108 get_partial_orders(tmp, num);
00109 w.resize(sz);
00110 fill(w.begin(), w.end(), 0);
00111 if (method == "average") {
00112 for (uint c = 0, reps; c < num; c += reps) { reps = 1;
00113 while (c + reps < num && p[tmp[c]] == p[tmp[c + reps]]) ++reps;
00114 for (uint k = 0; k < reps; ++k)
00115 w[tmp[c + k]] = S(2 * c + reps - 1) / 2 + 1;
00116 }
00117 } else if (method == "min") {
00118 for (uint c = 0, reps; c < num; c += reps) { reps = 1;
00119 while (c + reps < num && p[tmp[c]] == p[tmp[c + reps]]) ++reps;
00120 for (uint k = 0; k < reps; ++k) w[tmp[c + k]] = c + 1;
00121 }
00122 } else if (method == "max") {
00123 for (uint c = 0, reps; c < num; c += reps) { reps = 1;
00124 while (c + reps < num && p[tmp[c]] == p[tmp[c + reps]]) ++reps;
00125 for (uint k = 0; k < reps; ++k) w[tmp[c + k]] = c + reps;
00126 }
00127 } else
00128 for (uint c = 0; c < num; ++c) w[tmp[c]] = c + 1;
00129 }
00130
00131 };
00132
00133 template <class T, class S>
00134 inline void rank(const vector<T>& v, vector<S>& w,
00135 const string& method = "average")
00136 { ranker<T, lt<T> > r(v); r.get_ranks(w, method); }
00137
00138 template <class T, class S>
00139 inline void rank(const T* d, uint size, vector<S>& w,
00140 const string& method = "average")
00141 { ranker<T, lt<T> > r(d, size); r.get_ranks(w, method); }
00142
00143 template <class T, class S>
00144 inline void partial_rank(const vector<T>& v, vector<S>& w, uint num,
00145 const string& method = "average")
00146 { ranker<T, lt<T> > r(v); r.get_partial_ranks(w, method, num); }
00147
00148 template <class T, class S>
00149 inline void partial_rank(const T* d, uint size, vector<S>& w, uint num,
00150 const string& method = "average")
00151 { ranker<T, lt<T> > r(d, size); r.get_partial_ranks(w, method, num); }
00152
00153 template <class T, class S>
00154 inline void order(const vector<T>& v, vector<S>& w)
00155 { ranker<T, lt<T> > r(v); r.get_orders(w); }
00156
00157 template <class T, class S>
00158 inline void order(const T* d, uint size, vector<S>& w)
00159 { ranker<T, lt<T> > r(d, size); r.get_orders(w); }
00160
00161 template <class T, class S>
00162 inline void partial_order(const vector<T>& v, vector<S>& w, uint num)
00163 { ranker<T, lt<T> > r(v); r.get_partial_orders(w, num); }
00164
00165 template <class T, class S>
00166 inline void partial_order(const T* d, uint size, vector<S>& w, uint num)
00167 { ranker<T, lt<T> > r(d, size); r.get_partial_orders(w, num); }
00168
00169 template <class T, class S>
00170 inline void rankhigh(const vector<T>& v, vector<S>& w,
00171 const string& method = "average")
00172 { ranker<T, gt<T> > r(v); r.get_ranks(w, method); }
00173
00174 template <class T, class S>
00175 inline void rankhigh(const T* d, uint size, vector<S>& w,
00176 const string& method = "average")
00177 { ranker<T, gt<T> > r(d, size); r.get_ranks(w, method); }
00178
00179 template <class T, class S>
00180 inline void partial_rankhigh(const vector<T>& v, vector<S>& w, uint num,
00181 const string& method = "average")
00182 { ranker<T, gt<T> > r(v); r.get_partial_ranks(w, method, num); }
00183
00184 template <class T, class S>
00185 inline void partial_rankhigh(const T* d, uint size, vector<S>& w, uint num,
00186 const string& method = "average")
00187 { ranker<T, gt<T> > r(d, size); r.get_partial_ranks(w, method, num); }
00188
00189 template <class T, class S>
00190 inline void orderhigh(const vector<T>& v, vector<S>& w)
00191 { ranker<T, gt<T> > r(v); r.get_orders(w); }
00192
00193 template <class T, class S>
00194 inline void orderhigh(const T* d, uint size, vector<S>& w)
00195 { ranker<T, gt<T> > r(d, size); r.get_orders(w); }
00196
00197 template <class T, class S>
00198 inline void partial_orderhigh(const vector<T>& v, vector<S>& w, uint num)
00199 { ranker<T, gt<T> > r(v); r.get_partial_orders(w, num); }
00200
00201 template <class T, class S>
00202 inline void partial_orderhigh(const T* d, uint size, vector<S>& w, uint num)
00203 { ranker<T, gt<T> > r(d, size); r.get_partial_orders(w, num); }
00204
00205 template <class T>
00206 inline T quantile(const T* d, const uint size, const double q)
00207 {
00208 if (size == 0) return T(0);
00209 if (size == 1) return d[0];
00210 if (q <= 0) return *std::min_element(d, d + size);
00211 if (q >= 1) return *std::max_element(d, d + size);
00212
00213 double pos = (size - 1) * q;
00214 uint ind = uint(pos);
00215 double delta = pos - ind;
00216 vector<T> w(size); std::copy(d, d + size, w.begin());
00217 std::nth_element(w.begin(), w.begin() + ind, w.end());
00218 T i1 = *(w.begin() + ind);
00219 T i2 = *std::min_element(w.begin() + ind + 1, w.end());
00220 return (T) (i1 * (1.0 - delta) + i2 * delta);
00221 }
00222
00223 template <class T>
00224 inline T quantile(const vector<T>& v, const double q)
00225 { return quantile(&v[0], v.size(), q); }
00226
00227 #endif
00228
