Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_IntegerRangeList.hpp
Go to the documentation of this file.
1 // @HEADER
2 //
3 // ***********************************************************************
4 //
5 // Zoltan2: A package of combinatorial algorithms for scientific computing
6 // Copyright 2012 Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Karen Devine (kddevin@sandia.gov)
39 // Erik Boman (egboman@sandia.gov)
40 // Siva Rajamanickam (srajama@sandia.gov)
41 //
42 // ***********************************************************************
43 //
44 // @HEADER
45 
50 #ifndef _ZOLTAN2_INTEGERRANGELIST_HPP_
51 #define _ZOLTAN2_INTEGERRANGELIST_HPP_
52 
53 #include <Zoltan2_config.h>
54 
55 #include <Teuchos_ParameterEntryValidator.hpp>
56 #include <Teuchos_ValidatorXMLConverter.hpp>
57 #include <Teuchos_XMLObject.hpp>
58 #include <Teuchos_ValidatorMaps.hpp>
59 #include <Teuchos_DummyObjectGetter.hpp>
60 #include <Teuchos_StrUtils.hpp>
61 
62 #ifdef _MSC_VER
63 // for isspace(int), else one gets isspace(_Elem _Ch, const locale& _Loc) from <locale>
64 #include <cctype>
65 #endif
66 
67 // Had to redefine this type from Teuchos_ParameterEntryValidator.hpp.
68 // Compiler stumbled on it.
69 typedef Teuchos::RCP<const Teuchos::Array<std::string> > ValidStringsList;
70 
71 namespace Zoltan2{
72 
76 enum RangeType {
81 };
82 
83 template <typename T> class IntegerRangeListValidator;
84 
86 // Helper functions for interpreting integer range list arrays.
88 
95 template <typename Integral>
96  bool validIntegralRangeList(const Teuchos::Array<Integral> &vals)
97 {
98  typedef typename Teuchos::Array<Integral>::size_type arraySize_t;
99  arraySize_t len = vals.size();
100  if (len==0)
101  return false;
102 
103  Integral flag = vals[len-1];
104  if ((flag != RANGE_INCLUDES_ALL) && (flag != RANGE_IS_EMPTY) &&
105  (flag != RANGE_IS_LISTED))
106  return false;
107 
108  return true;
109 }
110 
125 template <typename Integral>
126  bool allValuesAreInRangeList(const Teuchos::Array<Integral> &vals)
127 {
128  if (!validIntegralRangeList(vals))
129  throw std::runtime_error("list is not a valid range list");
130  return vals[vals.size()-1] == RANGE_INCLUDES_ALL;
131 }
132 
147 template <typename Integral>
148  bool allValuesAreInRangeList(const Teuchos::ParameterEntry &e)
149 {
150  if (!e.isType<Teuchos::Array<Integral> >())
151  throw std::runtime_error("Should not call until modified");
152 
153  Teuchos::Array<Integral> *valPtr=NULL;
154  Teuchos::Array<Integral> &vals = e.getValue(valPtr);
155  return allValuesAreInRangeList(vals);
156 }
157 
172 template <typename Integral>
173  bool noValuesAreInRangeList(const Teuchos::Array<Integral> &vals)
174 {
175  if (!validIntegralRangeList(vals))
176  throw std::runtime_error("list is not a valid range list");
177  return vals[vals.size()-1] == RANGE_IS_EMPTY;
178 }
179 
194 template <typename Integral>
195  bool noValuesAreInRangeList(const Teuchos::ParameterEntry &e)
196 {
197  if (!e.isType<Teuchos::Array<Integral> >())
198  throw std::runtime_error("Should not call until modified");
199 
200  Teuchos::Array<Integral> *valPtr=NULL;
201  Teuchos::Array<Integral> &vals = e.getValue(valPtr);
202  return noValuesAreInRangeList(vals);
203 }
204 
205 // TODO :
206 // inList(std::vector<Integral> &val, std::vector<bool> &result)
207 
219 template <typename Integral>
220  bool IsInRangeList(const Integral val, const Teuchos::Array<Integral> &valList, bool sorted=true)
221 {
222  if (allValuesAreInRangeList(valList))
223  return true;
224  else if (noValuesAreInRangeList(valList))
225  return false;
226 
227  if (sorted){
228  typename Teuchos::Array<Integral>::const_iterator flag = valList.end();
229  --flag;
230  if (std::binary_search(valList.begin(), flag, val))
231  return true;
232  else
233  return false;
234  }
235  else{
236  for (typename Teuchos::Array<Integral>::size_type i=0; i < valList.size()-1; i++){
237  if (valList[i] == val)
238  return true;
239  }
240  return false;
241  }
242 }
243 
254 template <typename Integral>
255  bool IsInRangeList(const Integral val, const Teuchos::ParameterEntry &e)
256 {
257  if (!e.isType<Teuchos::Array<Integral> >())
258  throw std::runtime_error("Should not call until modified");
259 
260  Teuchos::Array<Integral> *valPtr=NULL;
261  Teuchos::Array<Integral> &valList = e.getValue(valPtr);
262 
264  RCP<const irl_t> irl;
265  bool fail = false;
266 
267  RCP<const Teuchos::ParameterEntryValidator> valtor = e.validator();
268  if (!valtor.is_null()){
269  try{
270  irl = rcp_dynamic_cast<const irl_t>(valtor);
271  }
272  catch (...){
273  fail = true;
274  }
275  }
276  else{
277  fail = true;
278  }
279 
280  if (fail)
281  throw std::runtime_error("wrong type of parameter entry");
282 
283  bool sorted = irl->inputListWillBeSorted();
284 
285  return IsInRangeList(val, valList, sorted);
286 }
287 
296 template <typename Integral>
297  Teuchos::ArrayView<Integral> getList(Teuchos::Array<Integral> &irl)
298 {
299  Teuchos::ArrayView<Integral> av; // av.size() == 0
300 
303  av = irl.view(0, irl.size()-1); // skip last value, it's a flag
304 
305  return av;
306 }
307 
316 template <typename Integral>
317  void printIntegralRangeList(std::ostream &os, Teuchos::Array<Integral> &irl)
318 {
320  os << "all";
321  else if (Zoltan2::noValuesAreInRangeList(irl))
322  os << "empty";
323  else{
324  Teuchos::ArrayView<const Integral> view =
325  irl.view(0, irl.size()-1); // skip last value, it's a flag
326  os << view;
327  }
328 }
329 
331 // Validator class
333 
393 template <typename Integral>
394  class IntegerRangeListValidator : public Teuchos::ParameterEntryValidator
395 {
396 private:
397 
398 #ifndef DOXYGEN_SHOULD_SKIP_THIS
399 
400  Integral min_;
401  Integral max_;
402  bool unsorted_;
403 
404  static const std::string listDelim_;
405  static const std::string rangeDelim_;
406  static const std::string allText_;
407 
408  static void checkValid(char c);
409  static bool listSaysAll(std::string &l);
410  static int breakRange(std::string &range, std::string &from, std::string &to);
411 
412 #endif
413 
414 public:
420  IntegerRangeListValidator(bool unsorted=false);
421 
431  IntegerRangeListValidator(Integral validMin, Integral validMax,
432  bool unsorted=false);
433 
434  // Implementation of ParameterEntryValidator interface
435 
436  const std::string getXMLTypeName() const;
437 
438  void printDoc(std::string const& docString, std::ostream &out) const;
439 
441 
442  void validate( Teuchos::ParameterEntry const& entry,
443  std::string const& paramName, std::string const& sublistName
444  ) const;
445 
446  void validateAndModify( std::string const& paramName,
447  std::string const& sublistName, Teuchos::ParameterEntry * entry
448  ) const;
449 
450  // IntegerRangeListValidator methods
451 
457  Integral getAllowedMinimum() const { return min_;}
458 
464  Integral getAllowedMaximum() const { return max_;}
465 
472  bool inputListWillBeSorted() const { return !unsorted_;}
473 
474 }; // end class
475 
477 // Class definitions
479 
480 template <typename Integral>
481 const std::string IntegerRangeListValidator<Integral>::listDelim_(",");
482 
483 template <typename Integral>
484 const std::string IntegerRangeListValidator<Integral>::rangeDelim_("-");
485 
486 template <typename Integral>
487 const std::string IntegerRangeListValidator<Integral>::allText_("all");
488 
489 template <typename Integral>
490  void IntegerRangeListValidator<Integral>::checkValid(char c)
491 {
492  if (std::isspace(c) || std::isdigit(c) || (c == ',') || (c == '-'))
493  return;
494  else
495  throw std::runtime_error("invalid integer range list");
496 }
497 
498 template <typename Integral>
499  bool IntegerRangeListValidator<Integral>::listSaysAll(std::string &l)
500 {
501  std::transform(l.begin(), l.end(), l.begin(), (int(*)(int)) tolower);
502  if (l.find(allText_) != std::string::npos)
503  return true; // "all" is in the string
504  else
505  return false;
506 }
507 
508 template <typename Integral>
509  int IntegerRangeListValidator<Integral>::breakRange(
510  std::string &range, std::string &from, std::string &to)
511 {
512  from.clear();
513  to.clear();
514  std::string::size_type loc = range.find(rangeDelim_);
515  if (loc == std::string::npos){
516  from = range;
517  }
518  else{
519  from = range.substr(0, loc);
520  to = range.substr(loc+1, range.size());
521  }
522  long a, b;
523  std::istringstream iss1(from);
524  iss1 >> a;
525  b = a;
526  if (to.size() > 0){
527  std::istringstream iss2(to);
528  iss2 >> b;
529  if (b < a)
530  std::swap(from,to);
531  }
532  return (b != a) ? 2 : 1;
533 }
534 
535 
536 template <typename Integral>
538  bool unsorted): min_(1), max_(0), unsorted_(unsorted)
539 {
540 }
541 
542 template <typename Integral>
544  Integral validMin, Integral validMax, bool unsorted) :
545  min_(validMin), max_(validMax), unsorted_(unsorted)
546 {
547  if (min_ < max_) std::swap(min_,max_);
548 }
549 
550  // Implementation of ParameterEntryValidator interface
551 
552 template <typename Integral>
553  const std::string
555 {
556  std::string className("IntegerRangeListValidator");
557  std::string classType("("+Teuchos::TypeNameTraits<Integral>::name()+")");
558  return std::string(className + classType);
559 }
560 
561 template <typename Integral>
563  std::string const& docString, std::ostream &out) const
564 {
565  Teuchos::StrUtils::printLines(out,"# ",docString);
566  out << "#\tAn integer range list is a string which can contain:\n";
567  out << "#\t\tthe text \"all\", which indicates all values\n";
568  out << "#\t\ta list of integer ranges separated by commas.\n";
569  out << "#\tA range is one value, or two values separated by a dash.\n";
570  out << "#\tExample: \"all\" or \"1-10\" or \"3, 10-12\" or \"25\"\n";
571  if (max_ >= min_){
572  out << "#\tThe range of valid integers is [";
573  out << min_ << "," << max_ << "]\n";
574  }
575 }
576 
577 template <typename Integral>
579 {
580  return Teuchos::null;
581 }
582 
583 template <typename Integral>
585  Teuchos::ParameterEntry const& entry,
586  std::string const& /* paramName */, std::string const& /* sublistName */) const
587 {
588  if (!entry.isType<std::string>()){
589  return; // already converted to an an array
590  }
591  std::string *sptr=NULL;
592  std::string &rangeList = entry.getValue(sptr);
593  std::string inValue(rangeList);
594 
595  if (listSaysAll(inValue))
596  return; // "all" is in the string
597 
598  // throw error if invalid integer range list
599  std::for_each(inValue.begin(), inValue.end(), checkValid);
600 
601  if (max_ >= min_){
602  std::string::const_iterator rangeBegin = inValue.begin();
603  std::string::const_iterator valueEnd = inValue.end();
604 
605  while (rangeBegin != valueEnd){
606  std::string::const_iterator rangeEnd = std::search(
607  rangeBegin, valueEnd, listDelim_.begin(), listDelim_.end());
608  std::string range(rangeBegin, rangeEnd);
609  std::string aHalf, bHalf;
610  int count = breakRange(range, aHalf, bHalf);
611 
612  Integral a, b;
613  std::istringstream iss1(aHalf);
614  iss1 >> a;
615  if (count > 1){
616  std::istringstream iss2(bHalf);
617  iss2 >> b;
618  }
619  else
620  b = a;
621 
622  if ((a < min_) || (b > max_)){
623  std::ostringstream oss;
624  oss << "input range [" << a << "," << b << "] ";
625  oss << "exceeds valid range [" << min_ << "," << max_ << "] ";
626  throw std::runtime_error(oss.str());
627  }
628  if (rangeEnd == valueEnd)
629  rangeBegin = rangeEnd;
630  else
631  rangeBegin = ++rangeEnd;
632  }
633  }
634 }
635 
636 template <typename Integral>
638  std::string const& /* paramName */, std::string const& /* sublistName */,
639  Teuchos::ParameterEntry * entry) const
640 {
641  typedef typename Teuchos::Array<Integral>::size_type arraySize_t;
642  if (!entry->isType<std::string>()){
643  return;
644  }
645 
646  std::string *sptr=NULL;
647  std::string &rangeList = entry->getValue(sptr);
648  Teuchos::Array<Integral> valueList;
649 
650  std::string inValue(rangeList);
651 
652  if (listSaysAll(inValue)){
653  valueList.push_back(RANGE_INCLUDES_ALL);
654  }
655  else{
656  // throw error if invalid integer range list
657  std::for_each(inValue.begin(), inValue.end(), checkValid);
658 
659  std::string::const_iterator rangeBegin = inValue.begin();
660  std::string::const_iterator valueEnd = inValue.end();
661 
662  while (rangeBegin != valueEnd){
663  std::string::const_iterator rangeEnd = std::search(rangeBegin,
664  valueEnd, listDelim_.begin(), listDelim_.end());
665  std::string range(rangeBegin, rangeEnd);
666  std::string aHalf, bHalf;
667  int count = breakRange(range, aHalf, bHalf);
668 
669  Integral a, b;
670  std::istringstream iss1(aHalf);
671  iss1 >> a;
672  if (count > 1){
673  std::istringstream iss2(bHalf);
674  iss2 >> b;
675  }
676  else
677  b = a;
678 
679  if ((max_ >= min_) && ((a < min_) || (b > max_))){
680  std::ostringstream oss;
681  oss << "input range [" << a << "," << b << "] ";
682  oss << "exceeds valid range [" << min_ << "," << max_ << "] ";
683  throw std::runtime_error(oss.str());
684  }
685  for (Integral i=a; i <=b; i++)
686  valueList.push_back(i);
687  if (rangeEnd == valueEnd)
688  rangeBegin = rangeEnd;
689  else
690  rangeBegin = ++rangeEnd;
691  }
692  if (!unsorted_ && valueList.size() > 1){ // sort & remove duplicates
693  std::sort(valueList.begin(), valueList.end());
694  arraySize_t listEnd = 0;
695  arraySize_t length = valueList.size();
696  for (arraySize_t i=1; i < length; i++){
697  if (valueList[i] > valueList[listEnd]){
698  listEnd++;
699  if (listEnd != i)
700  valueList[listEnd] = valueList[i];
701  }
702  }
703  if (++listEnd < length)
704  valueList.resize(listEnd);
705  }
706 
707  Integral flag = RANGE_IS_LISTED;
708  if (valueList.size() == 0){
709  flag = RANGE_IS_EMPTY;
710  }
711  else if (max_ >= min_){
712  Integral allSize = max_ - min_ + 1;
713  if (valueList.size() == allSize){
714  flag = RANGE_INCLUDES_ALL;
715  valueList.clear();
716  }
717  }
718  valueList.push_back(flag);
719  }
720  entry->setValue(valueList);
721 }
722 
724 // Parameter entry validator <-> XML conversion
726 
739 template <typename Integral>
740 class IntegerRangeListValidatorXMLConverter : public Teuchos::ValidatorXMLConverter
741 {
742 
743 public:
744 
745  RCP<Teuchos::ParameterEntryValidator> convertXML(
746  const Teuchos::XMLObject& xmlObj,
747  const Teuchos::IDtoValidatorMap& validatorIDsMap) const;
748 
749  void convertValidator(
750  const RCP<const Teuchos::ParameterEntryValidator> validator,
751  Teuchos::XMLObject& xmlObj,
752  const Teuchos::ValidatortoIDMap& validatorIDsMap) const;
753 
754 #ifdef HAVE_TEUCHOS_DEBUG
755 
756  RCP<const Teuchos::ParameterEntryValidator> getDummyValidator() const{
757  return Teuchos::DummyObjectGetter<IntegerRangeListValidator<Integral> >::getDummyObject();
758  }
759 #endif
760 };
761 
762 template <typename Integral>
763  RCP<Teuchos::ParameterEntryValidator>
765  const Teuchos::XMLObject& xmlObj,
766  const Teuchos::IDtoValidatorMap& /*validatorIDsMap*/) const
767 {
768  Integral minValue=0, maxValue=0;
769  bool unsorted=false, hasMin=false, hasMax=false;
770 
771  if (xmlObj.hasAttribute(std::string("min"))) {
772  minValue = xmlObj.getRequired<Integral>(std::string("min"));
773  hasMin = true;
774  }
775 
776  if (xmlObj.hasAttribute(std::string("max"))) {
777  maxValue = xmlObj.getRequired<Integral>(std::string("max"));
778  hasMax = true;
779  }
780 
781  if (xmlObj.hasAttribute(std::string("unsorted")))
782  unsorted = xmlObj.getRequired<bool>(std::string("unsorted"));
783 
784  RCP<Teuchos::ParameterEntryValidator> toReturn;
785 
786  if (hasMin && hasMax)
787  toReturn = rcp(new IntegerRangeListValidator<Integral>(minValue, maxValue, unsorted));
788  else if (!hasMin && !hasMax)
789  toReturn = rcp(new IntegerRangeListValidator<Integral>(unsorted));
790  else
791  throw std::runtime_error("invalid XML representation");
792 
793  return toReturn;
794 }
795 
796 template<typename Integral>
798  const RCP<const Teuchos::ParameterEntryValidator > validator,
799  Teuchos::XMLObject& xmlObj,
800  const Teuchos::ValidatortoIDMap& /*validatorIDsMap*/) const
801 {
802  RCP<const IntegerRangeListValidator<Integral> > castedValidator =
803  rcp_dynamic_cast<const IntegerRangeListValidator<Integral> >(
804  validator, true);
805 
806  Integral minValue = castedValidator->getAllowedMinimum();
807  Integral maxValue = castedValidator->getAllowedMaximum();
808  bool unsorted = castedValidator->inputListWillBeSorted();
809 
810  if (minValue < maxValue){
811  xmlObj.addAttribute<Integral>(std::string("min"), minValue);
812  xmlObj.addAttribute<Integral>(std::string("max"), maxValue);
813  }
814 
815  xmlObj.addAttribute<bool>(std::string("unsorted"), unsorted);
816 }
817 
818 }
819  // end of namespace Zoltan2
820 
821 #endif
void validateAndModify(std::string const &paramName, std::string const &sublistName, Teuchos::ParameterEntry *entry) const
the listed values are in the Array&lt;int&gt;
Integral getAllowedMinimum() const
Return the minimum value permitted in the list.
XML conversion code for IntegerRangeListValidator.
RangeType
Codes that indicate how to interpret the Array&lt;int&gt; representing the user&#39;s integer range list...
void convertValidator(const RCP< const Teuchos::ParameterEntryValidator > validator, Teuchos::XMLObject &xmlObj, const Teuchos::ValidatortoIDMap &validatorIDsMap) const
A ParameterList validator for integer range lists.
dictionary vals
Definition: xml2dox.py:186
bool validIntegralRangeList(const Teuchos::Array< Integral > &vals)
A helper function that indicates whether an array is a valid integer range list.
Integral getAllowedMaximum() const
Return the maximum value permitted in the list.
bool IsInRangeList(const Integral val, const Teuchos::Array< Integral > &valList, bool sorted=true)
A helper function that determines if a value is in the list.
Teuchos::RCP< const Teuchos::Array< std::string > > ValidStringsList
static const std::string fail
void validate(Teuchos::ParameterEntry const &entry, std::string const &paramName, std::string const &sublistName) const
bool noValuesAreInRangeList(const Teuchos::Array< Integral > &vals)
A helper function that determines if no values are in the list.
IntegerRangeListValidator(bool unsorted=false)
Constructor: any Integral is valid.
void printIntegralRangeList(std::ostream &os, Teuchos::Array< Integral > &irl)
A helper function that prints the meaning of an encoded integer range list.
Teuchos::ArrayView< Integral > getList(Teuchos::Array< Integral > &irl)
A helper function that returns a view of the list.
bool inputListWillBeSorted() const
Return whether the list is sorted or not.
void printDoc(std::string const &docString, std::ostream &out) const
RCP< Teuchos::ParameterEntryValidator > convertXML(const Teuchos::XMLObject &xmlObj, const Teuchos::IDtoValidatorMap &validatorIDsMap) const
tuple paramName
Definition: xml2dox.py:207
bool allValuesAreInRangeList(const Teuchos::Array< Integral > &vals)
A helper function that determines if all values are in the list.