1 // Copyright 2020 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef TOOLS_GN_VECTOR_UTILS_H_ 6 #define TOOLS_GN_VECTOR_UTILS_H_ 7 8 #include <algorithm> 9 #include <utility> 10 #include <vector> 11 12 // A VectorSetSorter is a convenience class used to efficiently sort and 13 // de-duplicate one or more sets of items of type T, then iterate over the 14 // result, or get it as a simple vector. Usage is the following: 15 // 16 // For performance reasons, this implementation only stores pointers to the 17 // input items in order to minimize memory usage. Callers should ensure the 18 // items added to this sorter do not change until the instance is destroyed. 19 // 20 // 1) Create instance, passing an optional initial capacity. 21 // 22 // 2) Add items using one of the Add() methods, as many times as 23 // necessary. Note that this records only pointers to said items 24 // so their content should not change until the instance is destroyed. 25 // 26 // 3) Call IteratorOver() to iterate over all sorted and de-duplicated 27 // items. 28 // 29 // 4) Alternatively, call AsVector() to return a new vector that contains 30 // copies of the original sorted / deduplicated items. 31 // 32 template <typename T> 33 class VectorSetSorter { 34 public: 35 // Constructor. |initial_capacity| might be provided to minimize the number 36 // of allocations performed by this instance, if the maximum number of 37 // input items is known in advance. 38 VectorSetSorter(size_t initial_capacity = 0) { 39 ptrs_.reserve(initial_capacity); 40 } 41 42 // Add one single item to the sorter. Add(const T & item)43 void Add(const T& item) { 44 ptrs_.push_back(&item); 45 sorted_ = false; 46 } 47 48 // Add one range of items to the sorter. Add(typename std::vector<T>::const_iterator begin,typename std::vector<T>::const_iterator end)49 void Add(typename std::vector<T>::const_iterator begin, 50 typename std::vector<T>::const_iterator end) { 51 for (; begin != end; ++begin) 52 ptrs_.push_back(&(*begin)); 53 sorted_ = false; 54 } 55 56 // Add one range of items to the sorter. Add(const T * start,const T * end)57 void Add(const T* start, const T* end) { 58 for (; start != end; ++start) 59 ptrs_.push_back(start); 60 sorted_ = false; 61 } 62 63 // Iterate over all sorted items, removing duplicates from the loop. 64 // |item_callback| is a callable that will be invoked for each item in the 65 // result. 66 template <typename ITEM_CALLBACK> IterateOver(ITEM_CALLBACK item_callback)67 void IterateOver(ITEM_CALLBACK item_callback) { 68 if (!sorted_) { 69 Sort(); 70 } 71 const T* prev_item = nullptr; 72 for (const T* item : ptrs_) { 73 if (!prev_item || *prev_item != *item) { 74 item_callback(*item); 75 prev_item = item; 76 } 77 } 78 } 79 80 // Return the sorted and de-duplicated resulting set as a vector of items. 81 // Note that this copies the input items. AsVector()82 std::vector<T> AsVector() { 83 std::vector<T> result; 84 result.reserve(ptrs_.size()); 85 IterateOver([&result](const T& item) { result.push_back(item); }); 86 return result; 87 } 88 89 private: 90 // Sort all items previously added to this instance. 91 // Must be called after adding all desired items, and before 92 // calling IterateOver() or AsVector(). Sort()93 void Sort() { 94 std::sort(ptrs_.begin(), ptrs_.end(), 95 [](const T* a, const T* b) { return *a < *b; }); 96 sorted_ = true; 97 } 98 99 std::vector<const T*> ptrs_; 100 bool sorted_ = false; 101 }; 102 103 #endif // TOOLS_GN_VECTOR_UTILS_H_ 104