Home | History | Annotate | Download | only in gn 
      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_
     70