/*
	$Id: Collections.cs 6 2009-12-26 00:58:57Z catwalk $
*/
using System;
using System.Collections;
using System.Collections.ObjectModel;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Linq;

namespace Hiyoko.Utilities{
	public class PriorityQueue<T> : Heap<PriorityQueue<T>.PriorityItem>{
		#region コンストラクタ
		
		public PriorityQueue() : base(new PriorityComparer()){
		}
		
		public PriorityQueue(bool isMaxHeap) : base(new PriorityComparer(), isMaxHeap){
		}
		
		public PriorityQueue(int capacity) : base(capacity, new PriorityComparer()){
		}
		
		public PriorityQueue(int capacity, bool isMaxHeap) : base(capacity, new PriorityComparer(), isMaxHeap){
		}
		
		#endregion
		
		#region クラス
		
		public class PriorityItem{
			public int Priority{get; private set;}
			public T Value{get; set;}
			
			public PriorityItem(int priority, T value){
				this.Priority = priority;
				this.Value = value;
			}
		}
		
		private class PriorityComparer : IComparer<PriorityItem>{
			public int Compare(PriorityItem x, PriorityItem y){
				return y.Priority.CompareTo(x);
			}
		}
		
		#endregion
	}
	
	public class Heap<T> : IEnumerable<T>, ICollection{
		#region フィールド
		
		private List<T> list;
		private IComparer<T> comparer;
		private bool isMaxHeap;
		
		#endregion
		
		#region コンストラクタ
		
		public Heap() : this(Comparer<T>.Default, false){
			this.list = new List<T>();
		}
		
		public Heap(IComparer<T> comparer) : this(comparer, false){
			this.list = new List<T>();
		}
		
		public Heap(bool isMaxHeap) : this(Comparer<T>.Default, isMaxHeap){
			this.list = new List<T>();
		}
		
		public Heap(IComparer<T> comparer, bool isMaxHeap){
			this.list = new List<T>();
			if(comparer == null){
				throw new ArgumentNullException();
			}
			this.comparer = comparer;
			this.isMaxHeap = isMaxHeap;
		}
		
		public Heap(int capacity) : this(Comparer<T>.Default, false){
			this.list = new List<T>(capacity);
		}
		
		public Heap(int capacity, IComparer<T> comparer) : this(comparer, false){
			this.list = new List<T>(capacity);
		}
		
		public Heap(int capacity, bool isMaxHeap) : this(Comparer<T>.Default, isMaxHeap){
			this.list = new List<T>(capacity);
		}
		
		public Heap(int capacity, IComparer<T> comparer, bool isMaxHeap) : this(comparer, isMaxHeap){
			this.list = new List<T>(capacity);
		}
		
		#endregion
		
		#region 関数
		
		public void Push(T item){
			int i = this.list.Count;
			this.list.Add(item);
			while(i != 0){
				int parentIndex = (i - 1) / 2;
				T parent = this.list[parentIndex];
				if(this.Compare(parent, item) > 0){	// iが親より小さければ入れ替え
					this.Swap(i, parentIndex);
					i = parentIndex;
				}else{	// iが親より大きければ終了
					break;
				}
			}
		}
		
		public T Pop(){
			if(list.Count > 0){
				T item = this.list[0];
				int lastIndex = this.list.Count - 1;
				this.list[0] = this.list[lastIndex];
				this.list.RemoveAt(lastIndex);
				int i = 0;
				int count = this.list.Count;
				while(true){
					int left = 2 * i + 1;
					int right = 2 * i + 2;
					int child;
					T childValue;
					if(left >= count){	// 子要素がない(終了)
						break;
					}else if(right >= count){	// 右の子要素がない
						child = left;
						childValue = this.list[left];
					}else{	// どちらもない場合は小さい方
						T leftValue = this.list[left];
						T rightValue = this.list[right];
						if(this.Compare(leftValue, rightValue) < 0){
							child = left;
							childValue = leftValue;
						}else{
							child = right;
							childValue = rightValue;
						}
					}
					if(this.Compare(this.list[i], childValue) > 0){	// iが子より大きければ入れ替え
						this.Swap(i, child);
						i = child;
					}else{	// iが子より小さければ終了
						break;
					}
				}
				return item;
			}else{	// 要素が無いときはエラー
				throw new InvalidOperationException();
			}
		}
		
		public T Peek(){
			return this.list[0];
		}
		
		public void Clear(){
			this.list.Clear();
		}
		
		public void CopyTo(T[] array, int index){
			this.list.CopyTo(array, index);
		}
		
		void ICollection.CopyTo(Array array, int index){
			((ICollection)this.list).CopyTo(array, index);
		}
		
		public T[] ToArray(){
			return this.list.ToArray();
		}
		
		public void TrimExcess(){
			this.list.TrimExcess();
		}
		
		private void Swap(int x, int y){
			T temp = this.list[y];
			this.list[y] = this.list[x];
			this.list[x] = temp;
		}
		
		private int Compare(T x, T y){
			if(this.isMaxHeap){
				return this.comparer.Compare(y, x);
			}else{
				return this.comparer.Compare(x, y);
			}
		}
		
		IEnumerator IEnumerable.GetEnumerator(){
			return this.list.GetEnumerator();
		}
		
		public IEnumerator<T> GetEnumerator(){
			return this.list.GetEnumerator();
		}
		
		#endregion
		
		#region プロパティ
		
