source: golgotha/src/golg/interval.hh @ 80

Last change on this file since 80 was 80, checked in by Sam Hocevar, 11 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 4.2 KB
RevLine 
[80]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
30template <class T>
31class i4_interval_template
32{
33protected:
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
149public:
150  void print()
151  //{{{
152  {
153    print_tree(root);
154  }
155  //}}}
156protected:
157#endif
158 
159  //}}}
160 
161public:
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// folded-file: t
191// End:
192//}}}
Note: See TracBrowser for help on using the repository browser.