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