SST  11.1.0
StructuralSimulationToolkit
sparseVectorMap.h
1 // -*- c++ -*-
2 
3 // Copyright 2009-2021 NTESS. Under the terms
4 // of Contract DE-NA0003525 with NTESS, the U.S.
5 // Government retains certain rights in this software.
6 //
7 // Copyright (c) 2009-2021, NTESS
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/serialization/serializable.h"
18 #include "sst/core/sst_types.h"
19 
20 #include <algorithm>
21 #include <vector>
22 
23 namespace SST {
24 
25 /**
26  Class that stores data in a vector, but can access the data similar
27  to a map. The data structure is O(log n) on reads, but is O(n) to
28  insert. The primary use case is when data is inserted in order, but
29  accessed randomly. You can also create the SparseVectorMap with a
30  vector already loaded with the data. If the data is not already
31  sorted, it will call std::sort on the data, which likely has an
32  average complexity of O(n log n). This data structure should not
33  be used for large lists where inserts do not happen in sorted order.
34 
35  NOTE: Since the data is stored in the vector, reference returned
36  from the various accessor functions will not be valid longterm. If
37  an insert causes the vector to be resized, all references returned
38  before that reallocation may (likely will) be invalid. References
39  are only guaranteed to be valid until the next write to the data
40  structure.
41  */
42 template <typename keyT, typename classT = keyT>
44 {
45 private:
46  friend class SST::Core::Serialization::serialize<SparseVectorMap<keyT, classT>>;
47 
48  /**
49  Finds the insertion point for new data
50 
51  @param id ID of the data that needs to be inserted.
52 
53  @return Index where new data should be inserted. If key is
54  already in the map, it will return -1.
55  */
56  std::vector<classT> data;
57  int binary_search_insert(keyT id) const
58  {
59  // For insert, we've found the right place when id < n && id >
60  // n-1. We then insert at n.
61 
62  int size = data.size();
63 
64  // Check to see if it goes top or bottom
65  if ( size == 0 ) return 0;
66  if ( id > data[size - 1].key() ) return size;
67  if ( id < data[0].key() ) return 0;
68 
69  int bottom = 0;
70  int top = size - 1;
71  int middle;
72 
73  while ( bottom <= top ) {
74  middle = bottom + (top - bottom) / 2;
75  if ( id == data[middle].key() ) return -1; // Already in map
76  if ( id < data[middle].key() ) {
77  // May be the right place, need to see if id is greater
78  // than the one before the current middle. If so, then we
79  // have the right place.
80  if ( id > data[middle - 1].key() )
81  return middle;
82  else {
83  top = middle - 1;
84  }
85  }
86  else {
87  bottom = middle + 1;
88  }
89  }
90  /* Shouldn't be reached */
91  return -1;
92  }
93 
94  /**
95  Finds the index where the data associated with the given key is
96  found in the vector
97 
98  @param id ID of the data that needs to be found.
99 
100  @return Index where data for the provided ID is found. It
101  returns -1 if the key is not found in the data vector.
102  */
103  int binary_search_find(keyT id) const
104  {
105  int bottom = 0;
106  int top = data.size() - 1;
107  int middle;
108 
109  if ( data.size() == 0 ) return -1;
110  while ( bottom <= top ) {
111  middle = bottom + (top - bottom) / 2;
112  if ( id == data[middle].key() )
113  return middle;
114  else if ( id < data[middle].key() )
115  top = middle - 1;
116  else
117  bottom = middle + 1;
118  }
119  return -1;
120  }
121 
122  friend class ConfigGraph;
123 
124 public:
125  /**
126  Default constructor for SparseVectorMap
127  */
129 
130  /**
131  Constructor that allows you to pass an already filled in array
132  with data. The data in the passed in vector will be swapped
133  into the data vector of the sparsevectormap and the passed in
134  vector will be empty.
135 
136  @param new_data Vector of data to swap into the sparsevectormap
137  data
138 
139  @param sorted Specifies whether the vector is already sorted in
140  ascending order. if not, it will be sorted after swapping the
141  data in.
142  */
143  SparseVectorMap(std::vector<classT>& new_data, bool sorted = false)
144  {
145  data.swap(new_data);
146  if ( !sorted ) {
147  std::sort(data.begin(), data.end, [](const classT& lhs, const classT& rhs) -> bool {
148  return lhs.key() < rhs.key();
149  });
150  }
151  }
152 
153  typedef typename std::vector<classT>::iterator iterator;
154  typedef typename std::vector<classT>::const_iterator const_iterator;
155 
156  /**
157  Insert new value into SparseVectorMap. The inserted class must
158  have a key() function with return type keyT.
159 
160  @param val value to add to SparseVectorMap
161 
162  @return reference to the inserted item, or to the existing item
163  if it was already present in the map.
164 
165  */
166  classT& insert(const classT& val)
167  {
168  int index = binary_search_insert(val.key());
169  if ( index == -1 ) return data[binary_search_find(val.key())]; // already in the map
170  iterator it = data.begin();
171  it += index;
172  data.insert(it, val);
173  return data[index];
174  }
175 
176  /**
177  Returns the begin iterator to the underlying vector.
178 
179  @return begin iterator to data vector
180  */
181  iterator begin() { return data.begin(); }
182 
183  /**
184  Returns the end iterator to the underlying vector.
185 
186  @return end iterator to data vector
187  */
188  iterator end() { return data.end(); }
189 
190  /**
191  Returns the const begin iterator to the underlying vector.
192 
193  @return const begin iterator to data vector
194  */
195  const_iterator begin() const { return data.begin(); }
196 
197  /**
198  Returns the const end iterator to the underlying vector.
199 
200  @return const end iterator to data vector
201  */
202  const_iterator end() const { return data.end(); }
203 
204  /**
205  Checks if the provided id is found in the SparseVectorMap
206 
207  @param id id to check for
208 
209  @return true if id is found, false otherwise
210  */
211  bool contains(keyT id) const
212  {
213  if ( binary_search_find(id) == -1 ) return false;
214  return true;
215  }
216 
217  /**
218  Operator returns a reference to data with the specified id.
219  Value can be modified. This will only return references to
220  existing values, you must use insert() for new values.
221 
222  @param id id of the value to return (value returned by key())
223 
224  @return reference to the requested item.
225 
226  */
227  classT& operator[](keyT id)
228  {
229  int index = binary_search_find(id);
230  if ( index == -1 ) {
231  // Need to error out
232  }
233  return data[index];
234  }
235 
236  /**
237  Operator returns a const reference to data with the specified
238  id. Value cannot be modified. This will only return
239  references to existing values, you must use insert() for new
240  values.
241 
242  @param id id of the value to return (value returned by key())
243 
244  @return const reference to the requested item.
245 
246  */
247  const classT& operator[](keyT id) const
248  {
249  int index = binary_search_find(id);
250  if ( index == -1 ) {
251  // Need to error out
252  }
253  return data[index];
254  }
255 
256  /**
257  Clears the contents of the SparseVectorMap
258  */
259  void clear() { data.clear(); }
260 
261  /**
262  Returns the number of items in the SparseVectorMap
263 
264  @return number of items
265  */
266  size_t size() { return data.size(); }
267 };
268 
269 /**
270  Class that stores data in a vector, but can access the data similar
271  to a map. The data structure is O(log n) on reads, but is O(n) to
272  insert. The primary use case is when data is inserted in order, but
273  accessed randomly. You can also create the SparseVectorMap with a
274  vector already loaded with the data. If the data is not already
275  sorted, it will call std::sort on the data, which likely has an
276  average complexity of O(n log n). This data structure should not
277  be used for large lists where inserts do not happen in sorted order.
278 
279  NOTE: Since the data is stored in the vector, reference returned
280  from the various accessor functions will not be valid longterm. If
281  an insert causes the vector to be resized, all references returned
282  before that reallocation may (likely will) be invalid. References
283  are only guaranteed to be valid until the next write to the data
284  structure.
285  */
286 template <typename keyT, typename classT>
287 class SparseVectorMap<keyT, classT*>
288 {
289 private:
290  friend class SST::Core::Serialization::serialize<SparseVectorMap<keyT, classT*>>;
291 
292  /**
293  Finds the insertion point for new data
294 
295  @param id ID of the data that needs to be inserted.
296 
297  @return Index where new data should be inserted. If key is
298  already in the map, it will return -1.
299  */
300  std::vector<classT*> data;
301  int binary_search_insert(keyT id) const
302  {
303  // For insert, we've found the right place when id < n && id >
304  // n-1. We then insert at n.
305 
306  int size = data.size();
307 
308  // Check to see if it goes top or bottom
309  if ( size == 0 ) return 0;
310  if ( id > data[size - 1]->key() ) return size;
311  if ( id < data[0]->key() ) return 0;
312 
313  int bottom = 0;
314  int top = size - 1;
315  int middle;
316 
317  while ( bottom <= top ) {
318  middle = bottom + (top - bottom) / 2;
319  if ( id == data[middle]->key() ) return -1; // Already in map
320  if ( id < data[middle]->key() ) {
321  // May be the right place, need to see if id is greater
322  // than the one before the current middle. If so, then we
323  // have the right place.
324  if ( id > data[middle - 1]->key() )
325  return middle;
326  else {
327  top = middle - 1;
328  }
329  }
330  else {
331  bottom = middle + 1;
332  }
333  }
334  /* Shouldn't be reached */
335  return -1;
336  }
337 
338  /**
339  Finds the index where the data associated with the given key is
340  found in the vector
341 
342  @param id ID of the data that needs to be found.
343 
344  @return Index where data for the provided ID is found. It
345  returns -1 if the key is not found in the data vector.
346  */
347  int binary_search_find(keyT id) const
348  {
349  int bottom = 0;
350  int top = data.size() - 1;
351  int middle;
352 
353  if ( data.size() == 0 ) return -1;
354  while ( bottom <= top ) {
355  middle = bottom + (top - bottom) / 2;
356  if ( id == data[middle]->key() )
357  return middle;
358  else if ( id < data[middle]->key() )
359  top = middle - 1;
360  else
361  bottom = middle + 1;
362  }
363  return -1;
364  }
365 
366  friend class ConfigGraph;
367 
368 public:
369  /**
370  Default constructor for SparseVectorMap
371  */
373 
374  /**
375  Constructor that allows you to pass an already filled in array
376  with data. The data in the passed in vector will be swapped
377  into the data vector of the sparsevectormap and the passed in
378  vector will be empty.
379 
380  @param new_data Vector of data to swap into the sparsevectormap
381  data
382 
383  @param sorted Specifies whether the vector is already sorted in
384  ascending order. if not, it will be sorted after swapping the
385  data in.
386  */
387  SparseVectorMap(std::vector<classT*>& new_data, bool sorted = false)
388  {
389  data.swap(new_data);
390  if ( !sorted ) {
391  std::sort(data.begin(), data.end, [](const classT* lhs, const classT* rhs) -> bool {
392  return lhs->key() < rhs->key();
393  });
394  }
395  }
396 
397  typedef typename std::vector<classT*>::iterator iterator;
398  typedef typename std::vector<classT*>::const_iterator const_iterator;
399 
400  /**
401  Insert new value into SparseVectorMap. The inserted class must
402  have a key() function with return type keyT.
403 
404  @param val value to add to SparseVectorMap
405 
406  @return reference to the inserted item, or to the existing item
407  if it was already present in the map.
408 
409  */
410  classT* insert(classT* val)
411  {
412  int index = binary_search_insert(val->key());
413  if ( index == -1 ) return data[binary_search_find(val->key())]; // already in the map
414  iterator it = data.begin();
415  it += index;
416  data.insert(it, val);
417  return data[index];
418  }
419 
420  /**
421  Returns the begin iterator to the underlying vector.
422 
423  @return begin iterator to data vector
424  */
425  iterator begin() { return data.begin(); }
426 
427  /**
428  Returns the end iterator to the underlying vector.
429 
430  @return end iterator to data vector
431  */
432  iterator end() { return data.end(); }
433 
434  /**
435  Returns the const begin iterator to the underlying vector.
436 
437  @return const begin iterator to data vector
438  */
439  const_iterator begin() const { return data.begin(); }
440 
441  /**
442  Returns the const end iterator to the underlying vector.
443 
444  @return const end iterator to data vector
445  */
446  const_iterator end() const { return data.end(); }
447 
448  /**
449  Checks if the provided id is found in the SparseVectorMap
450 
451  @param id id to check for
452 
453  @return true if id is found, false otherwise
454  */
455  bool contains(keyT id) const
456  {
457  if ( binary_search_find(id) == -1 ) return false;
458  return true;
459  }
460 
461  /**
462  Operator returns a reference to data with the specified id.
463  Value can be modified. This will only return references to
464  existing values, you must use insert() for new values.
465 
466  @param id id of the value to return (value returned by key())
467 
468  @return reference to the requested item.
469 
470  */
471  classT* operator[](keyT id)
472  {
473  int index = binary_search_find(id);
474  if ( index == -1 ) {
475  // Need to error out
476  }
477  return data[index];
478  }
479 
480  /**
481  Operator returns a const reference to data with the specified
482  id. Value cannot be modified. This will only return
483  references to existing values, you must use insert() for new
484  values.
485 
486  @param id id of the value to return (value returned by key())
487 
488  @return const reference to the requested item.
489 
490  */
491  const classT* operator[](keyT id) const
492  {
493  int index = binary_search_find(id);
494  if ( index == -1 ) {
495  // Need to error out
496  }
497  return data[index];
498  }
499 
500  /**
501  Clears the contents of the SparseVectorMap
502  */
503  void clear() { data.clear(); }
504 
505  /**
506  Returns the number of items in the SparseVectorMap
507 
508  @return number of items
509  */
510  size_t size() { return data.size(); }
511 };
512 
513 /**
514  Templated version of SparseVectorMap where the data and key are the
515  same (actually more like a set than a map in this case). The type
516  must implement the less than operator. This is primarily intended
517  for use with native types.
518  */
519 template <typename keyT>
520 class SparseVectorMap<keyT, keyT>
521 {
522 private:
523  friend class SST::Core::Serialization::serialize<SparseVectorMap<keyT, keyT>>;
524 
525  /**
526  Finds the insertion point for new data
527 
528  @param id ID of the data that needs to be inserted.
529 
530  @return Index where new data should be inserted. If key is
531  already in the map, it will return -1.
532  */
533  std::vector<keyT> data;
534  int binary_search_insert(keyT id) const
535  {
536  // For insert, we've found the right place when id < n && id >
537  // n-1. We then insert at n.
538 
539  int size = data.size();
540 
541  // Check to see if it goes top or bottom
542  if ( size == 0 ) return 0;
543  if ( id < data[0] ) return 0;
544  if ( id > data[size - 1] ) return size;
545 
546  int bottom = 0;
547  int top = size - 1;
548  int middle;
549 
550  while ( bottom <= top ) {
551  middle = bottom + (top - bottom) / 2;
552  if ( id == data[middle] ) return -1; // Already in map
553  if ( id < data[middle] ) {
554  // May be the right place, need to see if id is greater
555  // than the one before the current middle. If so, then we
556  // have the right place.
557  if ( id > data[middle - 1] )
558  return middle;
559  else {
560  top = middle - 1;
561  }
562  }
563  else {
564  bottom = middle + 1;
565  }
566  }
567  /* Shouldn't be reached */
568  return -1;
569  }
570 
571  /**
572  Finds the index where the data associated with the given key is
573  found in the vector
574 
575  @param id ID of the data that needs to be found.
576 
577  @return Index where data for the provided ID is found. It
578  returns -1 if the key is not found in the data vector.
579  */
580  int binary_search_find(keyT id) const
581  {
582  int bottom = 0;
583  int top = data.size() - 1;
584  int middle;
585 
586  if ( data.size() == 0 ) return -1;
587  while ( bottom <= top ) {
588  middle = bottom + (top - bottom) / 2;
589  if ( id == data[middle] )
590  return middle;
591  else if ( id < data[middle] )
592  top = middle - 1;
593  else
594  bottom = middle + 1;
595  }
596  return -1;
597  }
598 
599  friend class ConfigGraph;
600 
601 public:
602  /**
603  Default constructor for SparseVectorMap
604  */
606 
607  /**
608  Constructor that allows you to pass an already filled in array
609  with data. The data in the passed in vector will be swapped
610  into the data vector of the SparseVectorMap and the passed in
611  vector will be empty.
612 
613  @param new_data Vector of data to swap into the SparseVectorMap
614  data
615 
616  @param sorted Specifies whether the vector is already sorted in
617  ascending order. If not, it will be sorted after swapping the
618  data in.
619  */
620  SparseVectorMap(std::vector<keyT>& new_data, bool sorted = false)
621  {
622  data.swap(new_data);
623  if ( !sorted ) {
624  std::sort(data.begin(), data.end, [](const keyT& lhs, const keyT& rhs) -> bool { return lhs < rhs; });
625  }
626  }
627 
628  typedef typename std::vector<keyT>::iterator iterator;
629  typedef typename std::vector<keyT>::const_iterator const_iterator;
630 
631  /**
632  Insert new value into SparseVectorMap. The inserted class must
633  have a key() function with return type keyT.
634 
635  @param val value to add to SparseVectorMap
636 
637  @return reference to the inserted item, or to the existing item
638  if it was already present in the map.
639 
640  */
641  keyT& insert(const keyT& val)
642  {
643  int index = binary_search_insert(val);
644  if ( index == -1 ) return data[binary_search_find(val)]; // already in the map
645  iterator it = data.begin();
646  it += index;
647  data.insert(it, val);
648  return data[index];
649  }
650 
651  /**
652  Returns the begin iterator to the underlying vector.
653 
654  @return begin iterator to data vector
655  */
656  iterator begin() { return data.begin(); }
657 
658  /**
659  Returns the end iterator to the underlying vector.
660 
661  @return end iterator to data vector
662  */
663  iterator end() { return data.end(); }
664 
665  /**
666  Returns the const begin iterator to the underlying vector.
667 
668  @return const begin iterator to data vector
669  */
670  const_iterator begin() const { return data.begin(); }
671 
672  /**
673  Returns the const end iterator to the underlying vector.
674 
675  @return const end iterator to data vector
676  */
677  const_iterator end() const { return data.end(); }
678 
679  /**
680  Checks if the provided id is found in the SparseVectorMap
681 
682  @param id id to check for
683 
684  @return true if id is found, false otherwise
685  */
686  bool contains(keyT id)
687  {
688  if ( binary_search_find(id) == -1 ) return false;
689  return true;
690  }
691 
692  /**
693  Operator returns a reference to data with the specified id.
694  Value can be modified. This will only return references to
695  existing values, you must use insert() for new values.
696 
697  @param id id of the value to return (value returned by key())
698 
699  @return reference to the requested item.
700 
701  */
702  keyT& operator[](keyT id)
703  {
704  int index = binary_search_find(id);
705  if ( index == -1 ) {
706  // Need to error out
707  }
708  return data[index];
709  }
710 
711  /**
712  Operator returns a const reference to data with the specified
713  id. Value cannot be modified. This will only return
714  references to existing values, you must use insert() for new
715  values.
716 
717  @param id id of the value to return (value returned by key())
718 
719  @return const reference to the requested item.
720 
721  */
722  const keyT& operator[](keyT id) const
723  {
724  int index = binary_search_find(id);
725  if ( index == -1 ) {
726  // Need to error out
727  }
728  return data[index];
729  }
730 
731  /**
732  Clears the contents of the SparseVectorMap
733  */
734  void clear() { data.clear(); }
735 
736  /**
737  Returns the number of items in the SparseVectorMap
738 
739  @return number of items
740  */
741  size_t size() { return data.size(); }
742 };
743 
744 } // namespace SST
745 
746 namespace SST {
747 namespace Core {
748 namespace Serialization {
749 
750 template <typename keyT, typename classT>
751 class serialize<SST::SparseVectorMap<keyT, classT>>
752 {
753 public:
754  void operator()(SST::SparseVectorMap<keyT, classT>& v, SST::Core::Serialization::serializer& ser) { ser& v.data; }
755 };
756 } // namespace Serialization
757 } // namespace Core
758 } // namespace SST
759 
760 #endif // SST_CORE_SPARSEVECTORMAP_H
const classT * operator[](keyT id) const
Operator returns a const reference to data with the specified id.
Definition: sparseVectorMap.h:491
iterator end()
Returns the end iterator to the underlying vector.
Definition: sparseVectorMap.h:663
This class is basically a wrapper for objects to declare the order in which their members should be s...
Definition: serializer.h:34
const_iterator begin() const
Returns the const begin iterator to the underlying vector.
Definition: sparseVectorMap.h:195
iterator end()
Returns the end iterator to the underlying vector.
Definition: sparseVectorMap.h:432
const_iterator end() const
Returns the const end iterator to the underlying vector.
Definition: sparseVectorMap.h:446
classT & operator[](keyT id)
Operator returns a reference to data with the specified id.
Definition: sparseVectorMap.h:227
bool contains(keyT id)
Checks if the provided id is found in the SparseVectorMap.
Definition: sparseVectorMap.h:686
classT & insert(const classT &val)
Insert new value into SparseVectorMap.
Definition: sparseVectorMap.h:166
classT * operator[](keyT id)
Operator returns a reference to data with the specified id.
Definition: sparseVectorMap.h:471
A Configuration Graph A graph representing Components and Links.
Definition: configGraph.h:375
iterator end()
Returns the end iterator to the underlying vector.
Definition: sparseVectorMap.h:188
const_iterator end() const
Returns the const end iterator to the underlying vector.
Definition: sparseVectorMap.h:677
iterator begin()
Returns the begin iterator to the underlying vector.
Definition: sparseVectorMap.h:181
const keyT & operator[](keyT id) const
Operator returns a const reference to data with the specified id.
Definition: sparseVectorMap.h:722
size_t size()
Returns the number of items in the SparseVectorMap.
Definition: sparseVectorMap.h:510
size_t size()
Returns the number of items in the SparseVectorMap.
Definition: sparseVectorMap.h:266
Base serialize class.
Definition: serialize.h:31
const classT & operator[](keyT id) const
Operator returns a const reference to data with the specified id.
Definition: sparseVectorMap.h:247
keyT & operator[](keyT id)
Operator returns a reference to data with the specified id.
Definition: sparseVectorMap.h:702
SparseVectorMap(std::vector< keyT > &new_data, bool sorted=false)
Constructor that allows you to pass an already filled in array with data.
Definition: sparseVectorMap.h:620
iterator begin()
Returns the begin iterator to the underlying vector.
Definition: sparseVectorMap.h:425
const_iterator end() const
Returns the const end iterator to the underlying vector.
Definition: sparseVectorMap.h:202
SparseVectorMap(std::vector< classT * > &new_data, bool sorted=false)
Constructor that allows you to pass an already filled in array with data.
Definition: sparseVectorMap.h:387
SparseVectorMap(std::vector< classT > &new_data, bool sorted=false)
Constructor that allows you to pass an already filled in array with data.
Definition: sparseVectorMap.h:143
iterator begin()
Returns the begin iterator to the underlying vector.
Definition: sparseVectorMap.h:656
bool contains(keyT id) const
Checks if the provided id is found in the SparseVectorMap.
Definition: sparseVectorMap.h:455
keyT & insert(const keyT &val)
Insert new value into SparseVectorMap.
Definition: sparseVectorMap.h:641
size_t size()
Returns the number of items in the SparseVectorMap.
Definition: sparseVectorMap.h:741
SparseVectorMap()
Default constructor for SparseVectorMap.
Definition: sparseVectorMap.h:128
bool contains(keyT id) const
Checks if the provided id is found in the SparseVectorMap.
Definition: sparseVectorMap.h:211
SparseVectorMap()
Default constructor for SparseVectorMap.
Definition: sparseVectorMap.h:605
const_iterator begin() const
Returns the const begin iterator to the underlying vector.
Definition: sparseVectorMap.h:439
Class that stores data in a vector, but can access the data similar to a map.
Definition: sparseVectorMap.h:43
const_iterator begin() const
Returns the const begin iterator to the underlying vector.
Definition: sparseVectorMap.h:670
void clear()
Clears the contents of the SparseVectorMap.
Definition: sparseVectorMap.h:734
SparseVectorMap()
Default constructor for SparseVectorMap.
Definition: sparseVectorMap.h:372
void clear()
Clears the contents of the SparseVectorMap.
Definition: sparseVectorMap.h:259
classT * insert(classT *val)
Insert new value into SparseVectorMap.
Definition: sparseVectorMap.h:410
void clear()
Clears the contents of the SparseVectorMap.
Definition: sparseVectorMap.h:503