using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

/*=====================================================================

  File:      Interval.cs for Spatial Sample
  Summary:   Implements a sorted list of intervals.
  Date:	     August 16, 2005

---------------------------------------------------------------------
 
======================================================= */


//
// Gyorgy Fekete 
// Johns Hopkins University
// Physics and Astronomy
namespace Spherical.HTM
{
    public struct Int64AugPair {
        public bool full;
		public Int64 lo;
		public Int64 hi;
        public Int64AugPair(Int64Pair lohi, bool full) {
            this.lo = lohi.lo;
            this.hi = lohi.hi;
            this.full = full;
        }
		public Int64AugPair(Int64 lo, Int64 hi, bool full) {
			this.lo = lo;
			this.hi = hi;
            this.full = full;
		}
    }
	public struct Int64Pair
	{
		public Int64 lo;
		public Int64 hi;
		public Int64Pair(Int64 lo, Int64 hi) {
			this.lo = lo;
			this.hi = hi;
		}
	};

	public class Interval
	{
		public List<Int64Pair> pairList = new List<Int64Pair>();
		private List<Int64Pair> _other = null;

		public Interval() {
		}

		static private bool disjoint(Int64Pair a, Int64Pair b) {
			return (a.hi < b.lo || b.hi < a.lo);
		}
        public static List<Int64Pair> combine(List<Int64Pair> ranges, List<Int64Pair> newranges) {
            // aran
            List<Int64Pair> result = new List<Int64Pair>(ranges.Count);

            Int64Pair proto;

            
            //
            // Pop one list into proto
            bool protomod = false;
            bool protovalid = false;
            if(newranges.Count < 1) {
                foreach(Int64Pair p in ranges) {
                    result.Add(p);
                }
                return result;
            }

            // Build a new range
            int left = newranges.Count + ranges.Count;
            int i = 0, j = 0;
            if(ranges.Count > 0 && ranges[0].lo <= newranges[0].lo) {
                proto.lo = ranges[0].lo;
                proto.hi = ranges[0].hi;
                protomod = true;
                protovalid = true;
                i++;
            } else {
                proto.lo = newranges[0].lo;
                proto.hi = newranges[0].hi;
                protomod = true;
                protovalid = true;
                j++;
            }
            left--;
            while(left > 0) {
                protomod = false; // See if this iteration modifies proto..
                if(!protovalid) {
                    if(i >= ranges.Count) { // main list is exhausted
                        proto.lo = newranges[j].lo;
                        proto.hi = newranges[j].hi;
                        protomod = true;
                        protovalid = true;
                        j++;
                    } else if(j >= newranges.Count) {   // newrange exhausted
                        proto.lo = ranges[i].lo;
                        proto.hi = ranges[i].hi;
                        protomod = true;
                        protovalid = true;
                        i++;
                    } else if(ranges.Count > 0 && ranges[i].lo <= newranges[j].lo) {
                        proto.lo = ranges[i].lo;
                        proto.hi = ranges[i].hi;
                        protomod = true;
                        protovalid = true;
                        i++;
                    } else {
                        proto.lo = newranges[j].lo;
                        proto.hi = newranges[j].hi;
                        protomod = true;
                        protovalid = true;
                        j++;
                    }
                    left--;
                }
                if(i < ranges.Count) {
                    if(protovalid && !disjoint(proto, ranges[i])) {
                        proto.lo = Math.Min(ranges[i].lo, proto.lo);
                        proto.hi = Math.Max(ranges[i].hi, proto.hi);
                        i++;
                        left--;
                        protomod = true;
                    }
                }
                // proto may have been modified above
                //
                if(j < newranges.Count) {
                    if(protovalid && !disjoint(proto, newranges[j])) {
                        proto.lo = Math.Min(newranges[j].lo, proto.lo);
                        proto.hi = Math.Max(newranges[j].hi, proto.hi);
                        j++;
                        left--;
                        protomod = true;
                    }
                }
                if(!protomod) { // proto was disjoint from both rangetops
                    result.Add(proto);
                    protomod = false;
                    protovalid = false;
                }
                // only continue, if both lists are nonempty
                //if (j >= newranges.Count || i >= pairList.Count) {
                //    break;
                //}
            }
            if(protovalid) {
                result.Add(proto);
                protovalid = false;
            }
            return result;
        }

