source: src/Common/VectorMap.hpp @ 4ff7ea3

Last change on this file since 4ff7ea3 was c92bdcc, checked in by Andrew Beach <ajbeach@…>, 7 months ago

Updated the rest of the names in src/ (except for the generated files).

  • Property mode set to 100644
File size: 7.9 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// VectorMap.hpp --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed Feb  1 16:55:00 2017
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Fri Jul 21 22:19:29 2017
13// Update Count     : 2
14//
15
16#pragma once
17
18#include <iterator>
19#include <utility>
20#include <vector>
21
22/// Maps integers from a contiguous range to T's
23template<typename T>
24class VectorMap {
25        std::vector<T> data;
26
27public:
28        typedef typename std::vector<T>::size_type size_type;
29        typedef size_type key_type;
30        typedef T mapped_type;
31        typedef std::pair<size_type, T&> value_type;
32        typedef std::pair<size_type, const T&> const_value_type;
33        typedef typename std::vector<T>::difference_type difference_type;
34        typedef const value_type& reference;
35        typedef const const_value_type& const_reference;
36        typedef const value_type* pointer;
37        typedef const const_value_type* const_pointer;
38
39        class iterator : public std::iterator<
40                        std::random_access_iterator_tag,
41                        value_type, difference_type, pointer, reference > {
42                friend class VectorMap;
43                friend class const_iterator;
44
45                value_type data;
46
47                iterator(size_type i, std::vector<T>& v) : data(i, v[i]) {}
48        public:
49                iterator(const iterator& that) : data(that.data) {}
50                iterator& operator= (const iterator& that) {
51                        new(&data) value_type{ that.data };
52                        return *this;
53                }
54
55                reference operator* () { return data; }
56                pointer operator-> () { return &data; }
57
58                iterator& operator++ () {
59                        // SHENANIGANS: relies on pair<unsigned, T&> having a trivial destructor and
60                        // vector<T> having contiguous layout
61                        new(&data) value_type{ (data.first + 1), *(&data.second + 1) };
62                        return *this;
63                }
64                iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
65
66                iterator& operator-- () {
67                        // SHENANIGANS: same reasons as operator++
68                        new(&data) value_type{ (data.first - 1), *(&data.second - 1) };
69                        return *this;
70                }
71                iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
72
73                iterator& operator+= (difference_type i) {
74                        // SHENANIGANS: same reasons as operator++
75                        new(&data) value_type{ (data.first + i), *(&data.second + i) };
76                        return *this;
77                }
78
79                iterator operator+ (difference_type i) const { iterator tmp = *this; return tmp += i; }
80
81                iterator& operator-= (difference_type i) {
82                        // SHENANIGANS: same reasons as operator++
83                        new(&data) value_type{ (data.first - i), *(&data.second - i) };
84                        return *this;
85                }
86
87                iterator operator- (difference_type i) const { iterator tmp = *this; return tmp -= i; }
88
89                difference_type operator- (const iterator& o) const { return data.first - o.data.first; }
90
91                value_type operator[] (difference_type i) const {
92                        // SHENANIGANS: same reasons as operator++
93                        return value_type{ (data.first + i), *(&data.second + i) };
94                }
95
96                bool operator== (const iterator& o) const {
97                        return data.first == o.data.first && &data.second == &o.data.second;
98                }
99
100                bool operator!= (const iterator& that) const { return !(*this == that); }
101
102                bool operator< (const iterator& o) const { return data.first < o.data.first; }
103
104                bool operator> (const iterator& o) const { return data.first > o.data.first; }
105
106                bool operator<= (const iterator& o) const { return data.first <= o.data.first; }
107
108                bool operator>= (const iterator& o) const { return data.first >= o.data.first; }
109        };
110
111        class const_iterator : public std::iterator<
112                        std::bidirectional_iterator_tag,
113                        const_value_type, difference_type, const_pointer, const_reference > {
114                friend class VectorMap;
115                const_value_type data;
116
117                const_iterator(size_type i, const std::vector<T>& v) : data(i, v[i]) {}
118        public:
119                const_iterator(const iterator& that) : data(that.data) {}
120                const_iterator(const const_iterator& that) : data(that.data) {}
121                const_iterator& operator= (const iterator& that) {
122                        new(&data) const_value_type{ that.data };
123                        return *this;
124                }
125                const_iterator& operator= (const const_iterator& that) {
126                        new(&data) const_value_type{ that.data };
127                        return *this;
128                }
129
130                const_reference operator* () { return data; }
131                const_pointer operator-> () { return &data; }
132
133                const_iterator& operator++ () {
134                        // SHENANIGANS: same reasons as iterator::operator++
135                        new(&data) const_value_type{ (data.first + 1), *(&data.second + 1) };
136                        return *this;
137                }
138                const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
139
140                const_iterator& operator-- () {
141                        // SHENANIGANS: same reasons as iterator::operator++
142                        new(&data) const_value_type{ (data.first - 1), *(&data.second - 1) };
143                        return *this;
144                }
145                const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
146
147                const_iterator& operator+= (difference_type i) {
148                        // SHENANIGANS: same reasons as iterator::operator++
149                        new(&data) const_value_type{ (data.first + i), *(&data.second + i) };
150                        return *this;
151                }
152
153                const_iterator operator+ (difference_type i) const {
154                        const_iterator tmp = *this; return tmp += i;
155                }
156
157                const_iterator& operator-= (difference_type i) {
158                        // SHENANIGANS: same reasons as iterator::operator++
159                        new(&data) const_value_type{ (data.first - i), *(&data.second - i) };
160                        return *this;
161                }
162
163                const_iterator operator- (difference_type i) const {
164                        const_iterator tmp = *this; return tmp -= i;
165                }
166
167                difference_type operator- (const const_iterator& o) const {
168                        return data.first - o.data.first;
169                }
170
171                const_value_type operator[] (difference_type i) const {
172                        // SHENANIGANS: same reasons as iterator::operator++
173                        return const_value_type{ (data.first + i), *(&data.second + i) };
174                }
175
176                bool operator== (const const_iterator& o) const {
177                        return data.first == o.data.first && &data.second == &o.data.second;
178                }
179
180                bool operator!= (const const_iterator& that) const { return !(*this == that); }
181
182                bool operator< (const const_iterator& o) const { return data.first < o.data.first; }
183
184                bool operator> (const const_iterator& o) const { return data.first > o.data.first; }
185
186                bool operator<= (const const_iterator& o) const { return data.first <= o.data.first; }
187
188                bool operator>= (const const_iterator& o) const { return data.first >= o.data.first; }
189        };
190
191        /// Reserve space for n elements
192        void reserve(size_type n) {
193                if ( n > data.size() ) { data.insert( data.end(), n - data.size(), T{} ); }
194        }
195
196        /// Unsafe access; no bounds checking
197        T& operator[] (size_type i) { return data[i]; }
198        const T& operator[] (size_type i) const { return data[i]; }
199
200        /// Safe access; will insert new values if needed
201        T& at(size_type i) {
202                reserve(i+1);
203                return data[i];
204        }
205
206        /// Number of stored values
207        unsigned size() const { return data.size(); }
208
209        /// No stored values
210        bool empty() const { return data.empty(); }
211
212        /// Empties the map
213        void clear() { data.clear(); }
214
215        /// Returns 1 if element in map, 0 otherwise
216        size_type count( size_type i ) const { return i < size() ? 1 : 0; }
217
218        iterator begin() { return iterator{ 0, data }; }
219        const_iterator begin() const { return const_iterator{ 0, data }; }
220        const_iterator cbegin() const { return const_iterator{ 0, data }; }
221
222        iterator end() { return iterator{ data.size(), data }; }
223        const_iterator end() const { return const_iterator{ data.size(), data }; }
224        const_iterator cend() const { return const_iterator{ data.size(), data }; }
225
226        iterator find( size_type i ) { return i < size() ? iterator{ i, data } : end(); }
227        const_iterator find( size_type i ) const { return i < size() ? const_iterator{ i, data } : end(); }
228};
229
230template<typename T>
231typename VectorMap<T>::iterator operator+(
232                typename VectorMap<T>::difference_type i,
233                const typename VectorMap<T>::iterator& it) {
234        return it + i;
235}
236
237template<typename T>
238typename VectorMap<T>::const_iterator operator+(
239                typename VectorMap<T>::difference_type i,
240                const typename VectorMap<T>::const_iterator& it) {
241        return it + i;
242}
243
244// Local Variables: //
245// tab-width: 4 //
246// mode: c++ //
247// compile-command: "make install" //
248// End: //
Note: See TracBrowser for help on using the repository browser.