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 void Merge (Interval i) {\r
  99                         if (i.IsEmpty)\r
 100                                 return;\r
 101                         if (IsEmpty) {\r
 102                                 this.low = i.low;\r
 103                                 this.high = i.high;\r
 104                         }\r
 105                 \r
 106                         if (i.low < low)\r
 107                                 low = i.low;\r
 108                         if (i.high > high)\r
 109                                 high = i.high;\r
 110                 }\r
 111 \r
 112                 public void Intersect (Interval i) {\r
 113                         if (IsDisjoint (i)) {\r
 114                                 low = 0;\r
 115                                 high = low - 1;\r
 116                                 return;\r
 117                         }\r
 118                 \r
 119                         if (i.low > low)\r
 120                                 low = i.low;\r
 121                         if (i.high > high)\r
 122                                 high = i.high;\r
 123                 }\r
 124 \r
 125                 public int CompareTo (object o) {\r
 126                         return low - ((Interval)o).low;\r
 127                 }\r
 128 \r
 129                 public new string ToString () {\r
 130                         if (IsEmpty)\r
 131                                 return "(EMPTY)";\r
 132                         else if (!contiguous)\r
 133                                 return "{" + low + ", " + high + "}";\r
 134                         else if (IsSingleton)\r
 135                                 return "(" + low + ")";\r
 136                         else\r
 137                                 return "(" + low + ", " + high + ")";\r
 138                 }\r
 139         }\r
 140 \r
 141         class IntervalCollection : ICollection, IEnumerable {\r
 142                 public IntervalCollection () {\r
 143                         intervals = new ArrayList ();\r
 144                 }\r
 145 \r
 146                 public Interval this[int i] {\r
 147                         get { return (Interval)intervals[i]; }\r
 148                         set { intervals[i] = value; }\r
 149                 }\r
 150 \r
 151                 public void Add (Interval i) {\r
 152                         intervals.Add (i);\r
 153                 }\r
 154                         \r
 155                 public void Clear () {\r
 156                         intervals.Clear ();\r
 157                 }\r
 158 \r
 159                 public void Sort () {\r
 160                         intervals.Sort ();\r
 161                 }\r
 162                 \r
 163                 public void Normalize () {\r
 164                         intervals.Sort ();\r
 165 \r
 166                         int j = 0;\r
 167                         while (j < intervals.Count - 1) {\r
 168                                 Interval a = (Interval)intervals[j];\r
 169                                 Interval b = (Interval)intervals[j + 1];\r
 170 \r
 171                                 if (!a.IsDisjoint (b) || a.IsAdjacent (b)) {\r
 172                                         a.Merge (b);\r
 173                                         intervals[j] = a;\r
 174                                         intervals.RemoveAt (j + 1);\r
 175                                 }\r
 176                                 else\r
 177                                         ++ j;\r
 178                         }\r
 179 \r
 180                 }\r
 181 \r
 182                 public delegate double CostDelegate (Interval i);\r
 183 \r
 184                 public IntervalCollection GetMetaCollection (CostDelegate cost_del) {\r
 185                         IntervalCollection meta = new IntervalCollection ();\r
 186                 \r
 187                         Normalize ();\r
 188                         Optimize (0, Count - 1, meta, cost_del);\r
 189                         meta.intervals.Sort ();\r
 190 \r
 191                         return meta;\r
 192                 }\r
 193 \r
 194                 private void Optimize (int begin, int end, IntervalCollection meta, CostDelegate cost_del) {\r
 195                         Interval set;\r
 196                         set.contiguous = false;\r
 197                 \r
 198                         int best_set_begin = -1;\r
 199                         int best_set_end = -1;\r
 200                         double best_set_cost = 0;\r
 201 \r
 202                         for (int i = begin; i <= end; ++ i) {\r
 203                                 set.low = this[i].low;\r
 204 \r
 205                                 double cost = 0.0;\r
 206                                 for (int j = i; j <= end; ++ j) {\r
 207                                         set.high = this[j].high;\r
 208                                         cost += cost_del (this[j]);\r
 209                                         \r
 210                                         double set_cost = cost_del (set);\r
 211                                         if (set_cost < cost && cost > best_set_cost) {\r
 212                                                 best_set_begin = i;\r
 213                                                 best_set_end = j;\r
 214                                                 best_set_cost = cost;\r
 215                                         }\r
 216                                 }\r
 217                         }\r
 218 \r
 219                         if (best_set_begin < 0) {\r
 220                                 // didn't find an optimal set: add original members\r
 221 \r
 222                                 for (int i = begin; i <= end; ++ i)\r
 223                                         meta.Add (this[i]);\r
 224                         }\r
 225                         else {\r
 226                                 // found set: add it ...\r
 227 \r
 228                                 set.low = this[best_set_begin].low;\r
 229                                 set.high = this[best_set_end].high;\r
 230                                 \r
 231                                 meta.Add (set);\r
 232 \r
 233                                 // ... and optimize to the left and right\r
 234 \r
 235                                 if (best_set_begin > begin)\r
 236                                         Optimize (begin, best_set_begin - 1, meta, cost_del);\r
 237                                 if (best_set_end < end)\r
 238                                         Optimize (best_set_end + 1, end, meta, cost_del);\r
 239                         }\r
 240                 }\r
 241 \r
 242                 // ICollection implementation\r
 243 \r
 244                 public int Count {\r
 245                         get { return intervals.Count; }\r
 246                 }\r
 247 \r
 248                 public bool IsSynchronized {\r
 249                         get { return false; }\r
 250                 }\r
 251 \r
 252                 public object SyncRoot {\r
 253                         get { return intervals; }\r
 254                 }\r
 255 \r
 256                 public void CopyTo (Array array, int index) {\r
 257                         foreach (Interval i in intervals) {\r
 258                                 if (index > array.Length)\r
 259                                         break;\r
 260                                 \r
 261                                 array.SetValue (i, index ++);\r
 262                         }\r
 263                 }\r
 264 \r
 265                 // IEnumerator implementation\r
 266 \r
 267                 public IEnumerator GetEnumerator () {\r
 268                         return new Enumerator (intervals);\r
 269                 }\r
 270 \r
 271                 private class Enumerator : IEnumerator {\r
 272                         public Enumerator (IList list) {\r
 273                                 this.list = list;\r
 274                                 Reset ();\r
 275                         }\r
 276 \r
 277                         public object Current {\r
 278                                 get {\r
 279                                         if (ptr >= list.Count)\r
 280                                                 throw new InvalidOperationException ();\r
 281 \r
 282                                         return list[ptr];\r
 283                                 }\r
 284                         }\r
 285 \r
 286                         public bool MoveNext () {\r
 287                                 if (ptr > list.Count)\r
 288                                         throw new InvalidOperationException ();\r
 289                                 \r
 290                                 return ++ ptr < list.Count;\r
 291                         }\r
 292 \r
 293                         public void Reset () {\r
 294                                 ptr = -1;\r
 295                         }\r
 296 \r
 297                         private IList list;\r
 298                         private int ptr;\r
 299                 }\r
 300 \r
 301                 // private fields\r
 302 \r
 303                 private ArrayList intervals;\r
 304         }\r
 305 }\r