// Copyright (c) 2013 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef TOOLS_GN_ORDERED_SET_H_ #define TOOLS_GN_ORDERED_SET_H_ #include <set> // An ordered set of items. Only appending is supported. Iteration is designed // to be by index. template<typename T> class OrderedSet { private: typedef std::set<T> set_type; typedef typename set_type::const_iterator set_iterator; typedef std::vector<set_iterator> vector_type; public: static const size_t npos = static_cast<size_t>(-1); OrderedSet() {} ~OrderedSet() {} const T& operator[](size_t index) const { return *ordering_[index]; } size_t size() const { return ordering_.size(); } bool empty() const { return ordering_.empty(); } bool has_item(const T& t) const { return set_.find(t) != set_.end(); } // Returns true if the item was inserted. False if it was already in the // set. bool push_back(const T& t) { std::pair<set_iterator, bool> result = set_.insert(t); if (result.second) ordering_.push_back(result.first); return true; } // Appends a range of items, skipping ones that already exist. template<class InputIterator> void append(const InputIterator& insert_begin, const InputIterator& insert_end) { for (InputIterator i = insert_begin; i != insert_end; ++i) { const T& t = *i; push_back(t); } } // Appends all items from the given other set. void append(const OrderedSet<T>& other) { for (size_t i = 0; i < other.size(); i++) push_back(other[i]); } private: set_type set_; vector_type ordering_; }; #endif // TOOLS_GN_ORDERED_SET_H_