Google OR-Tools: ortools/util/tuple

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

33#ifndef ORTOOLS_UTIL_TUPLE_SET_H_

34#define ORTOOLS_UTIL_TUPLE_SET_H_

36#include <algorithm>

37#include <cstdint>

38#include <vector>

40#include "absl/container/flat_hash_map.h"

41#include "absl/container/flat_hash_set.h"

48 public:

62 int Insert(const std::vector<int>& tuple);

63 int Insert(const std::vector<int64_t>& tuple);

65 int Insert2(int64_t v0, int64_t v1);

66 int Insert3(int64_t v0, int64_t v1, int64_t v2);

67 int Insert4(int64_t v0, int64_t v1, int64_t v2, int64_t v3);

69 void InsertAll(const std::vector<std::vector<int64_t> >& tuples);

70 void InsertAll(const std::vector<std::vector<int> >& tuples);

73 bool Contains(const std::vector<int>& tuple) const;

74 bool Contains(const std::vector<int64_t>& tuple) const;

81 int64_t Value(int tuple_index, int pos_in_tuple) const;

83 int Arity() const;

85 const int64_t* RawData() const;

94 private:

97 class Data {

98 public:

99 explicit Data(int arity);

100 Data(const Data& data);

101 ~Data();

102 void AddSharedOwner();

103 bool RemovedSharedOwner();

104 Data* CopyIfShared();

105 template <class T>

106 int Insert(const std::vector<T>& tuple);

107 template <class T>

108 bool Contains(const std::vector<T>& candidate) const;

109 template <class T>

110 int64_t Fingerprint(const std::vector<T>& tuple) const;

112 int64_t Value(int index, int pos) const;

113 int Arity() const;

114 const int64_t* RawData() const;

116

117 private:

118 const int arity_;

119 int num_owners_;

120

121 std::vector<int64_t> flat_tuples_;

122

123

124

125 absl::flat_hash_map<int64_t, std::vector<int> > tuple_fprint_to_index_;

126 };

127

128

129 struct IndexData {

130 int index;

131 IntTupleSet::Data* data;

132 IndexData(int i, IntTupleSet::Data* const d) : index(i), data(d) {}

133 static bool Compare(const IndexData& a, const IndexData& b);

134 };

135

136 struct IndexValue {

137 int index;

138 int64_t value;

139 IndexValue(int i, int64_t v) : index(i), value(v) {}

140 static bool Compare(const IndexValue& a, const IndexValue& b);

141 };

142

143 mutable Data* data_;

144};

145

146

147inline IntTupleSet::Data::Data(int arity) : arity_(arity), num_owners_(0) {}

148

149inline IntTupleSet::Data::Data(const Data& data)

150 : arity_(data.arity_),

151 num_owners_(0),

152 flat_tuples_(data.flat_tuples_),

153 tuple_fprint_to_index_(data.tuple_fprint_to_index_) {}

154

155inline IntTupleSet::Data::~Data() {}

156

157inline void IntTupleSet::Data::AddSharedOwner() { num_owners_++; }

158

159inline bool IntTupleSet::Data::RemovedSharedOwner() {

160 return (--num_owners_ == 0);

161}

162

163inline IntTupleSet::Data* IntTupleSet::Data::CopyIfShared() {

164 if (num_owners_ > 1) {

165 Data* const new_data = new Data(*this);

166 RemovedSharedOwner();

167 new_data->AddSharedOwner();

168 return new_data;

169 }

170 return this;

171}

172

173template <class T>

174int IntTupleSet::Data::Insert(const std::vector<T>& tuple) {

175 DCHECK(arity_ == 0 || flat_tuples_.size() % arity_ == 0);

176 CHECK_EQ(arity_, tuple.size());

177 DCHECK_EQ(1, num_owners_);

180 const int offset = flat_tuples_.size();

181 flat_tuples_.resize(offset + arity_);

182

183 for (int i = 0; i < arity_; ++i) {

184 flat_tuples_[offset + i] = tuple[i];

185 }

186 const int64_t fingerprint = Fingerprint(tuple);

187 tuple_fprint_to_index_[fingerprint].push_back(index);

188 return index;

189 } else {

190 return -1;

191 }

