src/my-place/utils/median.cpp

   1 /*
   2  * Copyright (c) 2016 Samsung Electronics Co., Ltd.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <algorithm>
  18 #include <Types.h>
  19 #include "median.h"
  20
  21 static bool compareFun(std::pair<double, int> &i, std::pair<double, int> &j) {
  22         return (i.first < j.first);
  23 }
  24
  25 double ctx::median(std::vector<double> &values, int &elemIdx, int &evenCaseElemIdx)
  26 {
  27         if (values.empty()) {
  28                 _E("Median of empty set");
  29                 return -1;
  30         }
  31         std::vector<std::pair<double, int>> valuesTemp;
  32         for (size_t i = 0; i < values.size(); i++) {
  33                 valuesTemp.push_back(std::pair<double, int>(values[i], i));
  34         }
  35         int n = valuesTemp.size() / 2;
  36         std::nth_element(valuesTemp.begin(), valuesTemp.begin() + n, valuesTemp.end(), compareFun);
  37         std::pair<double, int> valuesTempN = valuesTemp[n];
  38         elemIdx = valuesTempN.second;
  39         if (valuesTemp.size() % 2 == 1) { //odd size
  40                 evenCaseElemIdx = -1;
  41                 return valuesTempN.first;
  42         } else { // even size
  43                 std::nth_element(valuesTemp.begin(), valuesTemp.begin() + n - 1, valuesTemp.end());
  44                 evenCaseElemIdx = valuesTemp[n - 1].second;
  45                 return 0.5 * (valuesTempN.first + valuesTemp[n - 1].first);
  46         }
  47 }
  48
  49 ctx::Location ctx::medianLocation(std::vector<double> &latitudes, std::vector<double> &longitudes, std::vector<double> &accuracy)
  50 {
  51         ctx::Location location;
  52         if (latitudes.empty() || latitudes.size() != longitudes.size() || latitudes.size() != accuracy.size()) {
  53                 _E("Incorrect input vectors size");
  54                 return location;
  55         }
  56         int idx;
  57         int additionalIdx;
  58         location.latitude = median(latitudes, idx, additionalIdx);
  59         double latitudeAccuracy = accuracy[idx];
  60         if (additionalIdx >= 0) {
  61                 latitudeAccuracy = 0.5 * (latitudeAccuracy + accuracy[additionalIdx]);
  62         }
  63         location.longitude = median(longitudes, idx, additionalIdx);
  64         double longitudeAccuracy = accuracy[idx];
  65         if (additionalIdx >= 0) {
  66                 longitudeAccuracy = 0.5 * (longitudeAccuracy + accuracy[additionalIdx]);
  67         }
  68         location.accuracy = 0.5 * (latitudeAccuracy + longitudeAccuracy);
  69         return location;
  70 }