fork download 
  1. #include <iostream>
  2. #include <array>
  3. #include <utility>
  4. #include <boost/optional.hpp>
  5.  
  6.  
  7. void fill_range(
  8. 	std::array<boost::optional<std::pair<std::size_t, std::size_t>>, 10u>& ranges,
  9. 	const std::vector<float>& v,
  10. 	std::size_t b,
  11. 	std::size_t e)
  12. {
  13. 	if (b == e) {
  14. 		return;
  15. 	}
  16. 	int decile_b = v[b] / 0.1f;
  17. 	int decile_e = v[e - 1] / 0.1f;
  18.  
  19. 	if (decile_b == decile_e) {
  20. 		auto& range = ranges[decile_b];
  21.  
  22. 		if (range) {
  23. 			range->first = std::min(range->first, b);
  24. 			range->second = std::max(range->second, e);
  25. 		} else {
  26. 			range = std::make_pair(b, e);
  27. 		}
  28. 	} else {
  29. 		std::size_t mid = (b + e + 1) / 2;
  30. 		fill_range(ranges, v, b, mid);
  31. 		fill_range(ranges, v, mid, e);
  32. 	}
  33. }
  34.  
  35. std::array<boost::optional<std::pair<std::size_t, std::size_t>>, 10u>
  36. decile_ranges(const std::vector<float>& v)
  37. {
  38. 	// assume sorted `v` with value x: 0 <= x < 1
  39. 	std::array<boost::optional<std::pair<std::size_t, std::size_t>>, 10u> res;
  40. 	fill_range(res, v, 0, v.size());
  41. 	return res;
  42. }
  43.  
  44. void print(
  45. 	const std::array<boost::optional<std::pair<std::size_t, std::size_t>>, 10u>& a)
  46. {
  47. 	for (std::size_t i = 0; i != a.size(); ++i) {
  48. 		const auto& o = a[i];
  49.  
  50. 		std::cout << "[" << i * 0.1f << ", " << (i + 1) * 0.1f << "[ = ";
  51. 		if (o) {
  52. 			std::cout << o->first << "-" << o->second << std::endl;
  53. 		} else {
  54. 			std::cout << "none\n";
  55. 		}
  56. 	}
  57. }
  58.  
  59.  
  60. int main() {
  61. 	const std::vector<float> v = {0.f, 0.05f, 0.1f, 0.35f, 0.42f, 0.99f};
  62.  
  63.     print(decile_ranges(v));
  64. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin 
Standard input is empty
stdout 
[0, 0.1[ = 0-2
[0.1, 0.2[ = 2-3
[0.2, 0.3[ = none
[0.3, 0.4[ = 3-4
[0.4, 0.5[ = 4-5
[0.5, 0.6[ = none
[0.6, 0.7[ = none
[0.7, 0.8[ = none
[0.8, 0.9[ = none
[0.9, 1[ = 5-6
https://ideone.com/cK0HwR
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!