tools/gn/ordered_set.h

   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
  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_