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 
00067   virtual ~StringIndexedOrderedValueObjectContainerBase() {};
00068 
00069 public: // Public members (but only for unit testing purposes!)
00070 
00074   class OrdinalIndex {
00075   public:
00077     typedef StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal;
00079     Ordinal idx;
00081     OrdinalIndex()
00082       : idx(StringIndexedOrderedValueObjectContainerBase::getInvalidOrdinal())
00083       {}
00085     OrdinalIndex(const Ordinal idx_in)
00086       : idx(idx_in)
00087       {}
00088   };
00089 
00103   template<class ObjType>
00104   class KeyObjectPair {
00105   public:
00107     const std::string &first;
00109     ObjType second;
00111     std::string key;
00113     KeyObjectPair() : first(key), second(ObjType()), key(""), isActive_(true) {}
00115     KeyObjectPair(const std::string &key_in, const ObjType &obj_in, bool isActive_in = true)
00116       : first(key), second(obj_in), key(key_in), isActive_(isActive_in) {}
00118     KeyObjectPair(const KeyObjectPair<ObjType> &kop)
00119       : first(key), second(kop.second), key(kop.key), isActive_(kop.isActive_) {}
00121     KeyObjectPair<ObjType>& operator=(const KeyObjectPair<ObjType> &kop)
00122       {
00123         second = kop.second;
00124         key = kop.key;
00125         isActive_ = kop.isActive_;
00126         return *this;
00127       }
00129     static KeyObjectPair<ObjType> makeInvalid()
00130       { return KeyObjectPair("", ObjType(), false); }
00132     bool isActive() const { return isActive_; }
00133   private:
00134     bool isActive_;
00135   };
00136 
00138   template<class ObjType>
00139   class SelectActive {
00140   public:
00141     bool operator()(const KeyObjectPair<ObjType> &key_and_obj) const
00142       { return key_and_obj.isActive(); }
00143   };
00144 
00146   class InvalidOrdinalIndexError : public ExceptionBase
00147   {public:InvalidOrdinalIndexError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
00148 
00150   class InvalidKeyError : public ExceptionBase
00151   {public:InvalidKeyError(const std::string& what_arg) : ExceptionBase(what_arg) {}};
00152 
00153 };
00154 
00155 
00177 template<class ObjType>
00178 class StringIndexedOrderedValueObjectContainer
00179   : private StringIndexedOrderedValueObjectContainerBase
00180 {
00181 private:
00182 
00184   typedef KeyObjectPair<ObjType> key_and_obj_t;
00186   typedef std::deque<key_and_obj_t> key_and_obj_array_t; // See notes below!
00188   typedef std::map<std::string, OrdinalIndex> key_to_idx_map_t;
00189 
00190 public:
00191 
00194 
00196   typedef StringIndexedOrderedValueObjectContainerBase::Ordinal Ordinal;
00197 
00199   typedef FilteredIterator<typename key_and_obj_array_t::iterator, SelectActive<ObjType> >
00200   Iterator;
00201 
00203   typedef FilteredIterator<typename key_and_obj_array_t::const_iterator, SelectActive<ObjType> >
00204   ConstIterator;
00205 
00207 
00210 
00212   StringIndexedOrderedValueObjectContainer();
00213 
00215   Ordinal numObjects() const;
00216 
00218   Ordinal numStorage() const;
00219 
00221 
00224 
00233   Ordinal setObj(const std::string &key, const ObjType &obj);
00234 
00239   inline Ordinal getObjOrdinalIndex(const std::string &key) const;
00240 
00244   inline Ptr<ObjType> getNonconstObjPtr(const Ordinal &idx);
00245 
00249   inline Ptr<const ObjType> getObjPtr(const Ordinal &idx) const;
00250 
00254   inline Ptr<ObjType> getNonconstObjPtr(const std::string &key);
00255 
00259   inline Ptr<const ObjType> getObjPtr(const std::string &key) const;
00260 
00267   void removeObj(const Ordinal &idx);
00268 
00270   void removeObj(const std::string &key);
00271 
00273 
00276 
00278   inline Iterator nonconstBegin();
00279 
00281   inline Iterator nonconstEnd();
00282 
00284   inline ConstIterator begin() const;
00285 
00287   inline ConstIterator end() const;
00288 
00290 
00291 private: // data members
00292 
00294   key_and_obj_array_t key_and_obj_array_;
00296   key_to_idx_map_t key_to_idx_map_;
00297 
00298   // The above is a fairly simple data-structure.
00299   //
00300   // key_and_obj_array_: Array that stores the objects (and key names), by
00301   // value, in the order they are inserted.  Any removed objects will have the
00302   // index valuie of getInvalidOrdinal().  The key strings are also storied
00303   // with the objects so that a clean iterator can over the objects has access
00304   // to both the key and the object value.
00305   //
00306   // key_to_idx_map_: Maps the unique string key to the unigue ordinal index
00307   // for an object.
00308   //
00309   // NOTES:
00310   // 
00311   // A) This data-structure stores the key names twice in order to allow for
00312   // optimal iterator performance.  The array key_and_obj_array_ allows fast
00313   // ordered iterators through the data but in order to also provide the names
00314   // in a fast manner, they have to be stored twice.
00315   //
00316   // B) Deleting objects is done by just removing an entry from
00317   // key_to_idx_map_ but the corresponding entry in key_and_obj_array_ is just
00318   // abandoned with the object value set to ObjType().
00319 
00320 private: // member functions
00321 
00323   void assertOrdinalIndex(const Ordinal idx) const;
00324 
00326   key_and_obj_t& getNonconstKeyAndObject(const Ordinal idx);
00327 
00329   const key_and_obj_t& getKeyAndObject(const Ordinal idx) const;
00330 
00332   void throwInvalidKeyError(const Ordinal idx, const std::string &key) const;
00333 
00335   Ordinal assertKeyGetOrdinal(const std::string &key) const;
00336 
00337 };
00338 
00339 
00340 //
00341 // StringIndexedOrderedValueObjectContainer: Inline Implementations
00342 //
00343 
00344 
00345 // Set, get, and remove functions
00346 
00347 
00348 template<class ObjType>
00349 inline
00350 Ptr<ObjType>
00351 StringIndexedOrderedValueObjectContainer<ObjType>::getNonconstObjPtr(const Ordinal &idx)
00352 {
00353   return ptrFromRef(getNonconstKeyAndObject(idx).second);
00354 }
00355 
00356 
00357 template<class ObjType>
00358 inline
00359 Ptr<const ObjType>
00360 StringIndexedOrderedValueObjectContainer<ObjType>::getObjPtr(const Ordinal &idx) const
00361 {
00362   return ptrFromRef(getKeyAndObject(idx).second);
00363 }
00364 
00365 
00366 template<class ObjType>
00367 inline
00368 Ptr<ObjType>
00369 StringIndexedOrderedValueObjectContainer<ObjType>::getNonconstObjPtr(const std::string &key)
00370 {
00371   return getNonconstObjPtr(assertKeyGetOrdinal(key));
00372 }
00373 
00374 
00375 template<class ObjType>
00376 inline
00377 Ptr<const ObjType>
00378 StringIndexedOrderedValueObjectContainer<ObjType>::getObjPtr(const std::string &key) const
00379 {
00380   return getObjPtr(assertKeyGetOrdinal(key));
00381 }
00382 
00383 
00384 // Iterator access
00385 
00386 
00387 template<class ObjType>
00388 inline
00389 typename StringIndexedOrderedValueObjectContainer<ObjType>::Iterator
00390 StringIndexedOrderedValueObjectContainer<ObjType>::nonconstBegin()
00391 {
00392   return Iterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
00393     key_and_obj_array_.end());
00394 }
00395 
00396 
00397 template<class ObjType>
00398 inline
00399 typename StringIndexedOrderedValueObjectContainer<ObjType>::Iterator
00400 StringIndexedOrderedValueObjectContainer<ObjType>::nonconstEnd()
00401 {
00402   return Iterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
00403     key_and_obj_array_.end());
00404 }
00405 
00406 
00407 template<class ObjType>
00408 inline
00409 typename StringIndexedOrderedValueObjectContainer<ObjType>::ConstIterator
00410 StringIndexedOrderedValueObjectContainer<ObjType>::begin() const
00411 {
00412   return ConstIterator(key_and_obj_array_.begin(), key_and_obj_array_.begin(),
00413     key_and_obj_array_.end());
00414 }
00415 
00416 
00417 template<class ObjType>
00418 inline
00419 typename StringIndexedOrderedValueObjectContainer<ObjType>::ConstIterator
00420 StringIndexedOrderedValueObjectContainer<ObjType>::end() const
00421 {
00422   return ConstIterator(key_and_obj_array_.end(), key_and_obj_array_.begin(),
00423     key_and_obj_array_.end());
00424 }
00425 
00426 
00427 //
00428 // StringIndexedOrderedValueObjectContainer: Template Implementations
00429 //
00430 
00431 
00432 // Constructors/Destructors/Info
00433 
00434 
00435 template<class ObjType>
00436 StringIndexedOrderedValueObjectContainer<ObjType>::StringIndexedOrderedValueObjectContainer()
00437 {}
00438 
00439 
00440 template<class ObjType>
00441 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00442 StringIndexedOrderedValueObjectContainer<ObjType>::numObjects() const
00443 {
00444   return key_to_idx_map_.size();
00445 }
00446 
00447 
00448 template<class ObjType>
00449 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00450 StringIndexedOrderedValueObjectContainer<ObjType>::numStorage() const
00451 {
00452   return key_and_obj_array_.size();
00453 }
00454 
00455 
00456 // Set, get, and remove functions
00457 
00458 
00459 template<class ObjType>
00460 inline
00461 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00462 StringIndexedOrderedValueObjectContainer<ObjType>::getObjOrdinalIndex(const std::string &key) const
00463 {
00464   key_to_idx_map_t::const_iterator itr = key_to_idx_map_.find(key);
00465   if (itr != key_to_idx_map_.end()) {
00466     return itr->second.idx;
00467   }
00468   return getInvalidOrdinal();
00469 }
00470 
00471 
00472 template<class ObjType>
00473 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00474 StringIndexedOrderedValueObjectContainer<ObjType>::setObj(const std::string &key,
00475   const ObjType &obj)
00476 {
00477   typename key_to_idx_map_t::iterator obj_idx_itr = key_to_idx_map_.find(key);
00478   if (obj_idx_itr != key_to_idx_map_.end()) {
00479     // Object with the given key already exists
00480     const Ordinal obj_idx = obj_idx_itr->second.idx;
00481     key_and_obj_array_[obj_idx].second = obj;
00482     return obj_idx;
00483   }
00484   // Object with the given key does not already exist so create a new one.
00485   key_and_obj_array_.push_back(key_and_obj_t(key, obj));
00486   const Ordinal new_idx = key_and_obj_array_.size()-1;
00487   key_to_idx_map_[key] = new_idx;
00488   return new_idx;
00489 }
00490 
00491 
00492 template<class ObjType>
00493 void StringIndexedOrderedValueObjectContainer<ObjType>::removeObj(const Ordinal &idx)
00494 {
00495   key_and_obj_t &key_and_obj = getNonconstKeyAndObject(idx); 
00496   key_to_idx_map_.erase(key_and_obj.first);
00497   key_and_obj = key_and_obj_t::makeInvalid();
00498 }
00499 
00500 
00501 template<class ObjType>
00502 void StringIndexedOrderedValueObjectContainer<ObjType>::removeObj(const std::string &key)
00503 {
00504   typename key_to_idx_map_t::iterator itr = key_to_idx_map_.find(key);
00505   if (itr == key_to_idx_map_.end()) {
00506     throwInvalidKeyError(getInvalidOrdinal(), key);
00507   } 
00508   const Ordinal idx = itr->second.idx;
00509   key_to_idx_map_.erase(itr);
00510   key_and_obj_array_[idx] = key_and_obj_t::makeInvalid(); 
00511 }
00512 
00513 
00514 // private
00515 
00516 
00517 template<class ObjType>
00518 void StringIndexedOrderedValueObjectContainer<ObjType>::assertOrdinalIndex(const Ordinal idx) const
00519 {
00520   TEUCHOS_TEST_FOR_EXCEPTION( !(0 <= idx && idx < numStorage()),
00521     InvalidOrdinalIndexError,
00522     "Error, the ordinal index " << idx << " is invalid"
00523     << " because it falls outside of the range of valid objects"
00524     << " [0,"<<numStorage()-1<<"]!");
00525 }
00526 
00527 
00528 template<class ObjType>
00529 typename StringIndexedOrderedValueObjectContainer<ObjType>::key_and_obj_t&
00530 StringIndexedOrderedValueObjectContainer<ObjType>::getNonconstKeyAndObject(const Ordinal idx)
00531 {
00532   assertOrdinalIndex(idx);
00533   key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
00534   TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
00535     InvalidOrdinalIndexError,
00536     "Error, the ordinal index " << idx << " is invalid"
00537     << " because the object has been deleted!");
00538   return key_and_obj;
00539 }
00540 
00541 
00542 template<class ObjType>
00543 const typename StringIndexedOrderedValueObjectContainer<ObjType>::key_and_obj_t&
00544 StringIndexedOrderedValueObjectContainer<ObjType>::getKeyAndObject(const Ordinal idx) const
00545 {
00546   assertOrdinalIndex(idx);
00547   const key_and_obj_t &key_and_obj = key_and_obj_array_[idx];
00548   TEUCHOS_TEST_FOR_EXCEPTION( !key_and_obj.isActive(),
00549     InvalidOrdinalIndexError,
00550     "Error, the ordinal index " << idx << " is invalid"
00551     << " because the object has been deleted!");
00552   return key_and_obj;
00553 }
00554 
00555 
00556 template<class ObjType>
00557 void
00558 StringIndexedOrderedValueObjectContainer<ObjType>::throwInvalidKeyError(
00559   const Ordinal idx, const std::string &key) const
00560 {
00561   TEUCHOS_TEST_FOR_EXCEPTION( idx == getInvalidOrdinal(), InvalidKeyError,
00562     "Error, the key '" << key << "' does not exist!");
00563 }
00564 
00565 
00566 template<class ObjType>
00567 typename StringIndexedOrderedValueObjectContainer<ObjType>::Ordinal
00568 StringIndexedOrderedValueObjectContainer<ObjType>::assertKeyGetOrdinal(const std::string &key) const
00569 {
00570   const Ordinal idx = getObjOrdinalIndex(key);
00571   throwInvalidKeyError(idx, key);
00572   return idx;
00573 }
00574 
00575   
00576 } // end of Teuchos namespace
00577 
00578 /* Notes:
00579  *
00580  * This class may have a bit of a fragile implemenation.  It uses std::deque
00581  * instead of std::vector to hold the stored objects.  This is so that once an
00582  * object is added, it will keep the exact same address no matter how many
00583  * other objects are added.  This is not the case with std::vector because
00584  * when the memory is resized it will copy the value objects making the old
00585  * objects invalid.  My guess with the std::deque class is that it would
00586  * allocate and store the chunks such that once an objects was added to a
00587  * chunk that it would not get reallocated and moved like in std::vector.  I
00588  * don't feel very good about relying on this behavior but my guess is that
00589  * this will be pretty portable.  If this turns out not to be portable, we can
00590  * always just use RCP<ObjType> to store the object and that will guarantee
00591  * that the object address will never be moved.  Going with an RCP<ObjType>
00592  * implementation would also allow the Ptr<ObjType> views to catch dangling
00593  * references in a debug-mode build.
00594  */
00595 
00596 
00597 #endif // TEUCHOS_STRING_INDEXED_ORDERED_VALUE_OBJECT_CONTAINER_HPP
00598 
00599 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines