prom_options.hh

//  $Id: prom_options.hh,v 1.2 2004/01/27 21:15:54 adams Exp $
//  Author:             Mark F. Adams
// Copyright (c) 2000 by Mark F. Adams 
//  Filename:           prom_options.hh
//
#ifndef __PROM_OPTIONS_H__
#define __PROM_OPTIONS_H__

#if defined(PROM_USE_PETSC)
#define PROM_USE_PETSC_OPTIONS
#endif

#if defined(PROM_USE_PETSC_OPTIONS)

class PromOptions
{
public:
  PromOptions() : matrix_(FALSE), verbose_(FALSE), files_(FALSE) {}
  // methods
  int InsertOptions( int *argc, char ***argv, char *file ) {
    int ierr = PetscOptionsInsert( argc, argv, file ); CHKERRQ(ierr);
    return 0;
  }
  // methods
  int HasOptionName( const char name[], bool *flg ) const {
    PetscTruth f;
    int ierr = PetscOptionsHasName(PETSC_NULL,name,&f); CHKERRQ(ierr);
    *flg = (f == PETSC_TRUE);
    return 0;
  }
  //
  int GetOptionDouble(const char name[], double *dvalue, bool *flg)const{
    PetscTruth f;
    int ierr = PetscOptionsGetReal(PETSC_NULL,name,dvalue,&f); CHKERRQ(ierr);
    *flg = (f == PETSC_TRUE);
    return 0;
  }
  //
  int GetOptionInt( const char name[],int*ivalue, bool *flg)const{
    PetscTruth f;
    int ierr = PetscOptionsGetInt(PETSC_NULL,name,ivalue,&f); CHKERRQ(ierr);
    *flg = (f == PETSC_TRUE);
    return 0;
  }
  //
  int GetOptionString( const char name[], char string[],
                       int len, bool *flg ) const{
    PetscTruth f;
    int ierr = PetscOptionsGetString(PETSC_NULL,name,string,len,&f);
    CHKERRQ(ierr);
    *flg = (f == PETSC_TRUE);
    return 0;
  }
  int OptionsSetValue( const char iname[],const char value[] ) {
    int ierr = PetscOptionsSetValue( iname, value );  CHKERRQ(ierr);
    return 0;
  }
  // debug
  int print( int myproc = 0, FILE *file = stderr )const{
    int ierr = PetscOptionsPrint(file); CHKERRQ(ierr);
    return 0;
  }
  int verbose_;
  bool matrix_, files_;
};
#else 

#include <iostream.h>

#define void_error(s) { printf(s,__FILE__,__LINE__); exit(3); }

class String;
/* Int.h */
class Int
{
public:
  Int() : val_(0) {;}
  Int(int val) : val_(val) {;}
  int byteCount() const {return sizeof(int);}
  inline String toString() const ;
  int hashCode() const {return val_;}
  operator int () const {return val_;}
  bool operator==(const Int& other) const {return val_==other.val_;}
  bool operator==(const int& other) const {return val_==other;}
  bool operator<(const Int& other) const {return val_ < other.val_;}
  Int& operator+=(int i) {val_ += i; return *this;}
  friend Int& operator++(Int& x);
private:
  int val_;
};

/* Double.h */
class Double
{
public:
  Double() : val_(0.0) {;}
  Double(double val) : val_(val) {;}
  int byteCount() const {return sizeof(double);}
  inline String toString(int precision=16) const ;
  int hashCode() const {return (int) val_;}
  
  operator double () const {return val_;}
private:
  double val_;
};

/********************* Array.h *********************/
//#define NOBOUNDSCHECK
template<class T>
class Array {
public:
  inline Array();
  inline Array(int n); 
  inline Array(int n, const T* cArray);
  inline Array(int n, const T& t);
  // explicit copy ctor, dtor, and assign needed to prevent memory 
  // corruption
  inline ~Array();
  inline Array(const Array<T>& other);  
  inline const Array<T>& operator=(const Array<T>& other); 
  inline int length() const ;
  inline void resize(int newN);
  inline void reserve(int n); 
  inline int  reserve() const ;

  inline Array<T>& append(const T& rhs);
  inline T& operator[](int i);
  inline const T& operator[](int i) const;
  inline void remove(int i);

  inline int hashCode() const ;
  inline String toString() const ;
  inline int byteCount() const ;
private:
  T* data_;     
  int len_;     
  int reserve_; 
  
  int indexCheckCrash(int i) const;
  bool indexCheckNoCrash(int i) const;
};

/* Array utils.
   template<class T> ostream& operator<<(ostream& os, const Array<T>& array); 
   template<class T>
   Array<T> sliceArray(const Array<Array<T> >& array, int index);
   template<class T> Array<T> tuple(const T& a);
   template<class T> Array<T> tuple(const T& a, const T& b);
   template<class T> Array<T> tuple(const T& a, const T& b, const T& c);
   template<class T> 
   Array<T> tuple(const T& a, const T& b, const T& c, const T& d);
   template<class T> 
   Array<T> tuple(const T& a, const T& b, const T& c, const T& d, const T& e);
   template<class T> 
   Array<T> tuple(const T& a, const T& b, const T& c, const T& d, const T& e,
   const T& f); */

/* Array.inl */
// print in form (), (1), or (1,2)
template<class T> inline ostream& operator<<(ostream& os,const Array<T>& item) 
{
  const Array<T>& myItem = item;
  T myElem;
  
  os << "(";
  int ultimate = myItem.length()-1;        
  
  for (int i = 0; i < ultimate; ++i) {
    myElem = myItem[i];
    os << myElem;
    os << ", ";
  }
  if (ultimate >= 0)
    os << myItem[ultimate];
  os << ")";
  return os;
}

/*template<class T> inline int Array<T>::hashCode() const 
{
  int rtn = Int(len_).hashCode();
  for (int i=0; i<a.length(); i++)
    {
      rtn += (a[i]).hashCode();
    }
  return rtn;
  }*/

template<class T> inline int Array<T>::byteCount() const 
{
  int data = sizeof(Array<T>);
  for (int i=0; i<length(); i++)
    {
      data += (data_[i]).byteCount();
    }
  data += sizeof(T)*(reserve() - length());
  return data;
}

