3 // namespace: System.Text.RegularExpressions
\r
6 // author: Dan Lewis (dlewis@gmx.co.uk)
\r
10 // Permission is hereby granted, free of charge, to any person obtaining
11 // a copy of this software and associated documentation files (the
12 // "Software"), to deal in the Software without restriction, including
13 // without limitation the rights to use, copy, modify, merge, publish,
14 // distribute, sublicense, and/or sell copies of the Software, and to
15 // permit persons to whom the Software is furnished to do so, subject to
16 // the following conditions:
18 // The above copyright notice and this permission notice shall be
19 // included in all copies or substantial portions of the Software.
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 using System.Collections;
\r
33 namespace System.Text.RegularExpressions {
\r
35 struct Interval : IComparable {
\r
38 public bool contiguous;
\r
40 public static Interval Empty {
\r
45 i.contiguous = true;
\r
51 public static Interval Entire {
\r
52 get { return new Interval (Int32.MinValue, Int32.MaxValue); }
\r
55 public Interval (int low, int high) {
\r
64 this.contiguous = true;
\r
67 public bool IsDiscontiguous {
\r
68 get { return !contiguous; }
\r
71 public bool IsSingleton {
\r
72 get { return contiguous && low == high; }
\r
75 public bool IsRange {
\r
76 get { return !IsSingleton && !IsEmpty; }
\r
79 public bool IsEmpty {
\r
80 get { return low > high; }
\r
88 return high - low + 1;
\r
92 public bool IsDisjoint (Interval i) {
\r
93 if (IsEmpty || i.IsEmpty)
\r
96 return !(low <= i.high && i.low <= high);
\r
99 public bool IsAdjacent (Interval i) {
\r
100 if (IsEmpty || i.IsEmpty)
\r
103 return low == i.high + 1 || high == i.low - 1;
\r
106 public bool Contains (Interval i) {
\r
107 if (!IsEmpty && i.IsEmpty)
\r
112 return low <= i.low && i.high <= high;
\r
115 public bool Contains (int i) {
\r
116 return low <= i && i <= high;
\r
119 public bool Intersects (Interval i) {
\r
120 if (IsEmpty || i.IsEmpty)
\r
123 return ((Contains (i.low) && !Contains (i.high)) ||
\r
124 (Contains (i.high) && !Contains (i.low)));
\r
127 public void Merge (Interval i) {
\r
132 this.high = i.high;
\r
141 public void Intersect (Interval i) {
\r
142 if (IsDisjoint (i)) {
\r
154 public int CompareTo (object o) {
\r
155 return low - ((Interval)o).low;
\r
158 public new string ToString () {
\r
161 else if (!contiguous)
\r
162 return "{" + low + ", " + high + "}";
\r
163 else if (IsSingleton)
\r
164 return "(" + low + ")";
\r
166 return "(" + low + ", " + high + ")";
\r
170 class IntervalCollection : ICollection, IEnumerable {
\r
171 public IntervalCollection () {
\r
172 intervals = new ArrayList ();
\r
175 public Interval this[int i] {
\r
176 get { return (Interval)intervals[i]; }
\r
177 set { intervals[i] = value; }
\r
180 public void Add (Interval i) {
\r
184 public void Clear () {
\r
185 intervals.Clear ();
\r
188 public void Sort () {
\r
192 public void Normalize () {
\r
196 while (j < intervals.Count - 1) {
\r
197 Interval a = (Interval)intervals[j];
\r
198 Interval b = (Interval)intervals[j + 1];
\r
200 if (!a.IsDisjoint (b) || a.IsAdjacent (b)) {
\r
203 intervals.RemoveAt (j + 1);
\r
211 public delegate double CostDelegate (Interval i);
\r
213 public IntervalCollection GetMetaCollection (CostDelegate cost_del) {
\r
214 IntervalCollection meta = new IntervalCollection ();
\r
217 Optimize (0, Count - 1, meta, cost_del);
\r
218 meta.intervals.Sort ();
\r
223 private void Optimize (int begin, int end, IntervalCollection meta, CostDelegate cost_del) {
\r
225 set.contiguous = false;
\r
227 int best_set_begin = -1;
\r
228 int best_set_end = -1;
\r
229 double best_set_cost = 0;
\r
231 for (int i = begin; i <= end; ++ i) {
\r
232 set.low = this[i].low;
\r
235 for (int j = i; j <= end; ++ j) {
\r
236 set.high = this[j].high;
\r
237 cost += cost_del (this[j]);
\r
239 double set_cost = cost_del (set);
\r
240 if (set_cost < cost && cost > best_set_cost) {
\r
241 best_set_begin = i;
\r
243 best_set_cost = cost;
\r
248 if (best_set_begin < 0) {
\r
249 // didn't find an optimal set: add original members
\r
251 for (int i = begin; i <= end; ++ i)
\r
252 meta.Add (this[i]);
\r
255 // found set: add it ...
\r
257 set.low = this[best_set_begin].low;
\r
258 set.high = this[best_set_end].high;
\r
262 // ... and optimize to the left and right
\r
264 if (best_set_begin > begin)
\r
265 Optimize (begin, best_set_begin - 1, meta, cost_del);
\r
266 if (best_set_end < end)
\r
267 Optimize (best_set_end + 1, end, meta, cost_del);
\r
271 // ICollection implementation
\r
274 get { return intervals.Count; }
\r
277 public bool IsSynchronized {
\r
278 get { return false; }
\r
281 public object SyncRoot {
\r
282 get { return intervals; }
\r
285 public void CopyTo (Array array, int index) {
\r
286 foreach (Interval i in intervals) {
\r
287 if (index > array.Length)
\r
290 array.SetValue (i, index ++);
\r
294 // IEnumerator implementation
\r
296 public IEnumerator GetEnumerator () {
\r
297 return new Enumerator (intervals);
\r
300 private class Enumerator : IEnumerator {
\r
301 public Enumerator (IList list) {
\r
306 public object Current {
\r
308 if (ptr >= list.Count)
\r
309 throw new InvalidOperationException ();
\r
315 public bool MoveNext () {
\r
316 if (ptr > list.Count)
\r
317 throw new InvalidOperationException ();
\r
319 return ++ ptr < list.Count;
\r
322 public void Reset () {
\r
326 private IList list;
\r
332 private ArrayList intervals;
\r