include/llvm/ADT/SortedVector.h

   1 //===-- llvm/ADT/SortedVector.h ---------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_ADT_SORTEDVECTOR_H
  11 #define LLVM_ADT_SORTEDVECTOR_H
  12
  13 #include <vector>
  14 #include <cassert>
  15 #include <functional>
  16 #include "llvm/Support/raw_ostream.h"
  17
  18 namespace llvm {
  19
  20 /// \brief Lazily maintains a sorted and unique vector of elements of type T.
  21 template<typename T, typename CMP = std::less<T>>
  22 class SortedVector {
  23 public:
  24   typedef typename std::vector<T> VectorType;
  25   typedef typename VectorType::iterator iterator;
  26   typedef typename VectorType::const_iterator const_iterator;
  27
  28 private:
  29   VectorType Vector;
  30   bool IsSorted = true;
  31
  32   void doCheck() const {
  33     assert(IsSorted && "Unsorted SortedVector access; call sortUnique prior.");
  34   }
  35
  36 public:
  37   /// \brief Appends Entry to the sorted unique vector; sets the IsSorted flag
  38   /// to false if appending Entry puts Vector into an unsorted state.
  39   void insert(const T &Entry) {
  40     if (!Vector.size())
  41       Vector.push_back(Entry);
  42
  43     // Vector is sorted and Entry is a duplicate of the previous so skip.
  44     if (IsSorted && Entry == Vector.back())
  45       return;
  46
  47     IsSorted &= (CMP()(Vector.back(), Entry));
  48     Vector.push_back(Entry);
  49   }
  50
  51   // \brief Sorts and uniques Vector.
  52   void sortUnique() {
  53     if (IsSorted)
  54       return;
  55
  56     std::sort(Vector.begin(), Vector.end());
  57     Vector.erase(std::unique(Vector.begin(), Vector.end()), Vector.end());
  58     IsSorted = true;
  59   }
  60
  61   /// \brief Tells if Entry is in Vector without relying on sorted-uniqueness.
  62   bool has(T Entry) const {
  63     if (IsSorted)
  64       return std::binary_search(Vector.begin(), Vector.end(), Entry);
  65
  66     return std::find(Vector.begin(), Vector.end(), Entry) != Vector.end();
  67   }
  68
  69   /// \brief Returns a reference to the entry with the specified index.
  70   const T &operator[](unsigned index) const {
  71     assert(index < size() && "SortedVector index is out of range!");
  72     doCheck();
  73     return Vector[index];
  74   }
  75
  76   /// \brief Return an iterator to the start of the vector.
  77   iterator begin() {
  78     doCheck();
  79     return Vector.begin();
  80   }
  81
  82   /// \brief Returns const iterator to the start of the vector.
  83   const_iterator begin() const {
  84     doCheck();
  85     return Vector.begin();
  86   }
  87
  88   /// \brief Returns iterator to the end of Vector.
  89   iterator end() {
  90     doCheck();
  91     return Vector.end();
  92   }
  93
  94   /// \brief Returns const iterator to the end of Vector. Assert if unsorted.
  95   const_iterator end() const {
  96     doCheck();
  97     return Vector.end();
  98   }
  99
 100   /// \brief Erases Vector at position. Asserts if Vector is unsorted.
 101   iterator erase(iterator position) {
 102     doCheck();
 103     return Vector.erase(position);
 104   }
 105
 106   /// \brief Erases Vector entirely.
 107   iterator erase() {
 108     IsSorted = true;
 109     return Vector.erase();
 110   }
 111
 112   /// \brief Returns number of entries in Vector; asserts if it is unsorted.
 113   size_t size() const {
 114     doCheck();
 115     return Vector.size();
 116   }
 117
 118   /// \brief Returns true if Vector is empty.
 119   bool empty() const {
 120     return Vector.empty();
 121   }
 122
 123   /// \brief Clears all the entries.
 124   void reset() {
 125     IsSorted = true;
 126     Vector.resize(0, 0);
 127   }
 128 };
 129
 130 } // End of namespace llvm
 131
 132 #endif // LLVM_ADT_SORTEDVECTOR_H
 133