Zoltan2
Zoltan2_IntegerRangeList.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 
00050 #ifndef _ZOLTAN2_INTEGERRANGELIST_HPP_
00051 #define _ZOLTAN2_INTEGERRANGELIST_HPP_
00052 
00053 #include <Zoltan2_config.h>
00054 
00055 #include <Teuchos_ParameterEntryValidator.hpp>
00056 #include <Teuchos_ValidatorXMLConverter.hpp>
00057 #include <Teuchos_XMLObject.hpp>
00058 #include <Teuchos_ValidatorMaps.hpp>
00059 #include <Teuchos_DummyObjectGetter.hpp>
00060 #include <Teuchos_StrUtils.hpp>
00061 
00062 // Had to redefine this type from Teuchos_ParameterEntryValidator.hpp.
00063 // Compiler stumbled on it.
00064 typedef Teuchos::RCP<const Teuchos::Array<std::string> > ValidStringsList;
00065 
00066 namespace Zoltan2{
00067 
00071 enum RangeType {
00072   RANGE_INCLUDES_ALL,    
00073   RANGE_IS_EMPTY,        
00074   RANGE_IS_LISTED,       
00075   NUM_RANGE_TYPES
00076 };
00077 
00078 template <typename T> class IntegerRangeListValidator;
00079 
00081 // Helper functions for interpreting integer range list arrays.
00083 
00090 template <typename Integral>
00091   bool validIntegralRangeList(const Teuchos::Array<Integral> &vals)
00092 {
00093   typedef typename Teuchos::Array<Integral>::size_type arraySize_t;
00094   arraySize_t len = vals.size();
00095   if (len==0)
00096     return false;
00097 
00098   Integral flag = vals[len-1];
00099   if ((flag != RANGE_INCLUDES_ALL) && (flag != RANGE_IS_EMPTY) &&
00100       (flag != RANGE_IS_LISTED))
00101     return false;
00102 
00103   return true;
00104 }
00105 
00120 template <typename Integral>
00121   bool allValuesAreInRangeList(const Teuchos::Array<Integral> &vals)
00122 {
00123   if (!validIntegralRangeList(vals))
00124     throw std::runtime_error("list is not a valid range list");
00125   return vals[vals.size()-1] == RANGE_INCLUDES_ALL;
00126 }
00127 
00142 template <typename Integral>
00143   bool allValuesAreInRangeList(const Teuchos::ParameterEntry &e)
00144 {
00145   if (!e.isType<Teuchos::Array<Integral> >())
00146     throw std::runtime_error("Should not call until modified");
00147 
00148   Teuchos::Array<Integral> *valPtr=NULL;
00149   Teuchos::Array<Integral> &vals = e.getValue(valPtr);
00150   return allValuesAreInRangeList(vals);
00151 }
00152 
00167 template <typename Integral>
00168   bool noValuesAreInRangeList(const Teuchos::Array<Integral> &vals)
00169 {
00170   if (!validIntegralRangeList(vals))
00171     throw std::runtime_error("list is not a valid range list");
00172   return vals[vals.size()-1] == RANGE_IS_EMPTY;
00173 }
00174 
00189 template <typename Integral>
00190   bool noValuesAreInRangeList(const Teuchos::ParameterEntry &e)
00191 {
00192   if (!e.isType<Teuchos::Array<Integral> >())
00193     throw std::runtime_error("Should not call until modified");
00194 
00195   Teuchos::Array<Integral> *valPtr=NULL;
00196   Teuchos::Array<Integral> &vals = e.getValue(valPtr);
00197   return noValuesAreInRangeList(vals);
00198 }
00199 
00200 // TODO :
00201 // inList(std::vector<Integral> &val, std::vector<bool> &result)
00202 
00214 template <typename Integral>
00215   bool IsInRangeList(const Integral val, const Teuchos::Array<Integral> &valList, bool sorted=true)
00216 {
00217   if (allValuesAreInRangeList(valList))
00218     return true;
00219   else if (noValuesAreInRangeList(valList))
00220     return false;
00221 
00222   if (sorted){
00223     typename Teuchos::Array<Integral>::const_iterator flag = valList.end();
00224     --flag;
00225     if (std::binary_search(valList.begin(), flag, val))
00226       return true;
00227     else
00228       return false;
00229   }
00230   else{
00231     for (typename Teuchos::Array<Integral>::size_type i=0; i < valList.size()-1; i++){
00232       if (valList[i] == val)
00233         return true;
00234     }
00235     return false;
00236   }
00237 }
00238 
00249 template <typename Integral>
00250   bool IsInRangeList(const Integral val, const Teuchos::ParameterEntry &e)
00251 {
00252   if (!e.isType<Teuchos::Array<Integral> >())
00253     throw std::runtime_error("Should not call until modified");
00254 
00255   Teuchos::Array<Integral> *valPtr=NULL;
00256   Teuchos::Array<Integral> &valList = e.getValue(valPtr);
00257 
00258   typedef IntegerRangeListValidator<Integral> irl_t;
00259   RCP<const irl_t> irl;
00260   bool fail = false;
00261  
00262   RCP<const Teuchos::ParameterEntryValidator> valtor = e.validator();
00263   if (!valtor.is_null()){
00264     try{
00265       irl = rcp_dynamic_cast<const irl_t>(valtor);
00266     }
00267     catch (...){
00268       fail = true;
00269     }
00270   }
00271   else{
00272     fail = true;
00273   }
00274 
00275   if (fail)
00276     throw std::runtime_error("wrong type of parameter entry");
00277 
00278   bool sorted = irl->inputListWillBeSorted();
00279 
00280   return IsInRangeList(val, valList, sorted);
00281 } 
00282 
00291 template <typename Integral>
00292   Teuchos::ArrayView<Integral> getList(Teuchos::Array<Integral> &irl)
00293 {
00294   Teuchos::ArrayView<Integral> av;  // av.size() == 0
00295 
00296   if (!Zoltan2::allValuesAreInRangeList(irl) &&
00297       !Zoltan2::noValuesAreInRangeList(irl))
00298     av = irl.view(0, irl.size()-1); // skip last value, it's a flag
00299 
00300   return av;
00301 }
00302 
00311 template <typename Integral>
00312   void printIntegralRangeList(std::ostream &os, Teuchos::Array<Integral> &irl)
00313 {
00314   if (Zoltan2::allValuesAreInRangeList(irl))
00315     os << "all";
00316   else if (Zoltan2::noValuesAreInRangeList(irl))
00317     os << "empty";
00318   else{
00319     Teuchos::ArrayView<const Integral> view = 
00320       irl.view(0, irl.size()-1); // skip last value, it's a flag
00321     os << view;
00322   }    
00323 }
00324 
00326 // Validator class
00328 
00388 template <typename Integral>
00389   class IntegerRangeListValidator : public Teuchos::ParameterEntryValidator
00390 {
00391 private:
00392 
00393 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00394 
00395   Integral min_;
00396   Integral max_;
00397   bool unsorted_;
00398 
00399   static const std::string listDelim_;
00400   static const std::string rangeDelim_;
00401   static const std::string allText_;
00402 
00403   static void checkValid(char c); 
00404   static bool listSaysAll(std::string &l);
00405   static int breakRange(std::string &range, std::string &from, std::string &to);
00406 
00407 #endif
00408 
00409 public:
00415   IntegerRangeListValidator(bool unsorted=false);
00416 
00426   IntegerRangeListValidator(Integral validMin, Integral validMax,
00427     bool unsorted=false); 
00428 
00429   // Implementation of ParameterEntryValidator interface
00430 
00431   const std::string getXMLTypeName() const; 
00432 
00433   void printDoc(std::string const& docString, std::ostream &out) const;
00434 
00435   ValidStringsList validStringValues() const ;
00436 
00437   void validate( Teuchos::ParameterEntry  const& entry,
00438     std::string const& paramName, std::string const& sublistName
00439     ) const;
00440 
00441   void validateAndModify( std::string const& paramName,
00442     std::string const& sublistName, Teuchos::ParameterEntry * entry
00443     ) const;
00444 
00445   // IntegerRangeListValidator methods
00446 
00452   Integral getAllowedMinimum() const { return min_;}
00453 
00459   Integral getAllowedMaximum() const { return max_;}
00460 
00467   bool inputListWillBeSorted() const { return !unsorted_;}
00468 
00469 }; // end class
00470 
00472 // Class definitions
00474 
00475 template <typename Integral>
00476 const std::string IntegerRangeListValidator<Integral>::listDelim_(",");
00477 
00478 template <typename Integral>
00479 const std::string IntegerRangeListValidator<Integral>::rangeDelim_("-");
00480 
00481 template <typename Integral>
00482 const std::string IntegerRangeListValidator<Integral>::allText_("all");
00483 
00484 template <typename Integral>
00485   void IntegerRangeListValidator<Integral>::checkValid(char c)
00486 {
00487   if (std::isspace(c) || std::isdigit(c) || (c == ',') || (c == '-'))
00488     return;
00489   else
00490     throw std::runtime_error("invalid integer range list");
00491 }
00492 
00493 template <typename Integral>
00494   bool IntegerRangeListValidator<Integral>::listSaysAll(std::string &l)
00495 {
00496   std::transform(l.begin(), l.end(), l.begin(), (int(*)(int)) tolower);
00497   if (l.find(allText_) != std::string::npos)
00498     return true;  // "all" is in the string
00499   else
00500     return false;
00501 }
00502 
00503 template <typename Integral>
00504   int IntegerRangeListValidator<Integral>::breakRange(
00505     std::string &range, std::string &from, std::string &to)
00506 {
00507   from.clear();
00508   to.clear();
00509   std::string::size_type loc = range.find(rangeDelim_);
00510   if (loc == std::string::npos){
00511     from = range;
00512   }
00513   else{
00514     from = range.substr(0, loc);
00515     to = range.substr(loc+1, range.size());
00516   }
00517   long a, b;
00518   std::istringstream iss1(from);
00519   iss1 >> a;
00520   b = a;
00521   if (to.size() > 0){
00522     std::istringstream iss2(to);
00523     iss2 >> b;
00524     if (b < a)
00525       std::swap(from,to);
00526   }
00527   return (b != a) ? 2 : 1;
00528 }
00529 
00530 
00531 template <typename Integral>
00532   IntegerRangeListValidator<Integral>::IntegerRangeListValidator(
00533     bool unsorted): min_(1), max_(0), unsorted_(unsorted)
00534 {
00535 }
00536 
00537 template <typename Integral>
00538   IntegerRangeListValidator<Integral>::IntegerRangeListValidator(
00539     Integral validMin, Integral validMax, bool unsorted) :
00540       min_(validMin), max_(validMax), unsorted_(unsorted)
00541 {
00542   if (min_ < max_) std::swap(min_,max_);
00543 }
00544 
00545   // Implementation of ParameterEntryValidator interface
00546 
00547 template <typename Integral>
00548   const std::string 
00549     IntegerRangeListValidator<Integral>::getXMLTypeName() const 
00550 {
00551   std::string className("IntegerRangeListValidator");
00552   std::string classType("("+Teuchos::TypeNameTraits<Integral>::name()+")");
00553   return std::string(className + classType);
00554 }
00555 
00556 template <typename Integral>
00557   void IntegerRangeListValidator<Integral>::printDoc(
00558     std::string const& docString, std::ostream &out) const  
00559 {
00560   Teuchos::StrUtils::printLines(out,"# ",docString);
00561   out << "#\tAn integer range list is a string which can contain:\n";
00562   out << "#\t\tthe text \"all\", which indicates all values\n";
00563   out << "#\t\ta list of integer ranges separated by commas.\n";
00564   out << "#\tA range is one value, or two values separated by a dash.\n";
00565   out << "#\tExample: \"all\" or \"1-10\" or \"3, 10-12\" or \"25\"\n";
00566   if (max_ >= min_){
00567     out << "#\tThe range of valid integers is [";
00568     out << min_ << "," << max_ << "]\n";
00569   }
00570 }
00571 
00572 template <typename Integral>
00573   ValidStringsList IntegerRangeListValidator<Integral>::validStringValues() const 
00574 { 
00575   return Teuchos::null; 
00576 }
00577 
00578 template <typename Integral>
00579   void IntegerRangeListValidator<Integral>::validate( 
00580     Teuchos::ParameterEntry  const& entry,
00581     std::string const& paramName, std::string const& sublistName) const
00582 {
00583   if (!entry.isType<std::string>()){
00584     return;  // already converted to an an array
00585   }
00586   std::string *sptr=NULL;
00587   std::string &rangeList = entry.getValue(sptr);
00588   std::string inValue(rangeList);
00589 
00590   if (listSaysAll(inValue))
00591     return;  // "all" is in the string
00592 
00593   // throw error if invalid integer range list
00594   std::for_each(inValue.begin(), inValue.end(), checkValid);
00595 
00596   if (max_ >= min_){
00597     std::string::const_iterator rangeBegin = inValue.begin();
00598     std::string::const_iterator valueEnd = inValue.end();
00599 
00600     while (rangeBegin != valueEnd){
00601       std::string::const_iterator rangeEnd = std::search(
00602         rangeBegin, valueEnd, listDelim_.begin(), listDelim_.end());
00603       std::string range(rangeBegin, rangeEnd);
00604       std::string aHalf, bHalf;
00605       int count = breakRange(range, aHalf, bHalf);
00606 
00607       Integral a, b;
00608       std::istringstream iss1(aHalf);
00609       iss1 >> a;
00610       if (count > 1){
00611         std::istringstream iss2(bHalf);
00612         iss2 >> b;
00613       }
00614       else
00615         b = a;
00616 
00617       if ((a < min_) || (b > max_)){
00618         std::ostringstream oss;
00619         oss << "input range [" << a << "," << b << "] ";
00620         oss << "exceeds valid range [" << min_ << "," << max_ << "] ";
00621         throw std::runtime_error(oss.str());
00622       }
00623       if (rangeEnd == valueEnd)
00624         rangeBegin = rangeEnd;
00625       else
00626         rangeBegin = ++rangeEnd;
00627     }
00628   }
00629 }
00630 
00631 template <typename Integral>
00632   void IntegerRangeListValidator<Integral>::validateAndModify( 
00633     std::string const& paramName, std::string const& sublistName, 
00634     Teuchos::ParameterEntry * entry) const
00635 {
00636   typedef typename Teuchos::Array<Integral>::size_type arraySize_t;
00637   if (!entry->isType<std::string>()){
00638     return;
00639   }
00640   
00641   std::string *sptr=NULL;
00642   std::string &rangeList = entry->getValue(sptr);
00643   Teuchos::Array<Integral> valueList;
00644 
00645   std::string inValue(rangeList);
00646 
00647   if (listSaysAll(inValue)){
00648     valueList.push_back(RANGE_INCLUDES_ALL);
00649   }
00650   else{
00651     // throw error if invalid integer range list
00652     std::for_each(inValue.begin(), inValue.end(), checkValid);
00653 
00654     std::string::const_iterator rangeBegin = inValue.begin();
00655     std::string::const_iterator valueEnd = inValue.end();
00656 
00657     while (rangeBegin != valueEnd){
00658       std::string::const_iterator rangeEnd = std::search(rangeBegin,
00659         valueEnd, listDelim_.begin(), listDelim_.end());
00660       std::string range(rangeBegin, rangeEnd);
00661       std::string aHalf, bHalf;
00662       int count = breakRange(range, aHalf, bHalf);
00663 
00664       Integral a, b;
00665       std::istringstream iss1(aHalf);
00666       iss1 >> a;
00667       if (count > 1){
00668         std::istringstream iss2(bHalf);
00669         iss2 >> b;
00670       }
00671       else
00672         b = a;
00673 
00674       if ((max_ >= min_) && ((a < min_) || (b > max_))){
00675         std::ostringstream oss;
00676         oss << "input range [" << a << "," << b << "] ";
00677         oss << "exceeds valid range [" << min_ << "," << max_ << "] ";
00678         throw std::runtime_error(oss.str());
00679       }
00680       for (Integral i=a; i <=b; i++)
00681         valueList.push_back(i);
00682       if (rangeEnd == valueEnd)
00683        rangeBegin = rangeEnd;
00684       else
00685         rangeBegin = ++rangeEnd;
00686     }
00687     if (!unsorted_ && valueList.size() > 1){  // sort & remove duplicates
00688       std::sort(valueList.begin(), valueList.end());
00689       arraySize_t listEnd = 0;
00690       arraySize_t length = valueList.size();
00691       for (arraySize_t i=1; i < length; i++){
00692         if (valueList[i] > valueList[listEnd]){
00693           listEnd++;
00694           if (listEnd != i)
00695             valueList[listEnd] = valueList[i];
00696         }
00697       }
00698       if (++listEnd < length)
00699         valueList.resize(listEnd);
00700     }
00701 
00702     Integral flag = RANGE_IS_LISTED;
00703     if (valueList.size() == 0){
00704       flag = RANGE_IS_EMPTY;
00705     }
00706     else if (max_ >= min_){
00707       Integral allSize = max_ - min_ + 1;
00708       if (valueList.size() == allSize){
00709         flag = RANGE_INCLUDES_ALL;
00710         valueList.clear();
00711       }
00712     }
00713     valueList.push_back(flag);
00714   }
00715   entry->setValue(valueList);
00716 }
00717 
00719 // Parameter entry validator <-> XML conversion
00721 
00734 template <typename Integral>
00735 class IntegerRangeListValidatorXMLConverter : public Teuchos::ValidatorXMLConverter
00736 {
00737 
00738 public:
00739 
00740   RCP<Teuchos::ParameterEntryValidator> convertXML(
00741     const Teuchos::XMLObject& xmlObj,
00742     const Teuchos::IDtoValidatorMap& validatorIDsMap) const;
00743 
00744   void convertValidator(
00745     const RCP<const Teuchos::ParameterEntryValidator> validator,
00746     Teuchos::XMLObject& xmlObj,
00747     const Teuchos::ValidatortoIDMap& validatorIDsMap) const;
00748 
00749 #ifdef HAVE_TEUCHOS_DEBUG
00750 
00751   RCP<const Teuchos::ParameterEntryValidator> getDummyValidator() const{
00752     return Teuchos::DummyObjectGetter<IntegerRangeListValidator<Integral> >::getDummyObject();
00753   }
00754 #endif
00755 };
00756 
00757 template <typename Integral>
00758   RCP<Teuchos::ParameterEntryValidator>
00759    IntegerRangeListValidatorXMLConverter<Integral>::convertXML(
00760      const Teuchos::XMLObject& xmlObj, 
00761      const Teuchos::IDtoValidatorMap& /*validatorIDsMap*/) const
00762 {
00763   Integral minValue=0, maxValue=0;
00764   bool unsorted=false, hasMin=false, hasMax=false;
00765 
00766   if (xmlObj.hasAttribute(std::string("min"))) {
00767     minValue = xmlObj.getRequired<Integral>(std::string("min"));
00768     hasMin = true;
00769   }
00770 
00771   if (xmlObj.hasAttribute(std::string("max"))) {
00772     maxValue = xmlObj.getRequired<Integral>(std::string("max"));
00773     hasMax = true;
00774   }
00775 
00776   if (xmlObj.hasAttribute(std::string("unsorted"))) 
00777     unsorted = xmlObj.getRequired<bool>(std::string("unsorted"));
00778 
00779   RCP<Teuchos::ParameterEntryValidator> toReturn;
00780 
00781   if (hasMin && hasMax)
00782     toReturn = rcp(new IntegerRangeListValidator<Integral>(minValue, maxValue, unsorted));
00783   else if (!hasMin && !hasMax)
00784     toReturn = rcp(new IntegerRangeListValidator<Integral>(unsorted));
00785   else
00786     throw std::runtime_error("invalid XML representation");
00787 
00788   return toReturn;
00789 }
00790 
00791 template<typename Integral>
00792 void IntegerRangeListValidatorXMLConverter<Integral>::convertValidator(
00793   const RCP<const Teuchos::ParameterEntryValidator > validator,
00794   Teuchos::XMLObject& xmlObj,
00795   const Teuchos::ValidatortoIDMap& /*validatorIDsMap*/) const
00796 {
00797   RCP<const IntegerRangeListValidator<Integral> > castedValidator =
00798     rcp_dynamic_cast<const IntegerRangeListValidator<Integral> >(
00799       validator, true);
00800 
00801   Integral minValue = castedValidator->getAllowedMinimum();
00802   Integral maxValue = castedValidator->getAllowedMaximum();
00803   bool unsorted = castedValidator->inputListWillBeSorted();
00804 
00805   if (minValue < maxValue){
00806     xmlObj.addAttribute<Integral>(std::string("min"), minValue);
00807     xmlObj.addAttribute<Integral>(std::string("max"), maxValue);
00808   }
00809 
00810   xmlObj.addAttribute<bool>(std::string("unsorted"), unsorted);
00811 }
00812 
00813 }
00814  // end of namespace Zoltan2
00815 
00816 #endif