@@ -0,0 +1,2675 @@
+/* -*- Mode: Java; c-basic-offset: 4; tab-width: 20; indent-tabs-mode: nil; -*-%0A * This Source Code Form is subject to the terms of the Mozilla Public%0A * License, v. 2.0. If a copy of the MPL was not distributed with this%0A * file, You can obtain one at http://mozilla.org/MPL/2.0/. */%0Apackage org.mozilla.focus.webkit.matcher;%0A%0Aimport android.util.SparseArray;%0A%0Apublic class Trie %7B%0A%0A    /**%0A     * Trie that adds storage for a whitelist (itself another trie) on each node.%0A     */%0A    public static class WhiteListTrie extends Trie %7B%0A        Trie whitelist = null;%0A%0A        private WhiteListTrie(final char character, final WhiteListTrie parent) %7B%0A            super(character, parent);%0A        %7D%0A%0A        @Override%0A        protected Trie createNode(final char character, final Trie parent) %7B%0A            return new WhiteListTrie(character, (WhiteListTrie) parent);%0A        %7D%0A%0A        public static WhiteListTrie createRootNode() %7B%0A            return new WhiteListTrie(Character.MIN_VALUE, null);%0A        %7D%0A    %7D%0A%0A    public final char character;%0A    public final SparseArray%3CTrie%3E children = new SparseArray%3C%3E();%0A    public boolean terminator = false;%0A%0A    public Trie findNode(final String string) %7B%0A        if (terminator) %7B%0A            // Match achieved%0A            return this;%0A        %7D else if (string.length() == 0) %7B%0A            // Finished the string, no match%0A            return null;%0A        %7D%0A%0A        final Trie next = children.get(string.charAt(0));%0A%0A        if (next == null) %7B%0A            return null;%0A        %7D%0A%0A        return next.findNode(string.substring(1));%0A    %7D%0A%0A    public Trie put(final String string) %7B%0A        if (string.length() == 0) %7B%0A            terminator = true;%0A            return this;%0A        %7D%0A%0A        final char character = string.charAt(0);%0A%0A        final Trie child = put(character);%0A%0A        return child.put(string.substring(1));%0A    %7D%0A%0A    public Trie put(char character) %7B%0A        final Trie existingChild = children.get(character);%0A%0A        if (existingChild != null) %7B%0A            return existingChild;%0A        %7D%0A%0A        final Trie newChild = createNode(character, this);%0A%0A        children.put(character, newChild);%0A%0A        return newChild;%0A    %7D%0A%0A    private Trie(char character, Trie parent) %7B%0A        this.character = character;%0A%0A        if (parent != null) %7B%0A            parent.children.put(character, this);%0A        %7D%0A    %7D%0A%0A    public static Trie createRootNode() %7B%0A        return new Trie(Character.MIN_VALUE, null);%0A    %7D%0A%0A    // Subclasses must override to provide their node implementation%0A    protected Trie createNode(final char character, final Trie parent) %7B%0A        return new Trie(character, parent);%0A    %7D%0A%7D%0A

Add Trie implementation