1 // Copyright 2021 The Tint Authors. 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 #ifndef SRC_UTILS_UNIQUE_VECTOR_H_ 16 #define SRC_UTILS_UNIQUE_VECTOR_H_ 17 18 #include <functional> 19 #include <unordered_set> 20 #include <utility> 21 #include <vector> 22 23 namespace tint { 24 namespace utils { 25 26 /// UniqueVector is an ordered container that only contains unique items. 27 /// Attempting to add a duplicate is a no-op. 28 template <typename T, 29 typename HASH = std::hash<T>, 30 typename EQUAL = std::equal_to<T>> 31 struct UniqueVector { 32 /// The iterator returned by begin() and end() 33 using ConstIterator = typename std::vector<T>::const_iterator; 34 /// The iterator returned by rbegin() and rend() 35 using ConstReverseIterator = typename std::vector<T>::const_reverse_iterator; 36 37 /// Constructor 38 UniqueVector() = default; 39 40 /// Constructor 41 /// @param v the vector to construct this UniqueVector with. Duplicate 42 /// elements will be removed. UniqueVectorUniqueVector43 explicit UniqueVector(std::vector<T>&& v) { 44 for (auto& el : v) { 45 add(el); 46 } 47 } 48 49 /// add appends the item to the end of the vector, if the vector does not 50 /// already contain the given item. 51 /// @param item the item to append to the end of the vector 52 /// @returns true if the item was added, otherwise false. addUniqueVector53 bool add(const T& item) { 54 if (set.count(item) == 0) { 55 vector.emplace_back(item); 56 set.emplace(item); 57 return true; 58 } 59 return false; 60 } 61 62 /// @returns true if the vector contains `item` 63 /// @param item the item containsUniqueVector64 bool contains(const T& item) const { return set.count(item); } 65 66 /// @param i the index of the element to retrieve 67 /// @returns the element at the index `i` 68 T& operator[](size_t i) { return vector[i]; } 69 70 /// @param i the index of the element to retrieve 71 /// @returns the element at the index `i` 72 const T& operator[](size_t i) const { return vector[i]; } 73 74 /// @returns true if the vector is empty emptyUniqueVector75 size_t empty() const { return vector.empty(); } 76 77 /// @returns the number of items in the vector sizeUniqueVector78 size_t size() const { return vector.size(); } 79 80 /// @returns an iterator to the beginning of the vector beginUniqueVector81 ConstIterator begin() const { return vector.begin(); } 82 83 /// @returns an iterator to the end of the vector endUniqueVector84 ConstIterator end() const { return vector.end(); } 85 86 /// @returns an iterator to the beginning of the reversed vector rbeginUniqueVector87 ConstReverseIterator rbegin() const { return vector.rbegin(); } 88 89 /// @returns an iterator to the end of the reversed vector rendUniqueVector90 ConstReverseIterator rend() const { return vector.rend(); } 91 92 /// @returns a const reference to the internal vector 93 operator const std::vector<T> &() const { return vector; } 94 95 /// Removes the last element from the vector 96 /// @returns the popped element pop_backUniqueVector97 T pop_back() { 98 auto el = std::move(vector.back()); 99 set.erase(el); 100 vector.pop_back(); 101 return el; 102 } 103 104 private: 105 std::vector<T> vector; 106 std::unordered_set<T, HASH, EQUAL> set; 107 }; 108 109 } // namespace utils 110 } // namespace tint 111 112 #endif // SRC_UTILS_UNIQUE_VECTOR_H_ 113