Bird Programming Language: Part 3

using System;
using System.IO;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using System.Numerics;
using System.Linq;
using System.Text;
using System.Collections;
using System.Collections.ObjectModel;
using System.Reflection;

namespace Bird
{
	public class ByRef<T>
	{
		public T Object;

		public ByRef(T Object)
		{
			this.Object = Object;
		}
	}

	public struct AutoAllocatedList<T> : IEnumerable<T>
	{
		class Enumerator : IEnumerator, IEnumerator<T>
		{
			AutoAllocatedList<T> List;
			int Pos = -1;

			public Enumerator(AutoAllocatedList<T> List)
			{
				this.List = List;
			}

			public bool MoveNext()
			{
				Pos++;
				return Pos < List.Count;
			}

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

			object IEnumerator.Current
			{
				get { return List[Pos];  }
			}

			T IEnumerator<T>.Current
			{
				get { return List[Pos]; }
			}

			public void Dispose()
			{
			}
		}

		public List<T> List;

		public AutoAllocatedList(List<T> List)
		{
			this.List = List;
		}

		public T this[int Index]
		{
			get
			{
				if (Index < 0 || Index >= this.Count)
					throw new ArgumentOutOfRangeException("Index");

				return List[Index];
			}
			
			set
			{
				if (Index < 0 || Index >= this.Count)
					throw new ArgumentOutOfRangeException("Index");

				List[Index] = value;
			}
		}

		public int Count
		{
			get { return List == null ? 0 : List.Count; }
		}

		public void Set(List<T> List)
		{
			this.List = List;
		}

		public void Add(T Item)
		{
			Allocate();
			List.Add(Item);
		}

		public void AddRange(IEnumerable<T> Items)
		{
			Allocate();
			List.AddRange(Items);
		}

		public void AddRange(AutoAllocatedList<T> List)
		{
			if (List.List != null)
			{
				Allocate();
				this.List.AddRange(List.List);
			}
		}

		public void Allocate()
		{
			if (List == null)
				List = new List<T>();
		}

		public void ReAllocate()
		{
			List = new List<T>();
		}

		public void Insert(int Index, T Item)
		{
			Allocate();
			List.Insert(Index, Item);
		}

		public void InsertRange(int Index, IEnumerable<T> Items)
		{
			Allocate();
			List.InsertRange(Index, Items);
		}

		public void Remove(T Item)
		{
			if (List != null)
				List.Remove(Item);
		}

		public void RemoveAt(int Index)
		{
			if (Index < 0 || Index >= this.Count)
				throw new ArgumentOutOfRangeException("Index");

			List.RemoveAt(Index);
		}

		public void RemoveAll(Predicate<T> Func)
		{
			if (List != null)
				List.RemoveAll(Func);
		}

		public void RemoveRange(int Index, int Count)
		{
			if (Index < 0 || Index >= this.Count)
				throw new ArgumentOutOfRangeException("Index");

			if (Index + Count > this.Count)
				throw new ArgumentOutOfRangeException("Count");

			if (List != null)
				List.RemoveRange(Index, Count);
		}

		public bool Contains(T Item)
		{
			return List != null ? List.Contains(Item) : false;
		}

		public int IndexOf(T Item)
		{
			return List != null ? List.IndexOf(Item) : -1;
		}

		public static implicit operator AutoAllocatedList<T>(List<T> List)
		{
			return new AutoAllocatedList<T>(List);
		}

		public List<T> ToList()
		{
			Allocate();
			return List;
		}

		public AutoAllocatedList<T> Copy()
		{
			if (List == null) return new AutoAllocatedList<T>();
			else return new AutoAllocatedList<T>(List.ToList());
		}

		public AutoAllocatedList<T2> Change<T2>() where T2 : class
		{
			var Ret = new AutoAllocatedList<T2>();
			for (var i = 0; i < Count; i++)
				Ret.Add(this[i] as T2);

			return Ret;
		}

		public void Clear()
		{
			if (List != null)
				List.Clear();
		}