		public int Count{
			get{
				return this.list.Count;
			}
		}
		
		public bool IsMaxHeap{
			get{
				return this.isMaxHeap;
			}
		}
		
		bool ICollection.IsSynchronized{
			get{
				return ((ICollection)this.list).IsSynchronized;
			}
		}
		
		object ICollection.SyncRoot{
			get{
				return ((ICollection)this.list).SyncRoot;
			}
		}
		
		#endregion
	}
	
	public class ReversedComparer<T> : IComparer<T>{
		private IComparer<T> comparer;
		
		public ReversedComparer(IComparer<T> comparer){
			if(comparer == null){
				throw new ArgumentNullException();
			}
			this.comparer = comparer;
		}
		
		public int Compare(T x, T y){
			return -(this.comparer.Compare(x, y));
		}
		
		public IComparer<T> BaseComparer{
			get{
				return this.comparer;
			}
		}
	}
	
	public class CustomComparer<T> : IComparer<T>{
		private Func<T, T, int> compare;
		
		public CustomComparer(Func<T, T, int> compare){
			if(compare == null){
				throw new ArgumentNullException();
			}
			this.compare = compare;
		}
		
		public int Compare(T x, T y){
			return this.compare(x, y);
		}
	}
	
	public static class ArrayEx{
		public static T[] Join<T>(params IEnumerable<T>[] arrays){
			List<T> dest = new List<T>();
			foreach(IEnumerable<T> e in arrays){
				dest.AddRange(e);
			}
			return dest.ToArray();
		}
		
		public static bool Equals<T>(this T[] x, T[] y){
			if(x == null){
				if(y == null){
					return true;
				}else{
					return false;
				}
			}else{
				if(y == null){
					return false;
				}else{
					if(x.Length != y.Length){
						return false;
					}else{
						IEnumerator e1 = x.GetEnumerator();
						IEnumerator e2 = y.GetEnumerator();
						while(e1.MoveNext() && e2.MoveNext()){
							if(!e1.Current.Equals(e2.Current)){
								return false;
							}
						}
						return true;
					}
				}
			}
		}
	}
	
	public static class StringCollectionEx{
		/// <summary>
		/// StringCollectionからstring[]を得る。
		/// </summary>
		/// <param name="sc">StringCollection</param>
		/// <returns>string[]</returns>
		public static string[] ToArray(this StringCollection sc){
			string[] retArray = new string[sc.Count];
			sc.CopyTo(retArray, 0);
			return retArray;
		}
	}
	
	public class GapBuffer<T> : IList<T>{
		#region フィールド
		
		T[] buffer;
		int gapIndex;
		int gapLength;
		
		#endregion 
		
		#region コンストラクタ
		
		public GapBuffer() : this(0){
		}
		
		public GapBuffer(int capacity){
			this.InitializeArray(capacity);
		}
		
		#endregion
		
		#region ロジック
		
		private void InitializeArray(int capacity){
			this.buffer = new T[capacity];
			this.gapIndex = 0;
			this.gapLength = this.buffer.Length;
		}
		
		private void Increase(){
			if(this.buffer.Length == 0){
				this.Resize(4);
			}else{
				this.Resize(this.buffer.Length * 2);
			}
		}
		
		private void Resize(int capacity){
			T[] oldBuffer = this.buffer;
			int oldGapLength = this.gapLength;
			
			this.buffer = new T[capacity];
			this.gapLength += this.buffer.Length - oldBuffer.Length;
			Array.Copy(oldBuffer, 0, this.buffer, 0, this.gapIndex);
			Array.Copy(oldBuffer, this.gapIndex + oldGapLength, this.buffer, this.gapIndex + this.gapLength, oldBuffer.Length - this.gapIndex - oldGapLength);
		}
		
		private void SetGapIndexInternal(int index){
			if(index < this.gapIndex){
				int num = this.gapIndex - index;
				for(int i = 0; i < num; i++){
					this.gapIndex--;
					this.Swap(this.gapIndex, this.gapIndex + this.gapLength);
				}
			}else if(this.gapIndex < index){
				int num = index - this.gapIndex;
				for(int i = 0; i < num; i++){
					this.Swap(this.gapIndex, this.gapIndex + this.gapLength);
					this.gapIndex++;
				}
			}
		}
		
		private void Swap(int x, int y){
			T temp = this.buffer[x];
			this.buffer[x] = this.buffer[y];
			this.buffer[y] = temp;
		}
		
		private int GetBufferIndex(int index){
			return (index < this.gapIndex) ? index : (index + this.gapLength);
		}
		
		private void CheckIndex(int index){
			if((index < 0) || ((this.buffer.Length - this.gapLength) <= index)){
				throw new ArgumentOutOfRangeException();
			}
		}
		
		#endregion
		
		#region 関数
		
		public void Add(T item){
			this.Insert(this.Count, item);
		}
		
		public void AddRange(IEnumerable<T> col){
			if(this.gapLength == 0){
				this.Increase();
			}
			this.SetGapIndexInternal(this.Count);
			foreach(T item in col){
				if(this.gapLength == 0){
					this.Increase();
				}
				this.buffer[this.gapIndex] = item;
				this.gapIndex++;
				this.gapLength--;
			}
		}
		
		public void Insert(int index, T item){
			if((index < 0) || ((this.buffer.Length - this.gapLength) < index)){
				throw new ArgumentOutOfRangeException();
			}
			if(this.gapLength == 0){
				this.Increase();
			}
			this.SetGapIndexInternal(index);
			this.buffer[this.gapIndex] = item;
			this.gapIndex++;
			this.gapLength--;
		}
		
