/* -*- Mode: Java; c-basic-offset: 4; tab-width: 20; indent-tabs-mode: nil; -*-
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
package org.mozilla.focus.webkit.matcher;

import android.util.SparseArray;

public class Trie {

    /**
     * Trie that adds storage for a whitelist (itself another trie) on each node.
     */
    public static class WhiteListTrie extends Trie {
        Trie whitelist = null;

        private WhiteListTrie(final char character, final WhiteListTrie parent) {
            super(character, parent);
        }

        @Override
        protected Trie createNode(final char character, final Trie parent) {
            return new WhiteListTrie(character, (WhiteListTrie) parent);
        }

        public static WhiteListTrie createRootNode() {
            return new WhiteListTrie(Character.MIN_VALUE, null);
        }
    }

    public final char character;
    public final SparseArray<Trie> children = new SparseArray<>();
    public boolean terminator = false;

    public Trie findNode(final String string) {
        if (terminator) {
            // Match achieved
            return this;
        } else if (string.length() == 0) {
            // Finished the string, no match
            return null;
        }

        final Trie next = children.get(string.charAt(0));

        if (next == null) {
            return null;
        }

        return next.findNode(string.substring(1));
    }

    public Trie put(final String string) {
        if (string.length() == 0) {
            terminator = true;
            return this;
        }

        final char character = string.charAt(0);

        final Trie child = put(character);

        return child.put(string.substring(1));
    }

    public Trie put(char character) {
        final Trie existingChild = children.get(character);

        if (existingChild != null) {
            return existingChild;
        }

        final Trie newChild = createNode(character, this);

        children.put(character, newChild);

        return newChild;
    }

    private Trie(char character, Trie parent) {
        this.character = character;

        if (parent != null) {
            parent.children.put(character, this);
        }
    }

    public static Trie createRootNode() {
        return new Trie(Character.MIN_VALUE, null);
    }

    // Subclasses must override to provide their node implementation
    protected Trie createNode(final char character, final Trie parent) {
        return new Trie(character, parent);
    }
}

Add Trie implementation