1  /********************************************************************** <BR>


2  This file is part of Crack dot Com's free source code release of


3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


4  information about compiling & licensing issues visit this URL</a>


5  <PRE> If that doesn't help, contact Jonathan Clark at


6  golgotha_source@usa.net (Subject should have "GOLG" in it)


7  ***********************************************************************/


8 


9  //{{{ Numeric Interval template


10  //


11  // Allows the manipulation of numeric closed intervals, or the union of


12  // all numbers that fall between pairs of numbers, inclusively.


13  //


14  //Usage:


15  // Instantiate the template on a numeric type


16  // Add intervals using 'add_interval', which also returns whether the specified


17  // interval was not contained


18  // Test for containment using 'contains'


19  // Reset the interval with 'clear'


20  //


21  // To allow for printing of the interval list, define 'DEBUG_INTERVAL' and


22  // use 'print' in the debugger.


23  //


24  //$Id: interval.hh,v 1.4 1996/09/03 05:12:19 oliy Exp $


25  //}}}


26 


27  #include "arch.hh"


28  #include "math/num_type.hh"


29 


30  template <class T>


31  class i4_interval_template


32  {


33  protected:


34  class interval_node;


35  typedef interval_node *interval_link;


36  class interval_node


37  //{{{


38  {


39  friend class i4_interval_template<T>;


40  protected:


41  interval_link left, right;


42  public:


43  T min, max;


44 


45  interval_node() : left(0), right(0) {}


46  interval_node(T _min, T _max)


47  : min(_min), max(_max), left(0), right(0) {}


48 


49  ~interval_node() { delete left; delete right; }


50  };


51  //}}}


52  interval_link root;


53 


54  interval_link *find_interval(T val, interval_link *pp)


55  //{{{


56  {


57  interval_link p;


58 


59  while ((p = *pp)!=0)


60  {


61  if (val<p>min)


62  pp = &p>left;


63  else if (val>p>max)


64  pp = &p>right;


65  else


66  return pp;


67  }


68  return pp;


69  }


70  //}}}


71 


72  i4_bool recurse_combine(interval_link *pp,


73  T min,


74  T max,


75  interval_link replace)


76  //{{{


77  {


78  interval_link p = *pp;


79 


80  if (!p)


81  {


82  if (!replace)


83  {


84  *pp = new interval_node(min,max);


85  return 1;


86  }


87  else


88  return 0;


89  }


90 


91  if (max<p>min)


92  // interval totally to the left of me


93  recurse_combine(&p>left,min,max,replace);


94  else if (min>p>max)


95  // interval totally to the right of me


96  recurse_combine(&p>right,min,max,replace);


97  else


98  {


99  // interval touches me


100  T local_min, local_max;


101 


102  if (min<=p>min)


103  // can possibly combine more to the left


104  recurse_combine(&p>left,min,max,p);


105  if (max>=p>max)


106  // can possibly combine more to the right


107  recurse_combine(&p>right,min,max,p);


108 


109  local_min = (min < p>min)? min : p>min;


110  local_max = (max > p>max)? max : p>max;


111 


112  if (replace)


113  {


114  // combine me into my ancestor


115  replace>min = (local_min < replace>min)? local_min : replace>min;


116  replace>max = (local_max > replace>max)? local_max : replace>max;


117 


118  delete p;


119  *pp = 0;


120  }


121  else


122  {


123  // combine interval with me


124  p>min = local_min;


125  p>max = local_max;


126  }


127  }


128  return 0;


129  }


130  //}}}


131 


132  //{{{ Debugging Tools


133 


134  #ifdef DEBUG_INTERVAL


135  void print_tree(interval_link tree)


136  //{{{


137  {


138  if (!tree)


139  return;


140 


141  print_tree(tree>left);


142  printf("[%f %f]\n",tree>min,tree>max);


143  print_tree(tree>right);


144  }


145  //}}}


146  #endif


147 


148  #ifdef DEBUG_INTERVAL


149  public:


150  void print()


151  //{{{


152  {


153  print_tree(root);


154  }


155  //}}}


156  protected:


157  #endif


158 


159  //}}}


160 


161  public:


162  i4_interval_template() : root(0) {}


163 


164  i4_bool contains(T val)


165  //{{{


166  {


167  return (*find_interval(val,&root) != 0);


168  }


169  //}}}


170 


171  i4_bool add_interval(T min, T max)


172  //{{{


173  {


174  return recurse_combine(&root,min,max,0);


175  }


176  //}}}


177 


178  void clear()


179  //{{{


180  {


181  if (root)


182  delete root;


183  root = 0;


184  }


185  //}}}


186  };


187 


188  //{{{ Emacs Locals


189  // Local Variables:


190  // foldedfile: t


191  // End:


192  //}}}