		public void RemoveAt(int index){
			this.CheckIndex(index);
			if(this.gapLength == 0){
				this.Increase();
			}
			int bufIndex = this.GetBufferIndex(index);
			if((this.gapIndex + this.gapLength) == bufIndex){
				this.buffer[bufIndex] = default(T);
				this.gapLength++;
			}else{
				this.SetGapIndexInternal(index);
				this.buffer[bufIndex] = default(T);
				this.gapLength++;
			}
		}
		
		public void Clear(){
			this.gapIndex = 0;
			this.gapLength = this.buffer.Length;
			for(int i = 0; i < this.buffer.Length; i++){
				this.buffer[i] = default(T);
			}
		}
		
		public bool Contains(T item){
			foreach(T item2 in this){
				if(item.Equals(item2)){
					return true;
				}
			}
			return false;
		}
		
		public int IndexOf(T item){
			int i = 0;
			foreach(T item2 in this){
				if(item.Equals(item2)){
					return i;
				}
				i++;
			}
			return -1;
		}
		
		public bool Remove(T item){
			int idx = this.IndexOf(item);
			if(idx != -1){
				this.RemoveAt(idx);
				return true;
			}else{
				return false;
			}
		}
		
		public void CopyTo(T[] array, int arrayIndex){
			if(array == null){
				throw new ArgumentNullException();
			}
			if(arrayIndex < 0){
				throw new ArgumentOutOfRangeException();
			}
			if((array.Rank > 1) || (array.Length <= arrayIndex) || (this.Count > (array.Length - arrayIndex))){
				throw new ArgumentException();
			}
			int i = arrayIndex;
			foreach(T item in this){
				array[i] = item;
				i++;
			}
		}
		
		IEnumerator IEnumerable.GetEnumerator(){
			return this.GetEnumerator();
		}
		
		public IEnumerator<T> GetEnumerator(){
			int count = this.Count;
			for(int i = 0; i < count; i++){
				yield return this.buffer[this.GetBufferIndex(i)];
			}
		}
		
		public T[] ToArray(){
			if(this.gapLength == 0){
				this.Increase();
			}
			this.SetGapIndexInternal(this.Count);
			
			T[] array = new T[this.Count];
			Array.Copy(this.buffer, 0, array, 0, this.Count);
			return array;
		}
		
		public void TrimExcess(){
			if(this.gapLength == 0){
				this.Increase();
			}
			this.SetGapIndexInternal(this.Count);
			
			Array.Resize<T>(ref this.buffer, this.Count);
		}
		
		#endregion
		
		#region プロパティ
		
		public int Count{
			get{
				return this.buffer.Length - this.gapLength;
			}
		}
		
		public int Capacity{
			get{
				return this.buffer.Length;
			}
		}
		
		public T this[int index]{
			get{
				this.CheckIndex(index);
				return this.buffer[this.GetBufferIndex(index)];
			}
			set{
				this.CheckIndex(index);
				this.buffer[this.GetBufferIndex(index)] = value;
			}
		}
		
		public bool IsReadOnly{
			get{
				return false;
			}
		}
		
		public int GapIndex{
			get{
				return this.gapIndex;
			}
			set{
				if((value < 0) || ((this.buffer.Length - this.gapLength) < value)){
					throw new ArgumentOutOfRangeException();
				}
				if(this.gapLength == 0){
					this.Increase();
				}
				this.SetGapIndexInternal(value);
			}
		}
		
		public int GapLength{
			get{
				return this.gapLength;
			}
		}
		
		#endregion
	}
	
	public class PrefixDictionary<T> : IDictionary<string, T>{
		#region フィールド
		
		private PrefixTreeNode<T> root = new PrefixTreeNode<T>(default(char), default(T), false);
		private IComparer<char> comparer = null;
		private int count = 0;
		
		#endregion
		
		#region コンストラクタ
		
		public PrefixDictionary(){
			this.comparer = Comparer<char>.Default;
		}
		
		public PrefixDictionary(IComparer<char> comparer){
			if(comparer == null){
				throw new ArgumentNullException();
			}
			this.comparer = comparer;
		}
		
		#endregion
		
		#region ロジック
		
		private bool FindNode(PrefixTreeNode<T> node, string key, out PrefixTreeNode<T> oNode){
			if(String.IsNullOrEmpty(key)){
				throw new ArgumentException("key");
			}
			int index = 0;
			int lastIndex = key.Length - 1;
			oNode = node;
			while(oNode != null){
				PrefixTreeNode<T> found = null;
				LinkedListNode<PrefixTreeNode<T>> llNode = oNode.Children.First;
				char c = key[index];
				while(llNode != null){
					PrefixTreeNode<T> child = llNode.Value;
					int d = this.comparer.Compare(c, child.Char);
					if(d == 0){
						found = child;
						break;
					}else if(d > 0){
						break;
					}
					llNode = llNode.Next;
				}
				if(found != null){
					oNode = found;
					if(index == lastIndex){
						return true;
					}
					index++;
				}else{
					break;
				}
			}
			return false;
		}
		
		protected static void CheckKey(string key){
			if(key == null){
				throw new ArgumentNullException();
			}
			if(key == ""){
				throw new ArgumentException();
			}
		}
		
		#endregion
		
		#region 関数
		
