UniqueVector.h 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
  1. //===-- llvm/ADT/UniqueVector.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. #ifndef LLVM_ADT_UNIQUEVECTOR_H
  10. #define LLVM_ADT_UNIQUEVECTOR_H
  11. #include <cassert>
  12. #include <map>
  13. #include <vector>
  14. namespace llvm {
  15. // //
  16. ///////////////////////////////////////////////////////////////////////////////
  17. /// UniqueVector - This class produces a sequential ID number (base 1) for each
  18. /// unique entry that is added. T is the type of entries in the vector. This
  19. /// class should have an implementation of operator== and of operator<.
  20. /// Entries can be fetched using operator[] with the entry ID.
  21. template<class T> class UniqueVector {
  22. public:
  23. typedef typename std::vector<T> VectorType;
  24. typedef typename VectorType::iterator iterator;
  25. typedef typename VectorType::const_iterator const_iterator;
  26. private:
  27. // Map - Used to handle the correspondence of entry to ID.
  28. std::map<T, unsigned> Map;
  29. // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1.
  30. //
  31. VectorType Vector;
  32. public:
  33. /// insert - Append entry to the vector if it doesn't already exist. Returns
  34. /// the entry's index + 1 to be used as a unique ID.
  35. unsigned insert(const T &Entry) {
  36. // Check if the entry is already in the map.
  37. unsigned &Val = Map[Entry];
  38. // See if entry exists, if so return prior ID.
  39. if (Val) return Val;
  40. // Compute ID for entry.
  41. Val = static_cast<unsigned>(Vector.size()) + 1;
  42. // Insert in vector.
  43. Vector.push_back(Entry);
  44. return Val;
  45. }
  46. /// idFor - return the ID for an existing entry. Returns 0 if the entry is
  47. /// not found.
  48. unsigned idFor(const T &Entry) const {
  49. // Search for entry in the map.
  50. typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry);
  51. // See if entry exists, if so return ID.
  52. if (MI != Map.end()) return MI->second;
  53. // No luck.
  54. return 0;
  55. }
  56. /// operator[] - Returns a reference to the entry with the specified ID.
  57. ///
  58. const T &operator[](unsigned ID) const {
  59. assert(ID-1 < size() && "ID is 0 or out of range!");
  60. return Vector[ID - 1];
  61. }
  62. /// \brief Return an iterator to the start of the vector.
  63. iterator begin() { return Vector.begin(); }
  64. /// \brief Return an iterator to the start of the vector.
  65. const_iterator begin() const { return Vector.begin(); }
  66. /// \brief Return an iterator to the end of the vector.
  67. iterator end() { return Vector.end(); }
  68. /// \brief Return an iterator to the end of the vector.
  69. const_iterator end() const { return Vector.end(); }
  70. /// size - Returns the number of entries in the vector.
  71. ///
  72. size_t size() const { return Vector.size(); }
  73. /// empty - Returns true if the vector is empty.
  74. ///
  75. bool empty() const { return Vector.empty(); }
  76. /// reset - Clears all the entries.
  77. ///
  78. void reset() {
  79. Map.clear();
  80. Vector.resize(0, 0);
  81. }
  82. };
  83. } // End of namespace llvm
  84. #endif // LLVM_ADT_UNIQUEVECTOR_H