template<class T> inline String Array<T>::toString() const 
{
  String rtn = "{";
  
  for (int i=0; i<length(); i++)
    {
      rtn += (data_[i]).toString();
      if (i<length()-1) rtn += ", ";
    }
  rtn += "}";
  
  return rtn;
} 

template<class T> inline Array<T>::Array()
  : data_(0),
    len_(0), 
    reserve_(0)
{
}

template<class T> inline Array<T>::Array(int n)
  : data_(0),
    len_(n), 
    reserve_(n)
{
  if (len_ < 0)
    void_error("file %s line %d: Negative length passed to Array<T>::Array(int n)\n");
  if (len_ > 0) 
    {
      data_ = new T [len_];
      if (!data_)
        void_error("file %s line %d: Array constructor out of memory\n");
    }
}

template<class T> inline Array<T>::Array(int n, const T* cArray)
  : data_(0),
    len_(n),
    reserve_(n)
{
  if (len_ < 0)
    void_error("file %s line %d: Negative lenght passed to Array::Array(n, cArray)\n");
  if (len_ > 0)
    {
      data_ = new T [len_];
      if (!data_)
        void_error("file %s line %d: Array constructor out of memory\n");
    }
  for (int i = 0; i < len_; i++) data_[i] = cArray[i];
}

template<class T> inline Array<T>::Array(int n, const T& t)
  : data_(0),
    len_(n), 
    reserve_(n)
{
  if (len_ < 0)
    void_error("file %s line %d: Negative length passed to Array<T>::Array(int n)\n");
  if (len_ > 0) 
    {
      data_ = new T [len_];
      if (!data_)
        void_error("file %s line %d: Array constructor out of memory\n");
    }
  for (int i = 0; i < len_; ++ i) 
    data_[i] = t;
}

template<class T> inline  Array<T>::Array(const Array<T>& arr)
  : data_(0),
    len_(arr.len_), 
    reserve_(arr.len_)
{
  if (len_ > 0) 
    {
      data_ = new T [reserve_];
      if (!data_)
        void_error("file %s line %d: Array constructor out of memory\n");
      for (int i = 0; i < len_; ++i)
        data_[i] = arr.data_[i];
    }
}

template<class T>  Array<T>::~Array() 
{
  delete [] data_;
}

template<class T>  inline
const Array<T>& Array<T>::operator=(const Array<T>& arr) 
{
  if (this != &arr) 
    { // don't bother to assign if they're already identical
      if (reserve_ < arr.len_) 
        { //If the reserved space is too small to hold arr
          delete [] data_;
          data_ = 0;
          reserve_ = arr.len_;
          if (reserve_ > 0) {
            data_ = new T[reserve_];
            if (!data_)
              void_error("file %s line %d: Array constructor out of memory\n");
          }
        }
      len_ = arr.len_;
      for (int i = 0; i < len_; ++i)
        data_[i] = arr[i];
    }
  return *this;
}

inline int bump(int start, int finish) 
{
  if (finish < 10000)
    {
      if (start == 0)
        start = 1;
      while (start < finish)
        start *= 2;
      return start;
    }
  else
    {
      while (start < finish)
        {
          start += 10000;
        }
      return start;
    }
}

template<class T> inline
void Array<T>::resize(int newN) {
  if (len_ != newN) { // do not do anything if new size is not different
    if (newN < 0)
      void_error("file %s line %d: Negative length passed to Array<T>::resize(int newN)\n");
    if(newN > reserve_)
      reserve(bump(reserve_, newN));
    len_ = newN;
  }
}

template<class T> inline
void Array<T>::reserve(int N){
  if(reserve_ != N){
    if(N < 0){
      void_error("file %s line %d: Negative length passed to Array<T>::reserve(int N)\n");
    }
    if(N < len_){ len_ = N;}
    reserve_ = N;
    T* oldData = data_;
    data_ = 0;
    data_ = new T [reserve_];
    if (!data_)
      void_error("file %s line %d: Array<T>::reserve(int N) out of memory\n");
    for (int i = 0; i < len_; i++)
      data_[i] = oldData[i];
    delete [] oldData;
  }
}

template<class T> inline int Array<T>::reserve() const{
  return reserve_;
}

template<class T> inline Array<T>& Array<T>::append(const T& rhs) 
{
  resize(len_+1);
  data_[len_-1] = rhs;
  return *this;
}

template<class T> inline T& Array<T>::operator[](int i) {
#ifndef NOBOUNDSCHECK
  indexCheckCrash(i);
#endif
  return data_[i];
}

template<class T> inline const T& Array<T>::operator[](int i) const {
#ifndef NOBOUNDSCHECK
  indexCheckCrash(i);
#endif
  return data_[i];
}

template<class T> inline void Array<T>::remove(int i)
{
#ifndef NOBOUNDSCHECK
  indexCheckCrash(i);
#endif
  for (int j=i+1; j<length(); j++)
    {
      data_[j-1] = data_[j];
    }
  data_[len_-1] = T();
  len_--;
}

template<class T> inline int Array<T>::length() const {
  return len_;
}

template<class T> inline int Array<T>::indexCheckCrash(int i) const 
{
  assert(i>=0 && i<len_);  
  return 0;
}

template<class T> inline bool Array<T>::indexCheckNoCrash(int i) const 
{
  if (i<0 || i>=len_) return FALSE;
  return TRUE;
}

/* Array utils. */
template<class T> inline Array<T> sliceArray(const Array<Array<T> >& array,
                                             int index)
{
  Array<T> rtn(array.length());
  
  for (int i=0; i<array.length(); i++)
    {
      rtn[i] = array[i][index];
    }
  return rtn;
}

// utilities for building small arrays
template<class T> inline Array<T> tuple(const T& a)
{
  Array<T> rtn(1, a);
  return rtn;
}

template<class T> inline Array<T> tuple(const T& a, const T& b)
{
  Array<T> rtn(2);
  rtn[0] = a;
  rtn[1] = b;
  return rtn;
}

