//
// assembly:	System
// namespace:	System.Text.RegularExpressions
// file:	interval.cs
//
// author:	Dan Lewis (dlewis@gmx.co.uk)
// 		(c) 2002

//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

using System;
using System.Collections;

namespace System.Text.RegularExpressions {

	struct Interval : IComparable {
		public int low;
		public int high;
		public bool contiguous;

		public static Interval Empty {
			get {
				Interval i;
				i.low = 0;
				i.high = i.low - 1;
				i.contiguous = true;

				return i;
			}
		}

		public static Interval Entire {
			get { return new Interval (Int32.MinValue, Int32.MaxValue); }
		}

		public Interval (int low, int high) {
			if (low > high) {
				int t = low;
				low = high;
				high = t;
			}
		
			this.low = low;
			this.high = high;
			this.contiguous = true;
		}

		public bool IsDiscontiguous {
			get { return !contiguous; }
		}
		
		public bool IsSingleton {
			get { return contiguous && low == high; }
		}

		public bool IsRange {
			get { return !IsSingleton && !IsEmpty; }
		}

		public bool IsEmpty {
			get { return low > high; }
		}

		public int Size {
			get {
				if (IsEmpty)
					return 0;
				
				return high - low + 1;
			}
		}

		public bool IsDisjoint (Interval i) {
			if (IsEmpty || i.IsEmpty)
				return true;
			
			return !(low <= i.high && i.low <= high);
		}

		public bool IsAdjacent (Interval i) {
			if (IsEmpty || i.IsEmpty)
				return false;
		
			return low == i.high + 1 || high == i.low - 1;
		}

		public bool Contains (Interval i) {
			if (!IsEmpty && i.IsEmpty)
				return true;
			if (IsEmpty)
				return false;
		
			return low <= i.low && i.high <= high;
		}

		public bool Contains (int i) {
			return low <= i && i <= high;
		}

		public bool Intersects (Interval i) {
 			if (IsEmpty || i.IsEmpty)
 				return false;
 			
 			return ((Contains (i.low) && !Contains (i.high)) ||
				(Contains (i.high) && !Contains (i.low)));
 		}	

		public void Merge (Interval i) {
			if (i.IsEmpty)
				return;
			if (IsEmpty) {
				this.low = i.low;
				this.high = i.high;
			}
		
			if (i.low < low)
				low = i.low;
			if (i.high > high)
				high = i.high;
		}

		public void Intersect (Interval i) {
			if (IsDisjoint (i)) {
				low = 0;
				high = low - 1;
				return;
			}
		
			if (i.low > low)
				low = i.low;
			if (i.high > high)
				high = i.high;
		}

		public int CompareTo (object o) {
			return low - ((Interval)o).low;
		}

		public new string ToString () {
			if (IsEmpty)
				return "(EMPTY)";
			else if (!contiguous)
				return "{" + low + ", " + high + "}";
			else if (IsSingleton)
				return "(" + low + ")";
			else
				return "(" + low + ", " + high + ")";
		}
	}

	class IntervalCollection : ICollection, IEnumerable {
		public IntervalCollection () {
			intervals = new ArrayList ();
		}

		public Interval this[int i] {
			get { return (Interval)intervals[i]; }
			set { intervals[i] = value; }
		}

		public void Add (Interval i) {
			intervals.Add (i);
		}
			
		public void Clear () {
			intervals.Clear ();
		}

		public void Sort () {
			intervals.Sort ();
		}
		
		public void Normalize () {
			intervals.Sort ();

			int j = 0;
			while (j < intervals.Count - 1) {
				Interval a = (Interval)intervals[j];
				Interval b = (Interval)intervals[j + 1];

				if (!a.IsDisjoint (b) || a.IsAdjacent (b)) {
					a.Merge (b);
					intervals[j] = a;
					intervals.RemoveAt (j + 1);
				}
				else
					++ j;
			}

		}

		public delegate double CostDelegate (Interval i);

		public IntervalCollection GetMetaCollection (CostDelegate cost_del) {
			IntervalCollection meta = new IntervalCollection ();
		
			Normalize ();
			Optimize (0, Count - 1, meta, cost_del);
			meta.intervals.Sort ();

			return meta;
		}

		private void Optimize (int begin, int end, IntervalCollection meta, CostDelegate cost_del) {
			Interval set;
			set.contiguous = false;
		
			int best_set_begin = -1;
			int best_set_end = -1;
			double best_set_cost = 0;

			for (int i = begin; i <= end; ++ i) {
				set.low = this[i].low;

				double cost = 0.0;
				for (int j = i; j <= end; ++ j) {
					set.high = this[j].high;
					cost += cost_del (this[j]);
					
					double set_cost = cost_del (set);
					if (set_cost < cost && cost > best_set_cost) {
						best_set_begin = i;
						best_set_end = j;
						best_set_cost = cost;
					}
				}
			}

			if (best_set_begin < 0) {
				// didn't find an optimal set: add original members

				for (int i = begin; i <= end; ++ i)
					meta.Add (this[i]);
			}
			else {
				// found set: add it ...

				set.low = this[best_set_begin].low;
				set.high = this[best_set_end].high;
				
				meta.Add (set);

				// ... and optimize to the left and right

				if (best_set_begin > begin)
					Optimize (begin, best_set_begin - 1, meta, cost_del);
				if (best_set_end < end)
					Optimize (best_set_end + 1, end, meta, cost_del);
			}
		}

		// ICollection implementation

		public int Count {
			get { return intervals.Count; }
		}

		public bool IsSynchronized {
			get { return false; }
		}

		public object SyncRoot {
			get { return intervals; }
		}

		public void CopyTo (Array array, int index) {
			foreach (Interval i in intervals) {
				if (index > array.Length)
					break;
				
				array.SetValue (i, index ++);
			}
		}

		// IEnumerator implementation

		public IEnumerator GetEnumerator () {
			return new Enumerator (intervals);
		}

		private class Enumerator : IEnumerator {
			public Enumerator (IList list) {
				this.list = list;
				Reset ();
			}

			public object Current {
				get {
					if (ptr >= list.Count)
						throw new InvalidOperationException ();

					return list[ptr];
				}
			}

			public bool MoveNext () {
				if (ptr > list.Count)
					throw new InvalidOperationException ();
				
				return ++ ptr < list.Count;
			}

			public void Reset () {
				ptr = -1;
			}

			private IList list;
			private int ptr;
		}

		// private fields

		private ArrayList intervals;
	}
}