From 3b62b01f9a6fbecbc8aa22750d797459f8ae6417 Mon Sep 17 00:00:00 2001
From: Rafael Espindola <rafael.espindola@gmail.com>
Date: Tue, 18 Sep 2012 18:43:21 +0000
Subject: [PATCH] Add a MapVector class. It provides a regular set iteration,
 but also provides a insertion order iteration over the values.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164157 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/MapVector.h | 153 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 153 insertions(+)
 create mode 100644 include/llvm/ADT/MapVector.h

diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h
new file mode 100644
index 00000000000..be3845f1d27
--- /dev/null
+++ b/include/llvm/ADT/MapVector.h
@@ -0,0 +1,153 @@
+//===- llvm/ADT/MapVector.h - Map with deterministic value order *- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a map that also provides access to all stored values
+// in a deterministic order via the getValues method. Note that the iteration
+// order itself is just the DenseMap order and not deterministic. The interface
+// is purposefully minimal.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_MAPVECTOR_H
+#define LLVM_ADT_MAPVECTOR_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include <vector>
+
+namespace llvm {
+
+/// This class implements a map that also provides access to all stored values
+/// in a deterministic order. The values are kept in a std::vector and the
+/// mapping is done with DenseMap from Keys to indexes in that vector.
+template<typename KeyT, typename ValueT>
+class MapVector {
+  typedef llvm::DenseMap<KeyT, unsigned> MapType;
+  typedef std::vector<ValueT> VectorType;
+  typedef typename VectorType::size_type SizeType;
+
+  MapType Map;
+  VectorType Vector;
+
+public:
+  // The keys and values are not stored close to each other, so the iterator
+  // operator->() cannot return a pointer to a std::pair like a DenseMap does.
+  // Instead it returns a FakePair that contains references to Key and Value.
+  // This lets code using this to look the same as if using a regular DenseMap.
+  template<bool IsConst>
+  struct FakePair {
+    typedef typename conditional<IsConst, const ValueT, ValueT>::type VT;
+    const KeyT &first;
+    VT &second;
+    FakePair(const KeyT &K, VT &V) : first(K), second(V) {
+    }
+    FakePair *operator->() {
+      return this;
+    }
+  };
+
+  template<bool IsConst>
+  class IteratorTemplate {
+    typedef typename MapType::const_iterator WrappedIteratorType;
+    WrappedIteratorType WrappedI;
+    typedef
+      typename conditional<IsConst, const VectorType, VectorType>::type VT;
+    VT &VecRef;
+    typedef FakePair<IsConst> PairType;
+    friend class IteratorTemplate<true>;
+
+  public:
+    IteratorTemplate(WrappedIteratorType I, VT &V) :
+      WrappedI(I), VecRef(V) {
+    }
+
+    // If IsConst is true this is a converting constructor from iterator to
+    // const_iterator and the default copy constructor is used.
+    // Otherwise this is a copy constructor for iterator.
+    IteratorTemplate(const IteratorTemplate<false>& I) :
+      WrappedI(I.WrappedI), VecRef(I.VecRef) {
+    }
+
+    bool operator!=(const IteratorTemplate &RHS) const {
+      return WrappedI != RHS.WrappedI;
+    }
+
+    IteratorTemplate &operator++() {  // Preincrement
+      ++WrappedI;
+      return *this;
+    }
+
+    PairType operator->() {
+      unsigned Pos = WrappedI->second;
+      PairType Ret(WrappedI->first, VecRef[Pos]);
+      return Ret;
+    }
+  };
+
+  typedef IteratorTemplate<false> iterator;
+  typedef IteratorTemplate<true> const_iterator;
+
+  SizeType size() const {
+    return Vector.size();
+  }
+
+  iterator begin() {
+    return iterator(Map.begin(), this->Vector);
+  }
+
+  const_iterator begin() const {
+    return const_iterator(Map.begin(), this->Vector);
+  }
+
+  iterator end() {
+    return iterator(Map.end(), this->Vector);
+  }
+
+  const_iterator end() const {
+    return const_iterator(Map.end(), this->Vector);
+  }
+
+  bool empty() const {
+    return Map.empty();
+  }
+
+  typedef typename VectorType::iterator value_iterator;
+  typedef typename VectorType::const_iterator const_value_iterator;
+
+  value_iterator value_begin() {
+    return Vector.begin();
+  }
+
+  const_value_iterator value_begin() const {
+    return Vector.begin();
+  }
+
+  value_iterator value_end() {
+    return Vector.end();
+  }
+
+  const_value_iterator value_end() const {
+    return Vector.end();
+  }
+
+  ValueT &operator[](const KeyT &Key) {
+    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
+    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
+    unsigned &I = Result.first->second;
+    if (Result.second) {
+      Vector.push_back(ValueT());
+      I = Vector.size() - 1;
+    }
+    return Vector[I];
+  }
+};
+
+}
+
+#endif
-- 
2.11.0