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