OR-Tools  8.2
protobuf_util.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_BASE_PROTOBUF_UTIL_H_
15#define OR_TOOLS_BASE_PROTOBUF_UTIL_H_
16
17#include "google/protobuf/repeated_field.h"
19
20namespace google {
21namespace protobuf {
22namespace util {
23// RepeatedPtrField version.
24template <typename T>
25inline void Truncate(RepeatedPtrField<T>* array, int new_size) {
26 const int size = array->size();
27 DCHECK_GE(size, new_size);
28 array->DeleteSubrange(new_size, size - new_size);
29}
30
31// Removes the elements at the indices specified by 'indices' from 'array' in
32// time linear in the size of 'array' (on average, even when 'indices' is a
33// singleton) while preserving the relative order of the remaining elements.
34// The indices must be a container of ints in strictly increasing order, such
35// as vector<int>, set<int> or initializer_list<int>, and in the range [0, N -
36// 1] where N is the number of elements in 'array', and RepeatedType must be
37// RepeatedField or RepeatedPtrField.
38// Returns number of elements erased.
39template <typename RepeatedType, typename IndexContainer = std::vector<int>>
40int RemoveAt(RepeatedType* array, const IndexContainer& indices) {
41 if (indices.size() == 0) {
42 return 0;
43 }
44 const int num_indices = indices.size();
45 const int num_elements = array->size();
46 DCHECK_LE(num_indices, num_elements);
47 if (num_indices == num_elements) {
48 // Assumes that 'indices' consists of [0 ... N-1].
49 array->Clear();
50 return num_indices;
51 }
52 typename IndexContainer::const_iterator remove_iter = indices.begin();
53 int write_index = *(remove_iter++);
54 for (int scan = write_index + 1; scan < num_elements; ++scan) {
55 if (remove_iter != indices.end() && *remove_iter == scan) {
56 ++remove_iter;
57 } else {
58 array->SwapElements(scan, write_index++);
59 }
60 }
61 DCHECK_EQ(write_index, num_elements - num_indices);
62 Truncate(array, write_index);
63 return num_indices;
64}
65} // namespace util
66} // namespace protobuf
67} // namespace google
68
69#endif // OR_TOOLS_BASE_PROTOBUF_UTIL_H_
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void Truncate(RepeatedPtrField< T > *array, int new_size)
Definition: protobuf_util.h:25
int RemoveAt(RepeatedType *array, const IndexContainer &indices)
Definition: protobuf_util.h:40