One deprecated implementation in PinIn since its slowness in construction and high memory consumption

PassiveTree.java

package me.towdium.pinin;

import it.unimi.dsi.fastutil.chars.*;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntList;
import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
import it.unimi.dsi.fastutil.ints.IntSet;
import it.unimi.dsi.fastutil.objects.Object2IntMap;
import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
import me.towdium.pinin.elements.Element;
import me.towdium.pinin.utils.IndexSet;
import me.towdium.pinin.utils.Matcher;

import java.util.*;
import java.util.function.BiConsumer;
import java.util.function.IntConsumer;
import java.util.stream.Collectors;

public class PassiveTree<T> {
    static final CharList chars = new CharArrayList();

    static {
        for (int i = 0; i < 26; i++) chars.add((char) ('a' + i));
        for (int i = 0; i < 5; i++) chars.add((char) ('0' + i));
    }

    Node root = new NDense();
    final PinIn context;
    List<T> objects = new ArrayList<>();

    public PassiveTree(PinIn context) {
        this.context = context;
    }

    public void put(String name, T identifier) {
        root = root.put(context, name, objects.size(), "");
        objects.add(identifier);
    }

    public Set<T> search(String s) {
        IntSet ret = new IntOpenHashSet();
        root.get(context, ret, "", s, 0);
        return ret.stream().map(i -> objects.get(i))
                .collect(Collectors.toSet());
    }

    interface Node {
        Node put(PinIn p, String name, int id, String location);

        void get(PinIn p, IntSet ret, String location, String input, int offset);
    }

    static class NMap implements Node {
        Char2ObjectMap<Node> children = new Char2ObjectOpenHashMap<>();
        IntList leaves = new IntArrayList();

        @Override
        public Node put(PinIn p, String name, int id, String location) {
            CharConsumer attempt = c -> {
                String s = location + c;
                if (p.contains(name, s)) {
                    Node n = children.computeIfAbsent(c, j -> new NDense());
                    n = n.put(p, name, id, s);
                    children.put(c, n);
                }
            };

            CharSet cs = check(name, location, p);
            for (char i: cs) {
                if (i == '\0') leaves.add(id);
                else attempt.accept(i);
            }
            for (char i: chars) attempt.accept(i);
            return this;
        }

        @Override
        public void get(PinIn p, IntSet ret, String location, String input, int offset) {
            if (location.equals(input)) ret.addAll(leaves);  // TODO get all children
            else {
                char c = input.charAt(offset);
                children.get(c).get(p, ret, location + c, input, offset + 1);
            }
        }

        public static CharSet check(String s1, String s2, PinIn p) {
            CharSet ret = new CharOpenHashSet();
            for (int i = 0; i < s1.length(); i++) check(ret, s2, 0, s1, i, p);
            return ret;
        }


        public static boolean check(CharSet ret, String s1, int start1, String s2, int start2, PinIn p) {
            if (start1 == s1.length()) {
                ret.add(s2.charAt(start2));
                return true;
            }

            Element r = p.genChar(s2.charAt(start2));
            IndexSet s = r.match(s1, start1);

            if (start2 == s2.length() - 1) {
                int i = s1.length() - start1;
                boolean b = s.get(i);
                if (b) ret.add('\0');
                return b;
            } else return !s.traverse(i -> !check(ret, s1, start1 + i, s2, start2 + 1, p));
        }
    }

    static class NDense implements Node {
        Map<String, IntSet> record = new HashMap<>();

        @Override
        public Node put(PinIn p, String name, int id, String location) {
            if (record.size() > 1024) {
                NMap ret = new NMap();
                record.forEach((s, is) -> is.forEach((IntConsumer) i ->
                        ret.put(p, s, i, location)));
                ret.put(p, name, id, location);
                return ret;
            } else {
                record.computeIfAbsent(name, i -> new IntOpenHashSet()).add(id);
            }
            return this;
        }

        @Override
        public void get(PinIn p, IntSet ret, String location, String input, int offset) {
            record.forEach((s, is) -> {
                if (p.contains(s, input)) ret.addAll(is);
            });
        }
    }
}