		public KeyValuePair<string,T>[] Search(string key){
			string prefix;
			return this.Search(key, out prefix);
		}
		
		public KeyValuePair<string,T>[] Search(string key, out string prefix){
			PrefixTreeNode<T> result;
			if(this.FindNode(this.root, key, out result)){
				var list = new List<KeyValuePair<string, T>>();
				if(result.IsAcceptState){
					list.Add(result.Entry);
				}
				foreach(PrefixTreeNode<T> node in result.SubNodes){
					if(node.IsAcceptState){
						list.Add(node.Entry);
					}
				}
				prefix = key;
				return list.ToArray();
			}else if(result != this.root){
				prefix = result.Key;
			}else{
				prefix = "";
			}
			return new KeyValuePair<string, T>[0];
		}
		
		public KeyValuePair<string,T>[] Search(string key, out KeyValuePair<string, T>[] nears){
			PrefixTreeNode<T> result;
			if(this.FindNode(this.root, key, out result)){
				var list = new List<KeyValuePair<string, T>>();
				if(result.IsAcceptState){
					list.Add(result.Entry);
				}
				foreach(PrefixTreeNode<T> node in result.SubNodes){
					if(node.IsAcceptState){
						list.Add(node.Entry);
					}
				}
				nears = new KeyValuePair<string, T>[0];
				return list.ToArray();
			}else if(result != this.root){
				var list = new List<KeyValuePair<string, T>>();
				foreach(PrefixTreeNode<T> node in result.SubNodes){
					if(node.IsAcceptState){
						list.Add(node.Entry);
					}
				}
				nears = new KeyValuePair<string, T>[0];
				return new KeyValuePair<string, T>[0];
			}
			nears = new KeyValuePair<string, T>[0];
			return new KeyValuePair<string, T>[0];
		}
		
		public void Add(KeyValuePair<string, T> pair){
			this.Add(pair.Key, pair.Value);
		}
		
		public void Add(string key, T value){
			CheckKey(key);

			PrefixTreeNode<T> node = this.root;
			int index = 0;
			int lastIndex = key.Length - 1;
			while(true){
				PrefixTreeNode<T> found = null;
				LinkedListNode<PrefixTreeNode<T>> right = null;
				LinkedListNode<PrefixTreeNode<T>> llNode = node.Children.First;
				while(llNode != null){
					PrefixTreeNode<T> child = llNode.Value;
					int d = this.comparer.Compare(key[index], child.Char);
					if(d == 0){
						found = child;
						break;
					}else if(d > 0){
						right = llNode;
						break;
					}
					llNode = llNode.Next;
				}
				
				if(found != null){
					if(index == lastIndex){
						if(found.IsAcceptState){
							throw new ArgumentException("key");
						}else{
							found.IsAcceptState = true;
							found.Value = value;
							this.count++;
							break;
						}
					}else{
						node = found;
					}
				}else{
					PrefixTreeNode<T> newNode = new PrefixTreeNode<T>(node, key[index]);
					if(right != null){
						node.Children.AddBefore(right, newNode);
					}else{
						node.Children.AddLast(newNode);
					}
					if(index == lastIndex){
						newNode.Value = value;
						newNode.IsAcceptState = true;
						this.count++;
						break;
					}else{
						node = newNode;
					}
				}
				index++;
			}
		}
		
		public bool Remove(KeyValuePair<string, T> pair){
			return this.Remove(pair.Key);
		}
		
		public bool Remove(string key){
			CheckKey(key);
			PrefixTreeNode<T> node;
			if(FindNode(this.root, key, out node)){
				if(node.Children.Count > 0){
					node.IsAcceptState = false;
					node.Value = default(T);
				}else{
					node.Parent.Children.Remove(node);
				}
				this.count--;
				return true;
			}else{
				return false;
			}
		}
		
		public bool Contains(KeyValuePair<string, T> pair){
			T item;
			if(this.TryGetValue(pair.Key, out item)){
				return item.Equals(pair.Value);
			}else{
				return false;
			}
		}
		
		public bool ContainsKey(string key){
			PrefixTreeNode<T> node;
			if(this.FindNode(this.root, key, out node)){
				return node.IsAcceptState;
			}else{
				return false;
			}
		}
		
		public bool TryGetValue(string key, out T item){
			PrefixTreeNode<T> node;
			if(this.FindNode(this.root, key, out node)){
				if(node.IsAcceptState){
					item = node.Value;
					return true;
				}
			}
			item = default(T);
			return false;
		}
		
		public void Clear(){
			this.root.Children.Clear();
		}
		
		IEnumerator IEnumerable.GetEnumerator(){
			return this.GetEnumerator();
		}
		
		public IEnumerator<KeyValuePair<string,T>> GetEnumerator(){
			foreach(PrefixTreeNode<T> node in this.Nodes){
				if(node.IsAcceptState){
					yield return node.Entry;
				}
			}
		}
		
		public void CopyTo(KeyValuePair<string,T>[] array, int arrayIndex){
			if(array == null){
				throw new ArgumentNullException();
			}
			if(arrayIndex < 0){
				throw new ArgumentOutOfRangeException();
			}
			if((array.Rank > 1) || (array.Length <= arrayIndex) || (this.Count > (array.Length - arrayIndex))){
				throw new ArgumentException();
			}
			int i = arrayIndex;
			foreach(PrefixTreeNode<T> node in this.Nodes){
				if(node.IsAcceptState){
					array[i] = node.Entry;
					i++;
				}
			}
		}
		
