Zoltan2 Version of the Day
Zoltan2_GidLookupHelper.hpp
Go to the documentation of this file.
00001 // @HEADER
00002 //
00003 // ***********************************************************************
00004 //
00005 //   Zoltan2: A package of combinatorial algorithms for scientific computing
00006 //                  Copyright 2012 Sandia Corporation
00007 //
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Karen Devine      (kddevin@sandia.gov)
00039 //                    Erik Boman        (egboman@sandia.gov)
00040 //                    Siva Rajamanickam (srajama@sandia.gov)
00041 //
00042 // ***********************************************************************
00043 //
00044 // @HEADER
00045 // @HEADER
00046 // ***********************************************************************
00047 //            copyright
00048 // ***********************************************************************
00049 // @HEADER
00050 
00055 #ifndef _ZOLTAN2_GIDLOOKUPHELPER
00056 #define _ZOLTAN2_GIDLOOKUPHELPER
00057 
00058 #include <Zoltan2_Standards.hpp>
00059 #include <Zoltan2_Environment.hpp>
00060 #include <Zoltan2_IdentifierTraits.hpp>
00061 #include <Teuchos_Hashtable.hpp>
00062 #include <map>
00063 
00064 namespace Zoltan2
00065 {
00075 template <typename T, typename lno_t>
00076   class GidLookupHelper{
00077 
00078 private:
00079 
00080   RCP<const Environment> env_;
00081   ArrayRCP<const T> gidList_;
00082   bool useHashTable_;
00083 
00084   map<T, lno_t> indexMap_;
00085 
00086   RCP<Teuchos::Hashtable<double, lno_t> > indexHash_;
00087 
00088 public:
00091   GidLookupHelper(const RCP<const Environment> &env, 
00092     const ArrayRCP<const T> &gidList);
00093 
00096   GidLookupHelper();
00097 
00104   lno_t lookup(const T gid) const;
00105 
00108   lno_t size() const {
00109     if (useHashTable_)
00110       return indexHash_->size();
00111     else
00112       return indexMap_.size();
00113   }
00114 
00120   void getIndices(ArrayRCP<lno_t> &indices) const;
00121 };
00122 
00123 template<typename T, typename lno_t>
00124   GidLookupHelper<T, lno_t>::GidLookupHelper():
00125     env_(rcp(new Environment)), gidList_(), useHashTable_(false), 
00126     indexMap_(), indexHash_()
00127  {}
00128 
00129 template<typename T, typename lno_t>
00130   GidLookupHelper<T, lno_t>::GidLookupHelper(
00131     const RCP<const Environment> &env, 
00132     const ArrayRCP<const T> &gidList):
00133     env_(env),
00134     gidList_(gidList), useHashTable_(false), indexMap_(), indexHash_()
00135 {
00136   lno_t len = gidList_.size();
00137 
00138   if (len < 1)
00139     return;
00140 
00141   if (IdentifierTraits<T>::hasUniqueKey())
00142     useHashTable_ = true;
00143 
00144   const T *ids = gidList_.getRawPtr();
00145 
00146   if (!useHashTable_){
00147     try{
00148       for (lno_t i=0; i < gidList.size(); i++){
00149         typename map<T, lno_t>::iterator rec = indexMap_.find(*ids);
00150         if (rec == indexMap_.end())
00151           indexMap_[*ids] = i;
00152         ids++;
00153       }
00154     }
00155     catch (const std::exception &e){
00156       env_->localMemoryAssertion(__FILE__, __LINE__, len, false);
00157     }
00158   }
00159   else{
00160     typedef typename Teuchos::Hashtable<double, lno_t> id2index_hash_t;
00161     id2index_hash_t *p = NULL;
00162   
00163     try{
00164       p = new id2index_hash_t(len);
00165     }
00166     catch (const std::exception &e){
00167       env_->localMemoryAssertion(__FILE__, __LINE__, len, false);
00168     }
00169   
00170     for (lno_t i=0; i < len; i++){
00171       double key = IdentifierTraits<T>::key(*ids++);
00172       try{
00173         if (!p->containsKey(key))
00174           p->put(key, i);
00175       }
00176       Z2_THROW_OUTSIDE_ERROR(*env_);
00177     }
00178 
00179     indexHash_ = rcp<id2index_hash_t>(p);
00180   }
00181 }
00182 
00183 template<typename T, typename lno_t>
00184   lno_t GidLookupHelper<T, lno_t>::lookup(const T gid) const
00185 {
00186   lno_t idx=0;
00187   bool badId=false;
00188   if (useHashTable_){
00189     try{
00190       double key = IdentifierTraits<T>::key(gid);
00191       idx = indexHash_->get(key);
00192     }
00193     catch (const std::exception &e) {
00194       badId = true;
00195     }
00196   }
00197   else{
00198     typename map<T, lno_t>::const_iterator next = indexMap_.find(gid);
00199     if (next == indexMap_.end())
00200       badId = true;
00201     else
00202       idx = (*next).second;
00203   }
00204 
00205   env_->localInputAssertion(__FILE__, __LINE__, "invalid global id",
00206     badId==false, BASIC_ASSERTION);
00207 
00208   return idx;
00209 }
00210 
00211 template<typename T, typename lno_t>
00212   void GidLookupHelper<T, lno_t>::getIndices(
00213     ArrayRCP<lno_t> &indices) const
00214 {
00215   lno_t numIds = size();
00216   lno_t *idx = new lno_t [numIds];
00217   ArrayRCP<lno_t> indexList = arcp(idx, 0, numIds, true);
00218 
00219   if (numIds == gidList_.size()){
00220     for (lno_t i=0; i < gidList_.size(); i++){
00221        *idx++ = i;
00222     }
00223   }
00224   else{
00225     const T *ids = gidList_.getRawPtr();
00226     set<T> allGids;
00227 
00228     for (lno_t i=0; i < gidList_.size(); i++){
00229       typename set<T>::iterator rec = allGids.find(ids[i]);
00230       if (rec == allGids.end()){
00231         allGids.insert(ids[i]);
00232         *idx++ = i;
00233       }
00234     }
00235   }
00236 
00237   indices = indexList;
00238 }
00239 
00240 } // namespace Z2
00241 
00242 #endif // _ZOLTAN2_GIDLOOKUPHELPER