mcs/class/System/System.Text.RegularExpressions/interval.cs

   1 //\r
   2 // assembly:    System\r
   3 // namespace:   System.Text.RegularExpressions\r
   4 // file:        interval.cs\r
   5 //\r
   6 // author:      Dan Lewis (dlewis@gmx.co.uk)\r
   7 //              (c) 2002\r
   8 \r
   9 using System;\r
  10 using System.Collections;\r
  11 \r
  12 namespace System.Text.RegularExpressions {\r
  13 \r
  14         struct Interval : IComparable {\r
  15                 public int low;\r
  16                 public int high;\r
  17                 public bool contiguous;\r
  18 \r
  19                 public static Interval Empty {\r
  20                         get {\r
  21                                 Interval i;\r
  22                                 i.low = 0;\r
  23                                 i.high = i.low - 1;\r
  24                                 i.contiguous = true;\r
  25 \r
  26                                 return i;\r
  27                         }\r
  28                 }\r
  29 \r
  30                 public static Interval Entire {\r
  31                         get { return new Interval (Int32.MinValue, Int32.MaxValue); }\r
  32                 }\r
  33 \r
  34                 public Interval (int low, int high) {\r
  35                         if (low > high) {\r
  36                                 int t = low;\r
  37                                 low = high;\r
  38                                 high = t;\r
  39                         }\r
  40                 \r
  41                         this.low = low;\r
  42                         this.high = high;\r
  43                         this.contiguous = true;\r
  44                 }\r
  45 \r
  46                 public bool IsDiscontiguous {\r
  47                         get { return !contiguous; }\r
  48                 }\r
  49                 \r
  50                 public bool IsSingleton {\r
  51                         get { return contiguous && low == high; }\r
  52                 }\r
  53 \r
  54                 public bool IsRange {\r
  55                         get { return !IsSingleton && !IsEmpty; }\r
  56                 }\r
  57 \r
  58                 public bool IsEmpty {\r
  59                         get { return low > high; }\r
  60                 }\r
  61 \r
  62                 public int Size {\r
  63                         get {\r
  64                                 if (IsEmpty)\r
  65                                         return 0;\r
  66                                 \r
  67                                 return high - low + 1;\r
  68                         }\r
  69                 }\r
  70 \r
  71                 public bool IsDisjoint (Interval i) {\r
  72                         if (IsEmpty || i.IsEmpty)\r
  73                                 return true;\r
  74                         \r
  75                         return !(low <= i.high && i.low <= high);\r
  76                 }\r
  77 \r
  78                 public bool IsAdjacent (Interval i) {\r
  79                         if (IsEmpty || i.IsEmpty)\r
  80                                 return false;\r
  81                 \r
  82                         return low == i.high + 1 || high == i.low - 1;\r
  83                 }\r
  84 \r
  85                 public bool Contains (Interval i) {\r
  86                         if (!IsEmpty && i.IsEmpty)\r
  87                                 return true;\r
  88                         if (IsEmpty)\r
  89                                 return false;\r
  90                 \r
  91                         return low <= i.low && i.high <= high;\r
  92                 }\r
  93 \r
  94                 public bool Contains (int i) {\r
  95                         return low <= i && i <= high;\r
  96                 }\r
  97 \r
  98                 public bool Intersects (Interval i) {\r
  99                         if (IsEmpty || i.IsEmpty)\r
 100                                 return false;\r
 101                         \r
 102                         return ((Contains (i.low) && !Contains (i.high)) ||\r
 103                                 (Contains (i.high) && !Contains (i.low)));\r
 104                 }       \r
 105 \r
 106                 public void Merge (Interval i) {\r
 107                         if (i.IsEmpty)\r
 108                                 return;\r
 109                         if (IsEmpty) {\r
 110                                 this.low = i.low;\r
 111                                 this.high = i.high;\r
 112                         }\r
 113                 \r
 114                         if (i.low < low)\r
 115                                 low = i.low;\r
 116                         if (i.high > high)\r
 117                                 high = i.high;\r
 118                 }\r
 119 \r
 120                 public void Intersect (Interval i) {\r
 121                         if (IsDisjoint (i)) {\r
 122                                 low = 0;\r
 123                                 high = low - 1;\r
 124                                 return;\r
 125                         }\r
 126                 \r
 127                         if (i.low > low)\r
 128                                 low = i.low;\r
 129                         if (i.high > high)\r
 130                                 high = i.high;\r
 131                 }\r
 132 \r
 133                 public int CompareTo (object o) {\r
 134                         return low - ((Interval)o).low;\r
 135                 }\r
 136 \r
 137                 public new string ToString () {\r
 138                         if (IsEmpty)\r
 139                                 return "(EMPTY)";\r
 140                         else if (!contiguous)\r
 141                                 return "{" + low + ", " + high + "}";\r
 142                         else if (IsSingleton)\r
 143                                 return "(" + low + ")";\r
 144                         else\r
 145                                 return "(" + low + ", " + high + ")";\r
 146                 }\r
 147         }\r
 148 \r
 149         class IntervalCollection : ICollection, IEnumerable {\r
 150                 public IntervalCollection () {\r
 151                         intervals = new ArrayList ();\r
 152                 }\r
 153 \r
 154                 public Interval this[int i] {\r
 155                         get { return (Interval)intervals[i]; }\r
 156                         set { intervals[i] = value; }\r
 157                 }\r
 158 \r
 159                 public void Add (Interval i) {\r
 160                         intervals.Add (i);\r
 161                 }\r
 162                         \r
 163                 public void Clear () {\r
 164                         intervals.Clear ();\r
 165                 }\r
 166 \r
 167                 public void Sort () {\r
 168                         intervals.Sort ();\r
 169                 }\r
 170                 \r
 171                 public void Normalize () {\r
 172                         intervals.Sort ();\r
 173 \r
 174                         int j = 0;\r
 175                         while (j < intervals.Count - 1) {\r
 176                                 Interval a = (Interval)intervals[j];\r
 177                                 Interval b = (Interval)intervals[j + 1];\r
 178 \r
 179                                 if (!a.IsDisjoint (b) || a.IsAdjacent (b)) {\r
 180                                         a.Merge (b);\r
 181                                         intervals[j] = a;\r
 182                                         intervals.RemoveAt (j + 1);\r
 183                                 }\r
 184                                 else\r
 185                                         ++ j;\r
 186                         }\r
 187 \r
 188                 }\r
 189 \r
 190                 public delegate double CostDelegate (Interval i);\r
 191 \r
 192                 public IntervalCollection GetMetaCollection (CostDelegate cost_del) {\r
 193                         IntervalCollection meta = new IntervalCollection ();\r
 194                 \r
 195                         Normalize ();\r
 196                         Optimize (0, Count - 1, meta, cost_del);\r
 197                         meta.intervals.Sort ();\r
 198 \r
 199                         return meta;\r
 200                 }\r
 201 \r
 202                 private void Optimize (int begin, int end, IntervalCollection meta, CostDelegate cost_del) {\r
 203                         Interval set;\r
 204                         set.contiguous = false;\r
 205                 \r
 206                         int best_set_begin = -1;\r
 207                         int best_set_end = -1;\r
 208                         double best_set_cost = 0;\r
 209 \r
 210                         for (int i = begin; i <= end; ++ i) {\r
 211                                 set.low = this[i].low;\r
 212 \r
 213                                 double cost = 0.0;\r
 214                                 for (int j = i; j <= end; ++ j) {\r
 215                                         set.high = this[j].high;\r
 216                                         cost += cost_del (this[j]);\r
 217                                         \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
 221                                                 best_set_end = j;\r
 222                                                 best_set_cost = cost;\r
 223                                         }\r
 224                                 }\r
 225                         }\r
 226 \r
 227                         if (best_set_begin < 0) {\r
 228                                 // didn't find an optimal set: add original members\r
 229 \r
 230                                 for (int i = begin; i <= end; ++ i)\r
 231                                         meta.Add (this[i]);\r
 232                         }\r
 233                         else {\r
 234                                 // found set: add it ...\r
 235 \r
 236                                 set.low = this[best_set_begin].low;\r
 237                                 set.high = this[best_set_end].high;\r
 238                                 \r
 239                                 meta.Add (set);\r
 240 \r
 241                                 // ... and optimize to the left and right\r
 242 \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
 247                         }\r
 248                 }\r
 249 \r
 250                 // ICollection implementation\r
 251 \r
 252                 public int Count {\r
 253                         get { return intervals.Count; }\r
 254                 }\r
 255 \r
 256                 public bool IsSynchronized {\r
 257                         get { return false; }\r
 258                 }\r
 259 \r
 260                 public object SyncRoot {\r
 261                         get { return intervals; }\r
 262                 }\r
 263 \r
 264                 public void CopyTo (Array array, int index) {\r
 265                         foreach (Interval i in intervals) {\r
 266                                 if (index > array.Length)\r
 267                                         break;\r
 268                                 \r
 269                                 array.SetValue (i, index ++);\r
 270                         }\r
 271                 }\r
 272 \r
 273                 // IEnumerator implementation\r
 274 \r
 275                 public IEnumerator GetEnumerator () {\r
 276                         return new Enumerator (intervals);\r
 277                 }\r
 278 \r
 279                 private class Enumerator : IEnumerator {\r
 280                         public Enumerator (IList list) {\r
 281                                 this.list = list;\r
 282                                 Reset ();\r
 283                         }\r
 284 \r
 285                         public object Current {\r
 286                                 get {\r
 287                                         if (ptr >= list.Count)\r
 288                                                 throw new InvalidOperationException ();\r
 289 \r
 290                                         return list[ptr];\r
 291                                 }\r
 292                         }\r
 293 \r
 294                         public bool MoveNext () {\r
 295                                 if (ptr > list.Count)\r
 296                                         throw new InvalidOperationException ();\r
 297                                 \r
 298                                 return ++ ptr < list.Count;\r
 299                         }\r
 300 \r
 301                         public void Reset () {\r
 302                                 ptr = -1;\r
 303                         }\r
 304 \r
 305                         private IList list;\r
 306                         private int ptr;\r
 307                 }\r
 308 \r
 309                 // private fields\r
 310 \r
 311                 private ArrayList intervals;\r
 312         }\r
 313 }\r