		#endregion
		
		#region プロパティ
		
		public int Count{
			get{
				return this.count;
			}
		}
		
		public T this[string key]{
			get{
				CheckKey(key);
				PrefixTreeNode<T> node;
				if(this.FindNode(this.root, key, out node)){
					return node.Value;
				}else{
					throw new KeyNotFoundException();
				}
			}
			set{
				CheckKey(key);
				PrefixTreeNode<T> node;
				if(this.FindNode(this.root, key, out node)){
					node.IsAcceptState = true;
					node.Value = value;
				}else{
					this.Add(key, value);
				}
			}
		}
		
		public ICollection<string> Keys{
			get{
				var list = new Collection<string>();
				foreach(PrefixTreeNode<T> node in this.Nodes){
					if(node.IsAcceptState){
						list.Add(node.Key);
					}
				}
				return list;
			}
		}
		
		public ICollection<T> Values{
			get{
				var list = new Collection<T>();
				foreach(PrefixTreeNode<T> node in this.Nodes){
					if(node.IsAcceptState){
						list.Add(node.Value);
					}
				}
				return list;
			}
		}
		
		public bool IsReadOnly{
			get{
				return false;
			}
		}
		
		public PrefixTreeNode<T> Root{
			get{
				return this.root;
			}
		}
		
		public IEnumerable<PrefixTreeNode<T>> Nodes{
			get{
				return this.root.SubNodes;
			}
		}
		
		#endregion
	}

	public class PrefixTreeNode<T>{
		#region フィールド
		
		public char Char{get; private set;}
		public T Value{get; set;}
		public PrefixTreeNode<T> Parent{get; set;}
		public LinkedList<PrefixTreeNode<T>> Children{get; set;}
		public bool IsAcceptState{get; set;}
		
		#endregion
		
		#region コンストラクタ
		
		public PrefixTreeNode(PrefixTreeNode<T> parent, char key) : this(parent, key, default(T), false){
		}
		
		public PrefixTreeNode(PrefixTreeNode<T> parent, char key, T value) : this(parent, key, default(T), true){
		}
		
		public PrefixTreeNode(PrefixTreeNode<T> parent, char key, T value, bool isAcceptState) : this(key, value, isAcceptState){
			if(parent == null){
				throw new ArgumentNullException();
			}
			this.Parent = parent;
			this.Children = new LinkedList<PrefixTreeNode<T>>();
		}
		
		public PrefixTreeNode(char key, T value, bool isAcceptState){
			this.Char = key;
			this.Value = value;
			this.IsAcceptState = isAcceptState;
			this.Children = new LinkedList<PrefixTreeNode<T>>();
		}
		
		#endregion
		
		#region プロパティ
		
		/// <summary>
		/// キー文字列を取得する。
		/// </summary>
		public string Key{
			get{
				PrefixTreeNode<T>[] nodes = this.PrefixNodes.ToArray();
				if(nodes.Length > 0){
					char[] chars = new char[nodes.Length + 1];
					for(int i = nodes.Length - 1, j = 0; j < nodes.Length; i--, j++){
						chars[j] = nodes[i].Char;
					}
					chars[nodes.Length] = this.Char;
					return new String(chars);
				}else{
					if(this.Char == '\0'){
						return String.Empty;
					}else{
						return this.Char.ToString();
					}
				}
			}
		}
		
		/// <summary>
		/// プレフィックスとなる上位ノードを取得する。
		/// 自分自身を含まない。
		/// <summary>
		public IEnumerable<PrefixTreeNode<T>> PrefixNodes{
			get{
				PrefixTreeNode<T> node = this;
				PrefixTreeNode<T> parent = this.Parent;
				while((parent != null) && (parent.Parent != null)){
					yield return parent;
					parent = parent.Parent;
				}
			}
		}
		
		/// <summary>
		/// 同じ長さで同じプレフィックスを持つノードを取得する。
		/// 自分自身を含む。
		/// <summary>
		public IEnumerable<PrefixTreeNode<T>> ColumnNodes{
			get{
				PrefixTreeNode<T> parent = this.Parent;
				if(parent != null){
					foreach(PrefixTreeNode<T> node in parent.Children){
						yield return node;
					}
				}
			}
		}
		
		/// <summary>
		/// 自分をプレフィックスとするノードを取得する。
		/// 自分自身を含まない。
		/// </summary>
		public IEnumerable<PrefixTreeNode<T>> SubNodes{
			get{
				foreach(PrefixTreeNode<T> node in this.Children){
					yield return node;
					foreach(PrefixTreeNode<T> node2 in node.SubNodes){
						yield return node2;
					}
				}
			}
		}
		
		public KeyValuePair<string,T> Entry{
			get{
				return new KeyValuePair<string, T>(this.Key, this.Value);
			}
		}
		
		#endregion
	}
	
	
	interface ISplitter<TSrc, TDst>{
		TDst[] Split(TSrc src);
		TSrc Join(TDst[] src);
	}
	
	public class StringSplitter : ISplitter<string, char>{
		public char[] Split(string src){
			return src.ToCharArray();
		}
		
		public string Join(char[] src){
			return new String(src);
		}
	}
	
	public class SkipList<T> : IList<T>{
		#region フィールド
		
		private SkipListNode topLeft;
		private SkipListNode bottomLeft;
		private SkipListNode topRight;
		private SkipListNode bottomRight;
		private int levels = 1;
		private int count = 0;
		private const int maxLevels = Int32.MaxValue;
		private Random random = new Random();
		
