SST  7.0.0
StructuralSimulationToolkit
sparseVectorMap.h
1 // -*- c++ -*-
2 
3 // Copyright 2009-2017 Sandia Corporation. Under the terms
4 // of Contract DE-AC04-94AL85000 with Sandia Corporation, the U.S.
5 // Government retains certain rights in this software.
6 //
7 // Copyright (c) 2009-2017, Sandia Corporation
8 // All rights reserved.
9 //
10 // This file is part of the SST software package. For license
11 // information, see the LICENSE file in the top level directory of the
12 // distribution.
13 
14 #ifndef SST_CORE_SPARSEVECTORMAP_H
15 #define SST_CORE_SPARSEVECTORMAP_H
16 
17 #include "sst/core/sst_types.h"
18 #include <sst/core/serialization/serializable.h>
19 
20 #include <vector>
21 
22 namespace SST {
23 
24 
25 template <typename keyT, typename classT = keyT>
27 private:
28  friend class SST::Core::Serialization::serialize<SparseVectorMap<keyT,classT> >;
29 
30  std::vector<classT> data;
31  int binary_search_insert(keyT id) const
32  {
33  // For insert, we've found the right place when id < n && id >
34  // n-1. We then insert at n.
35 
36  int size = data.size();
37 
38  // Check to see if it goes top or bottom
39  if ( size == 0 ) return 0;
40  if ( id < data[0].key() ) return 0;
41  if ( id > data[size-1].key() ) return size;
42 
43  int bottom = 0;
44  int top = size - 1;
45  int middle;
46 
47  while ( bottom <= top ) {
48  middle = bottom + (top - bottom) / 2;
49  if ( id == data[middle].key() ) return -1; // Already in map
50  if ( id < data[middle].key() ) {
51  // May be the right place, need to see if id is greater
52  // than the one before the current middle. If so, then we
53  // have the right place.
54  if ( id > data[middle-1].key() ) return middle;
55  else {
56  top = middle - 1;
57  }
58  }
59  else {
60  bottom = middle + 1;
61  }
62  }
63  /* Shouldn't be reached */
64  return -1;
65  }
66 
67  int binary_search_find(keyT id) const
68  {
69  int bottom = 0;
70  int top = data.size() - 1;
71  int middle;
72 
73  if ( data.size() == 0 ) return -1;
74  while (bottom <= top) {
75  middle = bottom + ( top - bottom ) / 2;
76  if ( id == data[middle].key() ) return middle;
77  else if ( id < data[middle].key() ) top = middle - 1;
78  else bottom = middle + 1;
79  }
80  return -1;
81  }
82 
83  friend class ConfigGraph;
84 
85 public:
86  typedef typename std::vector<classT>::iterator iterator;
87  typedef typename std::vector<classT>::const_iterator const_iterator;
88 
89  // Essentially insert with a hint to look at end first. This is
90  // just here for backward compatibility for now. Will be replaced
91  // with insert() onced things stabilize.
92  void push_back(const classT& val)
93  {
94  // First look to see if it goes on the end. If not, then find
95  // where it goes.
96  if ( data.size() == 0 ) {
97  data.push_back(val);
98  return;
99  }
100  if ( val.key() > data[data.size()-1].key() ) {
101  data.push_back(val);
102  return;
103  }
104 
105  // Didn't belong at end, call regular insert
106  insert(val);
107  }
108 
109  void insert(const classT& val)
110  {
111  int index = binary_search_insert(val.key());
112  if ( index == -1 ) return; // already in the map
113  iterator it = data.begin();
114  it += index;
115  data.insert(it, val);
116  }
117 
118  iterator begin() { return data.begin(); }
119  iterator end() { return data.end(); }
120 
121  const_iterator begin() const { return data.begin(); }
122  const_iterator end() const { return data.end(); }
123 
124  bool contains(keyT id) const
125  {
126  if ( binary_search_find(id) == -1 ) return false;
127  return true;
128  }
129 
130  classT& operator[] (keyT id)
131  {
132  int index = binary_search_find(id);
133  if ( index == -1 ) {
134  // Need to error out
135  }
136  return data[index];
137  }
138 
139  const classT& operator[] (keyT id) const
140  {
141  int index = binary_search_find(id);
142  if ( index == -1 ) {
143  // Need to error out
144  }
145  return data[index];
146  }
147 
148  void clear() { data.clear(); }
149  size_t size() { return data.size(); }
150 
151 };
152 
153 template <typename keyT>
154 class SparseVectorMap<keyT,keyT> {
155 private:
156  friend class SST::Core::Serialization::serialize<SparseVectorMap<keyT,keyT> >;
157 
158  std::vector<keyT> data;
159  int binary_search_insert(keyT id) const
160  {
161  // For insert, we've found the right place when id < n && id >
162  // n-1. We then insert at n.
163 
164  int size = data.size();
165 
166  // Check to see if it goes top or bottom
167  if ( size == 0 ) return 0;
168  if ( id < data[0] ) return 0;
169  if ( id > data[size-1] ) return size;
170 
171  int bottom = 0;
172  int top = size - 1;
173  int middle;
174 
175  while ( bottom <= top ) {
176  middle = bottom + (top - bottom) / 2;
177  if ( id == data[middle] ) return -1; // Already in map
178  if ( id < data[middle] ) {
179  // May be the right place, need to see if id is greater
180  // than the one before the current middle. If so, then we
181  // have the right place.
182  if ( id > data[middle-1] ) return middle;
183  else {
184  top = middle - 1;
185  }
186  }
187  else {
188  bottom = middle + 1;
189  }
190  }
191  /* Shouldn't be reached */
192  return -1;
193  }
194 
195  int binary_search_find(keyT id) const
196  {
197  int bottom = 0;
198  int top = data.size() - 1;
199  int middle;
200 
201  if ( data.size() == 0 ) return -1;
202  while (bottom <= top) {
203  middle = bottom + ( top - bottom ) / 2;
204  if ( id == data[middle] ) return middle;
205  else if ( id < data[middle] ) top = middle - 1;
206  else bottom = middle + 1;
207  }
208  return -1;
209  }
210 
211  friend class ConfigGraph;
212 
213 public:
214  typedef typename std::vector<keyT>::iterator iterator;
215  typedef typename std::vector<keyT>::const_iterator const_iterator;
216 
217  // Essentially insert with a hint to look at end first. This is
218  // just here for backward compatibility for now. Will be replaced
219  // with insert() onced things stabilize.
220  void push_back(const keyT& val)
221  {
222  // First look to see if it goes on the end. If not, then find
223  // where it goes.
224  if ( data.size() == 0 ) {
225  data.push_back(val);
226  return;
227  }
228  if ( val.key() > data[data.size()-1].key() ) {
229  data.push_back(val);
230  return;
231  }
232 
233  // Didn't belong at end, call regular insert
234  insert(val);
235  }
236 
237  void insert(const keyT& val)
238  {
239  int index = binary_search_insert(val);
240  if ( index == -1 ) return; // already in the map
241  iterator it = data.begin();
242  it += index;
243  data.insert(it, val);
244  }
245 
246  iterator begin() { return data.begin(); }
247  iterator end() { return data.end(); }
248 
249  const_iterator begin() const { return data.begin(); }
250  const_iterator end() const { return data.end(); }
251 
252  bool contains(keyT id)
253  {
254  if ( binary_search_find(id) == -1 ) return false;
255  return true;
256  }
257 
258  keyT& operator[] (keyT id)
259  {
260  int index = binary_search_find(id);
261  if ( index == -1 ) {
262  // Need to error out
263  }
264  return data[index];
265  }
266 
267  const keyT& operator[] (keyT id) const
268  {
269  int index = binary_search_find(id);
270  if ( index == -1 ) {
271  // Need to error out
272  }
273  return data[index];
274  }
275 
276  void clear() { data.clear(); }
277  size_t size() { return data.size(); }
278 
279 };
280 
281 
282 
283 } // namespace SST
284 
285 namespace SST {
286 namespace Core {
287 namespace Serialization {
288 
289 template <typename keyT, typename classT>
290 class serialize <SST::SparseVectorMap<keyT,classT>> {
291 public:
292  void
294  ser & v.data;
295  }
296 };
297 }
298 }
299 }
300 
301 
302 #endif // SST_CORE_CONFIGGRAPH_H
This class is basically a wrapper for objects to declare the order in which their members should be s...
Definition: serializer.h:35
A Configuration Graph A graph representing Components and Links.
Definition: configGraph.h:337
Definition: action.cc:17
Base serialize class.
Definition: serialize.h:33
Definition: sparseVectorMap.h:26