template<class T> inline Array<T> tuple(const T& a, const T& b, const T& c)
{
  Array<T> rtn(3);
  rtn[0] = a;
  rtn[1] = b;
  rtn[2] = c;
  return rtn;
}

template<class T> inline Array<T> tuple(const T& a, const T& b, const T& c,
                                        const T& d)
{
  Array<T> rtn(4);
  rtn[0] = a;
  rtn[1] = b;
  rtn[2] = c;
  rtn[3] = d;
  return rtn;
}

template<class T> inline Array<T> tuple(const T& a, const T& b, const T& c,
                                        const T& d, const T& e)
{
  Array<T> rtn(5);
  rtn[0] = a;
  rtn[1] = b;
  rtn[2] = c;
  rtn[3] = d;
  rtn[4] = e;
  return rtn;
}

template<class T> inline Array<T> tuple(const T& a, const T& b, const T& c,
                                        const T& d, const T& e, const T& f)
{
  Array<T> rtn(6);
  rtn[0] = a;
  rtn[1] = b;
  rtn[2] = c;
  rtn[3] = d;
  rtn[4] = e;
  rtn[5] = f;
  return rtn;
}

/********************* String.h *********************/
class String
{
 public:
  inline String();
  inline String(char c);
  inline String(const char* str);
  inline String(const char* str, int len);
  // Non-default copy ctor, assignment, and dtor must be defined.
  inline String(const String& other);
  inline ~String();
  inline String& operator=(const String& other);
  
  inline const char* cString() const ;
  inline int length() const ;
  
  inline const char& operator[](int i) const ;
  inline char& operator[](int i) ;
  
  inline bool operator==(const String& other) const ;
  inline bool operator!=(const String& other) const ;
  inline bool operator<(const String& other) const ;
  inline String& operator+=(const String& other);
  inline String operator+(const String& other) const ;
  inline String operator+(const int& x) const ;
  inline String operator+(const double& x) const ;
  
  inline bool contains(char c) const ;
  
  inline int find(const char* sub) const ;
  inline int find(const String& sub) const ;
  
  inline String before(const char* sub) const ;
  inline String before(const String& sub) const ;
  
  inline String after(const char* sub) const ;
  inline String after(const String& sub) const ;
  
  inline String beforeToken(const String& tokens) const ;
  inline String between(const String& begin, const String& end, 
                 String& front, String& back) const ;
  inline String subString(int begin, int end) const ;
  // conversion to all capital characters
  inline String allCaps() const ;
  // find out if string has any non-whitespace chars
  inline bool isWhite() const ;
  inline bool hasNonWhite() const ;
  
  /*
   * Return a String minus any initial whitespace contained in this String 
   */
  inline String trimInitialWhitespace() const ;

  inline static String readFromStream(istream& is);
  
  inline int hashCode() const ;
  inline String toString() const {return *this;}
  inline int byteCount() const ;
  
  inline int atoi() const;
  inline double atof() const ;
  inline bool atob() const ;
private:
  inline int indexcheck(int i) const ;
  inline int init(const char* str, int n);
  
  // pointer to beginning of string
  char* str_;
};

/* String.cpp */ 
inline ostream& operator<<(ostream& os, const String& str)
{
  os << str.cString();
  return os;
}

inline String operator+(const char* a, const String& b)
{
  return String(a)+b;
}

inline istream& operator>>(istream& is, String& str)
{
  str = String::readFromStream(is);
  return is;
} 

inline int findNextNonWhitespace(const String& str, int offset)
{
  for (int i=0; i<(str.length()-offset); i++)
    {
      if (!(str[i+offset]==' ' || str[i+offset]=='\t' || str[i+offset]=='\n'))
        {
          return i+offset;
        }
    }
  return str.length();
}

inline int atoi(const String& s) {return s.atoi();}
inline bool atob(const String& s) {return s.atob();}
inline double atof(const String& s) {return s.atof();}

/* String.h */
inline String::~String()
{
  delete [] str_;
}
inline const char* String::cString() const
{
  return str_;
}

inline int String::length() const
{
  return strlen(str_);
}

inline int String::byteCount() const 
{
  return length() + 1;
}

inline const char& String::operator[](int i) const
{
#ifndef NOBOUNDSCHECK
        indexcheck(i);
#endif
        return str_[i];
}

inline char& String::operator[](int i) 
{
#ifndef NOBOUNDSCHECK
  indexcheck(i);
#endif
  return str_[i];
}

inline bool String::operator==(const String& other) const
{
  return strcmp(str_, other.str_) == 0;
}

inline bool String::operator!=(const String& other) const
{
  return !(operator==(other));
}

inline bool String::operator< (const String& other) const 
{
  return (0 > strcmp(str_, other.str_));
}

inline String::String()
  : str_(0)
{
  str_ = new char[1];
  if (str_==0) void_error("%s line %d: String::String()\n");
  str_[0] = '\0';
}

inline String::String(char c)
  : str_(0)
{
  if (c=='\0')
    {
      str_ = new char[1];
      if (str_==0) void_error("%s line %d: String::String(char c)\n");
      str_[0] = c;
    }
  else
    {
      str_ = new char[2];
      if (str_==0) void_error("%s line %d: String::String(char c)");
      str_[0] = c;
      str_[1] = '\0';
    }
}

inline String::String(const char* str)
  : str_(0)
{
  if (str==0) void_error("%s line %d: String::String(const char* str) null argument");
  int len = strlen(str);
  init(str, len);
}

inline String::String(const char* str, int n)
  :     str_(0)
{
  init(str, n);
  str_[n] = '\0';
}

inline String::String(const String& other)
  : str_(0)
{
  init(other.cString(), other.length());
}

inline String String::readFromStream(istream& is)
{
  String rtn;
  char c;
  
  bool empty = TRUE;
  while (is.get(c))
    {
      if (isspace(c)) 
        {
          if (empty) continue;
          else break;
        }
      rtn += c;
      empty = FALSE;
    }
  
  return rtn;
}
        
inline String& String::operator=(const String& other) 
{
  if (*this != other)
    {
      delete [] str_;
      init(other.str_, other.length());
    }
  return *this;
}

inline int String::init(const char* str, int n)
{
  str_ = new char[n+1];
  if (str_==0) SETERRQ(1,"String::init");
  strncpy(str_, str, n+1);
  return 0;
}

inline String& String::operator+=(const String& other)
{
  if (other.length()==0) return *this;
  
  String tmp(str_);
  delete [] str_;
  str_ = new char[tmp.length() + other.length() + 1];
  if (str_==0) void_error("%s line %d: String::operator+=())");
  strcpy(str_, tmp.cString());
  strcat(str_, other.cString());
  
  return *this;
}

inline String String::operator+(const String& other) const 
{
  String rtn(*this);
  rtn += other;
  return rtn;
}

inline String String::operator+(const int& x) const 
{
  String rtn(*this);
  rtn += Int(x).toString();
  return rtn;
}

inline String String::operator+(const double& x) const 
{
  String rtn(*this);
  rtn += Double(x).toString();
  return rtn;
}

inline String operator+(const int& x, const String& s) 
{
  return Int(x).toString() + s;
}

inline String operator+(const double& x, const String& s) 
{
  return Double(x).toString() + s;
}

inline bool String::contains(char c) const
{
  char* p = strchr(str_, c);
  if (p==0) return FALSE;
  return TRUE;
}

inline int String::find(const char* sub) const
{
  char* p = strstr(str_, sub);
  if (p==0) return -1;
  return p-str_;
}

inline int String::find(const String& sub) const
{
  return find(sub.cString());
}

inline String String::subString(int begin, int end) const
{
  return String(str_+begin, end-begin);
}

inline String String::before(const char* sub) const
{
  if (sub==0) void_error("%s line %d: String::before: arg is null pointer");
  char* p = strstr(str_, sub);
  if (p==0) return *this;
  int subLen = p-str_;
  String rtn(str_, subLen);
  return rtn;
}

inline String String::before(const String& sub) const
{
  return before(sub.cString());
}

inline String String::after(const char* sub) const
{
  if (sub==0) void_error("%s line %d: String::after: arg is null pointer");
  // find beginning of substring
  char* p = strstr(str_, sub) ;
  // if substring not found, return empty string
  if (p==0) return String();
  // offset to end of substring
  p+= strlen(sub);
  return String(p);
}

inline String String::after(const String& sub) const 
{
  return after(sub.cString());
}

inline String String::beforeToken(const String& tokens) const
{
  String rtn = *this;
  int minLen = length();
  
  for (int i=0; i<tokens.length(); i++)
    {
      String tok = tokens[i];
      String test = before(tok);
      if (minLen > test.length()) 
        {
          rtn = test;
          minLen = test.length();
        }
    }
  
  return rtn;
}

inline String String::between(const String& begin, const String& end,
                       String& front, String& back) const
{
  front = before(begin);
  String middle = after(begin).before(end);
  back = after(end);
  return middle;
}

inline int String::indexcheck(int i) const
{
  if (i<0 || i>=(int) strlen(str_)) 
    SETERRQ3(1,"String::indexcheck %d %d %d", i, 0, strlen(str_));
  return 0;
}

inline String String::allCaps() const 
{
  int len = length();
  String newstr;
  
  if (len !=0)
    {
      
      for (int i = 0; i < len; i++)
        {
          int temp = (int) str_[i];
          if ( (temp >= 'a') && ( temp <= 'z') )
            temp = 'A' + (temp - 'a');
          String ch((char) temp);
          newstr += ch;
        }
      return newstr;
    }
  else return *this;
}

inline bool String::hasNonWhite() const
{
  // look for non-white characters
  int n = (int) strcspn(str_, " \n\t\r");
  if (n==0) return FALSE;
  return TRUE;
}

inline bool String::isWhite() const
{
  return !hasNonWhite();
}

inline String String::trimInitialWhitespace() const
{
  int offset = 0 ;
  int start = findNextNonWhitespace(*this, offset);
  return str_ + start;
}

inline int String::hashCode() const 
{
  int len = length();
  int step = len/4 + 1;
  int base = 1;
  int rtn = 0;
  
  for (int i=0; i<len/2; i+=step)
    {
      rtn += base*(int) str_[i];
      base *= 128;
      rtn += base*(int) str_[len-i-1];
      base *= 128;
    }
  
  return rtn;
}

inline int String::atoi() const 
{
  return ::atoi(cString());
}

inline double String::atof() const 
{
  return ::atof(cString());
}

inline bool String::atob() const 
{
  if (allCaps() == "TRUE")
    {
      return TRUE;
    }
  else return FALSE;
}


/******************** RBTreeNode.h *********************/
enum RBColor {RBRed, RBBlack};

template<class Key, class Value> class RBTreeNode
{
public:
   inline RBTreeNode(const Key& key, const Value& value,
              RBTreeNode<Key, Value>* parent, RBColor color);
   inline ~RBTreeNode();
   inline RBTreeNode<Key, Value>* clone() const ;
  
  // printing, with variable verboseness.
  inline void inorderPrint(ostream& os, bool debug) const ;
  // verbose printing.
  inline void debugPrint(ostream& os) const ;
  // laconic printing.
  inline void print(ostream& os) const ;
  
  // traversal functions.
  inline const RBTreeNode<Key, Value>* minimum() const ;
  inline const RBTreeNode<Key, Value>* maximum() const ;
  inline const RBTreeNode<Key, Value>* successor() const ;
  
  // some geneological operations that will be needed in 
  // balancing.
  inline bool isLeftChild() const ;
  inline RBTreeNode<Key, Value>* grandparent() const ;

  // data members are public. They should be used only by RBTRee.
  Key key_;
  Value value_;
  RBColor color_;
  RBTreeNode<Key, Value>* parent_;
  RBTreeNode<Key, Value>* left_;
  RBTreeNode<Key, Value>* right_;

private:
  // copy ctor and assignment are private. 
  // The copy ctor should be called only by clone().
  // The assignment op should never be called. It is left undefined
  // and made private to prevent accidental use.
  inline RBTreeNode(const RBTreeNode<Key,Value>& other);
  inline const RBTreeNode<Key,Value>& 
  operator=(const RBTreeNode<Key,Value>& other);
};