		public void ForEach(Action<T> Action)
		{
			if (List != null)
				List.ForEach(Action);
		}

		public bool TrueForAll(Predicate<T> Func)
		{
			return List == null ? true : List.TrueForAll(Func);
		}

		IEnumerator<T> IEnumerable<T>.GetEnumerator()
		{
			return new Enumerator(this);
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return new Enumerator(this);
		}
	}

	public class NotifiedList<T> : IList<T>
	{
		IList<T> _BaseList;
		Action _Changed;

		public IList<T> BaseList
		{
			get { return _BaseList; }
		}

		public NotifiedList(IList<T> BaseList, Action Changed)
		{
			if (BaseList == null)
				throw new ArgumentNullException("BaseList");

			if (Changed == null)
				throw new ArgumentNullException("Changed");

			_BaseList = BaseList;
			_Changed = Changed;
		}

		public int IndexOf(T item)
		{
			return _BaseList.IndexOf(item);
		}

		public void Insert(int index, T item)
		{
			_BaseList.Insert(index, item);
			_Changed();
		}

		public void RemoveAt(int index)
		{
			_BaseList.RemoveAt(index);
			_Changed();
		}

		public T this[int index]
		{
			get
			{
				return _BaseList[index];
			}

			set
			{
				_BaseList[index] = value;
				_Changed();
			}
		}

		public void Add(T item)
		{
			_BaseList.Add(item);
			_Changed();
		}

		public void Clear()
		{
			_BaseList.Clear();
			_Changed();
		}

		public bool Contains(T item)
		{
			return _BaseList.Contains(item);
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			_BaseList.CopyTo(array, arrayIndex);
		}

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

		public bool IsReadOnly
		{
			get { return _BaseList.IsReadOnly; }
		}

		public bool Remove(T item)
		{
			var Ret = _BaseList.Remove(item);
			if (Ret) _Changed();
			return Ret;
		}

		public IEnumerator<T> GetEnumerator()
		{
			return ((IEnumerable<T>)_BaseList).GetEnumerator();
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return ((IEnumerable)_BaseList).GetEnumerator();
		}
	}

	public class MyList<T> : IList<T>
	{
		T[] _Items;
		int _Count;

		public int Count
		{
			get { return _Count; }
		}

		public int Capacity
		{
			get
			{
				return _Items.Length;
			}

			set
			{
				if (value < _Count)
					throw new ArgumentOutOfRangeException();

				var NewItems = new T[value];
				CopyTo(NewItems, 0);
				_Items = NewItems;
			}
		}

		public MyList(int Capacity)
		{
			_Items = new T[Capacity];
		}

		public MyList()
		{
			_Items = new T[8];
		}

		public int IndexOf(T item)
		{
			for (var i = 0; i < _Count; i++)
				if (_Items[i].Equals(item)) return i;

			return -1;
		}

		public void Insert(int index, T item)
		{
			throw new NotImplementedException();
		}

		public void RemoveAt(int index)
		{
			throw new NotImplementedException();
		}

		public T this[int index]
		{
			get
			{
				if (index < 0 || index >= Count)
					throw new ArgumentOutOfRangeException("index");

				return _Items[index];
			}

			set
			{
				if (index < 0 || index >= Count)
					throw new ArgumentOutOfRangeException("index");

				_Items[index] = value;
			}
		}

		public void Add(T item)
		{
			if (Capacity == _Count)
				Capacity *= 2;

			_Items[_Count] = item;
			_Count++;
		}

		public void Clear()
		{
			_Count = 0;
		}

		public bool Contains(T item)
		{
			return IndexOf(item) != -1;
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			for (var i = 0; i < _Count; i++)
				array[arrayIndex + i] = _Items[i];
		}

		public bool IsReadOnly
		{
			get { return false; }
		}

		public bool Remove(T item)
		{
			var Index = IndexOf(item);
			if (Index == -1) return false;

			RemoveAt(Index);
			return true;
		}

