package com.polydes.common.collections;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import com.polydes.common.nodes.Branch;
import com.polydes.common.nodes.Leaf;
import com.polydes.common.nodes.NodeUtils;

public class SortedNodeCollection<T extends Leaf<T,U>, U extends Branch<T,U>> implements Collection<T>
{
	private List<T> list;
	private U root;
	
	private NodeOrderComparator comparator;
	
	public SortedNodeCollection(U root)
	{
		this.root = root;
		
		list = new ArrayList<>();
		comparator = new NodeOrderComparator();
	}
	
	public T get(int i)
	{
		return list.get(i);
	}
	
	@SuppressWarnings("unchecked")
	public ArrayList<T> copyList()
	{
		return (ArrayList<T>) ((ArrayList<T>) list).clone();
	}
	
	@Override
	public int size()
	{
		return list.size();
	}

	@Override
	public boolean isEmpty()
	{
		return list.isEmpty();
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean contains(Object o)
	{
		return binarySearch((T) o) >= 0;
	}

	@Override
	public Iterator<T> iterator()
	{
		return list.iterator();
	}
	
	@Override
	public Object[] toArray()
	{
		return list.toArray();
	}

	@Override
	public <S> S[] toArray(S[] a)
	{
		return list.toArray(a);
	}
	
	@Override
	public boolean add(T e)
	{
		int i = binarySearch(e);
		if(i >= 0)
			return false;
		
		list.add(-(i + 1), e);
		
		return true;
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(Object o)
	{
		int i = binarySearch((T) o);
		if(i < 0)
			return false;
		
		list.remove(i);
		return true;
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean containsAll(Collection<?> c)
	{
		for(Object o : c)
			if(binarySearch((T) o) < 0)
				return false;
		
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends T> c)
	{
		boolean changed = false;
		
		for(T t : c)
			changed = add(t) || changed;
		
		return changed;
	}
	
	@Override
	public boolean removeAll(Collection<?> c)
	{
		boolean changed = false;
		for(Object o : c)
			changed = remove(o) || changed;
		
		return changed;
	}

	@Override
	public boolean retainAll(Collection<?> c)
	{
		throw new UnsupportedOperationException();
	}

	@Override
	public void clear()
	{
		list.clear();
	}
	
	private int binarySearch(T node)
	{
		return Collections.binarySearch(list, node, comparator);
	}
	
	@SuppressWarnings("unchecked")
	public class NodeOrderComparator implements Comparator<T>
	{
		@Override
		public int compare(T o1, T o2)
		{
			int[] path = NodeUtils.getIndexPath(root, o1);
			
			int origDepth = NodeUtils.getDepth(o2);
			int depth = origDepth;
			while(depth > path.length)
			{
				o2 = (T) o2.getParent();
				--depth;
			}
			int pos = NodeUtils.getIndex(o2);
			
			if(path[depth - 1] != pos)
				return Integer.compare(path[depth - 1], pos);
			
			return Integer.compare(path.length, origDepth);
		}
	}
}
@@ -2404,40 +2404,8 @@
 %7D%0A%09%0A
-%09@SuppressWarnings(%22unchecked%22)%0A
 %09pub
@@ -2524,16 +2524,17 @@
 t%5B%5D path
+1
  = NodeU
@@ -2569,25 +2569,19 @@
 %0A%09%09%09
-%0A%09%09%09int origDep
+int%5B%5D pa
 th
+2
  = N
@@ -2596,178 +2596,116 @@
 .get
-Depth(o2);%0A%09%09%09int depth = origDepth;%0A%09%09%09while(depth %3E 
+IndexPath(root, o2);%0A%09%09%09%0A%09%09%09for(int i = 0, n = Math.min(
 path
+1
 .length
-)%0A%09%09%09%7B%0A%09%09%09%09o2 = (T) o2.getParent();%0A%09%09%09%09--depth;%0A%09%09%09%7D%0A%09%09%09int pos = NodeUtils.getIndex(o2);
+, path2.length); i %3C n; ++i)
 %0A%09%09%09
-%0A%09%09
 %09if(path
 %5Bdep
@@ -2704,28 +2704,27 @@
 path
-%5Bdepth - 1%5D != pos
+1%5Bi%5D != path2%5Bi%5D
 )%0A
+%09
 %09%09%09%09
@@ -2754,24 +2754,22 @@
 path
-%5Bdepth - 1%5D, pos
+1%5Bi%5D, path2%5Bi%5D
 );%0A%09
@@ -2801,16 +2801,17 @@
 are(path
+1
 .length,
@@ -2815,15 +2815,18 @@
 th, 
-origDep
+path2.leng
 th);

Fix dumb tree node comparator.