Teuchos - Trilinos Tools Package Version of the Day
Teuchos_StringIndexedOrderedValueObjectContainer.hpp
00001 // @HEADER
00002 // ***********************************************************************
00003 //
00004 //                    Teuchos: Common Tools Package
00005 //                 Copyright (2004) Sandia Corporation
00006 //
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 //
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
00038 //
00039 // ***********************************************************************
00040 // @HEADER
00041 
00042 
00043 #ifndef TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
00044 #define TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
00045 
00046 
00047 #include "Teuchos_Array.hpp"
00048 #include "Teuchos_FilteredIterator.hpp"
00049 
00050 
00051 namespace Teuchos {
00052 
00053 
00054 
00057 class StringIndexedOrderedValueObjectContainerBase {
00058 public:
00059 
00061   typedef Teuchos_Ordinal Ordinal;
00062 
00064   static Ordinal getInvalidOrdinal() { return -1; }
00065 
00066 public: // Public members (but only for unit testing purposes!)
00067 
00071   class OrdinalIndex {
00072   public:
00074     typedef StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal;
00076     Ordinal idx;
00078     OrdinalIndex()
00079       : idx(StringIndexedOrderedValueObjectContainerBase::getInvalidOrdinal())
00080       {}
00082     OrdinalIndex(const Ordinal idx_in)
00083       : idx(idx_in)
00084       {}
00085   };
00086 
00100   template<class ObjType>
00101   class KeyObjectPair {
00102   public:
00104     const std::string &first;
00106     ObjType second;
00108     std::string key;
00110     KeyObjectPair() : first(key), second(ObjType()), key(""), isActive_(true) {}
00112     KeyObjectPair(const std::string &key_in, const ObjType &obj_in, bool isActive_in = true)
00113       : first(key), second(obj_in), key(key_in), isActive_(isActive_in) {}
00115     KeyObjectPair(const KeyObjectPair<ObjType> &kop)
00116       : first(key), second(kop.second), key(kop.key), isActive_(kop.isActive_) {}
00118     KeyObjectPair<ObjType>& operator=(const KeyObjectPair<ObjType> &kop)
00119       {
00120         second = kop.second;
00121         key = kop.key;
00122         isActive_ = kop.isActive_;
00123         return *this;
00124       }
00126     static KeyObjectPair<ObjType> makeInvalid()
00127       { return KeyObjectPair("", ObjType(), false); }
00129     bool isActive() const { return isActive_; }
00130   private:
00131     bool isActive_;
00132   };
00133 
00135   template<class ObjType>
00136   class SelectActive {
00137   public:
00138     bool operator()(const KeyObjectPair<ObjType> &key_and_obj) const
00139       { return key_and_obj.isActive(); }
00140   };
00141 
00143   class InvalidOrdinalIndexError : public ExceptionBase
00144   {public:InvalidOrdinalIndexError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
00145 
00147   class InvalidKeyError : public ExceptionBase
00148   {public:InvalidKeyError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
00149 
00150 };
00151 
00152 
00174 template<class ObjType>
00175 class StringIndexedOrderedValueObjectContainer
00176   : private StringIndexedOrderedValueObjectContainerBase
00177 {
00178 private:
00179 
00181   typedef KeyObjectPair<ObjType> key_and_obj_t;
00183   typedef std::deque<key_and_obj_t> key_and_obj_array_t; // See notes below!
00185   typedef std::map<std::string, OrdinalIndex> key_to_idx_map_t;
00186 
00187 public:
00188 
00191 
00193   typedef StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal;
00194 
00196   typedef FilteredIterator<typename key_and_obj_array_t::iterator, SelectActive<ObjType> >
00197   Iterator;
00198 
00200   typedef FilteredIterator<typename key_and_obj_array_t::const_iterator, SelectActive<ObjType> >
00201   ConstIterator;
00202 
00204 
00207 
00209   StringIndexedOrderedValueObjectContainer();
00210 
00212   Ordinal numObjects() const;
00213 
00215   Ordinal numStorage() const;
00216 
00218 
00221 
00230   Ordinal setObj(const std::string &key, const ObjType &obj);
00231 
00236   inline Ordinal getObjOrdinalIndex(const std::string &key) const;
00237 
00241   inline Ptr<ObjType> getNonconstObjPtr(const Ordinal &idx);
00242 
00246   inline Ptr<const ObjType> getObjPtr(const Ordinal &idx) const;
00247 
00251   inline Ptr<ObjType> getNonconstObjPtr(const std::string &key);
00252 
00256   inline Ptr<const ObjType> getObjPtr(const std::string &key) const;
00257 
00264   void removeObj(const Ordinal &idx);
00265 
00267   void removeObj(const std::string &key);
00268 
00270 
00273 
00275   inline Iterator nonconstBegin();
00276 
00278   inline Iterator nonconstEnd();
00279 
00281   inline ConstIterator begin() const;
00282 
00284   inline ConstIterator end() const;
00285 
00287 
00288 private: // data members
00289 
00291   key_and_obj_array_t key_and_obj_array_;
00293   key_to_idx_map_t key_to_idx_map_;
00294 
00295   // The above is a fairly simple data-structure.
00296   //
00297   // key_and_obj_array_: Array that stores the objects (and key names), by
00298   // value, in the order they are inserted.  Any removed objects will have the
00299   // index valuie of getInvalidOrdinal().  The key strings are also storied
00300   // with the objects so that a clean iterator can over the objects has access
00301   // to both the key and the object value.
00302   //
00303   // key_to_idx_map_: Maps the unique string key to the unigue ordinal index
00304   // for an object.
00305   //
00306   // NOTES:
00307   // 
00308   // A) This data-structure stores the key names twice in order to allow for
00309   // optimal iterator performance.  The array key_and_obj_array_ allows fast
00310   // ordered iterators through the data but in order to also provide the names
00311   // in a fast manner, they have to be stored twice.
00312   //
00313   // B) Deleting objects is done by just removing an entry from
00314   // key_to_idx_map_ but the corresponding entry in key_and_obj_array_ is just
00315   // abandoned with the object value set to ObjType().
00316 
00317 private: // member functions
00318 
00320   void assertOrdinalIndex(const Ordinal idx) const;
00321 
00323   key_and_obj_t& getNonconstKeyAndObject(const Ordinal idx);
00324 
00326   const key_and_obj_t& getKeyAndObject(const Ordinal idx) const;
00327 
00329   void throwInvalidKeyError(const Ordinal idx, const std::string &key) const;
00330 
00332   Ordinal assertKeyGetOrdinal(const std::string &key) const;
00333 
00334 };
00335 
00336 
00337 //
00338 // StringIndexedOrderedValueObjectContainer: Inline Implementations
00339 //
00340 
00341 
00342 // Set, get, and remove functions
00343 
00344 
00345 template<class ObjType>
00346 inline
00347 Ptr<ObjType>
00348 StringIndexedOrderedValueObjectContainer<ObjType>::getNonconstObjPtr(const Ordinal &idx)
00349 {
00350   return ptrFromRef(getNonconstKeyAndObject(idx).second);
00351 }
00352 
00353 
00354 template<class ObjType>
00355 inline
00356 Ptr<const ObjType>
00357 StringIndexedOrderedValueObjectContainer<ObjType>::getObjPtr(const Ordinal &idx) const
00358 {
00359   return ptrFromRef(getKeyAndObject(idx).second);
00360 }
00361 
00362 
00363 template<class ObjType>
00364 inline
00365 Ptr<ObjType>
00366 StringIndexedOrderedValueObjectContainer<ObjType>::getNonconstObjPtr(const std::string &key)
00367 {
00368   return getNonconstObjPtr(assertKeyGetOrdinal(key));
00369 }
00370 
00371 
00372 template<class ObjType>
00373 inline
00374 Ptr<const ObjType>
00375 StringIndexedOrderedValueObjectContainer<ObjType>::getObjPtr(const std::string &key) const
00376 {
00377   return getObjPtr(assertKeyGetOrdinal(key));
00378 }
00379 
00380 
00381 // Iterator access
00382 
00383 
00384 template<class ObjType>
00385 inline
00386 typename StringIndexedOrderedValueObjectContainer<ObjType>::Iterator
00387 StringIndexedOrderedValueObjectContainer<ObjType>::nonconstBegin()
00388 {
00389   return Iterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
00390     key_and_obj_array_.end());
00391 }
00392 
00393 
00394 template<class ObjType>
00395 inline
00396 typename StringIndexedOrderedValueObjectContainer<ObjType>::Iterator
00397 StringIndexedOrderedValueObjectContainer<ObjType>::nonconstEnd()
00398 {
00399   return Iterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
00400     key_and_obj_array_.end());
00401 }
00402 
00403 
00404 template<class ObjType>
00405 inline
00406 typename StringIndexedOrderedValueObjectContainer<ObjType>::ConstIterator
00407 StringIndexedOrderedValueObjectContainer<ObjType>::begin() const
00408 {
00409   return ConstIterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
00410     key_and_obj_array_.end());
00411 }
00412 
00413 
00414 template<class ObjType>
00415 inline
00416 typename StringIndexedOrderedValueObjectContainer<ObjType>::ConstIterator
00417 StringIndexedOrderedValueObjectContainer<ObjType>::end() const
00418 {
00419   return ConstIterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
00420     key_and_obj_array_.end());
00421 }
00422 
00423 
00424 //
00425 // StringIndexedOrderedValueObjectContainer: Template Implementations
00426 //
00427 
00428 
00429 // Constructors/Destructors/Info
00430 
00431 
00432 template<class ObjType>
00433 StringIndexedOrderedValueObjectContainer<ObjType>::StringIndexedOrderedValueObjectContainer()
00434 {}
00435 
00436 
00437 template<class ObjType>
00438 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00439 StringIndexedOrderedValueObjectContainer<ObjType>::numObjects() const
00440 {
00441   return key_to_idx_map_.size();
00442 }
00443 
00444 
00445 template<class ObjType>
00446 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00447 StringIndexedOrderedValueObjectContainer<ObjType>::numStorage() const
00448 {
00449   return key_and_obj_array_.size();
00450 }
00451 
00452 
00453 // Set, get, and remove functions
00454 
00455 
00456 template<class ObjType>
00457 inline
00458 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00459 StringIndexedOrderedValueObjectContainer<ObjType>::getObjOrdinalIndex(const std::string &key) const
00460 {
00461   key_to_idx_map_t::const_iterator itr = key_to_idx_map_.find(key);
00462   if (itr != key_to_idx_map_.end()) {
00463     return itr->second.idx;
00464   }
00465   return getInvalidOrdinal();
00466 }
00467 
00468 
00469 template<class ObjType>
00470 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00471 StringIndexedOrderedValueObjectContainer<ObjType>::setObj(const std::string &key,
00472   const ObjType &obj)
00473 {
00474   typename key_to_idx_map_t::iterator obj_idx_itr = key_to_idx_map_.find(key);
00475   if (obj_idx_itr != key_to_idx_map_.end()) {
00476     // Object with the given key already exists
00477     const Ordinal obj_idx = obj_idx_itr->second.idx;
00478     key_and_obj_array_[obj_idx].second = obj;
00479     return obj_idx;
00480   }
00481   // Object with the given key does not already exist so create a new one.
00482   key_and_obj_array_.push_back(key_and_obj_t(key, obj));
00483   const Ordinal new_idx = key_and_obj_array_.size()-1;
00484   key_to_idx_map_[key] = new_idx;
00485   return new_idx;
00486 }
00487 
00488 
00489 template<class ObjType>
00490 void StringIndexedOrderedValueObjectContainer<ObjType>::removeObj(const Ordinal &idx)
00491 {
00492   key_and_obj_t &key_and_obj = getNonconstKeyAndObject(idx); 
00493   key_to_idx_map_.erase(key_and_obj.first);
00494   key_and_obj = key_and_obj_t::makeInvalid();
00495 }
00496 
00497 
00498 template<class ObjType>
00499 void StringIndexedOrderedValueObjectContainer<ObjType>::removeObj(const std::string &key)
00500 {
00501   typename key_to_idx_map_t::iterator itr = key_to_idx_map_.find(key);
00502   if (itr == key_to_idx_map_.end()) {
00503     throwInvalidKeyError(getInvalidOrdinal(), key);
00504   } 
00505   const Ordinal idx = itr->second.idx;
00506   key_to_idx_map_.erase(itr);
00507   key_and_obj_array_[idx] = key_and_obj_t::makeInvalid(); 
00508 }
00509 
00510 
00511 // private
00512 
00513 
00514 template<class ObjType>
00515 void StringIndexedOrderedValueObjectContainer<ObjType>::assertOrdinalIndex(const Ordinal idx) const
00516 {
00517   TEUCHOS_TEST_FOR_EXCEPTION( !(0 <= idx && idx < numStorage()),
00518     InvalidOrdinalIndexError,
00519     "Error, the ordinal index " << idx << " is invalid"
00520     << " because it falls outside of the range of valid objects"
00521     << " [0,"<<numStorage()-1<<"]!");
00522 }
00523 
00524 
00525 template<class ObjType>
00526 typename StringIndexedOrderedValueObjectContainer<ObjType>::key_and_obj_t&
00527 StringIndexedOrderedValueObjectContainer<ObjType>::getNonconstKeyAndObject(const Ordinal idx)
00528 {
00529   assertOrdinalIndex(idx);
00530   key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
00531   TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
00532     InvalidOrdinalIndexError,
00533     "Error, the ordinal index " << idx << " is invalid"
00534     << " because the object has been deleted!");
00535   return key_and_obj;
00536 }
00537 
00538 
00539 template<class ObjType>
00540 const typename StringIndexedOrderedValueObjectContainer<ObjType>::key_and_obj_t&
00541 StringIndexedOrderedValueObjectContainer<ObjType>::getKeyAndObject(const Ordinal idx) const
00542 {
00543   assertOrdinalIndex(idx);
00544   const key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
00545   TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
00546     InvalidOrdinalIndexError,
00547     "Error, the ordinal index " << idx << " is invalid"
00548     << " because the object has been deleted!");
00549   return key_and_obj;
00550 }
00551 
00552 
00553 template<class ObjType>
00554 void
00555 StringIndexedOrderedValueObjectContainer<ObjType>::throwInvalidKeyError(
00556   const Ordinal idx, const std::string &key) const
00557 {
00558   TEUCHOS_TEST_FOR_EXCEPTION( idx == getInvalidOrdinal(), InvalidKeyError,
00559     "Error, the key '" << key << "' does not exist!");
00560 }
00561 
00562 
00563 template<class ObjType>
00564 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00565 StringIndexedOrderedValueObjectContainer<ObjType>::assertKeyGetOrdinal(const std::string &key) const
00566 {
00567   const Ordinal idx = getObjOrdinalIndex(key);
00568   throwInvalidKeyError(idx, key);
00569   return idx;
00570 }
00571 
00572   
00573 } // end of Teuchos namespace
00574 
00575 /* Notes:
00576  *
00577  * This class may have a bit of a fragile implemenation.  It uses std::deque
00578  * instead of std::vector to hold the stored objects.  This is so that once an
00579  * object is added, it will keep the exact same address no matter how many
00580  * other objects are added.  This is not the case with std::vector because
00581  * when the memory is resized it will copy the value objects making the old
00582  * objects invalid.  My guess with the std::deque class is that it would
00583  * allocate and store the chunks such that once an objects was added to a
00584  * chunk that it would not get reallocated and moved like in std::vector.  I
00585  * don't feel very good about relying on this behavior but my guess is that
00586  * this will be pretty portable.  If this turns out not to be portable, we can
00587  * always just use RCP<ObjType> to store the object and that will guarantee
00588  * that the object address will never be moved.  Going with an RCP<ObjType>
00589  * implementation would also allow the Ptr<ObjType> views to catch dangling
00590  * references in a debug-mode build.
00591  */
00592 
00593 
00594 #endif // TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
00595 
00596 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines