1 /* 2 * Copyright (C) 2024 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 #pragma once 17 18 #include <compare> 19 #include <iterator> 20 #include <utility> 21 22 namespace android { 23 24 namespace detail { 25 // A few useful aliases to not repeat them everywhere 26 template <class It1, class It2> 27 using Value = std::pair<typename std::iterator_traits<It1>::value_type, 28 typename std::iterator_traits<It2>::value_type>; 29 30 template <class It1, class It2> 31 using BaseRefPair = std::pair<typename std::iterator_traits<It1>::reference, 32 typename std::iterator_traits<It2>::reference>; 33 34 template <class It1, class It2> 35 struct RefPair : BaseRefPair<It1, It2> { 36 using Base = BaseRefPair<It1, It2>; 37 using Value = detail::Value<It1, It2>; 38 RefPairRefPair39 RefPair(It1 it1, It2 it2) : Base(*it1, *it2) { 40 } 41 42 RefPair& operator=(const Value& v) { 43 this->first = v.first; 44 this->second = v.second; 45 return *this; 46 } ValueRefPair47 operator Value() const { 48 return Value(this->first, this->second); 49 } 50 bool operator==(const RefPair& other) { 51 return this->first == other.first; 52 } 53 bool operator==(const Value& other) { 54 return this->first == other.first; 55 } 56 std::strong_ordering operator<=>(const RefPair& other) const { 57 return this->first <=> other.first; 58 } 59 std::strong_ordering operator<=>(const Value& other) const { 60 return this->first <=> other.first; 61 } swapRefPair62 friend void swap(RefPair& l, RefPair& r) { 63 using std::swap; 64 swap(l.first, r.first); 65 swap(l.second, r.second); 66 } 67 }; 68 69 template <class It1, class It2> 70 struct RefPairPtr { 71 RefPair<It1, It2> value; 72 73 RefPair<It1, It2>* operator->() const { 74 return &value; 75 } 76 }; 77 } // namespace detail 78 79 // 80 // CombinedIterator - a class to combine two iterators to process them as a single iterator to a 81 // pair of values. Useful for processing a data structure of "struct of arrays", replacing 82 // array of structs for cache locality. 83 // 84 // The value type is a pair of copies of the values of each iterator, and the reference is a 85 // pair of references to the corresponding values. Comparison only compares the first element, 86 // making it most useful for using on data like (vector<Key>, vector<Value>) for binary searching, 87 // sorting both together and so on. 88 // 89 // The class is designed for handling arrays, so it requires random access iterators as an input. 90 // 91 92 template <class It1, class It2> 93 requires std::random_access_iterator<It1> && std::random_access_iterator<It2> 94 struct CombinedIterator { 95 typedef detail::Value<It1, It2> value_type; 96 typedef detail::RefPair<It1, It2> reference; 97 typedef std::ptrdiff_t difference_type; 98 typedef detail::RefPairPtr<It1, It2> pointer; 99 typedef std::random_access_iterator_tag iterator_category; 100 it1CombinedIterator101 CombinedIterator(It1 it1 = {}, It2 it2 = {}) : it1(it1), it2(it2) { 102 } 103 104 bool operator<(const CombinedIterator& other) const { 105 return it1 < other.it1; 106 } 107 bool operator<=(const CombinedIterator& other) const { 108 return it1 <= other.it1; 109 } 110 bool operator>(const CombinedIterator& other) const { 111 return it1 > other.it1; 112 } 113 bool operator>=(const CombinedIterator& other) const { 114 return it1 >= other.it1; 115 } 116 bool operator==(const CombinedIterator& other) const { 117 return it1 == other.it1; 118 } 119 pointer operator->() const { 120 return pointer{{it1, it2}}; 121 } 122 reference operator*() const { 123 return {it1, it2}; 124 } 125 reference operator[](difference_type n) const { 126 return {it1 + n, it2 + n}; 127 } 128 129 CombinedIterator& operator++() { 130 ++it1; 131 ++it2; 132 return *this; 133 } 134 CombinedIterator operator++(int) { 135 const auto res = *this; 136 ++*this; 137 return res; 138 } 139 CombinedIterator& operator--() { 140 --it1; 141 --it2; 142 return *this; 143 } 144 CombinedIterator operator--(int) { 145 const auto res = *this; 146 --*this; 147 return res; 148 } 149 CombinedIterator& operator+=(difference_type n) { 150 it1 += n; 151 it2 += n; 152 return *this; 153 } 154 CombinedIterator operator+(difference_type n) const { 155 CombinedIterator res = *this; 156 return res += n; 157 } 158 159 CombinedIterator& operator-=(difference_type n) { 160 it1 -= n; 161 it2 -= n; 162 return *this; 163 } 164 CombinedIterator operator-(difference_type n) const { 165 CombinedIterator res = *this; 166 return res -= n; 167 } 168 difference_type operator-(const CombinedIterator& other) { 169 return it1 - other.it1; 170 } 171 172 It1 it1; 173 It2 it2; 174 }; 175 176 } // namespace android 177