		#endregion
		
		#region コンストラクタ
		
		public SkipList(){
			this.topLeft = GetHeaderNode();
			this.bottomLeft = this.topLeft;
			this.topRight = this.bottomRight = this.topLeft.Next;
		}
		
		#endregion
		
		#region ロジック
		
		private static SkipListNode GetHeaderNode(){
			SkipListNode negativeInfinity = new SkipListNodeHeader();
			SkipListNode positiveInfinity = new SkipListNodeFooter();
			
			negativeInfinity.Next = positiveInfinity;
			positiveInfinity.Previous = negativeInfinity;
			
			return negativeInfinity;
		}
		
		protected virtual int GetRandomLevel(){
			const int q = Int32.MaxValue / 2;
			int newLevels = 1;
			int max = Math.Min(this.levels + 1, maxLevels);
			while ((random.Next() < q) && (newLevels < max)){
			    newLevels++;
			}
			return newLevels;
		}
		
		protected virtual void ClearEmptyLevels(){
			if(this.levels > 1){
				SkipListNode current = this.topLeft;
				while(current != this.bottomLeft){
					if(current.IsHeader && current.Next.IsFooter){
						SkipListNode belowLeft = current.Below;
						SkipListNode belowRight = current.Next.Below;
						this.topLeft = belowLeft;
						this.topRight = belowRight;
						this.levels--;
						current = belowLeft;
					}else{
						break;
					}
				}
			}
		}
		
		protected virtual SkipListNode GetNodeAt(int index){
			if((index < 0) || (this.count <= index)){
				throw new ArgumentOutOfRangeException("index");
			}
			// Headerの分インクリメント
			index++;
			
			SkipListNode node = this.topLeft;
			int d = 0;
			while(true){
				if(d < index){
					int t = d + node.NextDistance;
					if(t == index){
						return node.Next;
					}else if(t < index){
						d = t;
						node = node.Next;
					}else{
						if((index - d) > (t - index)){
							d = t;
							node = node.Next.Below;
						}else{
							node = node.Below;
						}
					}
				}else{
					int t = d - node.PreviousDistance;
					if(t == index){
						if(node.IsHeader){
							throw new Exception();
						}
						return node.Previous;
					}else if(t > index){
						d = t;
						if(node.IsHeader){
							throw new Exception();
						}
						node = node.Previous;
					}else{
						if((d - index) > (index - t)){
							d = t;
							node = node.Previous.Below;
						}else{
							node = node.Below;
						}
					}
				}
			}
			throw new SystemException();
		}
		
		#endregion
		
		#region 関数
		
		public virtual void Add(T value){
			this.Insert(this.Count, value);
		}
		
		public virtual void Insert(int index, T value){
			if((index < 0) || (this.count < index)){
				throw new ArgumentOutOfRangeException("index");
			}
			// Headerの分インクリメント
			index++;
			
			int levels = GetRandomLevel();
			
			// 上位レベルの構築
			int levelCount = levels - this.levels;
			while(levelCount > 0){
				SkipListNode newLevel = GetHeaderNode();
				
				int d = 0;
				SkipListNode node = this.topLeft;
				while(!(node.IsFooter)){
					d += node.NextDistance;
					node = node.Next;
				}
				newLevel.NextDistance = newLevel.Next.PreviousDistance = d;
				
				this.topLeft.Above = newLevel;
				this.topRight.Above = newLevel.Next;
				newLevel.Below = this.topLeft;
				newLevel.Next.Below = this.topRight;
				this.topLeft = newLevel;
				this.topRight = newLevel.Next;
				levelCount--;
				this.levels++;
			}
			
			// トップダウンにノードを構築
			SkipListNode current = this.topLeft;
			SkipListNode lastAbove = null;
			int currentLevel = this.levels;
			int currentDistance = 0;
			while(currentLevel > 0){
				while(!(current.IsFooter)){
					int t = currentDistance + current.NextDistance;
					if(t >= index){
						break;
					}else{
						currentDistance = t;
						current = current.Next;
					}
				}
				
				if(currentLevel > levels){
					current.NextDistance++;
					current.Next.PreviousDistance++;
				}else if((currentLevel == 1) || (currentLevel != levels) || ((currentDistance + 1) != index)){
					// currentの後ろに繋げる
					SkipListNode newNode = new SkipListNode(value);
					SkipListNode next = current.Next;
					newNode.Next = next;
					newNode.Previous = current;
					next.Previous = newNode;
					current.Next = newNode;
					if(currentLevel > 0){
						newNode.NextDistance = newNode.Next.PreviousDistance = currentDistance + current.NextDistance - index + 1;
						current.NextDistance = newNode.PreviousDistance = index - currentDistance;
					}
					
					if(lastAbove != null){
						lastAbove.Below = newNode;
						newNode.Above = lastAbove;
					}
					lastAbove = newNode;
				}
				
				current = current.Below;
				currentLevel--;
			}
			this.count++;
		}
		
		protected virtual void AddAfter(SkipListNode node, T value){
			if(node == null){
				throw new ArgumentNullException("node");
			}else if(node.IsHeader || node.IsFooter){
				throw new ArgumentException("node");
			}
			
			this.Insert(node.Index + 1, value);
		}
		
