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  KeyObjectPair(const std::string &key_in, const ObjType &obj_in, bool isActive_in = true)
118  : first(key), second(obj_in), key(key_in), isActive_(isActive_in) {}
121  : first(key), second(kop.second), key(kop.key), isActive_(kop.isActive_) {}
124  {
125  second = kop.second;
126  key = kop.key;
127  isActive_ = kop.isActive_;
128  return *this;
129  }
132  { return KeyObjectPair("", ObjType(), false); }
134  bool isActive() const { return isActive_; }
135  private:
136  bool isActive_;
137  };
138 
140  template<class ObjType>
141  class SelectActive {
142  public:
143  bool operator()(const KeyObjectPair<ObjType> &key_and_obj) const
144  { return key_and_obj.isActive(); }
145  };
146 
149  {public:InvalidOrdinalIndexError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
150 
153  {public:InvalidKeyError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
154 
155 };
156 
157 
179 template<class ObjType>
182 {
183 private:
184 
188  typedef std::deque<key_and_obj_t> key_and_obj_array_t; // See notes below!
190  typedef std::map<std::string, OrdinalIndex> key_to_idx_map_t;
191 
192 public:
193 
196 
199 
203 
207 
209 
212 
215 
217  Ordinal numObjects() const;
218 
220  Ordinal numStorage() const;
221 
223 
226 
235  Ordinal setObj(const std::string &key, const ObjType &obj);
236 
241  inline Ordinal getObjOrdinalIndex(const std::string &key) const;
242 
246  inline Ptr<ObjType> getNonconstObjPtr(const Ordinal &idx);
247 
251  inline Ptr<const ObjType> getObjPtr(const Ordinal &idx) const;
252 
256  inline Ptr<ObjType> getNonconstObjPtr(const std::string &key);
257 
261  inline Ptr<const ObjType> getObjPtr(const std::string &key) const;
262 
269  void removeObj(const Ordinal &idx);
270 
272  void removeObj(const std::string &key);
273 
275 
278 
280  inline Iterator nonconstBegin();
281 
283  inline Iterator nonconstEnd();
284 
286  inline ConstIterator begin() const;
287 
289  inline ConstIterator end() const;
290 
292 
293 private: // data members
294 
299 
300  // The above is a fairly simple data-structure.
301  //
302  // key_and_obj_array_: Array that stores the objects (and key names), by
303  // value, in the order they are inserted. Any removed objects will have the
304  // index valuie of getInvalidOrdinal(). The key strings are also storied
305  // with the objects so that a clean iterator can over the objects has access
306  // to both the key and the object value.
307  //
308  // key_to_idx_map_: Maps the unique string key to the unigue ordinal index
309  // for an object.
310  //
311  // NOTES:
312  //
313  // A) This data-structure stores the key names twice in order to allow for
314  // optimal iterator performance. The array key_and_obj_array_ allows fast
315  // ordered iterators through the data but in order to also provide the names
316  // in a fast manner, they have to be stored twice.
317  //
318  // B) Deleting objects is done by just removing an entry from
319  // key_to_idx_map_ but the corresponding entry in key_and_obj_array_ is just
320  // abandoned with the object value set to ObjType().
321 
322 private: // member functions
323 
325  void assertOrdinalIndex(const Ordinal idx) const;
326 
329 
331  const key_and_obj_t& getKeyAndObject(const Ordinal idx) const;
332 
334  void throwInvalidKeyError(const Ordinal idx, const std::string &key) const;
335 
337  Ordinal assertKeyGetOrdinal(const std::string &key) const;
338 
339 };
340 
341 
342 //
343 // StringIndexedOrderedValueObjectContainer: Inline Implementations
344 //
345 
346 
347 // Set, get, and remove functions
348 
349 
350 template<class ObjType>
351 inline
354 {
355  return ptrFromRef(getNonconstKeyAndObject(idx).second);
356 }
357 
358 
359 template<class ObjType>
360 inline
363 {
364  return ptrFromRef(getKeyAndObject(idx).second);
365 }
366 
367 
368 template<class ObjType>
369 inline
372 {
373  return getNonconstObjPtr(assertKeyGetOrdinal(key));
374 }
375 
376 
377 template<class ObjType>
378 inline
381 {
382  return getObjPtr(assertKeyGetOrdinal(key));
383 }
384 
385 
386 // Iterator access
387 
388 
389 template<class ObjType>
390 inline
393 {
394  return Iterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
395  key_and_obj_array_.end());
396 }
397 
398 
399 template<class ObjType>
400 inline
403 {
404  return Iterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
405  key_and_obj_array_.end());
406 }
407 
408 
409 template<class ObjType>
410 inline
413 {
414  return ConstIterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
415  key_and_obj_array_.end());
416 }
417 
418 
419 template<class ObjType>
420 inline
423 {
424  return ConstIterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
425  key_and_obj_array_.end());
426 }
427 
428 
429 //
430 // StringIndexedOrderedValueObjectContainer: Template Implementations
431 //
432 
433 
434 // Constructors/Destructors/Info
435 
436 
437 template<class ObjType>
439 {}
440 
441 
442 template<class ObjType>
445 {
446  return key_to_idx_map_.size();
447 }
448 
449 
450 template<class ObjType>
453 {
454  return key_and_obj_array_.size();
455 }
456 
457 
458 // Set, get, and remove functions
459 
460 
461 template<class ObjType>
462 inline
465 {
466  key_to_idx_map_t::const_iterator itr = key_to_idx_map_.find(key);
467  if (itr != key_to_idx_map_.end()) {
468  return itr->second.idx;
469  }
470  return getInvalidOrdinal();
471 }
472 
473 
474 template<class ObjType>
477  const ObjType &obj)
478 {
479  typename key_to_idx_map_t::iterator obj_idx_itr = key_to_idx_map_.find(key);
480  if (obj_idx_itr != key_to_idx_map_.end()) {
481  // Object with the given key already exists
482  const Ordinal obj_idx = obj_idx_itr->second.idx;
483  key_and_obj_array_[obj_idx].second = obj;
484  return obj_idx;
485  }
486  // Object with the given key does not already exist so create a new one.
487  key_and_obj_array_.push_back(key_and_obj_t(key, obj));
488  const Ordinal new_idx = key_and_obj_array_.size()-1;
489  key_to_idx_map_[key] = new_idx;
490  return new_idx;
491 }
492 
493 
494 template<class ObjType>
496 {
497  key_and_obj_t &key_and_obj = getNonconstKeyAndObject(idx);
498  key_to_idx_map_.erase(key_and_obj.first);
499  key_and_obj = key_and_obj_t::makeInvalid();
500 }
501 
502 
503 template<class ObjType>
505 {
506  typename key_to_idx_map_t::iterator itr = key_to_idx_map_.find(key);
507  if (itr == key_to_idx_map_.end()) {
508  throwInvalidKeyError(getInvalidOrdinal(), key);
509  }
510  const Ordinal idx = itr->second.idx;
511  key_to_idx_map_.erase(itr);
512  key_and_obj_array_[idx] = key_and_obj_t::makeInvalid();
513 }
514 
515 
516 // private
517 
518 
519 template<class ObjType>
521 {
522  TEUCHOS_TEST_FOR_EXCEPTION( !(0 <= idx && idx < numStorage()),
524  "Error, the ordinal index " << idx << " is invalid"
525  << " because it falls outside of the range of valid objects"
526  << " [0,"<<numStorage()-1<<"]!");
527 }
528 
529 
530 template<class ObjType>
533 {
534  assertOrdinalIndex(idx);
535  key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
536  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
538  "Error, the ordinal index " << idx << " is invalid"
539  << " because the object has been deleted!");
540  return key_and_obj;
541 }
542 
543 
544 template<class ObjType>
547 {
548  assertOrdinalIndex(idx);
549  const key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
550  TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
552  "Error, the ordinal index " << idx << " is invalid"
553  << " because the object has been deleted!");
554  return key_and_obj;
555 }
556 
557 
558 template<class ObjType>
559 void
561  const Ordinal idx, const std::string &key) const
562 {
563  TEUCHOS_TEST_FOR_EXCEPTION( idx == getInvalidOrdinal(), InvalidKeyError,
564  "Error, the key '" << key << "' does not exist!");
565 }
566 
567 
568 template<class ObjType>
571 {
572  const Ordinal idx = getObjOrdinalIndex(key);
573  throwInvalidKeyError(idx, key);
574  return idx;
575 }
576 
577 
578 } // end of Teuchos namespace
579 
580 /* Notes:
581  *
582  * This class may have a bit of a fragile implemenation. It uses std::deque
583  * instead of std::vector to hold the stored objects. This is so that once an
584  * object is added, it will keep the exact same address no matter how many
585  * other objects are added. This is not the case with std::vector because
586  * when the memory is resized it will copy the value objects making the old
587  * objects invalid. My guess with the std::deque class is that it would
588  * allocate and store the chunks such that once an objects was added to a
589  * chunk that it would not get reallocated and moved like in std::vector. I
590  * don't feel very good about relying on this behavior but my guess is that
591  * this will be pretty portable. If this turns out not to be portable, we can
592  * always just use RCP<ObjType> to store the object and that will guarantee
593  * that the object address will never be moved. Going with an RCP<ObjType>
594  * implementation would also allow the Ptr<ObjType> views to catch dangling
595  * references in a debug-mode build.
596  */
597 
598 
599 #endif // TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
600 
601 
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.
StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal
Ordinal used for the index.
KeyObjectPair(const std::string &key_in, const ObjType &obj_in, bool isActive_in=true)
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.
Ordinal setObj(const std::string &key, const ObjType &obj)
Set (or reset) object by value and return its ordinal index.
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...