3 // namespace: System.Text.RegularExpressions
\r
6 // author: Dan Lewis (dlewis@gmx.co.uk)
\r
10 using System.Collections;
\r
12 namespace System.Text.RegularExpressions {
\r
14 struct Interval : IComparable {
\r
17 public bool contiguous;
\r
19 public static Interval Empty {
\r
24 i.contiguous = true;
\r
30 public static Interval Entire {
\r
31 get { return new Interval (Int32.MinValue, Int32.MaxValue); }
\r
34 public Interval (int low, int high) {
\r
43 this.contiguous = true;
\r
46 public bool IsDiscontiguous {
\r
47 get { return !contiguous; }
\r
50 public bool IsSingleton {
\r
51 get { return contiguous && low == high; }
\r
54 public bool IsRange {
\r
55 get { return !IsSingleton && !IsEmpty; }
\r
58 public bool IsEmpty {
\r
59 get { return low > high; }
\r
67 return high - low + 1;
\r
71 public bool IsDisjoint (Interval i) {
\r
72 if (IsEmpty || i.IsEmpty)
\r
75 return !(low <= i.high && i.low <= high);
\r
78 public bool IsAdjacent (Interval i) {
\r
79 if (IsEmpty || i.IsEmpty)
\r
82 return low == i.high + 1 || high == i.low - 1;
\r
85 public bool Contains (Interval i) {
\r
86 if (!IsEmpty && i.IsEmpty)
\r
91 return low <= i.low && i.high <= high;
\r
94 public bool Contains (int i) {
\r
95 return low <= i && i <= high;
\r
98 public bool Intersects (Interval i) {
\r
99 if (IsEmpty || i.IsEmpty)
\r
102 return ((Contains (i.low) && !Contains (i.high)) ||
\r
103 (Contains (i.high) && !Contains (i.low)));
\r
106 public void Merge (Interval i) {
\r
111 this.high = i.high;
\r
120 public void Intersect (Interval i) {
\r
121 if (IsDisjoint (i)) {
\r
133 public int CompareTo (object o) {
\r
134 return low - ((Interval)o).low;
\r
137 public new string ToString () {
\r
140 else if (!contiguous)
\r
141 return "{" + low + ", " + high + "}";
\r
142 else if (IsSingleton)
\r
143 return "(" + low + ")";
\r
145 return "(" + low + ", " + high + ")";
\r
149 class IntervalCollection : ICollection, IEnumerable {
\r
150 public IntervalCollection () {
\r
151 intervals = new ArrayList ();
\r
154 public Interval this[int i] {
\r
155 get { return (Interval)intervals[i]; }
\r
156 set { intervals[i] = value; }
\r
159 public void Add (Interval i) {
\r
163 public void Clear () {
\r
164 intervals.Clear ();
\r
167 public void Sort () {
\r
171 public void Normalize () {
\r
175 while (j < intervals.Count - 1) {
\r
176 Interval a = (Interval)intervals[j];
\r
177 Interval b = (Interval)intervals[j + 1];
\r
179 if (!a.IsDisjoint (b) || a.IsAdjacent (b)) {
\r
182 intervals.RemoveAt (j + 1);
\r
190 public delegate double CostDelegate (Interval i);
\r
192 public IntervalCollection GetMetaCollection (CostDelegate cost_del) {
\r
193 IntervalCollection meta = new IntervalCollection ();
\r
196 Optimize (0, Count - 1, meta, cost_del);
\r
197 meta.intervals.Sort ();
\r
202 private void Optimize (int begin, int end, IntervalCollection meta, CostDelegate cost_del) {
\r
204 set.contiguous = false;
\r
206 int best_set_begin = -1;
\r
207 int best_set_end = -1;
\r
208 double best_set_cost = 0;
\r
210 for (int i = begin; i <= end; ++ i) {
\r
211 set.low = this[i].low;
\r
214 for (int j = i; j <= end; ++ j) {
\r
215 set.high = this[j].high;
\r
216 cost += cost_del (this[j]);
\r
218 double set_cost = cost_del (set);
\r
219 if (set_cost < cost && cost > best_set_cost) {
\r
220 best_set_begin = i;
\r
222 best_set_cost = cost;
\r
227 if (best_set_begin < 0) {
\r
228 // didn't find an optimal set: add original members
\r
230 for (int i = begin; i <= end; ++ i)
\r
231 meta.Add (this[i]);
\r
234 // found set: add it ...
\r
236 set.low = this[best_set_begin].low;
\r
237 set.high = this[best_set_end].high;
\r
241 // ... and optimize to the left and right
\r
243 if (best_set_begin > begin)
\r
244 Optimize (begin, best_set_begin - 1, meta, cost_del);
\r
245 if (best_set_end < end)
\r
246 Optimize (best_set_end + 1, end, meta, cost_del);
\r
250 // ICollection implementation
\r
253 get { return intervals.Count; }
\r
256 public bool IsSynchronized {
\r
257 get { return false; }
\r
260 public object SyncRoot {
\r
261 get { return intervals; }
\r
264 public void CopyTo (Array array, int index) {
\r
265 foreach (Interval i in intervals) {
\r
266 if (index > array.Length)
\r
269 array.SetValue (i, index ++);
\r
273 // IEnumerator implementation
\r
275 public IEnumerator GetEnumerator () {
\r
276 return new Enumerator (intervals);
\r
279 private class Enumerator : IEnumerator {
\r
280 public Enumerator (IList list) {
\r
285 public object Current {
\r
287 if (ptr >= list.Count)
\r
288 throw new InvalidOperationException ();
\r
294 public bool MoveNext () {
\r
295 if (ptr > list.Count)
\r
296 throw new InvalidOperationException ();
\r
298 return ++ ptr < list.Count;
\r
301 public void Reset () {
\r
305 private IList list;
\r
311 private ArrayList intervals;
\r