		protected virtual void AddBefore(SkipListNode node, T value){
			if(node == null){
				throw new ArgumentNullException("node");
			}else if(node.IsHeader || node.IsFooter){
				throw new ArgumentException("node");
			}
			
			this.Insert(node.Index, value);
		}
		
		public virtual bool Contains(T value){
			SkipListNode node = this.bottomLeft.Next;
			while(!(node.IsFooter)){
				if(node.Value.Equals(value)){
					return true;
				}
				node = node.Next;
			}
			return false;
		}
		
		public virtual bool Remove(T value){
			SkipListNode node = this.bottomLeft.Next;
			while(!(node.IsFooter)){
				if(node.Value.Equals(value)){
					this.Remove(node);
					return true;
				}
				node = node.Next;
			}
			return false;
		}
		
		public virtual void RemoveAt(int index){
			this.Remove(this.GetNodeAt(index));
		}
		
		protected virtual void Remove(SkipListNode node){
			if(node == null){
				throw new ArgumentNullException("node");
			}else if(node.IsHeader || node.IsFooter){
				throw new ArgumentException("node");
			}
			
			SkipListNode prev = node.HighestNode.Previous;
			while(prev != null){
				SkipListNode above = prev.Above;
				while(above != null){
					prev = above;
					above.NextDistance--;
					above.Next.PreviousDistance--;
					if(above.Above != null){
						above = above.Above;
					}else{
						break;
					}
				}
				prev = prev.Previous;
			}
			
			node = node.LowestNode;
			while(node != null){
				node.Previous.Next = node.Next;
				node.Next.Previous = node.Previous;
				node.Previous.NextDistance += node.NextDistance - 1;
				node.Next.PreviousDistance += node.PreviousDistance - 1;
				
				node = node.Above;
			}
			
			this.count--;
			this.ClearEmptyLevels();
		}
		
		public virtual int IndexOf(T value){
			int idx = 0;
			SkipListNode node = this.bottomLeft.Next;
			while(!(node.IsFooter)){
				if(node.Value.Equals(value)){
					return idx;
				}
				node = node.Next;
				idx++;
			}
			return -1;
		}
		
		public virtual void Clear(){
			this.count = 0;
			this.levels = 1;
			this.topLeft = GetHeaderNode();
			this.bottomLeft = this.topLeft;
			this.topRight = this.bottomRight = this.topLeft.Next;
		}
		
		IEnumerator IEnumerable.GetEnumerator(){
			return this.GetEnumerator();
		}
		
		public virtual IEnumerator<T> GetEnumerator(){
			SkipListNode node = this.bottomLeft.Next;
			while(!(node.IsFooter)){
				yield return node.Value;
				node = node.Next;
			}
		}
		
		public virtual void CopyTo(T[] array, int arrayIndex){
			if(array == null){
				throw new ArgumentNullException();
			}
			if(arrayIndex < 0){
				throw new ArgumentOutOfRangeException();
			}
			if((array.Rank > 1) || (array.Length <= arrayIndex) || (this.Count > (array.Length - arrayIndex))){
				throw new ArgumentException();
			}
			int i = arrayIndex;
			foreach(T value in this){
				array[i] = value;
				i++;
			}
		}
		/*
		public void DebugPrint(){
			SkipListNode col = this.topLeft;
			Console.WriteLine("DEBUGPRINT");
			while(col != null){
				SkipListNode node = col;
				while(node != null){
					if(node.Previous == null){
						Console.Write("_", node.Index);
					}else{
						Console.Write("{0}", node.Index);
					}
					if(node.NextDistance > 1){
						Console.Write("-{0}{1}", node.NextDistance, new String(' ', (node.NextDistance - 1) * 2 - 1));
					}else{
						Console.Write(" ");
					}
					node = node.Next;
				}
				Console.Write("\n");
				col = col.Below;
			}
		}
		*/
		#endregion
		
		#region プロパティ
		
		public virtual T this[int index]{
			get{
				return this.GetNodeAt(index).Value;
			}
			set{
				this.GetNodeAt(index).Value = value;
			}
		}
		
		public int Count{
			get{
				return this.count;
			}
			protected set{
				this.count = value;
			}
		}
		
		public virtual bool IsReadOnly{
			get{
				return false;
			}
		}
		
		public int Levels{
			get{
				return this.levels;
			}
			protected set{
				this.levels = value;
			}
		}
		
		protected SkipListNode TopLeft{
			get{
				return this.topLeft;
			}
			set{
				this.topLeft = value;
			}
		}
		
		protected SkipListNode TopRight{
			get{
				return this.topRight;
			}
			set{
				this.topRight = value;
			}
		}
		
		protected SkipListNode BottomLeft{
			get{
				return this.bottomLeft;
			}
			set{
				this.bottomLeft = value;
			}
		}
		
		protected SkipListNode BottomRight{
			get{
				return this.bottomRight;
			}
			set{
				this.bottomRight = value;
			}
		}
		
		#endregion
		
		#region クラス
		
		protected class SkipListNode{
			public T Value{get; set;}
			public SkipListNode Next{get; set;}
			public SkipListNode Previous{get; set;}
			public SkipListNode Above{get; set;}
			public SkipListNode Below{get; set;}
			public int NextDistance{get; set;}
			public int PreviousDistance{get; set;}
			
			public SkipListNode(){
				this.NextDistance = 1;
				this.PreviousDistance = 1;
			}
			
			public SkipListNode(T value) : this(){
				this.Value = value;
			}
			
