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