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