Google OR-Tools: ortools/util/range_minimum

Google OR-Tools: ortools/util/range_minimum_query.h Source File

73#ifndef ORTOOLS_UTIL_RANGE_MINIMUM_QUERY_H_

74#define ORTOOLS_UTIL_RANGE_MINIMUM_QUERY_H_

76#include <algorithm>

77#include <functional>

78#include <numeric>

79#include <utility>

80#include <vector>

82#include "absl/log/check.h"

86template <typename T, typename Compare = std::less<T>>

88 public:

92 cache_.resize(2);

93 };

100

101

102

103

104

105

106

108

109 void PushBack(T element) { cache_[0].push_back(element); }

110

111

112

113

114

115

116

118

119

120 int TableSize() const { return cache_[1].size(); }

121

122

123

125 for (auto& row : cache_) row.clear();

126 }

127

128

129 const std::vector<T>& array() const;

130

131 private:

132

133 std::vector<std::vector<T>> cache_;

134 Compare cmp_;

135};

136

137

138

139template <typename T, typename Compare = std::less<T>>

141 public:

144

145

148

149

150

152

153

154 const std::vector<T>& array() const;

155

156 private:

157

158 static std::vector<int> CreateIndexVector(int n);

159 struct IndexComparator {

160 bool operator()(int lhs_idx, int rhs_idx) const;

161 const std::vector<T> array;

162 Compare cmp;

163 } cmp_;

165};

166

167

168template <typename T, typename Compare>

171

172template <typename T, typename Compare>

174 Compare cmp)

175 : cache_(2), cmp_(std::move(cmp)) {

176

177

178 cache_[0] = std::move(array);

180}

181

182template <typename T, typename Compare>

184 DCHECK_LE(0, begin);

186 DCHECK_LE(end, cache_[1].size());

187 DCHECK_EQ(cache_[0].size(), cache_[1].size());

189 DCHECK_LT(layer, cache_.size());

190 const int window = 1 << layer;

191 const T* row = cache_[layer].data();

192 DCHECK_LE(end - window, cache_[layer].size());

193 return std::min(row[begin], row[end - window], cmp_);

194}

195

196

197

198

199

200template <typename T, typename Compare>

202 const int new_size = cache_[0].size();

203 const int old_size = cache_[1].size();

204 if (old_size >= new_size) return;

205

206

208 if (cache_.size() < num_rows) cache_.resize(num_rows);

209

210 cache_[1].resize(new_size);

211

212 for (int row = 1; row < num_rows; ++row) {

213 const int half_window = 1 << (row - 1);

214 const int last_col = new_size - 2 * half_window;

215 if (cache_[row].size() <= last_col) cache_[row].resize(last_col + 1);

216 for (int col = old_size; col <= last_col; ++col) {

217 cache_[row][col] = std::min(cache_[row - 1][col],

218 cache_[row - 1][col + half_window], cmp_);

219 }

220 }

221}

222

223template <typename T, typename Compare>

225 return cache_[0];

226}

227

228

229template <typename T, typename Compare>

231 std::vector<T> array)

233

234template <typename T, typename Compare>

236 Compare cmp)

237 : cmp_({std::move(array), std::move(cmp)}),

238 rmq_(CreateIndexVector(cmp_.array.size()), cmp_) {}

239

240template <typename T, typename Compare>

244 return rmq_.RangeMinimum(begin, end);

245}

246

247template <typename T, typename Compare>

248inline bool RangeMinimumIndexQuery<T, Compare>::IndexComparator::operator()(

249 int lhs_idx, int rhs_idx) const {

250 return cmp(array[lhs_idx], array[rhs_idx]);

251}

252

253template <typename T, typename Compare>

254std::vector<int> RangeMinimumIndexQuery<T, Compare>::CreateIndexVector(int n) {

255 std::vector<int> result(n, 0);

256 std::iota(result.begin(), result.end(), 0);

257 return result;

258}

259

260template <typename T, typename Compare>

262 return cmp_.array;

263}

264}

265#endif

RangeMinimumIndexQuery(const RangeMinimumIndexQuery &)=delete

RangeMinimumIndexQuery(std::vector< T > array)

Definition range_minimum_query.h:230

int GetMinimumIndexFromRange(int begin, int end) const

Definition range_minimum_query.h:241

const std::vector< T > & array() const

Definition range_minimum_query.h:261

RangeMinimumIndexQuery & operator=(const RangeMinimumIndexQuery &)=delete

void Clear()

Definition range_minimum_query.h:124

const std::vector< T > & array() const

Definition range_minimum_query.h:224

void PushBack(T element)

Definition range_minimum_query.h:109

void MakeTableFromNewElements()

Definition range_minimum_query.h:201

T RangeMinimum(int begin, int end) const

Definition range_minimum_query.h:183

RangeMinimumQuery()

Definition range_minimum_query.h:89

RangeMinimumQuery & operator=(const RangeMinimumQuery &)=delete

RangeMinimumQuery(const RangeMinimumQuery &)=delete

int TableSize() const

Definition range_minimum_query.h:120

ClosedInterval::Iterator end(ClosedInterval interval)

int MostSignificantBitPosition32(uint32_t n)

ClosedInterval::Iterator begin(ClosedInterval interval)