using System;

using System.Collections.Generic;

namespace EllipseTruncate {

	public class AngleRange {

		public static readonly double min = -Math.PI;

		public static readonly double max = Math.PI;

		public static readonly double period = max - min;

		public static readonly uint half = uint.MaxValue/2+1;

		public static readonly uint step = uint.MaxValue/16+1;

		public static uint discrete(uint a)

			{ return unchecked((a + step/2)/step*step); }

		public static uint toUIntDiscrete(double a)

			{ return discrete(toUInt(a)); }

		public static uint toUInt(double a)

			{ return unchecked((uint)Math.Round((a-min)/period*uint.MaxValue)); }

		public static double toDouble(uint a)

			{ return (double)a/(double)uint.MaxValue*period + min; }

		public struct Entry {

			public uint a0, a1;

			public Entry(uint a0, uint a1)

				{ this.a0 = a0; this.a1 = a1; }

			public bool isEmpty()

				{ return a0 == a1; }

			public Entry flipped()

				{ return new Entry(a1, a0); }

		}

		public bool flip = false;

		public readonly List<uint> angles = new List<uint>();</uint></uint>

		public AngleRange(bool fill = false)

			{ flip = fill; }

		public bool isEmpty()

			{ return angles.Count == 0 && !flip; }

		public bool isFull()

			{ return angles.Count == 0 && flip; }

		public void clear()

			{ angles.Clear(); flip = false; }

		public void fill()

			{ angles.Clear(); flip = true; }

		private void doSet(uint a0, uint a1) {

			angles.Clear();

			if (a0 < a1) {

				flip = false;

				angles.Add(a0);

				angles.Add(a1);

			} else {

				flip = true;

				angles.Add(a1);

				angles.Add(a0);

			}

		}

		public void set(Entry e) {

			if (e.isEmpty()) { clear(); return; }

			doSet(e.a0, e.a1);

		}

		public void set(AngleRange r, bool flip = false) {

			if (r == this) return;

			this.flip = (r.flip != flip);

			angles.Clear();

			angles.AddRange(r.angles);

		}

		public bool check() {

			if (angles.Count % 2 != 0)

				return false;

			for(int i = 1; i < angles.Count; ++i)

				if (angles[i-1] >= angles[i])

					return false;

			return true;

		}

		public void invert()

			{ flip = !flip; }

		private int find(uint a) {

			int i0 = 0, i1 = angles.Count - 1;

			if (a < angles[0]) return i1;

			if (angles[i1] <= a) return i1;

			while(true) {

				int i = (i1 + i0)/2;

				if (i == i0) break;

				if (angles[i] <= a) i0 = i; else i1 = i;

			}

			return i0;

		}

		private void remove(int p0, int p1) {

			if (p1 < p0) {

				angles.RemoveRange(p0, angles.Count - p0);

				angles.RemoveRange(0, p1 + 1);

			} else {

				angles.RemoveRange(p0, p1 - p0 + 1);

			}

		}

		private void insert(uint a) {

			int p = find(a);

			if (angles[p] == a) angles.RemoveAt(p); else

				if (a < angles[0]) angles.Insert(0, a); else

					angles.Insert(p+1, a);

		}

		private int decrease(int i)

			{ return i == 0 ? angles.Count - 1: i - 1; }

		private int increase(int i)

			{ return (i + 1)%angles.Count; }

		public void xor(Entry e) {

			if (e.isEmpty()) return;

			if (isEmpty()) { doSet(e.a0, e.a1); return; }

			if (isFull()) { doSet(e.a1, e.a0); return; }

			if (e.a1 < e.a0) flip = !flip;

			insert(e.a0);

			insert(e.a1);

		}

		public void xor(AngleRange r) {

			if (r.isEmpty()) { return; }

			if (r.isFull()) { invert(); return; }

			if (isEmpty()) { set(r); return; }

			if (isFull()) { set(r, true); return; }

			flip = flip != r.flip;

			foreach(uint a in r.angles)

				insert(a);

		}

		private bool doAdd(uint a0, uint a1) {

			int p0 = find(a0);

			int p1 = find(a1);

			if (p0 == p1) {

				bool v = (p0%2 != 0) == flip;

				if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) {

					if (v) { fill(); return true; }

					doSet(a0, a1);

				} else

				if (!v) {

					if (a1 < a0) flip = true;

					insert(a0);

					insert(a1);

				}

				return false;

			}

			bool v0 = (p0%2 != 0) == flip;

			bool v1 = (p1%2 != 0) == flip;

			remove(increase(p0), p1);

			if (!v0) insert(a0);

			if (!v1) insert(a1);

			if (angles.Count == 0) { flip = true; return true; }

			if (a1 < a0) flip = true;

			return false;

		}

		private bool doSubtract(uint a0, uint a1) {

			int p0 = find(a0);

			int p1 = find(a1);

			if (p0 == p1) {

				bool v = (p0%2 != 0) == flip;

				if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) {

					if (!v) { clear(); return true; }

					doSet(a1, a0);

				} else

				if (v) {

					if (a1 < a0) flip = false;

					insert(a0);

					insert(a1);

				}

				return false;

			}

			bool v0 = (p0%2 != 0) == flip;

			bool v1 = (p1%2 != 0) == flip;

			remove(increase(p0), p1);

			if (v0) insert(a0);

			if (v1) insert(a1);

			if (angles.Count == 0) { flip = false; return true; }

			if (a1 < a0) flip = false;

			return false;

		}

		public void add(Entry e) {

			if (!isFull() && !e.isEmpty())

				{ if (isEmpty()) doSet(e.a0, e.a1); else doAdd(e.a0, e.a1); }

		}

		public void subtract(Entry e) {

			if (!isEmpty() && !e.isEmpty())

				{ if (isFull()) doSet(e.a1, e.a0); else doSubtract(e.a0, e.a1); }

		}

		public void intersect(Entry e) {

			if (!isEmpty()) {

				if (e.isEmpty()) clear();

					else if (isFull()) doSet(e.a0, e.a1);

						else doSubtract(e.a1, e.a0);

			}

		}

		public void add(AngleRange r) {

			if (r == this || isFull() || r.isEmpty()) return;

			if (isEmpty()) { set(r); return; }

			if (r.isFull()) { fill(); return; }

			bool f = r.flip;

			uint prev = r.angles[r.angles.Count - 1];

			foreach(uint a in r.angles)

				if (f && doAdd(prev, a)) return;

					else { prev = a; f = !f; }

		}

		public void subtract(AngleRange r) {

			if (isEmpty() || r.isEmpty()) return;

			if (r == this || r.isFull()) { clear(); return; }

			if (isFull()) { set(r); invert(); return; }

			bool f = r.flip;

			uint prev = r.angles[r.angles.Count - 1];

			foreach(uint a in r.angles)

				if (f && doSubtract(prev, a)) return;

					else { prev = a; f = !f; }

		}

		public void intersect(AngleRange r) {

			if (r == this || isEmpty() || r.isFull()) return;

			if (r.isEmpty()) { clear(); return; }

			if (isFull()) { set(r); return; }

			bool f = !r.flip;

			uint prev = r.angles[r.angles.Count - 1];

			foreach(uint a in r.angles)

				if (f && doSubtract(prev, a)) return;

					else { prev = a; f = !f; }

		}

	}

}