forked from google/or-tools
-
Notifications
You must be signed in to change notification settings - Fork 0
/
vector_map.h
117 lines (99 loc) · 3.55 KB
/
vector_map.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// Copyright 2010-2021 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Vector with map from element to index in the vector.
#ifndef OR_TOOLS_UTIL_VECTOR_MAP_H_
#define OR_TOOLS_UTIL_VECTOR_MAP_H_
#include <vector>
#include "absl/container/flat_hash_map.h"
#include "ortools/base/map_util.h"
namespace operations_research {
// This class stores a vector of distinct elements, as well as a map
// from elements to index to find the index in the vector.
// This is useful to store mapping between objects and indices.
template <class T>
class VectorMap {
public:
// Adds an element if not already present, and returns its index in
// the vector-map.
int Add(const T& element) {
int current_index = Index(element);
if (current_index != -1) {
return current_index;
}
const int index = list_.size();
CHECK_EQ(index, map_.size());
list_.push_back(element);
map_[element] = index;
return index;
}
// TODO(user): Use ArraySlice.
// Adds all elements of the vector.
void Add(const std::vector<T>& elements) {
for (int i = 0; i < elements.size(); ++i) {
Add(elements[i]);
}
}
// Will return the index of the element if present, or die otherwise.
int IndexOrDie(const T& element) const {
return gtl::FindOrDie(map_, element);
}
// Returns -1 if the element is not in the vector, or its unique
// index if it is.
int Index(const T& element) const {
return gtl::FindWithDefault(map_, element, -1);
}
// TODO(user): explore a int-type version.
// Returns whether the element has already been added to the vector-map.
bool Contains(const T& element) const {
return gtl::ContainsKey(map_, element);
}
// Returns the element at position index.
const T& Element(int index) const {
CHECK_GE(index, 0);
CHECK_LT(index, list_.size());
return list_[index];
}
const T& operator[](int index) const { return Element(index); }
// Returns the number of distinct elements added to the vector-map.
int size() const { return list_.size(); }
// Clears all the elements added to the vector-map.
void clear() {
list_.clear();
map_.clear();
}
// Returns a read-only access to the vector of elements.
const std::vector<T>& list() const { return list_; }
// Standard STL container boilerplate.
typedef T value_type;
typedef const T* pointer;
typedef const T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
static const size_type npos;
typedef const T* const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
const_iterator begin() const { return list_.data(); }
const_iterator end() const { return list_.data() + list_.size(); }
const_reverse_iterator rbegin() const {
return const_reverse_iterator(list_.data() + list_.size());
}
const_reverse_iterator rend() const {
return const_reverse_iterator(list_.data());
}
private:
std::vector<T> list_;
absl::flat_hash_map<T, int> map_;
};
} // namespace operations_research
#endif // OR_TOOLS_UTIL_VECTOR_MAP_H_