[C++11] Replace llvm::next and llvm::prior with std::next and std::prev.
[oota-llvm.git] / include / llvm / ADT / MapVector.h
1 //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- 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 // This file implements a map that provides insertion order iteration. The
11 // interface is purposefully minimal. The key is assumed to be cheap to copy
12 // and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
13 // a std::vector.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #ifndef LLVM_ADT_MAPVECTOR_H
18 #define LLVM_ADT_MAPVECTOR_H
19
20 #include "llvm/ADT/DenseMap.h"
21 #include <vector>
22
23 namespace llvm {
24
25 /// This class implements a map that also provides access to all stored values
26 /// in a deterministic order. The values are kept in a std::vector and the
27 /// mapping is done with DenseMap from Keys to indexes in that vector.
28 template<typename KeyT, typename ValueT,
29          typename MapType = llvm::DenseMap<KeyT, unsigned>,
30          typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
31 class MapVector {
32   typedef typename VectorType::size_type SizeType;
33
34   MapType Map;
35   VectorType Vector;
36
37 public:
38   typedef typename VectorType::iterator iterator;
39   typedef typename VectorType::const_iterator const_iterator;
40
41   SizeType size() const {
42     return Vector.size();
43   }
44
45   iterator begin() {
46     return Vector.begin();
47   }
48
49   const_iterator begin() const {
50     return Vector.begin();
51   }
52
53   iterator end() {
54     return Vector.end();
55   }
56
57   const_iterator end() const {
58     return Vector.end();
59   }
60
61   bool empty() const {
62     return Vector.empty();
63   }
64
65   std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
66   const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
67   std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
68   const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
69
70   void clear() {
71     Map.clear();
72     Vector.clear();
73   }
74
75   ValueT &operator[](const KeyT &Key) {
76     std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
77     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
78     unsigned &I = Result.first->second;
79     if (Result.second) {
80       Vector.push_back(std::make_pair(Key, ValueT()));
81       I = Vector.size() - 1;
82     }
83     return Vector[I].second;
84   }
85
86   ValueT lookup(const KeyT &Key) const {
87     typename MapType::const_iterator Pos = Map.find(Key);
88     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
89   }
90
91   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
92     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
93     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
94     unsigned &I = Result.first->second;
95     if (Result.second) {
96       Vector.push_back(std::make_pair(KV.first, KV.second));
97       I = Vector.size() - 1;
98       return std::make_pair(std::prev(end()), true);
99     }
100     return std::make_pair(begin() + I, false);
101   }
102
103   unsigned count(const KeyT &Key) const {
104     typename MapType::const_iterator Pos = Map.find(Key);
105     return Pos == Map.end()? 0 : 1;
106   }
107
108   iterator find(const KeyT &Key) {
109     typename MapType::const_iterator Pos = Map.find(Key);
110     return Pos == Map.end()? Vector.end() :
111                             (Vector.begin() + Pos->second);
112   }
113
114   const_iterator find(const KeyT &Key) const {
115     typename MapType::const_iterator Pos = Map.find(Key);
116     return Pos == Map.end()? Vector.end() :
117                             (Vector.begin() + Pos->second);
118   }
119
120   /// \brief Remove the last element from the vector.
121   void pop_back() {
122     typename MapType::iterator Pos = Map.find(Vector.back().first);
123     Map.erase(Pos);
124     Vector.pop_back();
125   }
126 };
127
128 }
129
130 #endif