/* RBTreeNode.h */
// Constructor: insert (key, value), assign a color, and link to a parent.
template<class Key, class Value> inline
RBTreeNode<Key, Value>::RBTreeNode(const Key& key, const Value& value,
                                   RBTreeNode<Key, Value>* parent, 
                                   RBColor color)
  : key_(key),
    value_(value),
    color_(color),
    parent_(parent),
    left_(0),
    right_(0)
{
  ;
}

// Make a copy by copying the left and right subtrees as well as the data
// fields. Don't set the parent here; the calling code is responsible for
// registering the new parent with this node.
template<class Key, class Value> inline
RBTreeNode<Key, Value>::RBTreeNode(const RBTreeNode<Key,Value>& other)
  : key_(other.key_),
    
    value_(other.value_),
    color_(other.color_),
    parent_(0),
    left_(0),
    right_(0)
{
  if (other.left_ != 0)
    {
      left_ = other.left_->clone();
    }
  if (other.right_ != 0)
    {
      right_ = other.right_->clone();
    }
  // don't clone the parent. It will have to be set later.
}

// destructor: just delete the left and right subtrees.
template<class Key, class Value> inline
RBTreeNode<Key, Value>::~RBTreeNode() 
{
  delete left_;
  delete right_;
}

// Make a copy of the node and its subtrees.
// Register the copy node as the parent of the copy subtrees.
template<class Key, class Value> inline
RBTreeNode<Key,Value>* RBTreeNode<Key, Value>::clone() const 
{
  RBTreeNode<Key,Value>* result = new RBTreeNode<Key,Value>(*this);
  if (result == 0) 
    void_error("RBTreeNode<Key, Value>::clone() out of memory");
  if (result->left_ != 0)
    {
      result->left_->parent_ = result;
    }
  if (result->right_ != 0)
    {
      result->right_->parent_ = result;
    }
  
  return result;
}

// RBTreeNode* mininum()
// Find the pointer to the leftmost child. This is easy: at every node, 
// just walk left.

template<class Key, class Value>  inline
const RBTreeNode<Key, Value>* RBTreeNode<Key, Value>::minimum() const 
{
  const RBTreeNode<Key, Value>* minPtr = this;
  while (minPtr->left_ != 0)
    {
      minPtr = minPtr->left_;
    }
  return minPtr;
}

// RBTreeNode* maximum()
// Find the pointer to the rightmost child. This is easy: at every node, 
// just walk right.

template<class Key, class Value>  inline
const RBTreeNode<Key, Value>* RBTreeNode<Key, Value>::maximum() const 
{
  const RBTreeNode<Key, Value>* maxPtr = this;
  while (maxPtr->right_ != 0)
    {
      maxPtr = maxPtr->right_;
    }
  return maxPtr;
}

// RBTreeNode* successor()
// Find the pointer to the next-highest-keyed node.
// There are two possibilities:
// (1) There is a right child tree. Then, find the minimum
// of the right child subtree.
// (2) There is no right child tree. In that case, walk back up the tree
// until we find the node of which this branch is a left subtree.
template<class Key, class Value>  inline
const RBTreeNode<Key, Value>* RBTreeNode<Key, Value>::successor() const 
{
  if (right_ != 0)
    {
      return right_->minimum();
    }
  const RBTreeNode<Key, Value>* y = parent_;
  const RBTreeNode<Key, Value>* x = this;
  
  while (y != 0 && x==y->right_)
    {
      x = y;
      y = y->parent_;
                }
  return y;
}

template<class Key, class Value>  inline
bool RBTreeNode<Key, Value>::isLeftChild() const
{
  if (parent_->left_ == this) return TRUE;
  return FALSE;
}

template<class Key, class Value>  inline
RBTreeNode<Key, Value>* RBTreeNode<Key, Value>::grandparent() const 
{
  return parent_->parent_;
}

// Print nodes in order of keys. 
// If debug==TRUE, do a print of everything including pointers.
// If debug==FALSE, just print (key, value) pairs.
template<class Key, class Value> inline
void RBTreeNode<Key, Value>::inorderPrint(ostream& os, bool debug) const 
{
  if (left_) 
    {
      left_->inorderPrint(os, debug);
    }
  if (debug) debugPrint(os);
  else print(os);
  
  if (right_) 
    {
      if (!debug) os << ", ";
      right_->inorderPrint(os, debug);
    }
}

// Print everything including pointers.
template<class Key, class Value> inline
void RBTreeNode<Key, Value>::debugPrint(ostream& os) const 
{
  os << "P=" << parent_ 
     << " This=" << this 
     << " L=" << left_ 
     << " R=" << right_
     << " c=" << (int) color_ 
     << " data=(" << key_ 
     << ", " 
     << value_ << ")" << endl;
}

// Print just the key and value
template<class Key, class Value> inline
void RBTreeNode<Key, Value>::print(ostream& os) const 
{
  os << "(" << key_ 
     << ", " 
     << value_ << ")";
}

/* RBTree.h */
template<class Key, class Value> class RBTree
{
public:
  inline RBTree();
  inline RBTree(const RBTree<Key, Value>& other);
  inline ~RBTree();
  inline const RBTree<Key, Value>& operator=(const RBTree<Key, Value>& other);
  
  int size() const {return count_;}
  inline const Value& get( const Key& key ) const ;
  inline bool get( const Key& key, Value& value ) const ;
  inline bool containsKey( const Key& key ) const ;
  inline bool put( const Key& key, const Value& value );
  
  inline ostream& print(ostream& os, bool debug=TRUE) const ;
  // void arrayify(Array<Key>& keys, Array<Value>& values) const ;
  // Array<Key> arrayifyKeys() const ;
  // Array<Value> arrayifyValues() const ;
private:        
  inline const RBTreeNode<Key, Value>* minimum() const ;
  inline const RBTreeNode<Key, Value>* maximum() const ;
  inline int rotateLeft(RBTreeNode<Key, Value>* pivot);
  inline int rotateRight(RBTreeNode<Key, Value>* pivot);
  inline const RBTreeNode<Key, Value>* pointerTo(const Key& key) const ;
  inline RBTreeNode<Key, Value>* rawInsert(const Key& key, const Value& value);

  RBTreeNode<Key, Value>* root_;
  int count_;
  Key cacheKey_;
  Value cacheValue_;
};

