1 // Copyright (c) 2013 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_ORDERED_SET_H_ 6 #define TOOLS_GN_ORDERED_SET_H_ 7 8 #include <stddef.h> 9 10 #include <set> 11 12 // An ordered set of items. Only appending is supported. Iteration is designed 13 // to be by index. 14 template <typename T> 15 class OrderedSet { 16 private: 17 using set_type = std::set<T>; 18 using set_iterator = typename set_type::const_iterator; 19 using vector_type = std::vector<set_iterator>; 20 21 public: 22 static const size_t npos = static_cast<size_t>(-1); 23 OrderedSet()24 OrderedSet() {} ~OrderedSet()25 ~OrderedSet() {} 26 27 const T& operator[](size_t index) const { return *ordering_[index]; } size()28 size_t size() const { return ordering_.size(); } empty()29 bool empty() const { return ordering_.empty(); } 30 has_item(const T & t)31 bool has_item(const T& t) const { return set_.find(t) != set_.end(); } 32 33 // Returns true if the item was inserted. False if it was already in the 34 // set. push_back(const T & t)35 bool push_back(const T& t) { 36 std::pair<set_iterator, bool> result = set_.insert(t); 37 if (result.second) 38 ordering_.push_back(result.first); 39 return true; 40 } 41 42 // Appends a range of items, skipping ones that already exist. 43 template <class InputIterator> append(const InputIterator & insert_begin,const InputIterator & insert_end)44 void append(const InputIterator& insert_begin, 45 const InputIterator& insert_end) { 46 for (InputIterator i = insert_begin; i != insert_end; ++i) { 47 const T& t = *i; 48 push_back(t); 49 } 50 } 51 52 // Appends all items from the given other set. append(const OrderedSet<T> & other)53 void append(const OrderedSet<T>& other) { 54 for (size_t i = 0; i < other.size(); i++) 55 push_back(other[i]); 56 } 57 58 private: 59 set_type set_; 60 vector_type ordering_; 61 }; 62 63 #endif // TOOLS_GN_ORDERED_SET_H_ 64