Teuchos Package Browser (Single Doxygen Collection)  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Teuchos_StringIndexedOrderedValueObjectContainer.hpp
Go to the documentation of this file.
1 // @HEADER
2 // *****************************************************************************
3 // Teuchos: Common Tools Package
4 //
5 // Copyright 2004 NTESS and the Teuchos contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
10 #ifndef TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
11 #define TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
12 
13 
14 #include "Teuchos_Array.hpp"
16 #include <deque>
17 #include <map>
18 #include <string>
19 
20 namespace Teuchos {
21 
22 
23 
27 public:
28 
31 
33  static Ordinal getInvalidOrdinal() { return -1; }
34 
37 
38 public: // Public members (but only for unit testing purposes!)
39 
43  class OrdinalIndex {
44  public:
52  {}
54  OrdinalIndex(const Ordinal idx_in)
55  : idx(idx_in)
56  {}
57  };
58 
72  template<class ObjType>
73  class KeyObjectPair {
74  public:
76  const std::string &first;
78  ObjType second;
80  std::string key;
82  KeyObjectPair() : first(key), second(ObjType()), key(""), isActive_(true) {}
84  template <typename U, typename = std::enable_if_t<std::is_convertible_v<U, ObjType>>>
85  KeyObjectPair(const std::string &key_in, U&& obj_in, bool isActive_in = true)
86  : first(key), second(std::forward<U>(obj_in)), key(key_in), isActive_(isActive_in) {}
89  : first(key), second(kop.second), key(kop.key), isActive_(kop.isActive_) {}
92  : first(key), second(std::move(kop.second)), key(std::move(kop.key)), isActive_(kop.isActive_) {}
95  {
96  second = kop.second;
97  key = kop.key;
98  isActive_ = kop.isActive_;
99  return *this;
100  }
103  { return KeyObjectPair("", ObjType(), false); }
105  bool isActive() const { return isActive_; }
106  private:
107  bool isActive_;
108  };
109 
111  template<class ObjType>
112  class SelectActive {
113  public:
114  bool operator()(const KeyObjectPair<ObjType> &key_and_obj) const
115  { return key_and_obj.isActive(); }
116  };
117 
120  {public:InvalidOrdinalIndexError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
121 
124  {public:InvalidKeyError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
125 
126 };
127 
128 
150 template<class ObjType>
153 {
154 private:
155 
159  typedef std::deque<key_and_obj_t> key_and_obj_array_t; // See notes below!
161  typedef std::map<std::string, OrdinalIndex> key_to_idx_map_t;
162 
163 public:
164 
167 
170 
174 
178 
180 
183 
186 
188  Ordinal numObjects() const;
189 
191  Ordinal numStorage() const;
192 
194 
197 
206  template <typename U, typename = std::enable_if_t<std::is_convertible_v<U, ObjType>>>
207  Ordinal setObj(const std::string &key, U&& obj);
208 
213  inline Ordinal getObjOrdinalIndex(const std::string &key) const;
214 
218  inline Ptr<ObjType> getNonconstObjPtr(const Ordinal &idx);
219 
223  inline Ptr<const ObjType> getObjPtr(const Ordinal &idx) const;
224 
228  inline Ptr<ObjType> getNonconstObjPtr(const std::string &key);
229 
233  inline Ptr<const ObjType> getObjPtr(const std::string &key) const;
234 
241  void removeObj(const Ordinal &idx);
242 
244  void removeObj(const std::string &key);
245 
247 
250 
252  inline Iterator nonconstBegin();
253 
255  inline Iterator nonconstEnd();
256 
258  inline ConstIterator begin() const;
259 
261  inline ConstIterator end() const;
262 
264 
265 private: // data members
266 
271 
272  // The above is a fairly simple data-structure.
273  //
274  // key_and_obj_array_: Array that stores the objects (and key names), by
275  // value, in the order they are inserted. Any removed objects will have the
276  // index valuie of getInvalidOrdinal(). The key strings are also storied
277  // with the objects so that a clean iterator can over the objects has access
278  // to both the key and the object value.
279  //
280  // key_to_idx_map_: Maps the unique string key to the unigue ordinal index
281  // for an object.
282  //
283  // NOTES:
284  //
285  // A) This data-structure stores the key names twice in order to allow for
286  // optimal iterator performance. The array key_and_obj_array_ allows fast
287  // ordered iterators through the data but in order to also provide the names
288  // in a fast manner, they have to be stored twice.
289  //
290  // B) Deleting objects is done by just removing an entry from
291  // key_to_idx_map_ but the corresponding entry in key_and_obj_array_ is just
292  // abandoned with the object value set to ObjType().
293 
294 private: // member functions
295 
297  void assertOrdinalIndex(const Ordinal idx) const;
298 
301 
303  const key_and_obj_t& getKeyAndObject(const Ordinal idx) const;
304 
306  void throwInvalidKeyError(const Ordinal idx, const std::string &key) const;
307 
309  Ordinal assertKeyGetOrdinal(const std::string &key) const;
310 
311 };
312 
313 
314 //
315 // StringIndexedOrderedValueObjectContainer: Inline Implementations
316 //
317 
318 
319 // Set, get, and remove functions
320 
321 
322 template<class ObjType>
323 inline
326 {
327  return ptrFromRef(getNonconstKeyAndObject(idx).second);
328 }
329 
330 
331 template<class ObjType>
332 inline
335 {
336  return ptrFromRef(getKeyAndObject(idx).second);
337 }
338 
339 
340 template<class ObjType>
341 inline
344 {
345  return getNonconstObjPtr(assertKeyGetOrdinal(key));
346 }
347 
348 
349 template<class ObjType>
350 inline
353 {
354  return getObjPtr(assertKeyGetOrdinal(key));
355 }
356 
357 
358 // Iterator access
359 
360 
361 template<class ObjType>
362 inline
365 {
366  return Iterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
367  key_and_obj_array_.end());
368 }
369 
370 
371 template<class ObjType>
372 inline
375 {
376  return Iterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
377  key_and_obj_array_.end());
378 }
379 
380 
381 template<class ObjType>
382 inline
385 {
386  return ConstIterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
387  key_and_obj_array_.end());
388 }
389 
390 
391 template<class ObjType>
392 inline
395 {
396  return ConstIterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
397  key_and_obj_array_.end());
398 }
399 
400 
401 //
402 // StringIndexedOrderedValueObjectContainer: Template Implementations
403 //
404 
405 
406 // Constructors/Destructors/Info
407 
408 
409 template<class ObjType>
411 {}
412 
413 
414 template<class ObjType>
417 {
418  return key_to_idx_map_.size();
419 }
420 
421 
422 template<class ObjType>
425 {
426  return key_and_obj_array_.size();
427 }
428 
429 
430 // Set, get, and remove functions
431 
432 
433 template<class ObjType>
434 inline
437 {
438  key_to_idx_map_t::const_iterator itr = key_to_idx_map_.find(key);
439  if (itr != key_to_idx_map_.end()) {
440  return itr->second.idx;
441  }
442  return getInvalidOrdinal();
443 }
444 
445 
446 template <typename ObjType>
447 template <typename U, typename>
450  U&& obj)
451 {
452  typename key_to_idx_map_t::iterator obj_idx_itr = key_to_idx_map_.find(key);
453  if (obj_idx_itr != key_to_idx_map_.end()) {
454  // Object with the given key already exists
455  const Ordinal obj_idx = obj_idx_itr->second.idx;
456  key_and_obj_array_[obj_idx].second = std::forward<U>(obj);
457  return obj_idx;
458  }
459  // Object with the given key does not already exist so create a new one.
460  key_and_obj_array_.emplace_back(key, std::forward<U>(obj));
461  const Ordinal new_idx = key_and_obj_array_.size()-1;
462  key_to_idx_map_[key] = new_idx;
463  return new_idx;
464 }
465 
466 
467 template<class ObjType>
469 {
470  key_and_obj_t &key_and_obj = getNonconstKeyAndObject(idx);
471  key_to_idx_map_.erase(key_and_obj.first);
472  key_and_obj = key_and_obj_t::makeInvalid();
473 }
474 
475 
476 template<class ObjType>
478 {
479  typename key_to_idx_map_t::iterator itr = key_to_idx_map_.find(key);
480  if (itr == key_to_idx_map_.end()) {
481  throwInvalidKeyError(getInvalidOrdinal(), key);
482  }
483  const Ordinal idx = itr->second.idx;
484  key_to_idx_map_.erase(itr);
485  key_and_obj_array_[idx] = key_and_obj_t::makeInvalid();
486 }
487 
488 
489 // private
490 
491 
492 template<class ObjType>
494 {
495  TEUCHOS_TEST_FOR_EXCEPTION( !(0 <= idx && idx < numStorage()),
497  "Error, the ordinal index " << idx << " is invalid"
498  << " because it falls outside of the range of valid objects"
499  << " [0,"<<numStorage()-1<<"]!");
500 }
501 
502 
503 template<class ObjType>
506 {
507  assertOrdinalIndex(idx);
508  key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
509  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
511  "Error, the ordinal index " << idx << " is invalid"
512  << " because the object has been deleted!");
513  return key_and_obj;
514 }
515 
516 
517 template<class ObjType>
520 {
521  assertOrdinalIndex(idx);
522  const key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
523  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
525  "Error, the ordinal index " << idx << " is invalid"
526  << " because the object has been deleted!");
527  return key_and_obj;
528 }
529 
530 
531 template<class ObjType>
532 void
534  const Ordinal idx, const std::string &key) const
535 {
536  TEUCHOS_TEST_FOR_EXCEPTION( idx == getInvalidOrdinal(), InvalidKeyError,
537  "Error, the key '" << key << "' does not exist!");
538 }
539 
540 
541 template<class ObjType>
544 {
545  const Ordinal idx = getObjOrdinalIndex(key);
546  throwInvalidKeyError(idx, key);
547  return idx;
548 }
549 
550 
551 } // end of Teuchos namespace
552 
553 /* Notes:
554  *
555  * This class may have a bit of a fragile implemenation. It uses std::deque
556  * instead of std::vector to hold the stored objects. This is so that once an
557  * object is added, it will keep the exact same address no matter how many
558  * other objects are added. This is not the case with std::vector because
559  * when the memory is resized it will copy the value objects making the old
560  * objects invalid. My guess with the std::deque class is that it would
561  * allocate and store the chunks such that once an objects was added to a
562  * chunk that it would not get reallocated and moved like in std::vector. I
563  * don't feel very good about relying on this behavior but my guess is that
564  * this will be pretty portable. If this turns out not to be portable, we can
565  * always just use RCP<ObjType> to store the object and that will guarantee
566  * that the object address will never be moved. Going with an RCP<ObjType>
567  * implementation would also allow the Ptr<ObjType> views to catch dangling
568  * references in a debug-mode build.
569  */
570 
571 
572 #endif // TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
573 
574 
C++ Standard Library compatable filtered iterator.
Ordinal getObjOrdinalIndex(const std::string &key) const
Get the ordinal index given the string key.
FilteredIterator< typename key_and_obj_array_t::iterator, SelectActive< ObjType > > Iterator
The non-const iterator type.
key_and_obj_array_t key_and_obj_array_
Stories objects contiguously along with key strings.
String indexed ordered value-type object container class.
A safe ordinal index type that default initializes to a special value.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
Ordinal setObj(const std::string &key, U &&obj)
Set (or reset) object by value and return its ordinal index.
StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal
Ordinal used for the index.
TEUCHOS_ORDINAL_TYPE Teuchos_Ordinal
ExceptionBase(const std::string &what_arg)
FilteredIterator< typename key_and_obj_array_t::const_iterator, SelectActive< ObjType > > ConstIterator
The const iterator type.
Ptr< const ObjType > getObjPtr(const Ordinal &idx) const
Get a const semi-persisting association with the stored object indexed by ordinal.
Templated array class derived from the STL std::vector.
key_to_idx_map_t key_to_idx_map_
Provides lookups of key -&gt; ordinal index into above array.
void removeObj(const Ordinal &idx)
Remove an object given its ordinal index.
Base exception class for Teuchos.
Ptr< ObjType > getNonconstObjPtr(const Ordinal &idx)
Get a nonconst semi-persisting association with the stored object indexed by ordinal.
void throwInvalidKeyError(const Ordinal idx, const std::string &key) const
Simple wrapper class for raw pointers to single objects where no persisting relationship exists...