/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.trie;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.SortedMap;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.Map.Entry;

import org.apache.commons.collections4.Trie.Cursor;
import org.apache.commons.collections4.trie.analyzer.CharacterKeyAnalyzer;
import org.apache.commons.collections4.trie.analyzer.IntegerKeyAnalyzer;
import org.apache.commons.collections4.trie.analyzer.StringKeyAnalyzer;

import org.junit.Assert;
import org.junit.Test;

/**
 * JUnit tests.
 *
 * FIXME: add serialization support
 * TODO: integrate into test framework, utilize existing map tests
 *
 * @since 4.0
 * @version $Id$
 */
public class PatriciaTrieTest {

    @Test
    @SuppressWarnings("boxing") // OK in test code
    public void testSimple() {
        final PatriciaTrie<Integer, String> intTrie = new PatriciaTrie<Integer, String>(new IntegerKeyAnalyzer());
        Assert.assertTrue(intTrie.isEmpty());
        Assert.assertEquals(0, intTrie.size());

        intTrie.put(1, "One");
        Assert.assertFalse(intTrie.isEmpty());
        Assert.assertEquals(1, intTrie.size());

        Assert.assertEquals("One", intTrie.remove(1));
        Assert.assertNull(intTrie.remove(1));
        Assert.assertTrue(intTrie.isEmpty());
        Assert.assertEquals(0, intTrie.size());

        intTrie.put(1, "One");
        Assert.assertEquals("One", intTrie.get(1));
        Assert.assertEquals("One", intTrie.put(1, "NotOne"));
        Assert.assertEquals(1, intTrie.size());
        Assert.assertEquals("NotOne", intTrie.get(1));
        Assert.assertEquals("NotOne", intTrie.remove(1));
        Assert.assertNull(intTrie.put(1, "One"));
    }

    @Test
    @SuppressWarnings("boxing") // OK in test code
    public void testCeilingEntry() {
        final PatriciaTrie<Character, String> charTrie
            = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
        charTrie.put('c', "c");
        charTrie.put('p', "p");
        charTrie.put('l', "l");
        charTrie.put('t', "t");
        charTrie.put('k', "k");
        charTrie.put('a', "a");
        charTrie.put('y', "y");
        charTrie.put('r', "r");
        charTrie.put('u', "u");
        charTrie.put('o', "o");
        charTrie.put('w', "w");
        charTrie.put('i', "i");
        charTrie.put('e', "e");
        charTrie.put('x', "x");
        charTrie.put('q', "q");
        charTrie.put('b', "b");
        charTrie.put('j', "j");
        charTrie.put('s', "s");
        charTrie.put('n', "n");
        charTrie.put('v', "v");
        charTrie.put('g', "g");
        charTrie.put('h', "h");
        charTrie.put('m', "m");
        charTrie.put('z', "z");
        charTrie.put('f', "f");
        charTrie.put('d', "d");

        final Object[] results = new Object[] {
            'a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
            'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
            'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
            'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
            'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
            'z', "z"
        };

        for(int i = 0; i < results.length; i++) {
            final Map.Entry<Character, String> found = charTrie.ceilingEntry((Character)results[i]);
            Assert.assertNotNull(found);
            Assert.assertEquals(results[i], found.getKey());
            Assert.assertEquals(results[++i], found.getValue());
        }

        // Remove some & try again...
        charTrie.remove('a');
        charTrie.remove('z');
        charTrie.remove('q');
        charTrie.remove('l');
        charTrie.remove('p');
        charTrie.remove('m');
        charTrie.remove('u');

        Map.Entry<Character, String> found = charTrie.ceilingEntry('u');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'v', found.getKey());

