Blame mono/EllipseTruncate/AngleRange.cs

782bf6
using System;
782bf6
using System.Collections.Generic;
782bf6
782bf6
namespace EllipseTruncate {
782bf6
	public class AngleRange {
782bf6
		public static readonly double min = -Math.PI;
782bf6
		public static readonly double max = Math.PI;
782bf6
		public static readonly double period = max - min;
782bf6
		
782bf6
		public static readonly uint half = uint.MaxValue/2+1;
782bf6
		public static readonly uint step = uint.MaxValue/16+1;
782bf6
782bf6
		public static uint discrete(uint a)
782bf6
			{ return unchecked((a + step/2)/step*step); }
782bf6
		public static uint toUIntDiscrete(double a)
782bf6
			{ return discrete(toUInt(a)); }
782bf6
		public static uint toUInt(double a)
782bf6
			{ return unchecked((uint)Math.Round((a-min)/period*uint.MaxValue)); }
782bf6
		public static double toDouble(uint a)
782bf6
			{ return (double)a/(double)uint.MaxValue*period + min; }
782bf6
782bf6
		public struct Entry {
782bf6
			public uint a0, a1;
782bf6
			public Entry(uint a0, uint a1)
782bf6
				{ this.a0 = a0; this.a1 = a1; }
782bf6
			public bool isEmpty()
782bf6
				{ return a0 == a1; }
782bf6
			public Entry flipped()
782bf6
				{ return new Entry(a1, a0); }
782bf6
		}
782bf6
782bf6
		public bool flip = false;
782bf6
		public readonly List<uint> angles = new List<uint>();</uint></uint>
782bf6
		
782bf6
		public AngleRange(bool fill = false)
782bf6
			{ flip = fill; }
782bf6
		
782bf6
		public bool isEmpty()
782bf6
			{ return angles.Count == 0 && !flip; }
782bf6
		public bool isFull()
782bf6
			{ return angles.Count == 0 && flip; }
782bf6
782bf6
		public void clear()
782bf6
			{ angles.Clear(); flip = false; }
782bf6
		public void fill()
782bf6
			{ angles.Clear(); flip = true; }
782bf6
		
782bf6
		private void doSet(uint a0, uint a1) {
782bf6
			angles.Clear();
782bf6
			if (a0 < a1) {
782bf6
				flip = false;
782bf6
				angles.Add(a0);
782bf6
				angles.Add(a1);
782bf6
			} else {
782bf6
				flip = true;
782bf6
				angles.Add(a1);
782bf6
				angles.Add(a0);
782bf6
			}
782bf6
		}
782bf6
		
782bf6
		public void set(Entry e) {
782bf6
			if (e.isEmpty()) { clear(); return; }
782bf6
			doSet(e.a0, e.a1);
782bf6
		}
782bf6
		
782bf6
		public void set(AngleRange r, bool flip = false) {
782bf6
			if (r == this) return;
782bf6
			this.flip = (r.flip != flip);
782bf6
			angles.Clear();
782bf6
			angles.AddRange(r.angles);
782bf6
		}
782bf6
						
782bf6
		public bool check() {
782bf6
			if (angles.Count % 2 != 0)
782bf6
				return false;
782bf6
			for(int i = 1; i < angles.Count; ++i)
782bf6
				if (angles[i-1] >= angles[i])
782bf6
					return false;
782bf6
			return true;
782bf6
		}
782bf6
		
782bf6
		public void invert()
782bf6
			{ flip = !flip; }
782bf6
		
782bf6
		private int find(uint a) {
782bf6
			int i0 = 0, i1 = angles.Count - 1;
782bf6
			if (a < angles[0]) return i1;
782bf6
			if (angles[i1] <= a) return i1;
782bf6
			while(true) {
782bf6
				int i = (i1 + i0)/2;
782bf6
				if (i == i0) break;
782bf6
				if (angles[i] <= a) i0 = i; else i1 = i;
782bf6
			}
782bf6
			return i0;
782bf6
		}
782bf6
		
782bf6
		private void remove(int p0, int p1) {
782bf6
			if (p1 < p0) {
782bf6
				angles.RemoveRange(p0, angles.Count - p0);
782bf6
				angles.RemoveRange(0, p1 + 1);
782bf6
			} else {
782bf6
				angles.RemoveRange(p0, p1 - p0 + 1);
782bf6
			}
782bf6
		}
782bf6
		
782bf6
		private void insert(uint a) {
782bf6
			int p = find(a);
782bf6
			if (angles[p] == a) angles.RemoveAt(p); else
782bf6
				if (a < angles[0]) angles.Insert(0, a); else
782bf6
					angles.Insert(p+1, a);
782bf6
		}
782bf6
		
782bf6
		private int decrease(int i)
782bf6
			{ return i == 0 ? angles.Count - 1: i - 1; }
782bf6
		private int increase(int i)
782bf6
			{ return (i + 1)%angles.Count; }
782bf6
		
782bf6
		public void xor(Entry e) {
782bf6
			if (e.isEmpty()) return;
782bf6
			if (isEmpty()) { doSet(e.a0, e.a1); return; }
782bf6
			if (isFull()) { doSet(e.a1, e.a0); return; }
782bf6
			if (e.a1 < e.a0) flip = !flip;
782bf6
			insert(e.a0);
782bf6
			insert(e.a1);
782bf6
		}
782bf6
782bf6
		public void xor(AngleRange r) {
782bf6
			if (r.isEmpty()) { return; }
782bf6
			if (r.isFull()) { invert(); return; }
782bf6
			if (isEmpty()) { set(r); return; }
782bf6
			if (isFull()) { set(r, true); return; }
782bf6
			flip = flip != r.flip;
782bf6
			foreach(uint a in r.angles)
782bf6
				insert(a);
782bf6
		}
782bf6
				
782bf6
		private bool doAdd(uint a0, uint a1) {
782bf6
			int p0 = find(a0);
782bf6
			int p1 = find(a1);
782bf6
			if (p0 == p1) {
782bf6
				bool v = (p0%2 != 0) == flip;
782bf6
				if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) {
782bf6
					if (v) { fill(); return true; }
782bf6
					doSet(a0, a1);
782bf6
				} else
782bf6
				if (!v) {
782bf6
					if (a1 < a0) flip = true;
782bf6
					insert(a0);
782bf6
					insert(a1);
782bf6
				}
782bf6
				return false;
782bf6
			}
782bf6
782bf6
			bool v0 = (p0%2 != 0) == flip;
782bf6
			bool v1 = (p1%2 != 0) == flip;
782bf6
			remove(increase(p0), p1);
782bf6
			if (!v0) insert(a0);
782bf6
			if (!v1) insert(a1);
782bf6
			if (angles.Count == 0) { flip = true; return true; }
782bf6
			if (a1 < a0) flip = true;
782bf6
			return false;
782bf6
		}
782bf6
782bf6
		private bool doSubtract(uint a0, uint a1) {
782bf6
			int p0 = find(a0);
782bf6
			int p1 = find(a1);
782bf6
			if (p0 == p1) {
782bf6
				bool v = (p0%2 != 0) == flip;
782bf6
				if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) {
782bf6
					if (!v) { clear(); return true; }
782bf6
					doSet(a1, a0);
782bf6
				} else
782bf6
				if (v) {
782bf6
					if (a1 < a0) flip = false;
782bf6
					insert(a0);
782bf6
					insert(a1);
782bf6
				}
782bf6
				return false;
782bf6
			}
782bf6
782bf6
			bool v0 = (p0%2 != 0) == flip;
782bf6
			bool v1 = (p1%2 != 0) == flip;
782bf6
			remove(increase(p0), p1);
782bf6
			if (v0) insert(a0);
782bf6
			if (v1) insert(a1);
782bf6
			if (angles.Count == 0) { flip = false; return true; }
782bf6
			if (a1 < a0) flip = false;
782bf6
			return false;
782bf6
		}
