Zoltan2
Zoltan2_IdentifierTraits.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 // ***********************************************************************
00050 // @HEADER
00051 
00056 #ifndef _ZOLTAN2_IDENTIFIERTRAITS
00057 #define _ZOLTAN2_IDENTIFIERTRAITS
00058 
00059 #include <Zoltan2_Standards.hpp>
00060 #include <Zoltan2_AlltoAll.hpp>
00061 
00062 #include <Teuchos_SerializationTraits.hpp>
00063 #include <Teuchos_HashUtils.hpp>
00064 #include <Teuchos_ReductionOp.hpp>
00065 
00066 #include <utility>
00067 #include <iostream>
00068 #include <sstream>
00069 #include <string>
00070 #include <limits>
00071 #include <cstdlib>
00072 
00073 using Teuchos::SerializationTraits;
00074 
00075 namespace Zoltan2
00076 {
00077 extern int getHashCode(const unsigned char *a, size_t len);
00078 
00081 template <typename T>
00082   std::pair<T, T> z2LocalMinMax(const T *val, size_t n)
00083 {
00084   T max = std::numeric_limits<T>::min();
00085   T min = std::numeric_limits<T>::max();
00086 
00087   for (size_t i=0; i < n; i++){
00088     if (val[i] < min) min = val[i];
00089     if (val[i] > max) max = val[i];
00090   }
00091   return std::pair<T,T>(min,max);
00092 }
00093 
00094 
00100 template <typename T> class Zoltan2_MinMaxOperation :
00101   public Teuchos::ValueTypeReductionOp<int, char>
00102 {
00103 public:
00104   void reduce(
00105     const int count, const char inBuffer[], char inoutBuffer[]) const
00106   {
00107     const T *in = reinterpret_cast<const T*>(inBuffer);
00108     T *inout = reinterpret_cast<T*>(inoutBuffer);
00109 
00110     if (in[0] < inout[0]) inout[0] = in[0];
00111     if (in[1] > inout[1]) inout[1] = in[1];
00112   }
00113 };
00114 
00117 template <typename T>
00118   void z2GlobalMinMax(const Comm<int> &comm, bool noLocalValues,
00119     T localMin, T localMax, T &globalMin, T &globalMax)
00120 {
00121   if (noLocalValues){
00122     localMin = std::numeric_limits<T>::max();
00123     localMax = std::numeric_limits<T>::min();
00124   }
00125 
00126   if (comm.getSize() == 1){
00127     globalMin = localMin;
00128     globalMax = localMax;
00129     return;
00130   }
00131 
00132   T localValues[2] = {localMin, localMax};
00133   T globalValues[2];
00134 
00135   char *lv = reinterpret_cast<char *>(&localValues[0]);
00136   char *gv = reinterpret_cast<char *>(&globalValues[0]);
00137 
00138   Zoltan2_MinMaxOperation<T> reductionOp;
00139   Teuchos::reduceAll<int, char>(comm, reductionOp, 2*sizeof(T), lv, gv);
00140 
00141   globalMin = globalValues[0];
00142   globalMax = globalValues[1];
00143 }
00144 
00147 template <typename T>
00148   bool z2AreConsecutive(const T *val, size_t n)
00149 {
00150   if (n == 0) return true;
00151 
00152   if (val[n-1] - val[0] + 1 != T(n))
00153     return false;
00154 
00155   T nextval = val[0]+1;
00156   for (size_t i=1; i < n-1; i++){
00157     if (val[i] != nextval)
00158       return false;
00159     nextval++;
00160   }
00161   return true;
00162 }
00163 
00166 template <typename T>
00167   std::string stringifyOrdinal(T ordinal)
00168 {
00169   std::ostringstream oss;
00170   oss << ordinal;
00171   return oss.str();
00172 }
00173 
00176 template<typename T>
00177 struct UndefIdTraits
00178 {
00179 static inline void noop() {
00180   T::UsingInvalidGlobalIdentifierDataType();
00181 }
00182 static inline T invalid() {
00183   return T::UsingInvalidGlobalIdentifierDataType();
00184 }
00185 };
00186 
00187 
00239 template<typename T>
00240 struct IdentifierTraits {
00241 
00247   static int hashCode(const T id) {
00248    return UndefIdTraits<int>::invalid();
00249   }
00250 
00255   static inline bool hasUniqueKey(){
00256    return UndefIdTraits<bool>::invalid();}
00257 
00265   static inline double key(const T c){return static_cast<double>(c); }
00266 
00271   static inline std::string name() {
00272     return UndefIdTraits<std::string>::invalid();
00273   }
00274 
00280   static std::string stringify(T val) {
00281     return UndefIdTraits<std::string>::invalid();
00282   }
00283 
00290   static inline bool isGlobalOrdinal() {
00291     return UndefIdTraits<bool>::invalid();
00292   }
00293 
00303   static inline T difference(const T a, const T b) {
00304     return UndefIdTraits<bool>::invalid();
00305   }
00306 
00312   static inline bool is_valid_id_type() { return false; }
00313 
00323   static void minMax(const T *values, size_t numValues, T &min, T&max) {
00324     UndefIdTraits<T>::noop();
00325   }
00326 
00340   static void globalMinMax(const Comm<int> &comm, bool flag,
00341       T localMin, T localMax, T &globalMin, T &globalMax){
00342     UndefIdTraits<T>::noop();
00343   }
00344 
00355   static bool areConsecutive(const T *val, size_t n){
00356     return UndefIdTraits<bool>::invalid();
00357   }
00358 
00359 };
00360 
00361 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00362 
00363 template<>
00364 struct IdentifierTraits<char> {
00365   typedef char T;
00366   static inline int hashCode(const T c) {return static_cast<int>(c);}
00367   static inline bool hasUniqueKey() { return true;}
00368   static inline double key(const T c){return static_cast<double>(c); }
00369   static inline std::string name()     {return("char");}
00370   static std::string stringify(T val) {return stringifyOrdinal(val);}
00371   static inline bool isGlobalOrdinal() {return true; }
00372 
00373   static inline T difference(const T a, const T b) { return (b-a); }
00374   static inline bool is_valid_id_type() {return true; }
00375   static void minMax(const T *values, size_t n, T &min, T &max) {
00376     std::pair<T, T> ext = z2LocalMinMax(values, n);
00377     min = ext.first;
00378     max = ext.second;
00379   }
00380   static void globalMinMax(const Comm<int> &comm, bool flag,
00381       T localMin, T localMax, T &globalMin, T &globalMax){
00382     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00383   static bool areConsecutive(const T *val, size_t n){
00384    return z2AreConsecutive(val, n); }
00385 };
00386 
00387 template<>
00388 struct IdentifierTraits<unsigned char> {
00389   typedef unsigned char T;
00390   static inline int hashCode(const T c) {return static_cast<int>(c);}
00391   static inline bool hasUniqueKey() { return true;}
00392   static inline double key(const T c){return static_cast<double>(c); }
00393   static inline std::string name()     {return("unsigned char");}
00394   static std::string stringify(T val) {return stringifyOrdinal(val);}
00395   static inline bool isGlobalOrdinal() {return true; }
00396 
00397   static inline T difference(const T a, const T b) { return (b-a); }
00398   static inline bool is_valid_id_type() {return true; }
00399   static void minMax(const T *values, size_t n, T &min, T &max) {
00400     std::pair<T, T> ext = z2LocalMinMax(values, n);
00401     min = ext.first;
00402     max = ext.second;
00403   }
00404   static void globalMinMax(const Comm<int> &comm, bool flag,
00405       T localMin, T localMax, T &globalMin, T &globalMax){
00406     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00407   static bool areConsecutive(const T *val, size_t n){
00408    return z2AreConsecutive(val, n); }
00409 };
00410 
00411 template<>
00412 struct IdentifierTraits<short> {
00413   typedef short T;
00414   static inline int hashCode(const T  a) {return static_cast<int>(a);}
00415   static inline bool hasUniqueKey() { return true;}
00416   static inline double key(const T a){return static_cast<double>(a); }
00417   static inline std::string name()   {return("short");}
00418   static std::string stringify(T val) {return stringifyOrdinal(val);}
00419   static inline bool isGlobalOrdinal() {return true; }
00420 
00421   static inline T difference(const T a, const T b) { return (b-a); }
00422   static inline bool is_valid_id_type() {return true; }
00423   static void minMax(const T *values, size_t n, T &min, T &max) {
00424     std::pair<T, T> ext = z2LocalMinMax(values, n);
00425     min = ext.first;
00426     max = ext.second;
00427   }
00428   static void globalMinMax(const Comm<int> &comm, bool flag,
00429       T localMin, T localMax, T &globalMin, T &globalMax){
00430     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00431   static bool areConsecutive(const T *val, size_t n){
00432   return z2AreConsecutive(val, n); }
00433 };
00434 
00435 template<>
00436 struct IdentifierTraits<unsigned short> {
00437   typedef unsigned short T;
00438   static inline int hashCode(const T  a) {return static_cast<int>(a);}
00439   static inline bool hasUniqueKey() { return true;}
00440   static inline double key(const T a){return static_cast<double>(a); }
00441   static inline std::string name()   {return("unsigned short");}
00442   static std::string stringify(T val) {return stringifyOrdinal(val);}
00443   static inline bool isGlobalOrdinal() {return true; }
00444 
00445   static inline T difference(const T a, const T b) { return (b-a); }
00446   static inline bool is_valid_id_type() {return true; }
00447   static void minMax(const T *values, size_t n, T &min, T &max) {
00448     std::pair<T, T> ext = z2LocalMinMax(values, n);
00449     min = ext.first;
00450     max = ext.second;
00451   }
00452   static void globalMinMax(const Comm<int> &comm, bool flag,
00453       T localMin, T localMax, T &globalMin, T &globalMax){
00454     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00455   static bool areConsecutive(const T *val, size_t n){
00456   return z2AreConsecutive(val, n); }
00457 };
00458 
00459 template<>
00460 struct IdentifierTraits<int> {
00461   typedef int T;
00462   static inline int hashCode(const T  a) {return static_cast<int>(a);}
00463   static inline bool hasUniqueKey() { return true;}
00464   static inline double key(const T a){return static_cast<double>(a); }
00465   static inline std::string name()   {return("int");}
00466   static std::string stringify(T val) {return stringifyOrdinal(val);}
00467   static inline bool isGlobalOrdinal() {return true; }
00468 
00469   static inline T difference(const T a, const T b) { return (b-a); }
00470   static inline bool is_valid_id_type() {return true; }
00471   static void minMax(const T *values, size_t n, T &min, T &max) {
00472     std::pair<T, T> ext = z2LocalMinMax(values, n);
00473     min = ext.first;
00474     max = ext.second;
00475   }
00476   static void globalMinMax(const Comm<int> &comm, bool flag,
00477       T localMin, T localMax, T &globalMin, T &globalMax){
00478     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00479   static bool areConsecutive(const T *val, size_t n){
00480   return z2AreConsecutive(val, n); }
00481 };
00482 
00483 template<>
00484 struct IdentifierTraits<unsigned int> {
00485   typedef unsigned int T;
00486   static inline int hashCode(const T  a) {return static_cast<int>(a);}
00487   static inline bool hasUniqueKey() { return true;}
00488   static inline double key(const T a){return static_cast<double>(a); }
00489   static inline std::string name()   {return("unsigned int");}
00490   static std::string stringify(T val) {return stringifyOrdinal(val);}
00491   static inline bool isGlobalOrdinal() {return true; }
00492 
00493   static inline T difference(const T a, const T b) { return (b-a); }
00494   static inline bool is_valid_id_type() {return true; }
00495   static void minMax(const T *values, size_t n, T &min, T &max) {
00496     std::pair<T, T> ext = z2LocalMinMax(values, n);
00497     min = ext.first;
00498     max = ext.second;
00499   }
00500   static void globalMinMax(const Comm<int> &comm, bool flag,
00501       T localMin, T localMax, T &globalMin, T &globalMax){
00502     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00503   static bool areConsecutive(const T *val, size_t n){
00504   return z2AreConsecutive(val, n); }
00505 };
00506 
00507 
00508 template<>
00509 struct IdentifierTraits<long> {
00510   typedef long T;
00511   static inline int hashCode(const T a) {
00512     return getHashCode(
00513       reinterpret_cast<const unsigned char *>(&a), sizeof(T));}
00514   static inline bool hasUniqueKey() { return true;}
00515   static inline double key(const T a){return static_cast<double>(a); }
00516   static inline std::string name()    {return("long");}
00517   static std::string stringify(T val) {return stringifyOrdinal(val);}
00518   static inline bool isGlobalOrdinal() {return true; }
00519   static inline T difference(const T a, const T b) { return (b-a); }
00520   static inline bool is_valid_id_type() {return true; }
00521   static void minMax(const T *values, size_t n, T &min, T &max) {
00522     std::pair<T, T> ext = z2LocalMinMax(values, n);
00523     min = ext.first;
00524     max = ext.second;
00525   }
00526   static void globalMinMax(const Comm<int> &comm, bool flag,
00527       T localMin, T localMax, T &globalMin, T &globalMax){
00528     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00529   static bool areConsecutive(const T *val, size_t n){
00530     return z2AreConsecutive(val, n); }
00531 };
00532 
00533 template<>
00534 struct IdentifierTraits<unsigned long> {
00535   typedef unsigned long T;
00536   static inline int hashCode(const T a) {
00537     return getHashCode(
00538       reinterpret_cast<const unsigned char *>(&a), sizeof(T));}
00539   static inline bool hasUniqueKey() { return true;}
00540   static inline double key(const T a){return static_cast<double>(a);}
00541   static inline std::string name()   {return("unsigned long");}
00542   static std::string stringify(T val) {return stringifyOrdinal(val);}
00543   static inline bool isGlobalOrdinal() {return true; }
00544   static inline T difference(const T a, const T b) { return (b-a); }
00545   static inline bool is_valid_id_type() {return true; }
00546   static void minMax(const T *values, size_t n, T &min, T &max) {
00547     std::pair<T, T> ext = z2LocalMinMax(values, n);
00548     min = ext.first;
00549     max = ext.second;
00550   }
00551   static void globalMinMax(const Comm<int> &comm, bool flag,
00552       T localMin, T localMax, T &globalMin, T &globalMax){
00553     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00554   static bool areConsecutive(const T *val, size_t n){
00555     return z2AreConsecutive(val, n); }
00556 };
00557 
00558 #ifdef HAVE_ZOLTAN2_LONG_LONG
00559 
00560 template<>
00561 struct IdentifierTraits<long long> {
00562   typedef long long T;
00563   static inline int hashCode(const T a) {
00564     return getHashCode(
00565       reinterpret_cast<const unsigned char *>(&a), sizeof(T));}
00566   static inline bool hasUniqueKey() { return true;}
00567   static inline double key(const T a){return static_cast<double>(a); }
00568   static inline std::string name()    {return("long long");}
00569   static std::string stringify(T val) {return stringifyOrdinal(val);}
00570   static inline bool isGlobalOrdinal() {return true; }
00571   static inline T difference(const T a, const T b) { return (b-a); }
00572   static inline bool is_valid_id_type() {return true; }
00573   static void minMax(const T *values, size_t n, T &min, T &max) {
00574     std::pair<T, T> ext = z2LocalMinMax(values, n);
00575     min = ext.first;
00576     max = ext.second;
00577   }
00578   static void globalMinMax(const Comm<int> &comm, bool flag,
00579       T localMin, T localMax, T &globalMin, T &globalMax){
00580     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00581   static bool areConsecutive(const T *val, size_t n){
00582     return z2AreConsecutive(val, n); }
00583 };
00584 
00585 template<>
00586 struct IdentifierTraits<unsigned long long> {
00587   typedef unsigned long long T;
00588   static inline int hashCode(const T a) {
00589     return getHashCode(
00590       reinterpret_cast<const unsigned char *>(&a), sizeof(T));}
00591   static inline bool hasUniqueKey() { return true;}
00592   static inline double key(const T a){return static_cast<double>(a);}
00593   static inline std::string name()   {return("unsigned long long");}
00594   static std::string stringify(T val) {return stringifyOrdinal(val);}
00595   static inline bool isGlobalOrdinal() {return true; }
00596   static inline T difference(const T a, const T b) { return (b-a); }
00597   static inline bool is_valid_id_type() {return true; }
00598   static void minMax(const T *values, size_t n, T &min, T &max) {
00599     std::pair<T, T> ext = z2LocalMinMax(values, n);
00600     min = ext.first;
00601     max = ext.second;
00602   }
00603   static void globalMinMax(const Comm<int> &comm, bool flag,
00604       T localMin, T localMax, T &globalMin, T &globalMax){
00605     z2GlobalMinMax(comm, flag, localMin, localMax, globalMin, globalMax);}
00606   static bool areConsecutive(const T *val, size_t n){
00607     return z2AreConsecutive(val, n); }
00608 };
00609 
00610 #endif
00611 
00612 template<>
00613 struct IdentifierTraits<std::string> {
00614   typedef std::string T;
00615   static inline int hashCode(const T a) {
00616     return getHashCode(
00617       reinterpret_cast<const unsigned char *>(a.c_str()), a.size());}
00618   static inline bool hasUniqueKey() { return false;}
00619   static inline double key(const T a){ throw std::logic_error("invalid call");}
00620   static inline std::string name()   {return("string");}
00621   static std::string stringify(T val) {return val;}
00622   static inline bool isGlobalOrdinal() {return false; }
00623   static inline T difference(const T a, const T b) {
00624     throw std::logic_error("invalid call");}
00625   static inline bool is_valid_id_type() {return true; }
00626   static void minMax(const T *values, size_t n, T &min, T &max) {
00627     throw std::logic_error("invalid call");}
00628   static void globalMinMax(const Comm<int> &comm, bool flag,
00629       T localMin, T localMax, T &globalMin, T &globalMax){
00630     throw std::logic_error("invalid call");}
00631   static bool areConsecutive(const T *val, size_t n){
00632     throw std::logic_error("invalid call");}
00633 };
00634 
00635 template<typename T1, typename T2>
00636 struct IdentifierTraits<std::pair<T1, T2> > {
00637   typedef std::pair<T1, T2> pair_t;
00638   typedef typename std::pair<pair_t, pair_t> pairPair_t;
00639 
00640   static inline int hashCode(const pair_t p)  {
00641     return IdentifierTraits<T1>::hashCode(p.first) +
00642       IdentifierTraits<T2>::hashCode(p.second);
00643   }
00644 
00645   static inline bool hasUniqueKey() {
00646     if ((sizeof(T1)*2 <= sizeof(double))&&(sizeof(T2)*2 <= sizeof(double)))
00647       return true;
00648     else
00649       return false;
00650   }
00651 
00652   static inline double key(const pair_t p)  {
00653     size_t nbytes = sizeof(double) / 2;
00654     if ((sizeof(T1) > nbytes)||(sizeof(T2) > nbytes))
00655       throw std::logic_error("invalid call");
00656     else{
00657       double keyVal=0;
00658       char *cx = reinterpret_cast<char *>(&keyVal);
00659       char *cy = cx + nbytes;
00660       T1 *xpos = reinterpret_cast<T1 *>(cx + nbytes-sizeof(T1));
00661       T2 *ypos = reinterpret_cast<T2 *>(cy + nbytes-sizeof(T2));
00662       // mfh 17 Apr 2014: Must do a memcpy here rather than an
00663       // assignment, in order to avoid breaking strict ANSI aliasing
00664       // rules (which compilers expect in order to optimize
00665       // correctly).
00666       memcpy (xpos, &(p.first), sizeof (T1)); // *xpos = p.first;
00667       memcpy (ypos, &(p.second), sizeof (T2)); // *ypos = p.second;
00668       return keyVal;
00669     }
00670   }
00671 
00672   static inline std::string name() {
00673      std::string s("std::pair<");
00674      s += IdentifierTraits<T1>::name();
00675      s += std::string(", ");
00676      s += IdentifierTraits<T2>::name();
00677      s += std::string(">");
00678      return s;
00679   }
00680 
00681   static std::string stringify(pair_t val) {
00682     std::ostringstream oss;
00683     oss << "pair<" << IdentifierTraits<T1>::name();
00684     oss << "," << IdentifierTraits<T2>::name();
00685     oss << ">(" << val.first << "," << val.second << ")";
00686     return oss.str();
00687   }
00688 
00689   static inline bool isGlobalOrdinal() {return false; }
00690 
00691   static inline pair_t difference( const pair_t a, const pair_t b) {
00692       throw std::logic_error("invalid call");
00693       return pair_t();}
00694 
00695   static inline bool is_valid_id_type() {
00696     return (sizeof(T1)+sizeof(T2) <= sizeof(double)); }
00697 
00698   static void minMax(const pair_t *values, size_t n, pair_t &min, pair_t &max) {
00699       throw std::logic_error("invalid call");}
00700 
00701   static void globalMinMax(const Comm<int> &comm, bool flag,
00702       pair_t localMin, pair_t localMax,
00703       pair_t &globalMin, pair_t &globalMax){
00704       throw std::logic_error("invalid call");}
00705 
00706   static bool areConsecutive(const pair_t *val, size_t n){
00707       throw std::logic_error("invalid call");
00708       return false; }
00709 };
00710 
00712 //  A helper function.  If T is an ordinal, are the values
00713 //    globally consecutive?  If so return true, otherwise
00714 //    return false.
00715 //
00716 //  On return, globalLen is set to the sum of the local lengths.
00717 //
00718 //  If T is an ordinal, but the list is not globally consecutive,
00719 //    on return dist[0] is set to the global minimum of
00720 //    the values and dist[1] to the global maximum.
00721 //
00722 //  If T is an ordinal and the list is globally consecutive,
00723 //    on return dist[p] is set to val[0] on process p.  dist[nprocs]
00724 //    is set to one past the global maximum value.
00726 
00727 template <typename T>
00728   bool globallyConsecutiveOrdinals(
00729     const Comm<int> &comm, const Environment &env,
00730     const T* val, size_t len,
00731     ArrayRCP<T> &dist, size_t &globalLen)
00732 {
00733   // Non-ordinals can not be consecutive.
00734 
00735   if (!IdentifierTraits<T>::isGlobalOrdinal())
00736     return false;
00737 
00738   // return values
00739 
00740   T *distBuf= NULL;
00741   T *minMaxBuf= NULL;
00742   globalLen = 0;
00743 
00744   // Locally consecutive?
00745 
00746   int nprocs = comm.getSize();
00747   bool locallyConsecutive = IdentifierTraits<T>::areConsecutive(val, len);
00748   bool globallyConsecutive = false;
00749 
00750   if (nprocs == 1){
00751     if (locallyConsecutive){
00752       distBuf = new T [2];
00753       if (len > 0){
00754         distBuf[0] = val[0];
00755         distBuf[1] = val[len-1] + 1;
00756       }
00757       else{
00758         distBuf[0] = 0;
00759         distBuf[1] = 0;
00760       }
00761     }
00762     else{
00763       std::pair<T, T> extrema = z2LocalMinMax(val, len);
00764       minMaxBuf = new T [2];
00765       minMaxBuf[0] = extrema.first;
00766       minMaxBuf[1] = extrema.second;
00767     }
00768 
00769     globalLen = len;
00770     globallyConsecutive = locallyConsecutive;
00771   }
00772   else{   // nprocs > 1
00773     try{
00774       reduceAll<int, size_t>(comm, Teuchos::REDUCE_SUM, 1, &len, &globalLen);
00775     }
00776     Z2_THROW_OUTSIDE_ERROR(env);
00777 
00778     T v0, v1, gMin, gMax;
00779 
00780     if (len > 0){
00781       v0 = val[0];
00782       v1 = val[len-1];
00783     }
00784     else {
00785       v0 = std::numeric_limits<T>::max();
00786       v1 = std::numeric_limits<T>::min();
00787     }
00788 
00789     try{
00790       IdentifierTraits<T>::globalMinMax(comm, len==0, v0, v1, gMin, gMax);
00791     }
00792     Z2_FORWARD_EXCEPTIONS;
00793 
00794     int lFlag = (locallyConsecutive ? 1 : 0);
00795     int gFlag = 0;
00796 
00797     try{
00798       reduceAll<int, int>(comm, Teuchos::REDUCE_MIN, 1, &lFlag, &gFlag);
00799     }
00800     Z2_THROW_OUTSIDE_ERROR(env);
00801 
00802     if (gFlag == 1){  // all processes have consecutive values
00803 
00804       size_t g0 = static_cast<size_t>(gMin);
00805       size_t g1 = static_cast<size_t>(gMax);
00806 
00807       if (g1 - g0 + 1 == globalLen){
00808         size_t sentinel = g1 + 1;   // invalid id
00809         size_t sendVal = sentinel;
00810         if (len > 0)
00811           sendVal = static_cast<size_t>(v0);
00812 
00813         size_t *recvBuf = new size_t[nprocs];
00814 
00815         try {
00816           Teuchos::gatherAll<int, size_t>(comm, 1, &sendVal, nprocs, recvBuf);
00817         }
00818         Z2_THROW_OUTSIDE_ERROR(env);
00819 
00820         int numNoIds = 0;  // number of procs with no ids
00821         for (int i=0; i < nprocs; i++)
00822           if (recvBuf[i] == sentinel)
00823             numNoIds++;
00824 
00825         globallyConsecutive = true;
00826 
00827         if (numNoIds == 0){
00828           for (int i=1; globallyConsecutive && i < nprocs; i++)
00829             if (recvBuf[i] < recvBuf[i-1])
00830               globallyConsecutive = false;
00831 
00832           if (globallyConsecutive){
00833             distBuf = new T [nprocs+1];
00834             for (int i=0; i < nprocs; i++)
00835               distBuf[i] = static_cast<T>(recvBuf[i]);
00836             distBuf[nprocs] = static_cast<T>(sentinel);
00837           }
00838         }
00839         else{
00840           Array<int> index;
00841           for (int i=0; i < nprocs; i++)
00842             if (recvBuf[i] != sentinel)
00843               index.push_back(i);
00844 
00845           for (int i=1; i < index.size(); i++){
00846             if (recvBuf[index[i]] < recvBuf[index[i-1]])
00847               globallyConsecutive = false;
00848           }
00849 
00850           if (globallyConsecutive){
00851             distBuf = new T [nprocs+1];
00852             for (int i=0; i < nprocs+1; i++)
00853               distBuf[i] = static_cast<T>(sentinel);
00854 
00855             for (int i=0; i < index.size(); i++)
00856               distBuf[index[i]] = static_cast<T>(recvBuf[index[i]]);
00857 
00858             T useValue = static_cast<T>(sentinel);
00859             for (int i = nprocs-1; i >= 0; i--){
00860               if (distBuf[i] == static_cast<T>(sentinel))
00861                 distBuf[i] = useValue;
00862               else
00863                 useValue = distBuf[i];
00864             }
00865           }
00866         }
00867         delete [] recvBuf;
00868       }
00869     }  // all processes have locally consecutive values
00870 
00871     if (!globallyConsecutive){
00872       minMaxBuf = new T [2];
00873       minMaxBuf[0] = gMin;
00874       minMaxBuf[1] = gMax;
00875     }
00876   }    // nprocs > 1
00877 
00878   if (minMaxBuf)
00879     dist = arcp(minMaxBuf, 0, 2, true);
00880   else if (distBuf)
00881     dist = arcp(distBuf, 0, nprocs+1, true);
00882   else
00883      throw std::logic_error("no buffer");  // should never get here
00884 
00885   return globallyConsecutive;
00886 }
00887 
00888 #endif  // DOXYGEN_SHOULD_SKIP_THIS
00889 
00890 } // namespace Z2
00891 
00892 #endif // _ZOLTAN2_IDENTIFIERTRAITS