		public IEnumerator<T> GetEnumerator()
		{
			throw new NotImplementedException();
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			throw new NotImplementedException();
		}
	}

	public abstract class Node<T> where T : Node<T>
	{
		public T Parent;

		//public abstract void ForEachChildren(Action<T> Func);

		public Node(T Parent)
		{
			this.Parent = Parent;
		}

        public T2 NodeGetParent<T2>(Predicate<T2> Func = null) where T2 : T
		{
			var Node = this;
			while (Node != null)
			{
				var TNode = Node as T2;
				if (TNode != null && (Func == null || Func(TNode)))
					return TNode;

				Node = Node.Parent;
			}

			return null;
		}
		
		public void ForEach(Action<T> Func)
		{
			Func(this as T);
		}
	}

	public struct DataList
	{
		public List<object> Data;
		public object Data1, Data2, Data3;

		public bool Contains(object Obj)
		{
			if (Data1 == Obj || Data2 == Obj || Data3 == Obj)
				return true;

			return Data != null && Data.Contains(Obj);
		}

		public bool Contains<T>()
		{
			if (Data1 is T) return true;
			if (Data2 is T) return true;
			if (Data3 is T) return true;
			if (Data == null) return false;

			for (var i = 0; i < Data.Count; i++)
			{
				var Obj = (T)Data[i];
				if (Obj != null) return true;
			}

			return false;
		}

		public IEnumerable<T> Enum<T>()
		{
			if (Data1 is T) yield return (T)Data1;
			if (Data2 is T) yield return (T)Data2;
			if (Data3 is T) yield return (T)Data3;
			if (Data == null) yield break;

			for (var i = 0; i < Data.Count; i++)
			{
				var Obj = (T)Data[i];
				if (Obj != null) yield return Obj;
			}
		}

		public T Get<T>()
		{
			if (Data1 is T) return (T)Data1;
			if (Data2 is T) return (T)Data2;
			if (Data3 is T) return (T)Data3;
			if (Data == null) return default(T);

			for (var i = 0; i < Data.Count; i++)
			{
				var Obj = (T)Data[i];
				if (Obj != null) return Obj;
			}

			return default(T);
		}

		public object Get(System.Type T)
		{
			if (Data1 == null) return null;
			if (Data1.GetType().IsSubOrEqual(T)) return Data1;

			if (Data2 == null) return null;
			if (Data2.GetType().IsSubOrEqual(T)) return Data2;

			if (Data3 == null) return null;
			if (Data3.GetType().IsSubOrEqual(T)) return Data3;

			if (Data == null) return null;
			foreach (var e in Data)
				if (e.GetType().IsSubOrEqual(T)) return e;

			return null;
		}

		public void Set(object Value, bool Overwrite = true)
		{
			var T = Value.GetType();

			if (Data1 == null)
			{
				Data1 = Value;
			}
			else if (Data1.GetType().IsSubOrEqual(T))
			{
				if (!Overwrite)
					throw new InvalidOperationException("The list already contains an object with the same type");

				Data1 = Value;
			}

			else if (Data2 == null)
			{
				Data2 = Value;
			}
			else if (Data2.GetType().IsSubOrEqual(T))
			{
				if (!Overwrite)
					throw new InvalidOperationException("The list already contains an object with the same type");

				Data2 = Value;
			}

			else if (Data3 == null)
			{
				Data3 = Value;
			}
			else if (Data3.GetType().IsSubOrEqual(T))
			{
				if (!Overwrite)
					throw new InvalidOperationException("The list already contains an object with the same type");

				Data3 = Value;
			}

			else if (Data != null)
			{
				for (var i = 0; i < Data.Count; i++)
					if (Data[i].GetType().IsSubOrEqual(T))
					{
						if (!Overwrite)
							throw new InvalidOperationException("The list already contains an object with the same type");

						Data[i] = Value;
						return;
					}

				Data.Add(Value);
			}
			else
			{
				Data = new List<object>() { Value };
			}
		}

