158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// Copyright (c) 2013 The Chromium Authors. All rights reserved. 258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// found in the LICENSE file. 458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#ifndef TOOLS_GN_ORDERED_SET_H_ 658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#define TOOLS_GN_ORDERED_SET_H_ 758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#include <set> 958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 1058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// An ordered set of items. Only appending is supported. Iteration is designed 1158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// to be by index. 1258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)template<typename T> 1358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)class OrderedSet { 1458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) private: 1558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef std::set<T> set_type; 1658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef typename set_type::const_iterator set_iterator; 1758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef std::vector<set_iterator> vector_type; 1858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 1958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) public: 2058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) static const size_t npos = static_cast<size_t>(-1); 2158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 2258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) OrderedSet() {} 2358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) ~OrderedSet() {} 2458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 2558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) const T& operator[](size_t index) const { 2658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return *ordering_[index]; 2758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 2858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) size_t size() const { 2958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return ordering_.size(); 3058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 3158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) bool empty() const { 3258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return ordering_.empty(); 3358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 3458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 3558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) bool has_item(const T& t) const { 3658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return set_.find(t) != set_.end(); 3758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 3858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 3958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // Returns true if the item was inserted. False if it was already in the 4058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // set. 4158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) bool push_back(const T& t) { 4258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) std::pair<set_iterator, bool> result = set_.insert(t); 4358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) if (result.second) 4458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) ordering_.push_back(result.first); 4558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return true; 4658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 4758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 4858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // Appends a range of items, skipping ones that already exist. 4958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) template<class InputIterator> 5058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) void append(const InputIterator& insert_begin, 5158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) const InputIterator& insert_end) { 5258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) for (InputIterator i = insert_begin; i != insert_end; ++i) { 5358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) const T& t = *i; 5458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) push_back(t); 5558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 5658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 5758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 5858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // Appends all items from the given other set. 5958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) void append(const OrderedSet<T>& other) { 6058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) for (size_t i = 0; i < other.size(); i++) 6158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) push_back(other[i]); 6258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 6358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 6458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) private: 6558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) set_type set_; 6658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) vector_type ordering_; 6758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)}; 6858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 6958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#endif // TOOLS_GN_ORDERED_SET_H_ 70