782bf6
				
782bf6
		public void add(Entry e) {
782bf6
			if (!isFull() && !e.isEmpty())
782bf6
				{ if (isEmpty()) doSet(e.a0, e.a1); else doAdd(e.a0, e.a1); }
782bf6
		}
782bf6
		
782bf6
		public void subtract(Entry e) {
782bf6
			if (!isEmpty() && !e.isEmpty())
782bf6
				{ if (isFull()) doSet(e.a1, e.a0); else doSubtract(e.a0, e.a1); }
782bf6
		}
782bf6
		
782bf6
		public void intersect(Entry e) {
782bf6
			if (!isEmpty()) {
782bf6
				if (e.isEmpty()) clear();
782bf6
					else if (isFull()) doSet(e.a0, e.a1);
782bf6
						else doSubtract(e.a1, e.a0);
782bf6
			}
782bf6
		}
782bf6
782bf6
		public void add(AngleRange r) {
782bf6
			if (r == this || isFull() || r.isEmpty()) return;
782bf6
			if (isEmpty()) { set(r); return; }
782bf6
			if (r.isFull()) { fill(); return; }
782bf6
			bool f = r.flip;
782bf6
			uint prev = r.angles[r.angles.Count - 1];
782bf6
			foreach(uint a in r.angles)
782bf6
				if (f && doAdd(prev, a)) return;
782bf6
					else { prev = a; f = !f; }
782bf6
		}
782bf6
		
782bf6
		public void subtract(AngleRange r) {
782bf6
			if (isEmpty() || r.isEmpty()) return;
782bf6
			if (r == this || r.isFull()) { clear(); return; }
782bf6
			if (isFull()) { set(r); invert(); return; }
782bf6
			bool f = r.flip;
782bf6
			uint prev = r.angles[r.angles.Count - 1];
782bf6
			foreach(uint a in r.angles)
782bf6
				if (f && doSubtract(prev, a)) return;
782bf6
					else { prev = a; f = !f; }
782bf6
		}
782bf6
		
782bf6
		public void intersect(AngleRange r) {
782bf6
			if (r == this || isEmpty() || r.isFull()) return;
782bf6
			if (r.isEmpty()) { clear(); return; }
782bf6
			if (isFull()) { set(r); return; }
782bf6
			bool f = !r.flip;
782bf6
			uint prev = r.angles[r.angles.Count - 1];
782bf6
			foreach(uint a in r.angles)
782bf6
				if (f && doSubtract(prev, a)) return;
782bf6
					else { prev = a; f = !f; }
782bf6
		}
782bf6
	}
782bf6
}
782bf6