		void Adjust(bool RemoveFromList)
		{
			if (Data != null && RemoveFromList)
				Data.RemoveAll(x => x == null);

			for (var i = 0; i < 3; i++)
			{
				if (Data1 == null)
				{
					Data1 = Data2;
					Data2 = Data3;

					if (Data != null && Data.Count > 0)
					{
						Data3 = Data[0];
						Data.RemoveAt(0);
					}
				}
				else if (Data2 == null)
				{
					Data2 = Data3;
					if (Data != null && Data.Count > 0)
					{
						Data3 = Data[0];
						Data.RemoveAt(0);
					}
				}
				else if (Data3 == null)
				{
					if (Data != null && Data.Count > 0)
					{
						Data3 = Data[0];
						Data.RemoveAt(0);
					}
				}
			}
		}

		public void Remove<T>()
		{
			Remove(typeof(T));
		}

		public void Remove(System.Type Type)
		{
			if (Data1 == null) return;
			if (Data1.GetType().IsSubOrEqual(Type)) Data1 = null;

			if (Data2 == null) return;
			if (Data2.GetType().IsSubOrEqual(Type)) Data2 = null;

			if (Data3 == null) return;
			if (Data3.GetType().IsSubOrEqual(Type)) Data3 = null;

			if (Data != null)
				Data.RemoveAll(x => x.GetType().IsSubOrEqual(Type));

			Adjust(false);
		}

		public void Clear()
		{
			Data1 = null;
			Data2 = null;
			Data3 = null;
			Data = null;
		}

		public T Create<T>(object[] Params, bool Overwrite) where T : class
		{
			var Ret = Activator.CreateInstance(typeof(T), Params);
			Set(Ret, Overwrite);
			return Ret as T;
		}

		public T Create<T>(params object[] Params) where T : class
		{
			return Create<T>(Params, true);
		}

		public T GetOrCreate<T>(params object[] Params) where T : class
		{
			var Ret = Get<T>();
			if (Ret == null) Ret = Create<T>(Params);
			return Ret;
		}

		public T GetOrCreate<T>(object Param) where T : class
		{
			var Ret = Get<T>();
			if (Ret == null)
				Ret = Create<T>(new[] { Param }, true);

			return Ret;
		}
	}

	unsafe public static class Helper
	{
		public static void CopyMembers(object Dst, object Src)
		{
			var DstType = Dst.GetType();
			var SrcType = Src.GetType();
			if (!DstType.IsSubclassOf(SrcType) && !DstType.IsEquivalentTo(SrcType))
				throw new ArgumentException("Invalid types");

			var Members = SrcType.GetMembers(BindingFlags.NonPublic | BindingFlags.Public
				| BindingFlags.Instance | BindingFlags.Static);
			
			for (var i = 0; i < Members.Length; i++)
			{
				var Member = Members[i] as FieldInfo;
				if (Member == null) continue;

				Member.SetValue(Dst, Member.GetValue(Src));
			}
		}

		public static void Foreach<T>(this T[] Array, Action<T> Func)
		{
			for (var i = 0; i < Array.Length; i++)
				Func(Array[i]);
		}

		public static bool TrueForAll<T>(this T[] Array, Predicate<T> Func)
		{
			for (var i = 0; i < Array.Length; i++)
				if (!Func(Array[i])) return false;

			return true;
		}

		public static bool Compare<T>(this List<T> List1, List<T> List2)
			where T : class
		{
			if (List1.Count != List2.Count) return false;

			for (var i = 0; i < List1.Count; i++)
				if (List1[i] != List2[i]) return false;

			return true;
		}

		public static bool Compare<T>(this T[] Array1, T[] Array2)
			where T : class
		{
			if (Array1.Length != Array2.Length) return false;

			for (var i = 0; i < Array1.Length; i++)
				if (Array1[i] != Array2[i]) return false;

			return true;
		}