192}

193

194template <class T>

195bool IntTupleSet::Data::Contains(const std::vector<T>& candidate) const {

196 if (candidate.size() != arity_) {

197 return false;

198 }

199 const int64_t fingerprint = Fingerprint(candidate);

200 if (tuple_fprint_to_index_.contains(fingerprint)) {

201 const std::vector<int>& indices = tuple_fprint_to_index_.at(fingerprint);

202 for (int i = 0; i < indices.size(); ++i) {

203 const int tuple_index = indices[i];

204 for (int j = 0; j < arity_; ++j) {

205 if (candidate[j] != flat_tuples_[tuple_index * arity_ + j]) {

206 return false;

207 }

208 }

209 return true;

210 }

211 }

212 return false;

213}

214

215template <class T>

216int64_t IntTupleSet::Data::Fingerprint(const std::vector<T>& tuple) const {

217 switch (arity_) {

218 case 0:

219 return 0;

220 case 1:

221 return tuple[0];

222 case 2: {

223 uint64_t x = tuple[0];

224 uint64_t y = uint64_t{0xe08c1d668b756f82};

225 uint64_t z = tuple[1];

226 mix(x, y, z);

227 return z;

228 }

229 default: {

230 uint64_t x = tuple[0];

231 uint64_t y = uint64_t{0xe08c1d668b756f82};

232 for (int i = 1; i < tuple.size(); ++i) {

233 uint64_t z = tuple[i];

234 mix(x, y, z);

235 x = z;

236 }

237 return x;

238 }

239 }

240}

241

242inline int IntTupleSet::Data::NumTuples() const {

243 return tuple_fprint_to_index_.size();

244}

245

246inline int64_t IntTupleSet::Data::Value(int index, int pos) const {

247 DCHECK_GE(index, 0);

248 DCHECK_LT(index, flat_tuples_.size() / arity_);

249 DCHECK_GE(pos, 0);

250 DCHECK_LT(pos, arity_);

251 return flat_tuples_[index * arity_ + pos];

252}

253

254inline int IntTupleSet::Data::Arity() const { return arity_; }

255

256inline const int64_t* IntTupleSet::Data::RawData() const {

257 return flat_tuples_.data();

258}

259

260inline void IntTupleSet::Data::Clear() {

261 flat_tuples_.clear();

262 tuple_fprint_to_index_.clear();

263}

264

266 CHECK_GE(arity, 0);

267 data_->AddSharedOwner();

268}

269

271 data_->AddSharedOwner();

272}

273

275 CHECK(data_ != nullptr);

276 if (data_->RemovedSharedOwner()) {

277 delete data_;

278 }

279}

280

282 data_ = data_->CopyIfShared();

283 data_->Clear();

284}

285

287 data_ = data_->CopyIfShared();

288 return data_->Insert(tuple);

289}

290

292 data_ = data_->CopyIfShared();

293 return data_->Insert(tuple);

294}

295

297 std::vector<int64_t> tuple(2);

298 tuple[0] = v0;

299 tuple[1] = v1;

300 return Insert(tuple);

301}

302

304 std::vector<int64_t> tuple(3);

305 tuple[0] = v0;

306 tuple[1] = v1;

307 tuple[2] = v2;

308 return Insert(tuple);

309}

310

312 int64_t v3) {

313 std::vector<int64_t> tuple(4);

314 tuple[0] = v0;

315 tuple[1] = v1;

316 tuple[2] = v2;

317 tuple[3] = v3;

318 return Insert(tuple);

319}

320

322 return data_->Contains(tuple);

323}

324

326 return data_->Contains(tuple);

327}

328

330 const std::vector<std::vector<int> >& tuples) {

331 data_ = data_->CopyIfShared();

332 for (int i = 0; i < tuples.size(); ++i) {

334 }

335}

336

