OR-Tools  8.2
bitmap.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_BITMAP_H_
15#define OR_TOOLS_BASE_BITMAP_H_
16
17#include <string.h>
18
20
21namespace operations_research {
22namespace internal {
23inline uint64 OneBit64(int pos) { return uint64_t{1} << pos; }
24inline uint64 BitPos64(uint64 pos) { return (pos & 63); }
25inline uint64 BitOffset64(uint64 pos) { return (pos >> 6); }
26inline uint64 BitLength64(uint64 size) { return ((size + 63) >> 6); }
27inline bool IsBitSet64(const uint64* const bitset, uint64 pos) {
28 return (bitset[BitOffset64(pos)] & OneBit64(BitPos64(pos)));
29}
30inline void SetBit64(uint64* const bitset, uint64 pos) {
31 bitset[BitOffset64(pos)] |= OneBit64(BitPos64(pos));
32}
33inline void ClearBit64(uint64* const bitset, uint64 pos) {
34 bitset[BitOffset64(pos)] &= ~OneBit64(BitPos64(pos));
35}
36} // namespace internal
37
38class Bitmap {
39 public:
40 // Constructor : This allocates on a uint32 boundary.
41 // fill: true = initialize with 1's, false = initialize with 0's.
42 explicit Bitmap(uint32 size, bool fill = false)
43 : max_size_(size),
44 array_size_(internal::BitLength64(size)),
45 map_(new uint64[array_size_]) {
46 // initialize all of the bits
47 SetAll(fill);
48 }
49
50 // Destructor: clean up.
51 ~Bitmap() { delete[] map_; }
52
53 // Resizes the bitmap.
54 // If size < bits(), the extra bits will be discarded.
55 // If size > bits(), the extra bits will be filled with the fill value.
56 void Resize(uint32 size, bool fill = false);
57
58 bool Get(uint32 index) const {
59 assert(max_size_ == 0 || index < max_size_);
60 return internal::IsBitSet64(map_, index);
61 }
62 void Set(uint32 index, bool value) {
63 assert(max_size_ == 0 || index < max_size_);
64 if (value) {
66 } else {
68 }
69 }
70
71 // Sets all the bits to true or false
72 void SetAll(bool value) {
73 memset(map_, (value ? 0xFF : 0x00), array_size_ * sizeof(*map_));
74 }
75
76 // Clears all bits in the bitmap
77 void Clear() { SetAll(false); }
78
79 private:
80 uint32 max_size_; // the upper bound of the bitmap
81 uint32 array_size_;
82 uint64* map_; // the bitmap
83};
84
85} // namespace operations_research
86
87#endif // OR_TOOLS_BASE_BITMAP_H_
void Resize(uint32 size, bool fill=false)
Definition: bitmap.cc:22
void SetAll(bool value)
Definition: bitmap.h:72
bool Get(uint32 index) const
Definition: bitmap.h:58
Bitmap(uint32 size, bool fill=false)
Definition: bitmap.h:42
void Set(uint32 index, bool value)
Definition: bitmap.h:62
int64 value
unsigned int uint32
uint64_t uint64
uint64 BitPos64(uint64 pos)
Definition: bitmap.h:24
uint64 BitLength64(uint64 size)
Definition: bitmap.h:26
void SetBit64(uint64 *const bitset, uint64 pos)
Definition: bitmap.h:30
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
Definition: bitmap.h:27
void ClearBit64(uint64 *const bitset, uint64 pos)
Definition: bitmap.h:33
uint64 OneBit64(int pos)
Definition: bitmap.h:23
uint64 BitOffset64(uint64 pos)
Definition: bitmap.h:25
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 BitLength64(uint64 size)
Definition: bitset.h:338
int index
Definition: pack.cc:508