			public virtual bool IsHeader{
				get{
					return false;
				}
			}
			
			public virtual bool IsFooter{
				get{
					return false;
				}
			}
			
			public SkipListNode LowestNode{
				get{
					SkipListNode node = this;
					while(node.Below != null){
						node = node.Below;
					}
					return node;
				}
			}
			
			public SkipListNode HighestNode{
				get{
					SkipListNode node = this;
					while(node.Above != null){
						node = node.Above;
					}
					return node;
				}
			}
			
			public int Index{
				get{
					SkipListNode node = this.HighestNode;
					int idx = 0;
					while(!(node.IsHeader)){
						idx += node.PreviousDistance;
						node = node.Previous.HighestNode;
					}
					return idx;
				}
			}
		}
		
		protected class SkipListNodeHeader : SkipListNode{
			public SkipListNodeHeader() : base(){
			}
			
			public override bool IsHeader{
				get{
					return true;
				}
			}
		}
		
		protected class SkipListNodeFooter : SkipListNode{
			public SkipListNodeFooter() : base(){
			}
			
			public override bool IsFooter{
				get{
					return true;
				}
			}
		}
		
		#endregion
	}
	
	public class SkipListDictionary<TKey, TValue> : SkipList<KeyValuePair<TKey, TValue>>, IDictionary<TKey, TValue>{
		private IComparer<TKey> comparer;
		
		public SkipListDictionary() : this(Comparer<TKey>.Default){
		}
		
		public SkipListDictionary(IComparer<TKey> comparer){
			this.comparer = comparer;
		}
		
		#region 使用不可public関数
		
		public override void Insert(int index, KeyValuePair<TKey, TValue> value){
			throw new InvalidOperationException();
		}
		
		#endregion
		
		#region 関数
		
		public override void Add(KeyValuePair<TKey, TValue> item){
			SkipListNode node = this.TopLeft;
			int currentLevel = this.Levels;
			while(currentLevel > 0){
				while(!(node.Next.IsFooter)){
					int d = this.comparer.Compare(node.Next.Value.Key, item.Key);
					if(d == 0){
						throw new ArgumentException("key");
					}else if(d > 0){
						base.Insert(node.Index + 1, item);
						return;
					}
					node = node.Next;
				}
				currentLevel--;
				node = node.Below;
			}
			base.Insert(0, item);
		}
		
		public void Add(TKey key, TValue value){
			this.Add(new KeyValuePair<TKey, TValue>(key, value));
		}
		
		public bool Remove(TKey key){
			SkipListNode node;
			if(this.TryGetNode(key, out node)){
				this.RemoveAt(node.Index);
				return true;
			}else{
				return false;
			}
		}
		
		public override bool Remove(KeyValuePair<TKey, TValue> item){
			return this.Remove(item.Key);
		}
		
		public override bool Contains(KeyValuePair<TKey, TValue> item){
			TValue value;
			if(this.TryGetValue(item.Key, out value)){
				return value.Equals(item.Value);
			}else{
				return false;
			}
		}
		
		public bool TryGetValue(TKey key, out TValue value){
			SkipListNode node;
			if(this.TryGetNode(key, out node)){
				value = node.Value.Value;
				return true;
			}else{
				value = default(TValue);
				return false;
			}
		}
		
		protected bool TryGetNode(TKey key, out SkipListNode value){
			SkipListNode node = this.TopLeft;
			while(node != null){
				while(!(node.Next.IsFooter)){
					int d = this.comparer.Compare(node.Next.Value.Key, key);
					if(d == 0){
						value = node;
						return true;
					}else if(d > 0){
						break;
					}
					node = node.Next;
				}
				node = node.Below;
			}
			value = null;
			return false;
		}
		
		public bool ContainsKey(TKey key){
			SkipListNode node;
			return this.TryGetNode(key, out node);
		}
		
		public int IndexOf(TKey key){
			SkipListNode node;
			if(this.TryGetNode(key, out node)){
				return node.Index;
			}else{
				return -1;
			}
		}
		
		#endregion
		
		#region プロパティ
		
		public TValue this[TKey key]{
			get{
				TValue value;
				if(this.TryGetValue(key, out value)){
					return value;
				}else{
					throw new KeyNotFoundException();
				}
			}
			set{
				SkipListNode node = this.TopLeft;
				int currentLevel = this.Levels;
				while(currentLevel > 0){
					while(!(node.Next.IsFooter)){
						int d = this.comparer.Compare(node.Next.Value.Key, key);
						if(d == 0){
							node.Value = new KeyValuePair<TKey, TValue>(key, value);
						}else if(d > 0){
							break;
						}
						node = node.Next;
					}
					currentLevel--;
					if(currentLevel > 0){
						node = node.Below;
					}
				}
				
				base.Insert(node.Index + 1, new KeyValuePair<TKey, TValue>(key, value));
			}
		}
		
		public ICollection<TKey> Keys{
			get{
				TKey[] keys = new TKey[this.Count];
				int idx = 0;
				foreach(KeyValuePair<TKey, TValue> pair in this){
					keys[idx] = pair.Key;
					idx++;
				}
				return keys;
			}
		}
		
		public ICollection<TValue> Values{
			get{
				TValue[] values = new TValue[this.Count];
				int idx = 0;
				foreach(KeyValuePair<TKey, TValue> pair in this){
					values[idx] = pair.Value;
					idx++;
				}
				return values;
			}
		}
		
		#endregion
	}
}