package us.bannister.structures.trie2;

import java.util.Arrays;
import java.util.Comparator;

public class FixedTrieBuilder {
	private static class CountedSlot {
		int count;
		FixedTrie.Slot slot;
		CountedSlot(FixedTrie.Slot o) {
			// This could be optimized, but we are not so interested in builder performance.
			count = o.countSlots();
			slot = o;
		}
	}
	private static void cloneSlot(LinkedTrie.Slot slot1,FixedTrie.Slot slot2) {
		slot2.c = slot1.c;
		slot2.value = slot1.value;
		slot2.list = new FixedTrie.Slot[slot1.list.size()];
		int i = 0;
		for (LinkedTrie.Slot o1 : slot1.list) {
			slot2.list[i] = new FixedTrie.Slot();
			cloneSlot(o1,slot2.list[i++]);
		}
	}
	private static void sortSlot(FixedTrie.Slot slot) {
		int n = slot.list.length;
		CountedSlot[] a = new CountedSlot[n];
		for (int i=0; i<n; ++i) {
			a[i] = new CountedSlot(slot.list[i]);
		}
		Arrays.sort(a,new Comparator<CountedSlot>() {
			@Override public int compare(CountedSlot o1, CountedSlot o2) {
				return o2.count - o1.count;
			}
		});
		for (int i=0; i<n; ++i) {
			slot.list[i] = a[i].slot;
		}
	}
	public static FixedTrie makeFixed(LinkedTrie trie1) {
		FixedTrie trie2 = new FixedTrie();
		cloneSlot(trie1.root,trie2.root);
		sortSlot(trie2.root);
		return trie2;
	}
}