/* RBTree.h */
//----------------------- implementation -----------------------------------

template<class Key, class Value> inline RBTree<Key, Value>::RBTree()
  : root_(0), 
  count_(0), 
  cacheKey_(), 
  cacheValue_()
{
  ;
}

template<class Key, class Value> inline
RBTree<Key, Value>::RBTree(const RBTree<Key, Value>& other) :
  root_(0), 
  count_(0), 
  cacheKey_(other.cacheKey_), 
  cacheValue_(other.cacheValue_)
{
  if (other.root_ != 0) 
    {
      root_ = other.root_->clone();
      if (root_==0) void_error("file %s line %d: RBTree copy ctor\n");
      count_ = other.count_;
    }
}

template<class Key, class Value>  inline RBTree<Key, Value>::~RBTree()
{
  delete root_;
}

template<class Key, class Value> inline
const RBTree<Key, Value>& RBTree<Key, Value>::operator=
(const RBTree<Key, Value>& other) 
{
  if (this != &other) 
    {
      cacheKey_ = other.cacheKey_;
      cacheValue_ = other.cacheValue_;
      if (root_)
        {
          delete root_;
          root_ = 0;
        }
      if (other.root_ != 0) 
        {
          root_ = other.root_->clone();
          if (root_==0) void_error("file %s line %d: RBTree copy ctor\n");
          count_ = other.count_;
        }
    }
  return *this;
}

// -------------------------------------------------------------------------
//
//     Insertion: put() and rawInsert()
//
//--------------------------------------------------------------------------


// rawInsert() sticks a node into the tree without regard to red/black 
// coloring. put() does a raw insert, followed by recoloring and rotations
// for balance.

template<class Key, class Value> inline
RBTreeNode<Key, Value>* RBTree<Key, Value>::rawInsert(const Key& key, 
                                                      const Value& value)
{
  count_++;
  // If this is the first entry into the tree, root_ will not exist. 
  // In that case, create root with a null parent.
  if (root_==0) 
    {
      root_ = new RBTreeNode<Key, Value>(key, value, 0, RBRed);
      return root_;
    }
  
  // Otherwise, begin at root and do an ordered search for a place to fit
  // the new node.
  
  RBTreeNode<Key, Value>* newParent = 0 ;
  RBTreeNode<Key, Value>* newPtr = root_;
  
  // Compare to key at each node along path, and go left/right accordingly.
  // At each turn, keep track of whether the turn was left or right; that 
  // will be needed in the final step.
  bool lastWasLeft = FALSE;
  while (newPtr != 0)
    {
      newParent = newPtr;
      if (key < newPtr->key_)
        {
          newPtr = newPtr->left_;
          lastWasLeft = TRUE;
        }
      else if (key == newPtr->key_)
        {
          count_--;
          newPtr->value_ = value;
          return newPtr;
        }
      else
        {
          newPtr = newPtr->right_;
          lastWasLeft = FALSE;
        }
    }
  
  // OK, we've found a location for the new node.
  // Create a node object, and inform the parent that it has a new
  // left or right child.
  RBTreeNode<Key, Value>* newNode 
    = new RBTreeNode<Key, Value>(key, value, newParent, RBRed);
  if (lastWasLeft)
    {
      newParent->left_ = newNode;
    }
  else
    {
      newParent->right_ = newNode;
    }
  
  // all done; return a ptr to the newly created node.
  return newNode;
}

// put(). Do a rawInsert(), then fix up balance.
template<class Key, class Value>  inline
bool RBTree<Key, Value>::put(const Key& key, const Value& value) 
{
  // stick the new node in, coloring it red.
  RBTreeNode<Key, Value>* x = rawInsert(key, value);
  if (x==0) return FALSE;
  
  // now fix up the RB state of the tree.
  
  while (x != root_ && x->parent_ != 0 && x->parent_->color_ == RBRed)
    {
      if (x->grandparent() == 0) void_error("file %s line %d: RBTree::put() null grandparent discovered\n");
      if (x->parent_->isLeftChild())
        {
          RBTreeNode<Key, Value>* y = x->grandparent()->right_;
          if (y!=0  && y->color_ == RBRed)
            {
              x->parent_->color_ = RBBlack;
              y->color_ = RBBlack;
              x->grandparent()->color_ = RBRed;
              x = x->grandparent();
            }
          else if (!x->isLeftChild())
            {
              x = x->parent_;
              rotateLeft(x);
            }
          else
            {
              x->parent_->color_ = RBBlack;
              x->grandparent()->color_ = RBRed;
              rotateRight(x->grandparent());
            }
        }
      else
        {
          RBTreeNode<Key, Value>* y = x->grandparent()->left_;
          if (y!=0 && y->color_ == RBRed)
            {
              x->parent_->color_ = RBBlack;
              y->color_ = RBBlack;
              x->grandparent()->color_ = RBRed;
              x = x->grandparent();
            }
          else if (x->isLeftChild())
            {
              x = x->parent_;
              rotateRight(x);
            }
          else
            {
              x->parent_->color_ = RBBlack;
              x->grandparent()->color_ = RBRed;
              rotateLeft(x->grandparent());
            }
        }
    }
  
  root_->color_ = RBBlack;
  return TRUE;
}

template<class Key, class Value>  inline
const RBTreeNode<Key, Value>* RBTree<Key, Value>::minimum() const 
{
  if (root_==0) return 0;
  else return root_->minimum();
}

template<class Key, class Value>  inline
const RBTreeNode<Key, Value>* RBTree<Key, Value>::maximum() const 
{
  if (root_==0) return 0;
  else return root_->maximum();
}

