TTK
Loading...
Searching...
No Matches
RangeMinimumQuery.h
Go to the documentation of this file.
1
8
9#pragma once
10
11#include <Debug.h>
12
13#include <algorithm>
14#include <cmath>
15#include <sstream>
16#include <string>
17#include <vector>
18
19namespace ttk {
20
21 template <class DataType>
22 class RangeMinimumQuery : virtual public Debug {
23 public:
25 RangeMinimumQuery(std::vector<DataType> &input);
26
27 inline void setVector(std::vector<DataType> &input) {
28 input_ = input.data();
29 input_end_ = input.data() + input.size();
30 }
31
32 int preprocess(const bool silent = false);
33 int query(int i, int j) const;
34
35 protected:
36 // Input vector
37 DataType *input_{};
38 DataType *input_end_{};
39
40 // Sparse Table
41 std::vector<std::vector<int>> table_{};
42 };
43
44} // namespace ttk
45
46/* Function definitions */
47
48// Constructors
49template <class DataType>
51 this->setDebugMsgPrefix("RangeMinimumQuery");
52}
53template <class DataType>
55 std::vector<DataType> &input) {
56 setVector(input);
57}
58
59// Preprocessing
60template <class DataType>
62
63 Timer t;
64
65 // Compute the size of the matrix
66 int sizeOfArray = static_cast<int>(input_end_ - input_);
67 int numberOfBlocs = static_cast<unsigned int>(log2(sizeOfArray + 1)) + 1;
68
69 // Init the matrix
70 table_.resize(sizeOfArray);
71 for(int i = 0; i < sizeOfArray; i++) {
72 table_[i].resize(numberOfBlocs);
73 fill(table_[i].begin(), table_[i].end(), -1);
74 }
75
76 // Initialize for blocs of size 1 (k==0)
77 for(int i = 0; i < sizeOfArray; i++) {
78 table_[i][0] = i;
79 }
80 // Compute other values recursively
81 for(int k = 1; ((1 << k) - 1) < sizeOfArray; k++) {
82 for(int i = 0; (i + (1 << k) - 1) < sizeOfArray; i++) {
83 if(input_[table_[i][k - 1]]
84 <= input_[table_[i + (1 << (k - 1))][k - 1]]) {
85 table_[i][k] = table_[i][k - 1];
86 } else {
87 table_[i][k] = table_[i + (1 << (k - 1))][k - 1];
88 }
89 }
90 }
91 // Debug messages
92 if(!silent) {
93 this->printMsg("Preprocessed queries.", 1.0, t.getElapsedTime(), 1);
94 }
95 return 0;
96}
97
98template <class DataType>
100
101#ifndef TTK_ENABLE_KAMIKAZE
102 // i must be lower or equal to j, else swap values
103 if(i > j) {
104 std::swap(i, j);
105 }
106#endif
107
108 // Compute size of blocs (2^k) to use
109 int k = static_cast<int>(log2(j - i + 1));
110 // Compute the range minimum
111 if(input_[table_[i][k]] <= input_[table_[j - (1 << k) + 1][k]]) {
112 return table_[i][k];
113 } else {
114 return table_[j - (1 << k) + 1][k];
115 }
116}
Minimalist debugging class.
Definition: Debug.h:88
Class to answer range minimum queries in an array in constant time after a linearithmic time preproce...
int preprocess(const bool silent=false)
RangeMinimumQuery(std::vector< DataType > &input)
std::vector< std::vector< int > > table_
void setVector(std::vector< DataType > &input)
int query(int i, int j) const
double getElapsedTime()
Definition: Timer.h:15
The Topology ToolKit.
printMsg(debug::output::GREEN+"                           "+debug::output::ENDCOLOR+debug::output::GREEN+"▒"+debug::output::ENDCOLOR+debug::output::GREEN+"▒▒▒▒▒▒▒▒▒▒▒▒▒░"+debug::output::ENDCOLOR, debug::Priority::PERFORMANCE, debug::LineMode::NEW, stream)