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 //
4 // Teuchos: Common Tools Package
5 // Copyright (2004) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38 //
39 // ***********************************************************************
40 // @HEADER
41 
42 
43 #ifndef TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
44 #define TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
45 
46 
47 #include "Teuchos_Array.hpp"
49 #include <deque>
50 #include <map>
51 #include <string>
52 
53 namespace Teuchos {
54 
55 
56 
60 public:
61 
64 
66  static Ordinal getInvalidOrdinal() { return -1; }
67 
70 
71 public: // Public members (but only for unit testing purposes!)
72 
76  class OrdinalIndex {
77  public:
85  {}
87  OrdinalIndex(const Ordinal idx_in)
88  : idx(idx_in)
89  {}
90  };
91 
105  template<class ObjType>
107  public:
109  const std::string &first;
111  ObjType second;
113  std::string key;
115  KeyObjectPair() : first(key), second(ObjType()), key(""), isActive_(true) {}
117  template <typename U, typename = std::enable_if_t<std::is_convertible_v<U, ObjType>>>
118  KeyObjectPair(const std::string &key_in, U&& obj_in, bool isActive_in = true)
119  : first(key), second(std::forward<U>(obj_in)), key(key_in), isActive_(isActive_in) {}
122  : first(key), second(kop.second), key(kop.key), isActive_(kop.isActive_) {}
125  : first(key), second(std::move(kop.second)), key(std::move(kop.key)), isActive_(kop.isActive_) {}
128  {
129  second = kop.second;
130  key = kop.key;
131  isActive_ = kop.isActive_;
132  return *this;
133  }
136  { return KeyObjectPair("", ObjType(), false); }
138  bool isActive() const { return isActive_; }
139  private:
140  bool isActive_;
141  };
142 
144  template<class ObjType>
145  class SelectActive {
146  public:
147  bool operator()(const KeyObjectPair<ObjType> &key_and_obj) const
148  { return key_and_obj.isActive(); }
149  };
150 
153  {public:InvalidOrdinalIndexError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
154 
157  {public:InvalidKeyError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
158 
159 };
160 
161 
183 template<class ObjType>
186 {
187 private:
188 
192  typedef std::deque<key_and_obj_t> key_and_obj_array_t; // See notes below!
194  typedef std::map<std::string, OrdinalIndex> key_to_idx_map_t;
195 
196 public:
197 
200 
203 
207 
211 
213 
216 
219 
221  Ordinal numObjects() const;
222 
224  Ordinal numStorage() const;
225 
227 
230 
239  template <typename U, typename = std::enable_if_t<std::is_convertible_v<U, ObjType>>>
240  Ordinal setObj(const std::string &key, U&& obj);
241 
246  inline Ordinal getObjOrdinalIndex(const std::string &key) const;
247 
251  inline Ptr<ObjType> getNonconstObjPtr(const Ordinal &idx);
252 
256  inline Ptr<const ObjType> getObjPtr(const Ordinal &idx) const;
257 
261  inline Ptr<ObjType> getNonconstObjPtr(const std::string &key);
262 
266  inline Ptr<const ObjType> getObjPtr(const std::string &key) const;
267 
274  void removeObj(const Ordinal &idx);
275 
277  void removeObj(const std::string &key);
278 
280 
283 
285  inline Iterator nonconstBegin();
286 
288  inline Iterator nonconstEnd();
289 
291  inline ConstIterator begin() const;
292 
294  inline ConstIterator end() const;
295 
297 
298 private: // data members
299 
304 
305  // The above is a fairly simple data-structure.
306  //
307  // key_and_obj_array_: Array that stores the objects (and key names), by
308  // value, in the order they are inserted. Any removed objects will have the
309  // index valuie of getInvalidOrdinal(). The key strings are also storied
310  // with the objects so that a clean iterator can over the objects has access
311  // to both the key and the object value.
312  //
313  // key_to_idx_map_: Maps the unique string key to the unigue ordinal index
314  // for an object.
315  //
316  // NOTES:
317  //
318  // A) This data-structure stores the key names twice in order to allow for
319  // optimal iterator performance. The array key_and_obj_array_ allows fast
320  // ordered iterators through the data but in order to also provide the names
321  // in a fast manner, they have to be stored twice.
322  //
323  // B) Deleting objects is done by just removing an entry from
324  // key_to_idx_map_ but the corresponding entry in key_and_obj_array_ is just
325  // abandoned with the object value set to ObjType().
326 
327 private: // member functions
328 
330  void assertOrdinalIndex(const Ordinal idx) const;
331 
334 
336  const key_and_obj_t& getKeyAndObject(const Ordinal idx) const;
337 
339  void throwInvalidKeyError(const Ordinal idx, const std::string &key) const;
340 
342  Ordinal assertKeyGetOrdinal(const std::string &key) const;
343 
344 };
345 
346 
347 //
348 // StringIndexedOrderedValueObjectContainer: Inline Implementations
349 //
350 
351 
352 // Set, get, and remove functions
353 
354 
355 template<class ObjType>
356 inline
359 {
360  return ptrFromRef(getNonconstKeyAndObject(idx).second);
361 }
362 
363 
364 template<class ObjType>
365 inline
368 {
369  return ptrFromRef(getKeyAndObject(idx).second);
370 }
371 
372 
373 template<class ObjType>
374 inline
377 {
378  return getNonconstObjPtr(assertKeyGetOrdinal(key));
379 }
380 
381 
382 template<class ObjType>
383 inline
386 {
387  return getObjPtr(assertKeyGetOrdinal(key));
388 }
389 
390 
391 // Iterator access
392 
393 
394 template<class ObjType>
395 inline
398 {
399  return Iterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
400  key_and_obj_array_.end());
401 }
402 
403 
404 template<class ObjType>
405 inline
408 {
409  return Iterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
410  key_and_obj_array_.end());
411 }
412 
413 
414 template<class ObjType>
415 inline
418 {
419  return ConstIterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
420  key_and_obj_array_.end());
421 }
422 
423 
424 template<class ObjType>
425 inline
428 {
429  return ConstIterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
430  key_and_obj_array_.end());
431 }
432 
433 
434 //
435 // StringIndexedOrderedValueObjectContainer: Template Implementations
436 //
437 
438 
439 // Constructors/Destructors/Info
440 
441 
442 template<class ObjType>
444 {}
445 
446 
447 template<class ObjType>
450 {
451  return key_to_idx_map_.size();
452 }
453 
454 
455 template<class ObjType>
458 {
459  return key_and_obj_array_.size();
460 }
461 
462 
463 // Set, get, and remove functions
464 
465 
466 template<class ObjType>
467 inline
470 {
471  key_to_idx_map_t::const_iterator itr = key_to_idx_map_.find(key);
472  if (itr != key_to_idx_map_.end()) {
473  return itr->second.idx;
474  }
475  return getInvalidOrdinal();
476 }
477 
478 
479 template <typename ObjType>
480 template <typename U, typename>
483  U&& obj)
484 {
485  typename key_to_idx_map_t::iterator obj_idx_itr = key_to_idx_map_.find(key);
486  if (obj_idx_itr != key_to_idx_map_.end()) {
487  // Object with the given key already exists
488  const Ordinal obj_idx = obj_idx_itr->second.idx;
489  key_and_obj_array_[obj_idx].second = std::forward<U>(obj);
490  return obj_idx;
491  }
492  // Object with the given key does not already exist so create a new one.
493  key_and_obj_array_.emplace_back(key, std::forward<U>(obj));
494  const Ordinal new_idx = key_and_obj_array_.size()-1;
495  key_to_idx_map_[key] = new_idx;
496  return new_idx;
497 }
498 
499 
500 template<class ObjType>
502 {
503  key_and_obj_t &key_and_obj = getNonconstKeyAndObject(idx);
504  key_to_idx_map_.erase(key_and_obj.first);
505  key_and_obj = key_and_obj_t::makeInvalid();
506 }
507 
508 
509 template<class ObjType>
511 {
512  typename key_to_idx_map_t::iterator itr = key_to_idx_map_.find(key);
513  if (itr == key_to_idx_map_.end()) {
514  throwInvalidKeyError(getInvalidOrdinal(), key);
515  }
516  const Ordinal idx = itr->second.idx;
517  key_to_idx_map_.erase(itr);
518  key_and_obj_array_[idx] = key_and_obj_t::makeInvalid();
519 }
520 
521 
522 // private
523 
524 
525 template<class ObjType>
527 {
528  TEUCHOS_TEST_FOR_EXCEPTION( !(0 <= idx && idx < numStorage()),
530  "Error, the ordinal index " << idx << " is invalid"
531  << " because it falls outside of the range of valid objects"
532  << " [0,"<<numStorage()-1<<"]!");
533 }
534 
535 
536 template<class ObjType>
539 {
540  assertOrdinalIndex(idx);
541  key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
542  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
544  "Error, the ordinal index " << idx << " is invalid"
545  << " because the object has been deleted!");
546  return key_and_obj;
547 }
548 
549 
550 template<class ObjType>
553 {
554  assertOrdinalIndex(idx);
555  const key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
556  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
558  "Error, the ordinal index " << idx << " is invalid"
559  << " because the object has been deleted!");
560  return key_and_obj;
561 }
562 
563 
564 template<class ObjType>
565 void
567  const Ordinal idx, const std::string &key) const
568 {
569  TEUCHOS_TEST_FOR_EXCEPTION( idx == getInvalidOrdinal(), InvalidKeyError,
570  "Error, the key '" << key << "' does not exist!");
571 }
572 
573 
574 template<class ObjType>
577 {
578  const Ordinal idx = getObjOrdinalIndex(key);
579  throwInvalidKeyError(idx, key);
580  return idx;
581 }
582 
583 
584 } // end of Teuchos namespace
585 
586 /* Notes:
587  *
588  * This class may have a bit of a fragile implemenation. It uses std::deque
589  * instead of std::vector to hold the stored objects. This is so that once an
590  * object is added, it will keep the exact same address no matter how many
591  * other objects are added. This is not the case with std::vector because
592  * when the memory is resized it will copy the value objects making the old
593  * objects invalid. My guess with the std::deque class is that it would
594  * allocate and store the chunks such that once an objects was added to a
595  * chunk that it would not get reallocated and moved like in std::vector. I
596  * don't feel very good about relying on this behavior but my guess is that
597  * this will be pretty portable. If this turns out not to be portable, we can
598  * always just use RCP<ObjType> to store the object and that will guarantee
599  * that the object address will never be moved. Going with an RCP<ObjType>
600  * implementation would also allow the Ptr<ObjType> views to catch dangling
601  * references in a debug-mode build.
602  */
603 
604 
605 #endif // TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
606 
607 
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...