        found = charTrie.ceilingEntry('a');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'b', found.getKey());

        found = charTrie.ceilingEntry('z');
        Assert.assertNull(found);

        found = charTrie.ceilingEntry('q');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'r', found.getKey());

        found = charTrie.ceilingEntry('l');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'n', found.getKey());

        found = charTrie.ceilingEntry('p');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'r', found.getKey());

        found = charTrie.ceilingEntry('m');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'n', found.getKey());

        found = charTrie.ceilingEntry('\0');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'b', found.getKey());

        charTrie.put('\0', "");
        found = charTrie.ceilingEntry('\0');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'\0', found.getKey());
    }

    @Test
    @SuppressWarnings("boxing") // OK in test code
    public void testLowerEntry() {
        final PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
        charTrie.put('c', "c");
        charTrie.put('p', "p");
        charTrie.put('l', "l");
        charTrie.put('t', "t");
        charTrie.put('k', "k");
        charTrie.put('a', "a");
        charTrie.put('y', "y");
        charTrie.put('r', "r");
        charTrie.put('u', "u");
        charTrie.put('o', "o");
        charTrie.put('w', "w");
        charTrie.put('i', "i");
        charTrie.put('e', "e");
        charTrie.put('x', "x");
        charTrie.put('q', "q");
        charTrie.put('b', "b");
        charTrie.put('j', "j");
        charTrie.put('s', "s");
        charTrie.put('n', "n");
        charTrie.put('v', "v");
        charTrie.put('g', "g");
        charTrie.put('h', "h");
        charTrie.put('m', "m");
        charTrie.put('z', "z");
        charTrie.put('f', "f");
        charTrie.put('d', "d");

        final Object[] results = new Object[] {
            'a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
            'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
            'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
            'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
            'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
            'z', "z"
        };

        for(int i = 0; i < results.length; i+=2) {
            //System.out.println("Looking for: " + results[i]);
            final Map.Entry<Character, String> found = charTrie.lowerEntry((Character)results[i]);
            if(i == 0) {
                Assert.assertNull(found);
            } else {
                Assert.assertNotNull(found);
                Assert.assertEquals(results[i-2], found.getKey());
                Assert.assertEquals(results[i-1], found.getValue());
            }
        }

        Map.Entry<Character, String> found = charTrie.lowerEntry((char)('z' + 1));
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'z', found.getKey());

        // Remove some & try again...
        charTrie.remove('a');
        charTrie.remove('z');
        charTrie.remove('q');
        charTrie.remove('l');
        charTrie.remove('p');
        charTrie.remove('m');
        charTrie.remove('u');

        found = charTrie.lowerEntry('u');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'t', found.getKey());

        found = charTrie.lowerEntry('v');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'t', found.getKey());

        found = charTrie.lowerEntry('a');
        Assert.assertNull(found);

        found = charTrie.lowerEntry('z');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'y', found.getKey());

        found = charTrie.lowerEntry((char)('z'+1));
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'y', found.getKey());

        found = charTrie.lowerEntry('q');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'o', found.getKey());

        found = charTrie.lowerEntry('r');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'o', found.getKey());

        found = charTrie.lowerEntry('p');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'o', found.getKey());

        found = charTrie.lowerEntry('l');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'k', found.getKey());

        found = charTrie.lowerEntry('m');
        Assert.assertNotNull(found);
        Assert.assertEquals((Character)'k', found.getKey());

        found = charTrie.lowerEntry('\0');
        Assert.assertNull(found);

        charTrie.put('\0', "");
        found = charTrie.lowerEntry('\0');
        Assert.assertNull(found);
    }

    @Test
    @SuppressWarnings("boxing") // OK in test code
    public void testIteration() {
        final PatriciaTrie<Integer, String> intTrie = new PatriciaTrie<Integer, String>(new IntegerKeyAnalyzer());
        intTrie.put(1, "One");
        intTrie.put(5, "Five");
        intTrie.put(4, "Four");
        intTrie.put(2, "Two");
        intTrie.put(3, "Three");
        intTrie.put(15, "Fifteen");
        intTrie.put(13, "Thirteen");
        intTrie.put(14, "Fourteen");
        intTrie.put(16, "Sixteen");

        TestCursor cursor = new TestCursor(
                1, "One", 2, "Two", 3, "Three", 4, "Four", 5, "Five", 13, "Thirteen",
                14, "Fourteen", 15, "Fifteen", 16, "Sixteen");

        cursor.starting();
        intTrie.traverse(cursor);
        cursor.finished();

        cursor.starting();
        for (final Map.Entry<Integer, String> entry : intTrie.entrySet()) {
            cursor.select(entry);
        }
        cursor.finished();

        cursor.starting();
        for (final Integer integer : intTrie.keySet()) {
            cursor.checkKey(integer);
        }
        cursor.finished();

        cursor.starting();
        for (final String string : intTrie.values()) {
            cursor.checkValue(string);
        }
        cursor.finished();

        final PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
        charTrie.put('c', "c");
        charTrie.put('p', "p");
        charTrie.put('l', "l");
        charTrie.put('t', "t");
        charTrie.put('k', "k");
        charTrie.put('a', "a");
        charTrie.put('y', "y");
        charTrie.put('r', "r");
        charTrie.put('u', "u");
        charTrie.put('o', "o");
        charTrie.put('w', "w");
        charTrie.put('i', "i");
        charTrie.put('e', "e");
        charTrie.put('x', "x");
        charTrie.put('q', "q");
        charTrie.put('b', "b");
        charTrie.put('j', "j");
        charTrie.put('s', "s");
        charTrie.put('n', "n");
        charTrie.put('v', "v");
        charTrie.put('g', "g");
        charTrie.put('h', "h");
        charTrie.put('m', "m");
        charTrie.put('z', "z");
        charTrie.put('f', "f");
        charTrie.put('d', "d");
        cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
                'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
                'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
                'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
                'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
                'z', "z");

        cursor.starting();
        charTrie.traverse(cursor);
        cursor.finished();

        cursor.starting();
        for (final Map.Entry<Character, String> entry : charTrie.entrySet()) {
            cursor.select(entry);
        }
        cursor.finished();

        cursor.starting();
        for (final Character character : charTrie.keySet()) {
            cursor.checkKey(character);
        }
        cursor.finished();

        cursor.starting();
        for (final String string : charTrie.values()) {
            cursor.checkValue(string);
        }
        cursor.finished();
    }

    @Test
    @SuppressWarnings("boxing") // OK in test code
    public void testSelect() {
        final PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
        charTrie.put('c', "c");
        charTrie.put('p', "p");
        charTrie.put('l', "l");
        charTrie.put('t', "t");
        charTrie.put('k', "k");
        charTrie.put('a', "a");
        charTrie.put('y', "y");
        charTrie.put('r', "r");
        charTrie.put('u', "u");
        charTrie.put('o', "o");
        charTrie.put('w', "w");
        charTrie.put('i', "i");
        charTrie.put('e', "e");
        charTrie.put('x', "x");
        charTrie.put('q', "q");
        charTrie.put('b', "b");
        charTrie.put('j', "j");
        charTrie.put('s', "s");
        charTrie.put('n', "n");
        charTrie.put('v', "v");
        charTrie.put('g', "g");
        charTrie.put('h', "h");
        charTrie.put('m', "m");
        charTrie.put('z', "z");
        charTrie.put('f', "f");
        charTrie.put('d', "d");
        final TestCursor cursor = new TestCursor(
                'd', "d", 'e', "e", 'f', "f", 'g', "g",
                'a', "a", 'b', "b", 'c', "c",
                'l', "l", 'm', "m", 'n', "n", 'o', "o",
                'h', "h", 'i', "i", 'j', "j", 'k', "k",
                't', "t", 'u', "u", 'v', "v", 'w', "w",
                'p', "p", 'q', "q", 'r', "r", 's', "s",
                'x', "x", 'y', "y", 'z', "z");

        Assert.assertEquals(26, charTrie.size());

        cursor.starting();
        charTrie.select('d', cursor);
        cursor.finished();
    }

    @Test
    @SuppressWarnings("boxing") // OK in test code
    public void testTraverseCursorRemove() {
        final PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
        charTrie.put('c', "c");
        charTrie.put('p', "p");
        charTrie.put('l', "l");
        charTrie.put('t', "t");
        charTrie.put('k', "k");
        charTrie.put('a', "a");
        charTrie.put('y', "y");
        charTrie.put('r', "r");
        charTrie.put('u', "u");
        charTrie.put('o', "o");
        charTrie.put('w', "w");
        charTrie.put('i', "i");
        charTrie.put('e', "e");
        charTrie.put('x', "x");
        charTrie.put('q', "q");
        charTrie.put('b', "b");
        charTrie.put('j', "j");
        charTrie.put('s', "s");
        charTrie.put('n', "n");
        charTrie.put('v', "v");
        charTrie.put('g', "g");
        charTrie.put('h', "h");
        charTrie.put('m', "m");
        charTrie.put('z', "z");
        charTrie.put('f', "f");
        charTrie.put('d', "d");
        final TestCursor cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
                'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
                'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
                'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
                'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
                'z', "z");

        cursor.starting();
        charTrie.traverse(cursor);
        cursor.finished();

        // Test removing both an internal & external node.
        // 'm' is an example External node in this Trie, and 'p' is an internal.

        Assert.assertEquals(26, charTrie.size());

        final Object[] toRemove = new Object[] { 'g', 'd', 'e', 'm', 'p', 'q', 'r', 's' };
        cursor.addToRemove(toRemove);

        cursor.starting();
        charTrie.traverse(cursor);
        cursor.finished();

        Assert.assertEquals(26 - toRemove.length, charTrie.size());

        cursor.starting();
        charTrie.traverse(cursor);
        cursor.finished();

        cursor.starting();
        for (final Entry<Character, String> entry : charTrie.entrySet()) {
            cursor.select(entry);
            if (Arrays.asList(toRemove).contains(entry.getKey())) {
                Assert.fail("got an: " + entry);
            }
        }
        cursor.finished();
    }

    @Test
    @SuppressWarnings("boxing") // OK in test code
    public void testIteratorRemove() {
        final PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
        charTrie.put('c', "c");
        charTrie.put('p', "p");
        charTrie.put('l', "l");
        charTrie.put('t', "t");
        charTrie.put('k', "k");
        charTrie.put('a', "a");
        charTrie.put('y', "y");
        charTrie.put('r', "r");
        charTrie.put('u', "u");
        charTrie.put('o', "o");
        charTrie.put('w', "w");
        charTrie.put('i', "i");
        charTrie.put('e', "e");
        charTrie.put('x', "x");
        charTrie.put('q', "q");
        charTrie.put('b', "b");
        charTrie.put('j', "j");
        charTrie.put('s', "s");
        charTrie.put('n', "n");
        charTrie.put('v', "v");
        charTrie.put('g', "g");
        charTrie.put('h', "h");
        charTrie.put('m', "m");
        charTrie.put('z', "z");
        charTrie.put('f', "f");
        charTrie.put('d', "d");
        final TestCursor cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
                'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
                'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
                'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
                'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
                'z', "z");

        // Test removing both an internal & external node.
        // 'm' is an example External node in this Trie, and 'p' is an internal.

        Assert.assertEquals(26, charTrie.size());

        final Object[] toRemove = new Object[] { 'e', 'm', 'p', 'q', 'r', 's' };

        cursor.starting();
        for(final Iterator<Map.Entry<Character, String>> i = charTrie.entrySet().iterator(); i.hasNext(); ) {
            final Map.Entry<Character,String> entry = i.next();
            cursor.select(entry);
            if(Arrays.asList(toRemove).contains(entry.getKey())) {
                i.remove();
            }
        }
        cursor.finished();

        Assert.assertEquals(26 - toRemove.length, charTrie.size());

        cursor.remove(toRemove);

        cursor.starting();
        for (final Entry<Character, String> entry : charTrie.entrySet()) {
            cursor.select(entry);
            if (Arrays.asList(toRemove).contains(entry.getKey())) {
                Assert.fail("got an: " + entry);
            }
        }
        cursor.finished();
    }

    @Test
    public void testHamlet() throws Exception {
        // Make sure that Hamlet is read & stored in the same order as a SortedSet.
        final List<String> original = new ArrayList<String>();
        final List<String> control = new ArrayList<String>();
        final SortedMap<String, String> sortedControl = new TreeMap<String, String>();
        final PatriciaTrie<String, String> trie = new PatriciaTrie<String, String>(new StringKeyAnalyzer());

        final InputStream in = getClass().getResourceAsStream("hamlet.txt");
        final BufferedReader reader = new BufferedReader(new InputStreamReader(in));

        String read = null;
        while( (read = reader.readLine()) != null) {
            final StringTokenizer st = new StringTokenizer(read);
            while(st.hasMoreTokens()) {
                final String token = st.nextToken();
                original.add(token);
                sortedControl.put(token, token);
                trie.put(token, token);
            }
        }
        control.addAll(sortedControl.values());

        Assert.assertEquals(control.size(), sortedControl.size());
        Assert.assertEquals(sortedControl.size(), trie.size());
        Iterator<String> iter = trie.values().iterator();
        for (final String aControl : control) {
            Assert.assertEquals(aControl, iter.next());
        }

        final Random rnd = new Random();
        int item = 0;
        iter = trie.values().iterator();
        int removed = 0;
        for(; item < control.size(); item++) {
            Assert.assertEquals(control.get(item), iter.next());
            if(rnd.nextBoolean()) {
                iter.remove();
                removed++;
            }
        }

        Assert.assertEquals(control.size(), item);
        Assert.assertTrue(removed > 0);
        Assert.assertEquals(control.size(), trie.size() + removed);

        // reset hamlet
        trie.clear();
        for (final String anOriginal : original) {
            trie.put(anOriginal, anOriginal);
        }

        assertEqualArrays(sortedControl.values().toArray(), trie.values().toArray());
        assertEqualArrays(sortedControl.keySet().toArray(), trie.keySet().toArray());
        assertEqualArrays(sortedControl.entrySet().toArray(), trie.entrySet().toArray());

        Assert.assertEquals(sortedControl.firstKey(), trie.firstKey());
        Assert.assertEquals(sortedControl.lastKey(), trie.lastKey());

        SortedMap<String, String> sub = trie.headMap(control.get(523));
        Assert.assertEquals(523, sub.size());
        for(int i = 0; i < control.size(); i++) {
            if(i < 523) {
                Assert.assertTrue(sub.containsKey(control.get(i)));
            } else {
                Assert.assertFalse(sub.containsKey(control.get(i)));
            }
        }
        // Too slow to check values on all, so just do a few.
        Assert.assertTrue(sub.containsValue(control.get(522)));
        Assert.assertFalse(sub.containsValue(control.get(523)));
        Assert.assertFalse(sub.containsValue(control.get(524)));

        try {
            sub.headMap(control.get(524));
            Assert.fail("should have thrown IAE");
        } catch(final IllegalArgumentException expected) {}

        Assert.assertEquals(sub.lastKey(), control.get(522));
        Assert.assertEquals(sub.firstKey(), control.get(0));

        sub = sub.tailMap(control.get(234));
        Assert.assertEquals(289, sub.size());
        Assert.assertEquals(control.get(234), sub.firstKey());
        Assert.assertEquals(control.get(522), sub.lastKey());
        for(int i = 0; i < control.size(); i++) {
            if(i < 523 && i > 233) {
                Assert.assertTrue(sub.containsKey(control.get(i)));
            } else {
                Assert.assertFalse(sub.containsKey(control.get(i)));
            }
        }

        try {
            sub.tailMap(control.get(232));
            Assert.fail("should have thrown IAE");
        } catch(final IllegalArgumentException expected) {}

        sub = sub.subMap(control.get(300), control.get(400));
        Assert.assertEquals(100, sub.size());
        Assert.assertEquals(control.get(300), sub.firstKey());
        Assert.assertEquals(control.get(399), sub.lastKey());

        for(int i = 0; i < control.size(); i++) {
            if(i < 400 && i > 299) {
                Assert.assertTrue(sub.containsKey(control.get(i)));
            } else {
                Assert.assertFalse(sub.containsKey(control.get(i)));
            }
        }
    }

    @Test
    public void testPrefixedBy() {
        final PatriciaTrie<String, String> trie
            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());

        final String[] keys = new String[]{
                "",
                "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
                "Alberts", "Allie", "Alliese", "Alabama", "Banane",
                "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
                "Amma"
        };

        for (final String key : keys) {
            trie.put(key, key);
        }

        SortedMap<String, String> map;
        Iterator<String> iterator;
        Iterator<Map.Entry<String, String>> entryIterator;
        Map.Entry<String, String> entry;

        map = trie.getPrefixedBy("Al");
        Assert.assertEquals(8, map.size());
        Assert.assertEquals("Alabama", map.firstKey());
        Assert.assertEquals("Alliese", map.lastKey());
        Assert.assertEquals("Albertoo", map.get("Albertoo"));
        Assert.assertNotNull(trie.get("Xavier"));
        Assert.assertNull(map.get("Xavier"));
        Assert.assertNull(trie.get("Alice"));
        Assert.assertNull(map.get("Alice"));
        iterator = map.values().iterator();
        Assert.assertEquals("Alabama", iterator.next());
        Assert.assertEquals("Albert", iterator.next());
        Assert.assertEquals("Alberto", iterator.next());
        Assert.assertEquals("Albertoo", iterator.next());
        Assert.assertEquals("Alberts", iterator.next());
        Assert.assertEquals("Alien", iterator.next());
        Assert.assertEquals("Allie", iterator.next());
        Assert.assertEquals("Alliese", iterator.next());
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("Albert");
        iterator = map.keySet().iterator();
        Assert.assertEquals("Albert", iterator.next());
        Assert.assertEquals("Alberto", iterator.next());
        Assert.assertEquals("Albertoo", iterator.next());
        Assert.assertEquals("Alberts", iterator.next());
        Assert.assertFalse(iterator.hasNext());
        Assert.assertEquals(4, map.size());
        Assert.assertEquals("Albert", map.firstKey());
        Assert.assertEquals("Alberts", map.lastKey());
        Assert.assertNull(trie.get("Albertz"));
        map.put("Albertz", "Albertz");
        Assert.assertEquals("Albertz", trie.get("Albertz"));
        Assert.assertEquals(5, map.size());
        Assert.assertEquals("Albertz", map.lastKey());
        iterator = map.keySet().iterator();
        Assert.assertEquals("Albert", iterator.next());
        Assert.assertEquals("Alberto", iterator.next());
        Assert.assertEquals("Albertoo", iterator.next());
        Assert.assertEquals("Alberts", iterator.next());
        Assert.assertEquals("Albertz", iterator.next());
        Assert.assertFalse(iterator.hasNext());
        Assert.assertEquals("Albertz", map.remove("Albertz"));

        map = trie.getPrefixedBy("Alberto");
        Assert.assertEquals(2, map.size());
        Assert.assertEquals("Alberto", map.firstKey());
        Assert.assertEquals("Albertoo", map.lastKey());
        entryIterator = map.entrySet().iterator();
        entry = entryIterator.next();
        Assert.assertEquals("Alberto", entry.getKey());
        Assert.assertEquals("Alberto", entry.getValue());
        entry = entryIterator.next();
        Assert.assertEquals("Albertoo", entry.getKey());
        Assert.assertEquals("Albertoo", entry.getValue());
        Assert.assertFalse(entryIterator.hasNext());
        trie.put("Albertoad", "Albertoad");
        Assert.assertEquals(3, map.size());
        Assert.assertEquals("Alberto", map.firstKey());
        Assert.assertEquals("Albertoo", map.lastKey());
        entryIterator = map.entrySet().iterator();
        entry = entryIterator.next();
        Assert.assertEquals("Alberto", entry.getKey());
        Assert.assertEquals("Alberto", entry.getValue());
        entry = entryIterator.next();
        Assert.assertEquals("Albertoad", entry.getKey());
        Assert.assertEquals("Albertoad", entry.getValue());
        entry = entryIterator.next();
        Assert.assertEquals("Albertoo", entry.getKey());
        Assert.assertEquals("Albertoo", entry.getValue());
        Assert.assertFalse(entryIterator.hasNext());
        Assert.assertEquals("Albertoo", trie.remove("Albertoo"));
        Assert.assertEquals("Alberto", map.firstKey());
        Assert.assertEquals("Albertoad", map.lastKey());
        Assert.assertEquals(2, map.size());
        entryIterator = map.entrySet().iterator();
        entry = entryIterator.next();
        Assert.assertEquals("Alberto", entry.getKey());
        Assert.assertEquals("Alberto", entry.getValue());
        entry = entryIterator.next();
        Assert.assertEquals("Albertoad", entry.getKey());
        Assert.assertEquals("Albertoad", entry.getValue());
        Assert.assertFalse(entryIterator.hasNext());
        Assert.assertEquals("Albertoad", trie.remove("Albertoad"));
        trie.put("Albertoo", "Albertoo");

        map = trie.getPrefixedBy("X");
        Assert.assertEquals(2, map.size());
        Assert.assertFalse(map.containsKey("Albert"));
        Assert.assertTrue(map.containsKey("Xavier"));
        Assert.assertFalse(map.containsKey("Xalan"));
        iterator = map.values().iterator();
        Assert.assertEquals("Xavier", iterator.next());
        Assert.assertEquals("XyZ", iterator.next());
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("An");
        Assert.assertEquals(1, map.size());
        Assert.assertEquals("Anna", map.firstKey());
        Assert.assertEquals("Anna", map.lastKey());
        iterator = map.keySet().iterator();
        Assert.assertEquals("Anna", iterator.next());
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("Ban");
        Assert.assertEquals(1, map.size());
        Assert.assertEquals("Banane", map.firstKey());
        Assert.assertEquals("Banane", map.lastKey());
        iterator = map.keySet().iterator();
        Assert.assertEquals("Banane", iterator.next());
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("Am");
        Assert.assertFalse(map.isEmpty());
        Assert.assertEquals(3, map.size());
        Assert.assertEquals("Amber", trie.remove("Amber"));
        iterator = map.keySet().iterator();
        Assert.assertEquals("Amma", iterator.next());
        Assert.assertEquals("Ammun", iterator.next());
        Assert.assertFalse(iterator.hasNext());
        iterator = map.keySet().iterator();
        map.put("Amber", "Amber");
        Assert.assertEquals(3, map.size());
        try {
            iterator.next();
            Assert.fail("CME expected");
        } catch(final ConcurrentModificationException expected) {}
        Assert.assertEquals("Amber", map.firstKey());
        Assert.assertEquals("Ammun", map.lastKey());

        map = trie.getPrefixedBy("Ak\0");
        Assert.assertTrue(map.isEmpty());

        map = trie.getPrefixedBy("Ak");
        Assert.assertEquals(2, map.size());
        Assert.assertEquals("Akka", map.firstKey());
        Assert.assertEquals("Akko", map.lastKey());
        map.put("Ak", "Ak");
        Assert.assertEquals("Ak", map.firstKey());
        Assert.assertEquals("Akko", map.lastKey());
        Assert.assertEquals(3, map.size());
        trie.put("Al", "Al");
        Assert.assertEquals(3, map.size());
        Assert.assertEquals("Ak", map.remove("Ak"));
        Assert.assertEquals("Akka", map.firstKey());
        Assert.assertEquals("Akko", map.lastKey());
        Assert.assertEquals(2, map.size());
        iterator = map.keySet().iterator();
        Assert.assertEquals("Akka", iterator.next());
        Assert.assertEquals("Akko", iterator.next());
        Assert.assertFalse(iterator.hasNext());
        Assert.assertEquals("Al", trie.remove("Al"));

        map = trie.getPrefixedBy("Akka");
        Assert.assertEquals(1, map.size());
        Assert.assertEquals("Akka", map.firstKey());
        Assert.assertEquals("Akka", map.lastKey());
        iterator = map.keySet().iterator();
        Assert.assertEquals("Akka", iterator.next());
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("Ab");
        Assert.assertTrue(map.isEmpty());
        Assert.assertEquals(0, map.size());
        try {
            final Object o = map.firstKey();
            Assert.fail("got a first key: " + o);
        } catch(final NoSuchElementException nsee) {}
        try {
            final Object o = map.lastKey();
            Assert.fail("got a last key: " + o);
        } catch(final NoSuchElementException nsee) {}
        iterator = map.values().iterator();
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("Albertooo");
        Assert.assertTrue(map.isEmpty());
        Assert.assertEquals(0, map.size());
        try {
            final Object o = map.firstKey();
            Assert.fail("got a first key: " + o);
        } catch(final NoSuchElementException nsee) {}
        try {
            final Object o = map.lastKey();
            Assert.fail("got a last key: " + o);
        } catch(final NoSuchElementException nsee) {}
        iterator = map.values().iterator();
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("");
        Assert.assertSame(trie, map); // stricter than necessary, but a good check

        map = trie.getPrefixedBy("\0");
        Assert.assertTrue(map.isEmpty());
        Assert.assertEquals(0, map.size());
        try {
            final Object o = map.firstKey();
            Assert.fail("got a first key: " + o);
        } catch(final NoSuchElementException nsee) {}
        try {
            final Object o = map.lastKey();
            Assert.fail("got a last key: " + o);
        } catch(final NoSuchElementException nsee) {}
        iterator = map.values().iterator();
        Assert.assertFalse(iterator.hasNext());
    }

    @Test
    public void testPrefixByOffsetAndLength() {
        final PatriciaTrie<String, String> trie
            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());

        final String[] keys = new String[]{
                "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
                "Alberts", "Allie", "Alliese", "Alabama", "Banane",
                "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
                "Amma"
        };

        for (final String key : keys) {
            trie.put(key, key);
        }

        SortedMap<String, String> map;
        Iterator<String> iterator;

        map = trie.getPrefixedBy("Alice", 2);
        Assert.assertEquals(8, map.size());
        Assert.assertEquals("Alabama", map.firstKey());
        Assert.assertEquals("Alliese", map.lastKey());
        Assert.assertEquals("Albertoo", map.get("Albertoo"));
        Assert.assertNotNull(trie.get("Xavier"));
        Assert.assertNull(map.get("Xavier"));
        Assert.assertNull(trie.get("Alice"));
        Assert.assertNull(map.get("Alice"));
        iterator = map.values().iterator();
        Assert.assertEquals("Alabama", iterator.next());
        Assert.assertEquals("Albert", iterator.next());
        Assert.assertEquals("Alberto", iterator.next());
        Assert.assertEquals("Albertoo", iterator.next());
        Assert.assertEquals("Alberts", iterator.next());
        Assert.assertEquals("Alien", iterator.next());
        Assert.assertEquals("Allie", iterator.next());
        Assert.assertEquals("Alliese", iterator.next());
        Assert.assertFalse(iterator.hasNext());

        map = trie.getPrefixedBy("BAlice", 1, 2);
        Assert.assertEquals(8, map.size());
        Assert.assertEquals("Alabama", map.firstKey());
        Assert.assertEquals("Alliese", map.lastKey());
        Assert.assertEquals("Albertoo", map.get("Albertoo"));
        Assert.assertNotNull(trie.get("Xavier"));
        Assert.assertNull(map.get("Xavier"));
        Assert.assertNull(trie.get("Alice"));
        Assert.assertNull(map.get("Alice"));
        iterator = map.values().iterator();
        Assert.assertEquals("Alabama", iterator.next());
        Assert.assertEquals("Albert", iterator.next());
        Assert.assertEquals("Alberto", iterator.next());
        Assert.assertEquals("Albertoo", iterator.next());
        Assert.assertEquals("Alberts", iterator.next());
        Assert.assertEquals("Alien", iterator.next());
        Assert.assertEquals("Allie", iterator.next());
        Assert.assertEquals("Alliese", iterator.next());
        Assert.assertFalse(iterator.hasNext());
    }

    @Test
    public void testPrefixedByRemoval() {
        final PatriciaTrie<String, String> trie
            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());

        final String[] keys = new String[]{
                "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
                "Alberts", "Allie", "Alliese", "Alabama", "Banane",
                "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
                "Amma"
        };

        for (final String key : keys) {
            trie.put(key, key);
        }

        SortedMap<String, String> map = trie.getPrefixedBy("Al");
        Assert.assertEquals(8, map.size());
        Iterator<String> iter = map.keySet().iterator();
        Assert.assertEquals("Alabama", iter.next());
        Assert.assertEquals("Albert", iter.next());
        Assert.assertEquals("Alberto", iter.next());
        Assert.assertEquals("Albertoo", iter.next());
        Assert.assertEquals("Alberts", iter.next());
        Assert.assertEquals("Alien", iter.next());
        iter.remove();
        Assert.assertEquals(7, map.size());
        Assert.assertEquals("Allie", iter.next());
        Assert.assertEquals("Alliese", iter.next());
        Assert.assertFalse(iter.hasNext());

        map = trie.getPrefixedBy("Ak");
        Assert.assertEquals(2, map.size());
        iter = map.keySet().iterator();
        Assert.assertEquals("Akka", iter.next());
        iter.remove();
        Assert.assertEquals(1, map.size());
        Assert.assertEquals("Akko", iter.next());
        if(iter.hasNext()) {
            Assert.fail("shouldn't have next (but was: " + iter.next() + ")");
        }
        Assert.assertFalse(iter.hasNext());
    }

    @Test
    public void testTraverseWithAllNullBitKey() {
        final PatriciaTrie<String, String> trie
            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());

        //
        // One entry in the Trie
        // Entry is stored at the root
        //

        // trie.put("", "All Bits Are Zero");
        trie.put("\0", "All Bits Are Zero");

        //
        //  / ("")   <-- root
        //  \_/  \
        //       null
        //

        final List<String> strings = new ArrayList<String>();
        trie.traverse(new Cursor<String, String>() {
            public Decision select(final Entry<? extends String, ? extends String> entry) {
                strings.add(entry.getValue());
                return Decision.CONTINUE;
            }
        });

        Assert.assertEquals(1, strings.size());

        strings.clear();
        for (final String s : trie.values()) {
            strings.add(s);
        }
        Assert.assertEquals(1, strings.size());
    }

    @Test
    public void testSelectWithAllNullBitKey() {
        final PatriciaTrie<String, String> trie
            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());

        // trie.put("", "All Bits Are Zero");
        trie.put("\0", "All Bits Are Zero");

        final List<String> strings = new ArrayList<String>();
        trie.select("Hello", new Cursor<String, String>() {
            public Decision select(final Entry<? extends String, ? extends String> entry) {
                strings.add(entry.getValue());
                return Decision.CONTINUE;
            }
        });
        Assert.assertEquals(1, strings.size());
    }

    private static class TestCursor implements Cursor<Object, Object> {
        private final List<Object> keys;
        private final List<Object> values;
        private Object selectFor;
        private List<Object> toRemove;
        private int index = 0;

        TestCursor(final Object... objects) {
            if(objects.length % 2 != 0) {
                throw new IllegalArgumentException("must be * 2");
            }

            keys = new ArrayList<Object>(objects.length / 2);
            values = new ArrayList<Object>(keys.size());
            toRemove = Collections.emptyList();
            for(int i = 0; i < objects.length; i++) {
                keys.add(objects[i]);
                values.add(objects[++i]);
            }
        }

        @SuppressWarnings("unused")
        void selectFor(final Object object) {
            selectFor = object;
        }

        void addToRemove(final Object... objects) {
            toRemove = new ArrayList<Object>(Arrays.asList(objects));
        }

        void remove(final Object... objects) {
            for (final Object object : objects) {
                final int idx = keys.indexOf(object);
                keys.remove(idx);
                values.remove(idx);
            }
        }

        void starting() {
            index = 0;
        }

        public void checkKey(final Object k) {
            Assert.assertEquals(keys.get(index++), k);
        }

        public void checkValue(final Object o) {
            Assert.assertEquals(values.get(index++), o);
        }

        public Decision select(final Entry<?, ?> entry) {
          //  System.out.println("Scanning: " + entry.getKey());
            Assert.assertEquals(keys.get(index), entry.getKey());
            Assert.assertEquals(values.get(index), entry.getValue());
            index++;

            if(toRemove.contains(entry.getKey())) {
              // System.out.println("Removing: " + entry.getKey());
                index--;
                keys.remove(index);
                values.remove(index);
                toRemove.remove(entry.getKey());
                return Decision.REMOVE;
            }

            if(selectFor != null && selectFor.equals(entry.getKey())) {
                return Decision.EXIT;
            } else {
                return Decision.CONTINUE;
            }
        }

        void finished() {
            Assert.assertEquals(keys.size(), index);
        }
    }

    private static void assertEqualArrays(final Object[] a, final Object[] b) {
        Assert.assertTrue(Arrays.equals(a, b));
    }
}