Teuchos Package Browser (Single Doxygen Collection) Version of the Day
Loading...
Searching...
No Matches
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
53namespace Teuchos {
54
55
56
60public:
61
64
66 static Ordinal getInvalidOrdinal() { return -1; }
67
70
71public: // Public members (but only for unit testing purposes!)
72
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:
137 };
138
140 template<class ObjType>
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
179template<class ObjType>
182{
183private:
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
192public:
193
196
199
203
207
209
212
215
218
221
223
226
235 Ordinal setObj(const std::string &key, const ObjType &obj);
236
241 inline Ordinal getObjOrdinalIndex(const std::string &key) const;
242
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
281
284
286 inline ConstIterator begin() const;
287
289 inline ConstIterator end() const;
290
292
293private: // 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
322private: // 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
350template<class ObjType>
351inline
354{
355 return ptrFromRef(getNonconstKeyAndObject(idx).second);
356}
357
358
359template<class ObjType>
360inline
363{
364 return ptrFromRef(getKeyAndObject(idx).second);
365}
366
367
368template<class ObjType>
369inline
372{
373 return getNonconstObjPtr(assertKeyGetOrdinal(key));
374}
375
376
377template<class ObjType>
378inline
381{
382 return getObjPtr(assertKeyGetOrdinal(key));
383}
384
385
386// Iterator access
387
388
389template<class ObjType>
390inline
393{
394 return Iterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
395 key_and_obj_array_.end());
396}
397
398
399template<class ObjType>
400inline
403{
404 return Iterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
405 key_and_obj_array_.end());
406}
407
408
409template<class ObjType>
410inline
413{
414 return ConstIterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
415 key_and_obj_array_.end());
416}
417
418
419template<class ObjType>
420inline
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
437template<class ObjType>
439{}
440
441
442template<class ObjType>
445{
446 return key_to_idx_map_.size();
447}
448
449
450template<class ObjType>
453{
454 return key_and_obj_array_.size();
455}
456
457
458// Set, get, and remove functions
459
460
461template<class ObjType>
462inline
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
474template<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
494template<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
503template<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
519template<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
530template<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
544template<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
558template<class ObjType>
559void
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
568template<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
Templated array class derived from the STL std::vector.
TEUCHOS_ORDINAL_TYPE Teuchos_Ordinal
Base exception class for Teuchos.
C++ Standard Library compatable filtered iterator.
Simple wrapper class for raw pointers to single objects where no persisting relationship exists.
KeyObjectPair(const std::string &key_in, const ObjType &obj_in, bool isActive_in=true)
A safe ordinal index type that default initializes to a special value.
Ptr< const ObjType > getObjPtr(const std::string &key) const
Get a const semi-persisting association with the stored object indexed by string key.
Ordinal getObjOrdinalIndex(const std::string &key) const
Get the ordinal index given the string key.
FilteredIterator< typename key_and_obj_array_t::const_iterator, SelectActive< ObjType > > ConstIterator
The const iterator type.
key_and_obj_array_t key_and_obj_array_
Stories objects contiguously along with key strings.
FilteredIterator< typename key_and_obj_array_t::iterator, SelectActive< ObjType > > Iterator
The non-const iterator type.
void removeObj(const Ordinal &idx)
Remove an object given its ordinal index.
key_to_idx_map_t key_to_idx_map_
Provides lookups of key -> ordinal index into above array.
Ptr< ObjType > getNonconstObjPtr(const std::string &key)
Get a nonconst semi-persisting association with the stored object indexed by string key.
void throwInvalidKeyError(const Ordinal idx, const std::string &key) const
Ptr< ObjType > getNonconstObjPtr(const Ordinal &idx)
Get a nonconst semi-persisting association with the stored object indexed by ordinal.
Ordinal setObj(const std::string &key, const ObjType &obj)
Set (or reset) object by value and return its ordinal index.
StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal
Ordinal used for the index.
Ptr< const ObjType > getObjPtr(const Ordinal &idx) const
Get a const semi-persisting association with the stored object indexed by ordinal.
void removeObj(const std::string &key)
Remove an object given its string key.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.