1 // Copyright 2018 Google Inc. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS-IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 16 // Author: ericv@google.com (Eric Veach) 17 18 #ifndef S2_ENCODED_S2CELL_ID_VECTOR_H_ 19 #define S2_ENCODED_S2CELL_ID_VECTOR_H_ 20 21 #include "s2/third_party/absl/types/span.h" 22 #include "s2/encoded_uint_vector.h" 23 #include "s2/s2cell_id.h" 24 25 namespace s2coding { 26 27 // Encodes a vector of S2CellIds in a format that can later be decoded as an 28 // EncodedS2CellIdVector. The S2CellIds do not need to be valid. 29 // 30 // REQUIRES: "encoder" uses the default constructor, so that its buffer 31 // can be enlarged as necessary by calling Ensure(int). 32 void EncodeS2CellIdVector(absl::Span<const S2CellId> v, Encoder* encoder); 33 34 // This class represents an encoded vector of S2CellIds. Values are decoded 35 // only when they are accessed. This allows for very fast initialization and 36 // no additional memory use beyond the encoded data. The encoded data is not 37 // owned by this class; typically it points into a large contiguous buffer 38 // that contains other encoded data as well. 39 // 40 // This is one of several helper classes that allow complex data structures to 41 // be initialized from an encoded format in constant time and then decoded on 42 // demand. This can be a big performance advantage when only a small part of 43 // the data structure is actually used. 44 // 45 // The S2CellIds do not need to be sorted or at the same level. The 46 // implementation is biased towards minimizing decoding times rather than 47 // space usage. 48 // 49 // NOTE: If your S2CellIds represent S2Points that have been snapped to 50 // S2CellId centers, then EncodedS2PointVector is both faster and smaller. 51 class EncodedS2CellIdVector { 52 public: 53 // Constructs an uninitialized object; requires Init() to be called. EncodedS2CellIdVector()54 EncodedS2CellIdVector() {} 55 56 // Initializes the EncodedS2CellIdVector. 57 // 58 // REQUIRES: The Decoder data buffer must outlive this object. 59 bool Init(Decoder* decoder); 60 61 // Returns the size of the original vector. 62 size_t size() const; 63 64 // Returns the element at the given index. 65 S2CellId operator[](int i) const; 66 67 // Returns the index of the first element x such that (x >= target), or 68 // size() if no such element exists. 69 // 70 // REQUIRES: The vector elements are sorted in non-decreasing order. 71 size_t lower_bound(S2CellId target) const; 72 73 // Decodes and returns the entire original vector. 74 std::vector<S2CellId> Decode() const; 75 76 private: 77 // Values are decoded as (base_ + (deltas_[i] << shift_)). 78 EncodedUintVector<uint64> deltas_; 79 uint64 base_; 80 uint8 shift_; 81 }; 82 83 84 ////////////////// Implementation details follow //////////////////// 85 86 size()87inline size_t EncodedS2CellIdVector::size() const { 88 return deltas_.size(); 89 } 90 91 inline S2CellId EncodedS2CellIdVector::operator[](int i) const { 92 return S2CellId((deltas_[i] << shift_) + base_); 93 } 94 lower_bound(S2CellId target)95inline size_t EncodedS2CellIdVector::lower_bound(S2CellId target) const { 96 // We optimize the search by converting "target" to the corresponding delta 97 // value and then searching directly in the deltas_ vector. 98 // 99 // To invert operator[], we essentially compute ((target - base_) >> shift_) 100 // except that we also need to round up when shifting. The first two cases 101 // ensure that "target" doesn't wrap around past zero when we do this. 102 if (target.id() <= base_) return 0; 103 if (target >= S2CellId::End(S2CellId::kMaxLevel)) return size(); 104 return deltas_.lower_bound( 105 (target.id() - base_ + (1ULL << shift_) - 1) >> shift_); 106 } 107 108 } // namespace s2coding 109 110 #endif // S2_ENCODED_S2CELL_ID_VECTOR_H_ 111