		public static T[] Resize<T>(this T[] Array, int NewSize)
		{
			var MinSize = Math.Min(NewSize, Array.Length);
			var Ret = new T[NewSize];
			for (var i = 0; i < MinSize; i++)
				Ret[i] = Array[i];

			return Ret;
		}

		public static T[] Copy<T>(this T[] Array)
		{
			var Ret = new T[Array.Length];
			Array.CopyTo(Ret, 0);
			return Ret;
		}

		public static NotifiedList<T> AsNotifiedList<T>(this IList<T> BaseList, Action Changed)
		{
			return new NotifiedList<T>(BaseList, Changed);
		}

		public static int GetBracket(char c)
		{
			if (c == '(' || c == '[' || c == '{') return 1;
			if (c == ')' || c == ']' || c == '}') return -1;

			return 0;
		}

		public static bool GetBracket(char c, bool Back)
		{
			if (Back) return c == ')' || c == ']' || c == '}';
			else return c == '(' || c == '[' || c == '{';
		}

		public static void ProcessNewLines(string String, int Index, int Length, Action<int> NewLine)
		{
			NewLine(0);
			ProcessLineEnds(String, Index, Length, x => NewLine(x + 1));
		}

		public static void ProcessNewLines(string String, Action<int> NewLine)
		{
			NewLine(0);
			ProcessLineEnds(String, 0, String.Length, x => NewLine(x + 1));
		}

		public static void ProcessLineEnds(string String, int Index, int Length, Action<int> EndLine)
		{
			var End = Index + Length;
			for (var i = Index; i < End; i++)
			{
				var Chr = String[i];
				if (Chr == '\n')
				{
					EndLine(i);
				}
				else if (Chr == '\r')
				{
					if (i + 1 < End && String[i + 1] == '\n')
						i++;

					EndLine(i);
				}
			}
		}

		public static void ProcessLineEnds(string String, Action<int> EndLine)
		{
			ProcessLineEnds(String, 0, String.Length - 1, EndLine);
		}

		public static int GetLineCount(string String, int Index, int Length)
		{
			var Result = 0;
			ProcessLineEnds(String, Index, Length, x => Result++);
			return Result + 1;
		}

		public static int GetLineCount(string String)
		{
			var Result = 0;
			ProcessLineEnds(String, 0, String.Length, x => Result++);
			return Result + 1;
		}

		public static string[] GetStrings(IEnumerable<string> Array, IEnumerable<string> Skip = null)
		{
			var RetList = new List<string>();
			foreach (var e in Array)
			{
				if (Skip != null)
				{
					var Ok = true;
					foreach (var f in Skip)
						if (f.Contains(e))
						{
							Ok = false;
							break;
						}

					if (!Ok) continue;
				}

				if (!RetList.Contains(e))
					RetList.Add(e);
			}

			if (RetList.Count == 0) return null;
			else return RetList.ToArray();
		}

		public static bool IsIdChar(char c)
		{
			return char.IsLetterOrDigit(c) || c == '_';
		}

		public static void ProcessIndexLength(int RealLength, bool Back, ref int Index, ref int Length)
		{
			if (Back)
			{
				if (Index == -1) Index = RealLength - 1;
				if (Length == -1) Length = Index + 1;

				if (Index < -1 || Index > RealLength)
					throw new ArgumentOutOfRangeException("Index");

				if (Length < 0 || Index - Length < -1)
					throw new ArgumentOutOfRangeException("Index");
			}
			else
			{
				if (Index == -1) Index = 0;
				if (Length == -1) Length = RealLength - Index;

				if (Index < -1 || Index > RealLength)
					throw new ArgumentOutOfRangeException("Index");

				if (Length < 0 || Index + Length > RealLength)
					throw new ArgumentOutOfRangeException("Index");
			}
		}

		public static void Verify(int RealLength, int Index, int Length, string IndexErr = "Index", string LengthErr = "Length")
		{
			if (Index < 0 || RealLength < Index)
				throw new ArgumentOutOfRangeException(IndexErr);

			if (Length < 0 || RealLength < Index + Length)
				throw new ArgumentOutOfRangeException(LengthErr);
		}