template<class Key, class Value>  inline
const RBTreeNode<Key, Value>* RBTree<Key, Value>::pointerTo(const Key& key) const 
{
  RBTreeNode<Key, Value>* tryPtr = root_;
  
  /* 
     This code is generating a possibly uninitialized variable error at the
     highest optimization levels.
  */
  while (tryPtr != 0)
    {
      if (tryPtr->key_ == key) return tryPtr;
      if (key < tryPtr->key_) 
        {
          tryPtr = tryPtr->left_;
        }
      else 
        {
          tryPtr = tryPtr->right_;
        }
    }
  return tryPtr;
}

template<class Key, class Value>  inline
bool RBTree<Key, Value>::containsKey(const Key& key) const 
{
  const RBTreeNode<Key, Value>* ptr = pointerTo(key);
  if (ptr==0) return FALSE;
  (Key&) cacheKey_ = key;
  (Value&) cacheValue_ = ptr->value_;
  return TRUE;
}

template<class Key, class Value>  inline
const Value& RBTree<Key, Value>::get(const Key& key) const 
{
  if (!containsKey(key)) void_error("file %s line %d: RBTree::get() key not found\n");
  return cacheValue_;
}

template<class Key, class Value>  inline
bool RBTree<Key, Value>::get(const Key& key, Value& value) const 
{
  const RBTreeNode<Key, Value>* ptr = pointerTo(key);
  if (ptr==0) return FALSE;
  value = ptr->value_;
  return TRUE;
}

template<class Key, class Value>  inline
ostream& RBTree<Key, Value>::print(ostream& os, bool debug) const 
{
  if (root_!=0) root_->inorderPrint(os, debug);
  return os;
}

template<class Key, class Value> inline
ostream& operator<<(ostream& os, const RBTree<Key, Value>& t)
{
  return t.print(os, FALSE);
}

//-------------------------------------------------------------------------
//
//                      Rotations

template<class Key, class Value>  inline
int RBTree<Key, Value>::rotateLeft(RBTreeNode<Key, Value>* x)
{
  // check for bad input; failure indicates a logic error in the 
  // red-black balancing code.
  if (x==0) SETERRQ(1,"RBTree::rotateLeft input error: x = nil. This should never happen, and indicates a bug in the tree balancing code.");
  if (x->right_ == 0) SETERRQ(1,"RBTree::rotateLeft input error:  x->right = nil. This should never happen, and indicates a bug in the tree balancing code.");
  RBTreeNode<Key, Value>* y = x->right_;

  // attach left subtree of y to right side of x. 
  x->right_ = y->left_;
  // notify the former left subtree of y that it is now a subtree of x.
  if (y->left_ != 0) y->left_->parent_ = x;
  
  // link x's former parent to y.
  y->parent_ = x->parent_;
  
  // if x was root, set root to y.
  if (x->parent_ == 0)
    {
      root_ = y;
    }
  // otherwise, tell x's former parent about y.
  else if (x == x->parent_->left_)
    {
      x->parent_->left_ = y;
    }
  else
    {
      x->parent_->right_ = y;
    }
  
  // attach x to y's left
  y->left_ = x;
  // inform x that y is now its parent.
  x->parent_ = y;

  return 0;
}
        
template<class Key, class Value>  inline
int RBTree<Key, Value>::rotateRight(RBTreeNode<Key, Value>* x)
{
  // check for bad input; failure indicates a logic error in the 
  // red-black balancing code.
  if (x==0) SETERRQ(1,"RBTree::rotateRight input error: x = nil. This should never happen, and indicates a bug in the tree balancing code.");
  if (x->left_ == 0) SETERRQ(1,"RBTree::rotateRight input error:  x->left = nil. This should never happen, and indicates a bug in the tree balancing code.");

  RBTreeNode<Key, Value>* y = x->left_;
  
  // attach right subtree of y to left side of x. 
  x->left_ = y->right_;
  // notify the former right subtree of y that it is now a subtree of x.
  if (y->right_ != 0) y->right_->parent_ = x;

  // link x's former parent to y.
  y->parent_ = x->parent_;
  
  // if x was root, set root to y.
  if (x->parent_ == 0)
    {
      root_ = y;
    }
  // otherwise, tell x's former parent about y.
  else if (x == x->parent_->right_)
    {
      x->parent_->right_ = y;
    }
  else
    {
      x->parent_->left_ = y;
    }
  
  // attach x to y's right
  y->right_ = x;
  // inform x that y is now its parent.
  x->parent_ = y;

  return 0;
}


/* CommandLine.h */
/* class PromOptions ********************************************************
 * BUGS/FEATURES:
 * 
 * If for some strange reason a key appears twice, e.g. 
 *    myCode -pi 3.14 -pi 2.72
 * the second value wins. 
 *
 * Everything crashes if you try to call init() twice. I'd rather have
 * a crash than the possibility of inconsistent results. 
 *
 *      If you forget to call init() and then call one of the CommandLine 
 * functions, everything crashes. 
 *
 */
class PromOptions
{
public:
  inline PromOptions() : matrix_(FALSE), verbose_(FALSE), files_(FALSE) {}
  // 
  int InsertOptions( int *, char ***, char * );
  int HasOptionName(const char name[], bool *flg)const {
    *flg = find( String(name) );
    return 0;
  }
  //
  int GetOptionDouble(const char name[],double *dvalue,bool *flg)const{
    double val;
    *flg = findDouble( String(name), val );
    if( *flg ) *dvalue = val;
    return 0;
  }
  //
  int GetOptionInt(const char name[], int *ivalue, bool *flg) const {
    int val;
    *flg = findInt( String(name), val );
    if( *flg ) *ivalue = val;
    return 0;
  }
  //
  int GetOptionString( const char name[], char string[], int len,
                       bool *flg ) const {
    String val(len);
    *flg = findString( String(name), val );
    if( strlen(val.cString()) >= len ) SETERRQ(1,"string buffer too short");
    strcpy(string,val.cString());

    return 0;
  }
  int OptionsSetValue( const char iname[], const char value[] ) {
    int ntok = tokens_.length();
    if( iname != NULL && iname[0] != '\0' ){
      int ii = 1;
      if( value != NULL && value[0] != '\0' ) ii++;
      tokens_.resize(ntok+ii);
      tokens_[ntok] = String( iname );
      tokenMap_.put( tokens_[ntok], ntok );
#if defined(PROM_HAVE_PETSc)
      if( strcmp(iname,"-log_info") == 0 || strcmp(iname,"-trmalloc") ||
          strcmp(iname,"-trdump") ){
        int ierr = PetscOptionsSetValue( iname, "" );  CHKERRQ(ierr);
      }
#endif
      if( ii == 2 ) {
        ntok++;
        if( value != NULL ) tokens_[ntok] = String( value );
        else tokens_[ntok] = String( "" );
        tokenMap_.put( tokens_[ntok], ntok );
      }
    }
    return 0;
  }
  inline int print(int myproc = 0, FILE *file=stderr)const;
  inline bool findString(const String& str, String& val) const;
  inline void debugPrint()const{ 
    //tokens_.print(cout);
    tokenMap_.print(cout);
  } 
private:
  inline bool find(const String& str) const;
  inline bool find(const String& str, int& position) const;
  inline bool findDouble( const String& str, double& val ) const;
  inline bool findInt(const String& str, int& val) const;
  inline bool findInt(const String& str, Array<int>& val,
               int count) const;
  inline int checkInitialization()const;
  // data
  Array<String> tokens_;
  RBTree<String, int> tokenMap_;
public:
  bool matrix_, files_;
  int verbose_;
};

