Teuchos - Trilinos Tools Package  Version of the Day
Teuchos_StringIndexedOrderedValueObjectContainer.hpp
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"
48 #include "Teuchos_FilteredIterator.hpp"
49 
50 
51 namespace Teuchos {
52 
53 
54 
58 public:
59 
61  typedef Teuchos_Ordinal Ordinal;
62 
64  static Ordinal getInvalidOrdinal() { return -1; }
65 
68 
69 public: // Public members (but only for unit testing purposes!)
70 
74  class OrdinalIndex {
75  public:
83  {}
85  OrdinalIndex(const Ordinal idx_in)
86  : idx(idx_in)
87  {}
88  };
89 
103  template<class ObjType>
105  public:
107  const std::string &first;
109  ObjType second;
111  std::string key;
113  KeyObjectPair() : first(key), second(ObjType()), key(""), isActive_(true) {}
115  KeyObjectPair(const std::string &key_in, const ObjType &obj_in, bool isActive_in = true)
116  : first(key), second(obj_in), key(key_in), isActive_(isActive_in) {}
119  : first(key), second(kop.second), key(kop.key), isActive_(kop.isActive_) {}
122  {
123  second = kop.second;
124  key = kop.key;
125  isActive_ = kop.isActive_;
126  return *this;
127  }
130  { return KeyObjectPair("", ObjType(), false); }
132  bool isActive() const { return isActive_; }
133  private:
134  bool isActive_;
135  };
136 
138  template<class ObjType>
139  class SelectActive {
140  public:
141  bool operator()(const KeyObjectPair<ObjType> &key_and_obj) const
142  { return key_and_obj.isActive(); }
143  };
144 
147  {public:InvalidOrdinalIndexError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
148 
151  {public:InvalidKeyError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
152 
153 };
154 
155 
177 template<class ObjType>
180 {
181 private:
182 
186  typedef std::deque<key_and_obj_t> key_and_obj_array_t; // See notes below!
188  typedef std::map<std::string, OrdinalIndex> key_to_idx_map_t;
189 
190 public:
191 
194 
197 
201 
205 
207 
210 
213 
215  Ordinal numObjects() const;
216 
218  Ordinal numStorage() const;
219 
221 
224 
233  Ordinal setObj(const std::string &key, const ObjType &obj);
234 
239  inline Ordinal getObjOrdinalIndex(const std::string &key) const;
240 
244  inline Ptr<ObjType> getNonconstObjPtr(const Ordinal &idx);
245 
249  inline Ptr<const ObjType> getObjPtr(const Ordinal &idx) const;
250 
254  inline Ptr<ObjType> getNonconstObjPtr(const std::string &key);
255 
259  inline Ptr<const ObjType> getObjPtr(const std::string &key) const;
260 
267  void removeObj(const Ordinal &idx);
268 
270  void removeObj(const std::string &key);
271 
273 
276 
278  inline Iterator nonconstBegin();
279 
281  inline Iterator nonconstEnd();
282 
284  inline ConstIterator begin() const;
285 
287  inline ConstIterator end() const;
288 
290 
291 private: // data members
292 
294  key_and_obj_array_t key_and_obj_array_;
296  key_to_idx_map_t key_to_idx_map_;
297 
298  // The above is a fairly simple data-structure.
299  //
300  // key_and_obj_array_: Array that stores the objects (and key names), by
301  // value, in the order they are inserted. Any removed objects will have the
302  // index valuie of getInvalidOrdinal(). The key strings are also storied
303  // with the objects so that a clean iterator can over the objects has access
304  // to both the key and the object value.
305  //
306  // key_to_idx_map_: Maps the unique string key to the unigue ordinal index
307  // for an object.
308  //
309  // NOTES:
310  //
311  // A) This data-structure stores the key names twice in order to allow for
312  // optimal iterator performance. The array key_and_obj_array_ allows fast
313  // ordered iterators through the data but in order to also provide the names
314  // in a fast manner, they have to be stored twice.
315  //
316  // B) Deleting objects is done by just removing an entry from
317  // key_to_idx_map_ but the corresponding entry in key_and_obj_array_ is just
318  // abandoned with the object value set to ObjType().
319 
320 private: // member functions
321 
323  void assertOrdinalIndex(const Ordinal idx) const;
324 
326  key_and_obj_t& getNonconstKeyAndObject(const Ordinal idx);
327 
329  const key_and_obj_t& getKeyAndObject(const Ordinal idx) const;
330 
332  void throwInvalidKeyError(const Ordinal idx, const std::string &key) const;
333 
335  Ordinal assertKeyGetOrdinal(const std::string &key) const;
336 
337 };
338 
339 
340 //
341 // StringIndexedOrderedValueObjectContainer: Inline Implementations
342 //
343 
344 
345 // Set, get, and remove functions
346 
347 
348 template<class ObjType>
349 inline
352 {
353  return ptrFromRef(getNonconstKeyAndObject(idx).second);
354 }
355 
356 
357 template<class ObjType>
358 inline
361 {
362  return ptrFromRef(getKeyAndObject(idx).second);
363 }
364 
365 
366 template<class ObjType>
367 inline
370 {
371  return getNonconstObjPtr(assertKeyGetOrdinal(key));
372 }
373 
374 
375 template<class ObjType>
376 inline
379 {
380  return getObjPtr(assertKeyGetOrdinal(key));
381 }
382 
383 
384 // Iterator access
385 
386 
387 template<class ObjType>
388 inline
391 {
392  return Iterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
393  key_and_obj_array_.end());
394 }
395 
396 
397 template<class ObjType>
398 inline
401 {
402  return Iterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
403  key_and_obj_array_.end());
404 }
405 
406 
407 template<class ObjType>
408 inline
411 {
412  return ConstIterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
413  key_and_obj_array_.end());
414 }
415 
416 
417 template<class ObjType>
418 inline
421 {
422  return ConstIterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
423  key_and_obj_array_.end());
424 }
425 
426 
427 //
428 // StringIndexedOrderedValueObjectContainer: Template Implementations
429 //
430 
431 
432 // Constructors/Destructors/Info
433 
434 
435 template<class ObjType>
437 {}
438 
439 
440 template<class ObjType>
443 {
444  return key_to_idx_map_.size();
445 }
446 
447 
448 template<class ObjType>
451 {
452  return key_and_obj_array_.size();
453 }
454 
455 
456 // Set, get, and remove functions
457 
458 
459 template<class ObjType>
460 inline
463 {
464  key_to_idx_map_t::const_iterator itr = key_to_idx_map_.find(key);
465  if (itr != key_to_idx_map_.end()) {
466  return itr->second.idx;
467  }
468  return getInvalidOrdinal();
469 }
470 
471 
472 template<class ObjType>
475  const ObjType &obj)
476 {
477  typename key_to_idx_map_t::iterator obj_idx_itr = key_to_idx_map_.find(key);
478  if (obj_idx_itr != key_to_idx_map_.end()) {
479  // Object with the given key already exists
480  const Ordinal obj_idx = obj_idx_itr->second.idx;
481  key_and_obj_array_[obj_idx].second = obj;
482  return obj_idx;
483  }
484  // Object with the given key does not already exist so create a new one.
485  key_and_obj_array_.push_back(key_and_obj_t(key, obj));
486  const Ordinal new_idx = key_and_obj_array_.size()-1;
487  key_to_idx_map_[key] = new_idx;
488  return new_idx;
489 }
490 
491 
492 template<class ObjType>
494 {
495  key_and_obj_t &key_and_obj = getNonconstKeyAndObject(idx);
496  key_to_idx_map_.erase(key_and_obj.first);
497  key_and_obj = key_and_obj_t::makeInvalid();
498 }
499 
500 
501 template<class ObjType>
503 {
504  typename key_to_idx_map_t::iterator itr = key_to_idx_map_.find(key);
505  if (itr == key_to_idx_map_.end()) {
506  throwInvalidKeyError(getInvalidOrdinal(), key);
507  }
508  const Ordinal idx = itr->second.idx;
509  key_to_idx_map_.erase(itr);
510  key_and_obj_array_[idx] = key_and_obj_t::makeInvalid();
511 }
512 
513 
514 // private
515 
516 
517 template<class ObjType>
519 {
520  TEUCHOS_TEST_FOR_EXCEPTION( !(0 <= idx && idx < numStorage()),
521  InvalidOrdinalIndexError,
522  "Error, the ordinal index " << idx << " is invalid"
523  << " because it falls outside of the range of valid objects"
524  << " [0,"<<numStorage()-1<<"]!");
525 }
526 
527 
528 template<class ObjType>
529 typename StringIndexedOrderedValueObjectContainer<ObjType>::key_and_obj_t&
530 StringIndexedOrderedValueObjectContainer<ObjType>::getNonconstKeyAndObject(const Ordinal idx)
531 {
532  assertOrdinalIndex(idx);
533  key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
534  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
535  InvalidOrdinalIndexError,
536  "Error, the ordinal index " << idx << " is invalid"
537  << " because the object has been deleted!");
538  return key_and_obj;
539 }
540 
541 
542 template<class ObjType>
543 const typename StringIndexedOrderedValueObjectContainer<ObjType>::key_and_obj_t&
544 StringIndexedOrderedValueObjectContainer<ObjType>::getKeyAndObject(const Ordinal idx) const
545 {
546  assertOrdinalIndex(idx);
547  const key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
548  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
549  InvalidOrdinalIndexError,
550  "Error, the ordinal index " << idx << " is invalid"
551  << " because the object has been deleted!");
552  return key_and_obj;
553 }
554 
555 
556 template<class ObjType>
557 void
558 StringIndexedOrderedValueObjectContainer<ObjType>::throwInvalidKeyError(
559  const Ordinal idx, const std::string &key) const
560 {
561  TEUCHOS_TEST_FOR_EXCEPTION( idx == getInvalidOrdinal(), InvalidKeyError,
562  "Error, the key '" << key << "' does not exist!");
563 }
564 
565 
566 template<class ObjType>
568 StringIndexedOrderedValueObjectContainer<ObjType>::assertKeyGetOrdinal(const std::string &key) const
569 {
570  const Ordinal idx = getObjOrdinalIndex(key);
571  throwInvalidKeyError(idx, key);
572  return idx;
573 }
574 
575 
576 } // end of Teuchos namespace
577 
578 /* Notes:
579  *
580  * This class may have a bit of a fragile implemenation. It uses std::deque
581  * instead of std::vector to hold the stored objects. This is so that once an
582  * object is added, it will keep the exact same address no matter how many
583  * other objects are added. This is not the case with std::vector because
584  * when the memory is resized it will copy the value objects making the old
585  * objects invalid. My guess with the std::deque class is that it would
586  * allocate and store the chunks such that once an objects was added to a
587  * chunk that it would not get reallocated and moved like in std::vector. I
588  * don't feel very good about relying on this behavior but my guess is that
589  * this will be pretty portable. If this turns out not to be portable, we can
590  * always just use RCP<ObjType> to store the object and that will guarantee
591  * that the object address will never be moved. Going with an RCP<ObjType>
592  * implementation would also allow the Ptr<ObjType> views to catch dangling
593  * references in a debug-mode build.
594  */
595 
596 
597 #endif // TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
598 
599 
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.
Ptr< const ObjType > getObjPtr(const Ordinal &idx) const
Get a const semi-persisting association with the stored object indexed by ordinal.
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.
StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal
Ordinal used for the index.
KeyObjectPair(const std::string &key_in, const ObjType &obj_in, bool isActive_in=true)
FilteredIterator< typename key_and_obj_array_t::const_iterator, SelectActive< ObjType > > ConstIterator
The const iterator type.
Templated array class derived from the STL std::vector.
Ordinal setObj(const std::string &key, const ObjType &obj)
Set (or reset) object by value and return its ordinal index.
The Teuchos namespace contains all of the classes, structs and enums used by Teuchos, as well as a number of utility routines.
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.
Simple wrapper class for raw pointers to single objects where no persisting relationship exists...