		public static void Verify(int RealLength, int Index, string IndexErr = "Index")
		{
			if (Index < 0 || RealLength < Index)
				throw new ArgumentOutOfRangeException(IndexErr);
		}

		public static string GetRelativePath(string From, string To)
		{
			var FromAttr = GetPathAttribute(From);
			var ToAttr = GetPathAttribute(To);

			var Path = new StringBuilder(260);
			if (PathRelativePathTo(Path, From, FromAttr, To, ToAttr) == 0)
				throw new ArgumentException("Paths must have a common prefix");

			return Path.ToString();
		}

		private static int GetPathAttribute(string Path)
		{
			if (Directory.Exists(Path)) return FILE_ATTRIBUTE_DIRECTORY;
			else return FILE_ATTRIBUTE_NORMAL;
		}

		private const int FILE_ATTRIBUTE_DIRECTORY = 0x10;
		private const int FILE_ATTRIBUTE_NORMAL = 0x80;

		[DllImport("shlwapi.dll", SetLastError = true)]
		private static extern int PathRelativePathTo(StringBuilder pszPath,
			string pszFrom, int dwAttrFrom, string pszTo, int dwAttrTo);


		public static bool IsSubOrEqual(this System.Type Self, System.Type Type)
		{
			return Self.IsEquivalentTo(Type) || Self.IsSubclassOf(Type);
		}

		public static string[] GetSkipList(string[] List1, IEnumerable<string> List2)
		{
			if (List1 == null) return null;
			if (List2 == null) return List1.ToArray();

			var Ret = new List<string>();
			foreach (var e in List2)
			{
				for (var j = 0; j < List1.Length; j++)
					if (List1[j] == e) goto ContinueLabel;

				for (var j = 0; j < List1.Length; j++)
					if (e.Contains(List1[j]))
					{
						Ret.Add(e);
						break;
					}

			ContinueLabel: ;
			}

			return ToArrayWithoutSame(Ret);
		}

		public static T[] ToArrayWithoutSame<T>(List<T> List) where T : class
		{
			Helper.RemoveSameObject(List);
			if (List.Count == 0) return null;
			else return List.ToArray();
		}

		public static void RemoveSameObject<T>(List<T> List) where T : class
		{
			for (var i = 0; i < List.Count; i++)
				for (var j = i + 1; j < List.Count; j++)
					if (List[j] == List[i])
					{
						List.RemoveAt(j);
						j--;
					}
		}

		public static int Pow2Sqrt(int a)
		{
			var Val = 1;
			var Ret = 0;
			while (a > Val)
			{
				Val *= 2;
				Ret++;
			}

			return Ret;
		}

		public static BigInteger Pow2Sqrt(BigInteger a)
		{
			var Val = new BigInteger(1);
			var Ret = new BigInteger(0);
			while (a > Val)
			{
				Val *= 2;
				Ret++;
			}

			return Ret;
		}

		public static int Pow2(int a)
		{
			var Ret = 1;
			while (a > Ret) Ret *= 2;
			return Ret;
		}

		public static BigInteger Pow2(BigInteger a)
		{
			var Ret = 1U;
			while (a > Ret) Ret *= 2;
			return Ret;
		}

		public static T[] Slice<T>(this T[] Arr, int Index, int Count = -1)
		{
			if (Count == -1) Count = Arr.Length - Index;

			var Ret = new T[Count];
			for (int i = 0; i < Count; i++)
				Ret[i] = Arr[i + Index];

			return Ret;
		}

		public static List<T> Slice<T>(this List<T> Arr, int Index, int Count = -1)
		{
			if (Count == -1) Count = Arr.Count - Index;

			var Ret = new List<T>(Count);
			for (var i = 0; i < Count; i++)
				Ret.Add(Arr[i + Index]);

			return Ret;
		}

        public static IEnumerable<T> Union<T>(this IEnumerable<T> List, T New)
        {
            return List.Union(new[] { New });
        }
	}
}