/* Double.cpp */ 
inline String Double::toString( int precision ) const 
{
  int size = 40;
  char* str = new char[size+1];
  
  
  int fmtSize = 10;
  char* fmt = new char[fmtSize+1];
  int status = sprintf(fmt, "%%%d.%dle", precision+8, precision);
  if(status < 0) void_error("%s line %d: Double::toString() format truncated");
  status = sprintf(str, fmt, val_);
  delete [] fmt;
  if (status < 0) void_error("%s line %d: Double::toString() input truncated");
  
  String rtn = str;
  delete [] str;
  return rtn;
}

/* Int.cpp */ 
inline String Int::toString() const 
{
  int size = 12;
  char* str = new char[size+1];
  
  int status = sprintf(str, "%d", val_);
  if (status < 0) void_error("%s line %d: Int::toString() input truncated");
  
  String rtn = str;
  delete [] str;
  return rtn;
}

/* CommandLine.cpp */ 
// set argc and argv. This should only be done once, so the class
// is frozen when done. 
inline int PromOptions::InsertOptions( int *pargc, char ***pargv, char *fname)
{
  int argc=*pargc,ii=0,toki=0;
  char **argv = *pargv;

  // file
  FILE *file;
  if( fname != NULL && (file=fopen(fname,"r")) != NULL ) {
#define BUFF_SIZE 256
#define NOTISEND (jj < BUFF_SIZE && buff[jj] != '\0' && buff[jj] != '\n'&& buff[jj] != '!' && buff[jj] != '%' && buff[jj] != '/')
    char buff[BUFF_SIZE], word[BUFF_SIZE]; 
    int kk = 0, ntok = argc - 1;
    while( kk++ < 2 ) {
      while( fgets( buff, BUFF_SIZE, file ) != NULL ) {
        if( buff[0] == '-' ) {
          int len, jj = 0;
          while( NOTISEND  ) {
            // end of !white
            assert( buff[jj] != ' ' ); // have data
            for(len=0; buff[jj] != ' ' && NOTISEND; ) word[len++] = buff[jj++];
            word[len] = '\0';
            if( kk == 1 ) ntok++;
            else {
              String string( word, len );
              tokens_[toki] = string;
              tokenMap_.put( tokens_[toki], toki );
              toki++;
            }
            while(buff[jj] == ' ' && jj < BUFF_SIZE) jj++;//get to end of white
          }
        }
      }
      if( kk == 1 ) {
        tokens_.resize(ntok); // sets the size here: (argc-1) + |file| 
        rewind(file);
      }
    }
  }
  else tokens_.resize(argc-1); // sets the size here: (argc-1) + |file| 

  // command line args -- enter last so as to overide file args
  for(ii=0; ii<(argc-1); ii++) {
    if (argv[ii+1]==0) continue; 
    tokens_[toki] = String( argv[ii+1] );
    tokenMap_.put( tokens_[toki], toki );
    toki++;
  }

  return 0;
}

inline int PromOptions::checkInitialization() const
{
  return 0;
}

// check for presence of string on command line

inline bool PromOptions::find(const String& str) const
{
  int ierr = checkInitialization(); CHKERRQ(ierr);
  return tokenMap_.containsKey(str);
}

inline bool PromOptions::find(const String& str, int& position) const
{
  int ierr = checkInitialization(); CHKERRQ(ierr);
  return tokenMap_.get(str, position);
}

// return value via reference. Returns a bool indicating success or failure.

inline bool PromOptions::findDouble(const String& str, double& val) const
{
  int position;
  
  int ierr = checkInitialization(); CHKERRQ(ierr);
  
  bool rtn;
  rtn = tokenMap_.get(str, position);
  if (!rtn || position >= tokens_.length()) return FALSE;
  val = atof(tokens_[position+1].cString());
  return TRUE;
}

inline bool PromOptions::findInt(const String& str, int& val) const
{
  int position;
  
  int ierr = checkInitialization(); CHKERRQ(ierr);
  
  bool rtn;
  rtn = tokenMap_.get(str, position);
  if (!rtn || position >= tokens_.length()) return FALSE;
  val = atoi(tokens_[position+1].cString());
  return TRUE;
}

inline bool PromOptions::findString(const String& str, String& val) const
{
  int position;
  
  int ierr = checkInitialization(); CHKERRQ(ierr);
  
  bool rtn;
  rtn = tokenMap_.get(str, position);
  if (!rtn || position >= tokens_.length()) return FALSE;
  val = tokens_[position+1];
  return TRUE;
}

inline int PromOptions::print( int myproc, FILE *file /*= stderr*/ ) const
{
  const String str = tokens_.toString();
  fprintf(file, "[%d] PromOptions: %s\n", myproc, str.cString());
  return 0;
}

#endif // PROM_USE_PETSC_OPTIONS

#endif // __PROM_OPTIONS_H__

---