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.
12template<typename T>
13class 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
22  OrderedSet() {}
23  ~OrderedSet() {}
24
25  const T& operator[](size_t index) const {
26    return *ordering_[index];
27  }
28  size_t size() const {
29    return ordering_.size();
30  }
31  bool empty() const {
32    return ordering_.empty();
33  }
34
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.
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>
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.
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