338 const std::vector<std::vector<int64_t> >& tuples) {

339 data_ = data_->CopyIfShared();

340 for (int i = 0; i < tuples.size(); ++i) {

342 }

343}

344

346

348 return data_->Value(index, pos);

349}

350

352

354

356 if (col < 0 || col >= data_->Arity()) {

357 return 0;

358 }

359 absl::flat_hash_set<int64_t> values;

360 for (int i = 0; i < data_->NumTuples(); ++i) {

361 values.insert(data_->Value(i, col));

362 }

363 return values.size();

364}

365

366inline bool IntTupleSet::IndexValue::Compare(const IndexValue& a,

367 const IndexValue& b) {

368 return a.value < b.value || (a.value == b.value && a.index < b.index);

369}

370

372 std::vector<IndexValue> keys;

373 keys.reserve(data_->NumTuples());

374 for (int index = 0; index < data_->NumTuples(); ++index) {

375 keys.push_back(IndexValue(index, data_->Value(index, col)));

376 }

377 std::sort(keys.begin(), keys.end(), IntTupleSet::IndexValue::Compare);

378 const int arity = data_->Arity();

380 for (int i = 0; i < keys.size(); ++i) {

381 const int64_t* tuple_ptr = data_->RawData() + keys[i].index * arity;

382 sorted.Insert(std::vector<int64_t>(tuple_ptr, tuple_ptr + arity));

383 }

384 return sorted;

385}

386

387inline bool IntTupleSet::IndexData::Compare(const IndexData& a,

388 const IndexData& b) {

389 const IntTupleSet::Data* const data = a.data;

390 const int arity = data->Arity();

391 for (int i = 0; i < arity; ++i) {

392 const int64_t value1 = data->Value(a.index, i);

393 const int64_t value2 = data->Value(b.index, i);

394 if (value1 < value2) {

395 return true;

396 }

397 if (value1 > value2) {

398 return false;

399 }

400 }

401 return false;

402}

403

405 std::vector<IndexData> keys;

406 keys.reserve(data_->NumTuples());

407 for (int index = 0; index < data_->NumTuples(); ++index) {

408 keys.push_back(IndexData(index, data_));

409 }

410 std::sort(keys.begin(), keys.end(), IntTupleSet::IndexData::Compare);

411 const int arity = data_->Arity();

413 for (int i = 0; i < keys.size(); ++i) {

414 std::vector<int64_t> tuple(arity);

415 const int64_t* tuple_ptr = data_->RawData() + keys[i].index * arity;

416 sorted.Insert(std::vector<int64_t>(tuple_ptr, tuple_ptr + arity));

417 }

418 return sorted;

419}

420}

421

422#endif

int Insert3(int64_t v0, int64_t v1, int64_t v2)

Definition tuple_set.h:303

int Insert4(int64_t v0, int64_t v1, int64_t v2, int64_t v3)

Definition tuple_set.h:311

IntTupleSet(int arity)

Definition tuple_set.h:265

int64_t Value(int tuple_index, int pos_in_tuple) const

Definition tuple_set.h:347

int NumTuples() const

Definition tuple_set.h:345

void Clear()

Definition tuple_set.h:281

bool Contains(const std::vector< int > &tuple) const

Definition tuple_set.h:321

int Insert(const std::vector< int > &tuple)

Definition tuple_set.h:286

int Insert2(int64_t v0, int64_t v1)

Definition tuple_set.h:296

int NumDifferentValuesInColumn(int col) const

Definition tuple_set.h:355

IntTupleSet SortedLexicographically() const

Definition tuple_set.h:404

int Arity() const

Definition tuple_set.h:351

void InsertAll(const std::vector< std::vector< int64_t > > &tuples)

Definition tuple_set.h:337

~IntTupleSet()

Definition tuple_set.h:274

IntTupleSet SortedByColumn(int col) const

Definition tuple_set.h:371

const int64_t * RawData() const

Definition tuple_set.h:353

static void mix(uint64_t &a, uint64_t &b, uint64_t &c)