        public void merge(List<Int64Pair> newranges) {
			if (newranges == null) {
				return;
			}
			if (newranges.Count <= 0) {
				return;
			}
			Int64Pair proto;

			// Build a new range
			if (_other == null) {
				_other = new List<Int64Pair>();
			} else {
				_other.Clear();
			}
			int left = newranges.Count + pairList.Count;
			int i = 0, j = 0;
			//
			// Pop one list into proto
			bool protomod = false;
			bool protovalid = false;
			// newranges is not empty or null

			if (pairList.Count > 0 && pairList[0].lo <= newranges[0].lo) {
				proto.lo = pairList[0].lo;
				proto.hi = pairList[0].hi;
				protomod = true;
				protovalid = true;
				i++;
			} else {
				proto.lo = newranges[0].lo;
				proto.hi = newranges[0].hi;
				protomod = true;
				protovalid = true;
				j++;
			}
			left--;
			while (left > 0) {
				protomod = false; // See if this iteration modifies proto..
				if (!protovalid) {
					if (i >= pairList.Count) { // main list is exhausted
						proto.lo = newranges[j].lo;
						proto.hi = newranges[j].hi;
						protomod = true;
						protovalid = true;
						j++;
					} else if (j >= newranges.Count) {   // newrange exhausted
						proto.lo = pairList[i].lo;
						proto.hi = pairList[i].hi;
						protomod = true;
						protovalid = true;
						i++;
					} else if (pairList.Count > 0 && pairList[i].lo <= newranges[j].lo) {
						proto.lo = pairList[i].lo;
						proto.hi = pairList[i].hi;
						protomod = true;
						protovalid = true;
						i++;
					} else {
						proto.lo = newranges[j].lo;
						proto.hi = newranges[j].hi;
						protomod = true;
						protovalid = true;
						j++;
					}
					left--;
				}
				if (i < pairList.Count) {
					if (protovalid && !disjoint(proto, pairList[i])) {
						proto.lo = Math.Min(pairList[i].lo, proto.lo);
						proto.hi = Math.Max(pairList[i].hi, proto.hi);
						i++;
						left--;
						protomod = true;
					}
				}
				// proto may have been modified above
				//
				if (j < newranges.Count) {
					if (protovalid && !disjoint(proto, newranges[j])) {
						proto.lo = Math.Min(newranges[j].lo, proto.lo);
						proto.hi = Math.Max(newranges[j].hi, proto.hi);
						j++;
						left--;
						protomod = true;
					}
				}
				if (!protomod) { // proto was disjoint from both rangetops
					_other.Add(proto);
					protomod = false;
					protovalid = false;
				}
				// only continue, if both lists are nonempty
				//if (j >= newranges.Count || i >= pairList.Count) {
				//    break;
				//}
			}
			if (protovalid) {
				_other.Add(proto);
				protovalid = false;
			}
			//
			// at least one of the ranges is exhausted
			// is proto modified?
			// 
			//if (protomod) {
			//    _other.Add(proto);
			//}

			//while (i < pairList.Count) {
			//    proto.lo = pairList[i].lo;
			//    proto.hi = pairList[i].hi;
			//    _other.Add(proto);
			//    i++;
			//    left--;
			//}

			//while (j < newranges.Count) {
			//    _other.Add(newranges[j++]);
			//    left--;
			//}

			List<Int64Pair> tmp = pairList;
			pairList = _other;
			_other = tmp;
		}
        /// <summary>
        /// Add pair of hids to internal list of pairs. Does not do checking
        /// </summary>
        /// <param name="pair"></param>
        public void AddRange(Int64Pair pair) {
            pairList.Add(pair);
        }
		public void AddRange(Int64 lo, Int64 hi) {
			Int64Pair tp;
			tp.lo = lo;
			tp.hi = hi;
			pairList.Add(tp);
			return;
		}
		public void Clear() {
			pairList.Clear();
		}
		public static int ComparisonRanges(Int64Pair a, Int64Pair b) {
			return a.lo.CompareTo(b.lo);
		}
        /// <summary>
        /// Ensure that ranges are disjoint
        /// </summary>
		public void check() {
			for (int i = 1; i < pairList.Count; i++) {
				if (pairList[i - 1].hi > pairList[i].lo) {
					StringBuilder sb = new StringBuilder();
					sb.AppendFormat("{0}: ({1}, {2}), ({3}, {4})",
						i, pairList[i-1].lo, pairList[i-1].hi,
						pairList[i].lo, pairList[i].hi);
					
					throw new ApplicationException(sb.ToString());
				}
			}
		}
        /// <summary>
        /// Sort Interval by lows
        /// </summary>
		public void sort() {
			pairList.Sort(ComparisonRanges);
		}
		public static bool IsWellFormed(List<Int64Pair> sortedpairs){
			for (int i = 1; i < sortedpairs.Count; i++) {
				if (sortedpairs[i - 1].lo > sortedpairs[i].lo) {
					throw new Exception("sorted pair is not sorted");
				}
				if (sortedpairs[i - 1].hi + 1 >= sortedpairs[i].lo) {
					throw new Exception("sorted pair is not disjoint from neighbor");
				}
            }
			return true;
		}
        /// <summary>
        /// Merge adjacent intervals
        /// </summary>
		public void compact() {
			Int64Pair tp;
			int count;
			count = pairList.Count;
			count--; // because we compare i to t+1
			for (int i = 0; i < count; ) { // third part purposely empty
				if (pairList[i].hi + 1 == pairList[i + 1].lo) {
					tp.lo = pairList[i].lo;
					tp.hi = pairList[i + 1].hi;
					pairList.RemoveAt(i + 1);
					pairList.RemoveAt(i);
					pairList.Insert(i, tp);
					count--;
				} else {
					i++;
				}
			}
			return;
		}
        /// <summary>
        /// Merge adjacent intervals
        /// </summary>
        /// <param name="sortedPairs"></param>
		public static void compact(List<Int64Pair> sortedPairs) {
			Int64Pair tp;
			int count;
			count = sortedPairs.Count;
			count--; // because we compare i to t+1
			for (int i = 0; i < count; ) { // third part purposely empty
				if (sortedPairs[i].hi + 1 == sortedPairs[i + 1].lo) {
					tp.lo = sortedPairs[i].lo;
					tp.hi = sortedPairs[i + 1].hi;
					sortedPairs.RemoveAt(i + 1);
					sortedPairs.RemoveAt(i);
					sortedPairs.Insert(i, tp);
					count--;
				} else {
					i++;
				}
			}
			return;
		}
	}
}
