OR-Tools  8.1
zvector.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_UTIL_ZVECTOR_H_
15 #define OR_TOOLS_UTIL_ZVECTOR_H_
16 
17 #if (defined(__APPLE__) || defined(__FreeBSD__)) && defined(__GNUC__)
18 #include <machine/endian.h>
19 #elif !defined(_MSC_VER)
20 #include <endian.h>
21 #endif
22 #include <climits>
23 #include <cstdio>
24 #include <limits>
25 #include <memory>
26 #include <string>
27 
29 #include "ortools/base/logging.h"
30 #include "ortools/base/macros.h"
31 
32 // An array class for storing arrays of integers.
33 //
34 // The range of indices is specified at the construction of the object.
35 // The minimum and maximum indices are inclusive.
36 // Think of the Pascal syntax array[min_index..max_index] of ...
37 //
38 // For example, ZVector<int32>(-100000,100000) will store 200001
39 // signed integers of 32 bits each, and the possible range of indices
40 // will be -100000..100000.
41 
42 namespace operations_research {
43 
44 template <class T>
45 class ZVector {
46  public:
48  : base_(nullptr), min_index_(0), max_index_(-1), size_(0), storage_() {}
49 
51  : base_(nullptr), min_index_(0), max_index_(-1), size_(0), storage_() {
52  if (!Reserve(min_index, max_index)) {
53  LOG(DFATAL) << "Could not reserve memory for indices ranging from "
54  << min_index << " to " << max_index;
55  }
56  }
57 
58  int64 min_index() const { return min_index_; }
59 
60  int64 max_index() const { return max_index_; }
61 
62  // Returns the value stored at index.
63  T Value(int64 index) const {
64  DCHECK_LE(min_index_, index);
65  DCHECK_GE(max_index_, index);
66  DCHECK(base_ != nullptr);
67  return base_[index];
68  }
69 
70 #if !defined(SWIG)
71  // Shortcut for returning the value stored at index.
73  DCHECK_LE(min_index_, index);
74  DCHECK_GE(max_index_, index);
75  DCHECK(base_ != nullptr);
76  return base_[index];
77  }
78 
79  const T operator[](int64 index) const {
80  DCHECK_LE(min_index_, index);
81  DCHECK_GE(max_index_, index);
82  DCHECK(base_ != nullptr);
83  return base_[index];
84  }
85 #endif
86 
87  // Sets to value the content of the array at index.
88  void Set(int64 index, T value) {
89  DCHECK_LE(min_index_, index);
90  DCHECK_GE(max_index_, index);
91  DCHECK(base_ != nullptr);
92  base_[index] = value;
93  }
94 
95  // Reserves memory for new minimum and new maximum indices.
96  // Returns true if the memory could be reserved.
97  // Never shrinks the memory allocated.
98  bool Reserve(int64 new_min_index, int64 new_max_index) {
99  if (new_min_index > new_max_index) {
100  return false;
101  }
102  const uint64 new_size = new_max_index - new_min_index + 1;
103  if (base_ != nullptr) {
104  if (new_min_index >= min_index_ && new_max_index <= max_index_) {
105  min_index_ = new_min_index;
106  max_index_ = new_max_index;
107  size_ = new_size;
108  return true;
109  } else if (new_min_index > min_index_ || new_max_index < max_index_) {
110  return false;
111  }
112  }
113  T* new_storage = new T[new_size];
114  if (new_storage == nullptr) {
115  return false;
116  }
117 
118  T* const new_base = new_storage - new_min_index;
119  if (base_ != nullptr) {
120  T* const destination = new_base + min_index_;
121  memcpy(destination, storage_.get(), size_ * sizeof(*base_));
122  }
123 
124  base_ = new_base;
125  size_ = new_size;
126  min_index_ = new_min_index;
127  max_index_ = new_max_index;
128  storage_.reset(new_storage);
129  return true;
130  }
131 
132  // Sets all the elements in the array to value.
133  void SetAll(T value) {
134  DLOG_IF(WARNING, base_ == nullptr || size_ <= 0)
135  << "Trying to set values to uninitialized vector.";
136  for (int64 i = 0; i < size_; ++i) {
137  base_[min_index_ + i] = value;
138  }
139  }
140 
141  private:
142  // Pointer to the element indexed by zero in the array.
143  T* base_;
144 
145  // Minimum index for the array.
146  int64 min_index_;
147 
148  // Maximum index for the array.
149  int64 max_index_;
150 
151  // The number of elements in the array.
152  int64 size_;
153 
154  // Storage memory for the array.
155  std::unique_ptr<T[]> storage_;
156 };
157 
158 // Shorthands for all the types of ZVector's.
167 
168 } // namespace operations_research
169 
170 #endif // OR_TOOLS_UTIL_ZVECTOR_H_
operations_research::UInt32ZVector
ZVector< uint32 > UInt32ZVector
Definition: zvector.h:165
operations_research::UInt8ZVector
ZVector< uint8 > UInt8ZVector
Definition: zvector.h:163
integral_types.h
operations_research::ZVector::operator[]
const T operator[](int64 index) const
Definition: zvector.h:79
LOG
#define LOG(severity)
Definition: base/logging.h:420
logging.h
value
int64 value
Definition: demon_profiler.cc:43
macros.h
operations_research::ZVector::Set
void Set(int64 index, T value)
Definition: zvector.h:88
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::ZVector::operator[]
T & operator[](int64 index)
Definition: zvector.h:72
operations_research::ZVector::SetAll
void SetAll(T value)
Definition: zvector.h:133
WARNING
const int WARNING
Definition: log_severity.h:31
operations_research::ZVector::Value
T Value(int64 index) const
Definition: zvector.h:63
operations_research::ZVector::max_index
int64 max_index() const
Definition: zvector.h:60
operations_research::Int32ZVector
ZVector< int32 > Int32ZVector
Definition: zvector.h:161
int64
int64_t int64
Definition: integral_types.h:34
index
int index
Definition: pack.cc:508
operations_research::ZVector::ZVector
ZVector(int64 min_index, int64 max_index)
Definition: zvector.h:50
operations_research::ZVector::min_index
int64 min_index() const
Definition: zvector.h:58
operations_research::ZVector::ZVector
ZVector()
Definition: zvector.h:47
operations_research::Int8ZVector
ZVector< int8 > Int8ZVector
Definition: zvector.h:159
uint64
uint64_t uint64
Definition: integral_types.h:39
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::UInt16ZVector
ZVector< uint16 > UInt16ZVector
Definition: zvector.h:164
DCHECK_GE
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
operations_research::Int16ZVector
ZVector< int16 > Int16ZVector
Definition: zvector.h:160
operations_research::ZVector
Definition: zvector.h:45
operations_research::UInt64ZVector
ZVector< uint64 > UInt64ZVector
Definition: zvector.h:166
operations_research::ZVector::Reserve
bool Reserve(int64 new_min_index, int64 new_max_index)
Definition: zvector.h:98
DLOG_IF
#define DLOG_IF(severity, condition)
Definition: base/logging.h:877
DCHECK_LE
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
operations_research::Int64ZVector
ZVector< int64 > Int64ZVector
Definition: zvector.h:162