FrequencyTrie.java

/*******************************************************************************

 * Copyright (C) 2026, Leo Galambos

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are met:

 *

 * 1. Redistributions of source code must retain the above copyright notice,

 *    this list of conditions and the following disclaimer.

 *

 * 2. Redistributions in binary form must reproduce the above copyright notice,

 *    this list of conditions and the following disclaimer in the documentation

 *    and/or other materials provided with the distribution.

 *

 * 3. Neither the name of the copyright holder nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

 * POSSIBILITY OF SUCH DAMAGE.

 ******************************************************************************/

package org.egothor.stemmer;

import java.io.DataInputStream;

import java.io.DataOutputStream;

import java.io.IOException;

import java.io.InputStream;

import java.io.OutputStream;

import java.nio.charset.StandardCharsets;

import java.security.MessageDigest;

import java.security.NoSuchAlgorithmException;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.IdentityHashMap;

import java.util.LinkedHashMap;

import java.util.List;

import java.util.Locale;

import java.util.Map;

import java.util.Objects;

import java.util.function.IntFunction;

import java.util.logging.Level;

import java.util.logging.Logger;

import org.egothor.stemmer.trie.CompiledNode;

import org.egothor.stemmer.trie.LocalValueSummary;

import org.egothor.stemmer.trie.MutableNode;

import org.egothor.stemmer.trie.ReducedNode;

import org.egothor.stemmer.trie.ReductionContext;

import org.egothor.stemmer.trie.ReductionSignature;

/**

 * Read-only trie mapping {@link String} keys to one or more values with

 * frequency tracking.

 *

 * <p>

 * A key may be associated with multiple values. Each value keeps the number of

 * times it was inserted during the build phase. The method {@link #get(String)}

 * returns the locally most frequent value stored at the terminal node of the

 * supplied key, while {@link #getAll(String)} returns all locally stored values

 * ordered by descending frequency.

 *

 * <p>

 * If multiple values have the same local frequency, their ordering is

 * deterministic. The preferred value is selected by the following tie-breaking

 * rules, in order:

 * <ol>

 * <li>shorter {@link String} representation wins, based on

 * {@code value.toString()}</li>

 * <li>if the lengths are equal, lexicographically lower {@link String}

 * representation wins</li>

 * <li>if the textual representations are still equal, first-seen insertion

 * order remains stable</li>

 * </ol>

 *

 * <p>

 * Values may be stored at any trie node, including internal nodes and leaf

 * nodes. Therefore, reduction and canonicalization always operate on both the

 * node-local terminal values and the structure of all descendant edges.

 *

 * @param <V> value type

 */

@SuppressWarnings({ "PMD.CyclomaticComplexity", "PMD.CouplingBetweenObjects" })

public final class FrequencyTrie<V> {

    /**

     * Logger of this class.

     */

    /**

     * Domain separator used by the trie fingerprint canonical input.

     */

    private static final String FINGERPRINT_DOMAIN = "RADIXOR-FREQUENCY-TRIE-FINGERPRINT";

    /**

     * Version of the canonical fingerprint input format.

     */

    private static final int FINGERPRINT_FORMAT_VERSION = 2;

    /**

     * Root node of the compiled read-only trie.

     */

    private final CompiledNode<V> root;

    /**

     * Metadata persisted together with this trie.

     */

    private final TrieMetadata metadata;

    /**

     * Canonical SHA-256 fingerprint bytes. The internal array is never exposed

     * directly to callers.

     */

    private final byte[] fingerprintBytes;

    /**

     * Cached traversal direction used for key lookup.

     */

    private final WordTraversalDirection lookupTraversalDirection;

    /**

     * Whether lookups require lowercase normalization.

     */

    private final boolean lowercasesLookupKeys;

    /**

     * Whether lookups require diacritic stripping.

     */

    private final boolean removeDiacritics;

    /**

     * Shared empty array instance for empty lookup results from

     * {@link #getAll(String)}.

     */

    private final V[] emptyValues;

    /**

     * Binary format magic header.

     */

    private static final int STREAM_MAGIC = 0x45475452;

    /**

     * Minimum supported stream version constant retained for explicit range checks.

     */

    private static final int MIN_STREAM_VERSION = 1;

    /**

     * Number of stored values for which {@link #getEntries(String)} can return an

     * empty result.

     */

    private static final int NO_VALUE_COUNT = 0;

    /**

     * Number of stored values for which {@link #getEntries(String)} can use a

     * one-item immutable list special case.

     */

    private static final int SINGLE_VALUE_COUNT = 1;

    /**

     * Binary format version.

     */

    private static final int STREAM_VERSION = 6;

    /**

     * Version where traversal-direction ordinal is persisted.

     */

    private static final int TRAVERSAL_VERSION = 2;

    /**

     * Version where compact reduction metadata is persisted.

     */

    private static final int REDUCTION_VERSION = 3;

    /**

     * Version where case-processing mode ordinal is persisted.

     */

    private static final int CASE_VERSION = 4;

    /**

     * Version where the persisted metadata switched to a text block.

     */

    private static final int TEXT_METADATA_VERSION = 5;

    /**

     * Version where contracted accepting nodes are persisted.

     */

    private static final int ACCEPTING_NODE_VERSION = 6;

    /**

     * Argument name for lookup keys.

     */

    private static final String ARG_KEY = "key";

    /**

     * Default dense child lookup span in code points used when materializing

     * compiled nodes without an explicit override.

     * <p>

     * Increasing this value increases the chance of direct array indexing for child

     * lookup at runtime at the cost of per-node dense table memory for compact

     * character spans.

     * </p>

     */

    public static final int DEFAULT_MAX_EXPANDED_INDEX = 512;

    /**

     * Returns the current persisted binary stream format version.

     *

     * <p>

     * This method exists so other components can construct {@link TrieMetadata}

     * instances aligned with the currently written binary format without

     * duplicating constants.

     * </p>

     *

     * @return current trie stream format version

     */

    public static int currentFormatVersion() {

    }

    /**

     * Receives trie values during visitor-style lookup.

     *

     * <p>

     * Implementations are caller-owned and are not retained by the trie. Returning

     * {@code false} stops iteration after the current callback.

     * </p>

     *

     * @param <V> value type

     */

    @FunctionalInterface

    public interface EntrySink<V> {

        /**

         * Accepts one ordered local value.

         *

         * @param value stored value

         * @param count stored local occurrence count

         * @param rank  zero-based rank in deterministic local ordering

         * @return {@code true} to continue iteration, {@code false} to stop

         */

        boolean accept(V value, int count, int rank);

    }

    /**

     * Creates a new compiled trie instance.

     *

     * @param arrayFactory array factory

     * @param root         compiled root node

     * @param metadata     trie metadata describing lookup and persistence semantics

     * @throws NullPointerException if any argument is {@code null}

     */

    private FrequencyTrie(final IntFunction<V[]> arrayFactory, final CompiledNode<V> root,

    /**

     * Creates a trie from an already compiled root.

     *

     * @param arrayFactory array factory

     * @param root         compiled root

     * @param metadata     trie metadata

     * @param <V>          value type

     * @return trie instance

     */

    /* default */ static <V> FrequencyTrie<V> fromCompiled(final IntFunction<V[]> arrayFactory,

            final CompiledNode<V> root,

            final TrieMetadata metadata) {

    }

    /**

     * Returns the most frequent value stored at the node addressed by the supplied

     * key.

     *

     * <p>

     * If multiple values have the same local frequency, the returned value is

     * selected deterministically by shorter {@code toString()} value first, then by

     * lexicographically lower {@code toString()}, and finally by stable first-seen

     * order.

     *

     * <p>

     * The supplied key is normalized according to persisted

     * {@link TrieMetadata#caseProcessingMode()} before traversal.

     * 

     * @param key key to resolve

     * @return most frequent value, or {@code null} if the key does not exist or no

     *         value is stored at the addressed node

     * @throws NullPointerException if {@code key} is {@code null}

     */

    public V get(final String key) {

        }

        }

    }

    /**

     * Returns the preferred value for an already-normalized key.

     *

     * <p>

     * This method bypasses {@link TrieMetadata#caseProcessingMode()} and

     * {@link TrieMetadata#diacriticProcessingMode()}. Callers must supply input

     * normalized exactly as required by this trie's metadata. It is intended for

     * hot paths where normalization is guaranteed by an upstream tokenizer or

     * benchmark corpus and repeated lookup-time normalization would be redundant.

     * </p>

     *

     * @param key already-normalized key to resolve

     * @return most frequent value, or {@code null} if the key does not exist or no

     *         value is stored at the addressed node

     * @throws NullPointerException if {@code key} is {@code null}

     */

    public V getNormalized(final CharSequence key) {

        }

        }

    }

    /**

     * Returns the preferred value for an already-normalized {@link String} key.

     *

     * <p>

     * This overload keeps high-volume string lookup on a monomorphic path and

     * avoids the {@link CharSequence} dispatch used by the general overload.

     * Callers must supply input normalized exactly as required by this trie's

     * metadata.

     * </p>

     *

     * @param key already-normalized key to resolve

     * @return most frequent value, or {@code null} if the key does not exist or no

     *         value is stored at the addressed node

     * @throws NullPointerException if {@code key} is {@code null}

     */

    public V getNormalizedString(final String key) {

        }

        }

    }

    /**

     * Returns all values stored at the node addressed by the supplied key, ordered

     * by descending frequency.

     *

     * <p>

     * If multiple values have the same local frequency, the ordering is

     * deterministic by shorter {@code toString()} value first, then by

     * lexicographically lower {@code toString()}, and finally by stable first-seen

     * order.

     *

     * <p>

     * The returned array is a defensive copy.

     *

     * <p>

     * The supplied key is normalized according to persisted

     * {@link TrieMetadata#caseProcessingMode()} before traversal.

     *

     * @param key key to resolve

     * @return all values stored at the addressed node, ordered by descending

     *         frequency; returns an empty array if the key does not exist or no

     *         value is stored at the addressed node

     * @throws NullPointerException if {@code key} is {@code null}

     */

    @SuppressWarnings("PMD.MethodReturnsInternalArray")

    public V[] getAll(final String key) {

        }

        }

    }

    /**

     * Returns all values stored at the node addressed by the supplied key together

     * with their occurrence counts, ordered by the same rules as

     * {@link #getAll(String)}.

     *

     * <p>

     * The returned list is aligned with the arrays returned by

     * {@link #getAll(String)} and the internal compiled count representation.

     *

     * <p>

     * The returned list is immutable.

     *

     * <p>

     * In reduction modes that merge semantically equivalent subtrees, the returned

     * counts may be aggregated across multiple original build-time nodes that were

     * reduced into the same canonical compiled node.

     *

     * @param key key to resolve

     * @return immutable ordered list of value-count entries; returns an empty list

     *         if the key does not exist or no value is stored at the addressed node

     * @throws NullPointerException if {@code key} is {@code null}

     */

    public List<ValueCount<V>> getEntries(final String key) {

        }

        }

        }

        }

    }

    /**

     * Visits all values stored at the node addressed by an already-normalized

     * {@code char[]} key slice.

     *

     * <p>

     * This method bypasses {@link TrieMetadata#caseProcessingMode()} and

     * {@link TrieMetadata#diacriticProcessingMode()}. The caller must provide input

     * normalized exactly as required by this trie's metadata. The trie is immutable

     * and thread-safe for concurrent reads; the supplied sink is caller-owned and

     * is not retained.

     * </p>

     *

     * @param key        normalized key storage

     * @param offset     first character offset

     * @param length     number of characters to read

     * @param sink       value sink

     * @param maxResults maximum number of results to visit

     * @return number of visited values

     * @throws NullPointerException      if {@code key} or {@code sink} is

     *                                   {@code null}

     * @throws IndexOutOfBoundsException if the key slice is invalid

     * @throws IllegalArgumentException  if {@code maxResults} is negative

     */

    public int getAllNormalized(final char[] key, final int offset, final int length, final EntrySink<? super V> sink,

            final int maxResults) {

        }

    }

    /**

     * Visits all values stored at the node addressed by an already-normalized

     * character sequence.

     *

     * @param key        normalized key

     * @param sink       value sink

     * @param maxResults maximum number of results to visit

     * @return number of visited values

     * @throws NullPointerException     if {@code key} or {@code sink} is

     *                                  {@code null}

     * @throws IllegalArgumentException if {@code maxResults} is negative

     * @see #getAllNormalized(char[], int, int, EntrySink, int)

     */

    public int getAllNormalized(final CharSequence key, final EntrySink<? super V> sink, final int maxResults) {

        }

    }

    /**

     * Visits the first value stored at the node addressed by an already-normalized

     * {@code char[]} key slice.

     *

     * @param key    normalized key storage

     * @param offset first character offset

     * @param length number of characters to read

     * @param sink   value sink

     * @return {@code true} when a value was visited, otherwise {@code false}

     * @see #getAllNormalized(char[], int, int, EntrySink, int)

     */

    public boolean getFirstNormalized(final char[] key, final int offset, final int length,

            final EntrySink<? super V> sink) {

    }

    /**

     * Visits the first value stored at the node addressed by an already-normalized

     * character sequence.

     *

     * @param key  normalized key

     * @param sink value sink

     * @return {@code true} when a value was visited, otherwise {@code false}

     * @see #getAllNormalized(CharSequence, EntrySink, int)

     */

    public boolean getFirstNormalized(final CharSequence key, final EntrySink<? super V> sink) {

    }

    /**

     * Visits all values stored at the node addressed by the supplied key, applying

     * metadata-driven lookup normalization when required.

     *

     * <p>

     * This method preserves the same lookup normalization semantics as

     * {@link #getAll(String)}. It may allocate when metadata requires lowercase or

     * diacritic normalization.

     * </p>

     *

     * @param key        key to resolve

     * @param sink       value sink

     * @param maxResults maximum number of results to visit

     * @return number of visited values

     */

    public int getAll(final CharSequence key, final EntrySink<? super V> sink, final int maxResults) {

        }

    }

    /**

     * Visits the first value stored at the node addressed by the supplied key,

     * applying metadata-driven lookup normalization when required.

     *

     * @param key  key to resolve

     * @param sink value sink

     * @return {@code true} when a value was visited, otherwise {@code false}

     * @see #getAll(CharSequence, EntrySink, int)

     */

    public boolean getFirst(final CharSequence key, final EntrySink<? super V> sink) {

    }

    /**

     * Returns the logical key traversal direction used by this trie.

     *

     * <p>

     * The same direction must be used when reconstructing mutable builders or when

     * applying patch commands that were generated against keys stored in this trie.

     * </p>

     *

     * @return logical key traversal direction

     */

    public WordTraversalDirection traversalDirection() {

    }

    /**

     * Returns immutable persisted metadata associated with this trie.

     *

     * @return trie metadata

     */

    public TrieMetadata metadata() {

    }

    /**

     * Returns the deterministic SHA-256 fingerprint of this trie.

     *

     * <p>

     * The fingerprint is a canonical model identity, not a Java object identity. It

     * includes a fingerprint-domain marker, the fingerprint input format version,

     * persisted metadata, and the complete compiled-node structure reachable from

     * the root, including edges, child references, local values, and local counts.

     * </p>

     *

     * <p>

     * The returned value is stable across JVM runs for equivalent trie content and

     * metadata. It does not include object identity, memory layout, runtime cache

     * state, absolute file paths, timestamps, or other process-local state.

     * </p>

     *

     * @return 64-character lowercase hexadecimal SHA-256 fingerprint

     */

    public String getFingerprint() {

    }

    /**

     * Returns a defensive copy of the raw SHA-256 fingerprint bytes.

     *

     * <p>

     * The returned array has length {@code 32}. Mutating it does not affect this

     * trie.

     * </p>

     *

     * @return defensive copy of the 32-byte SHA-256 fingerprint

     */

    public byte[] copyFingerprintBytes() {

    }

    private static <V> byte[] computeFingerprintBytes(final CompiledNode<V> root, final TrieMetadata metadata) {

    }

    /**

     * Returns the root node mainly for diagnostics and tests within the package.

     *

     * @return compiled root node

     */

    /* default */ CompiledNode<V> root() {

    }

    /**

     * Writes this compiled trie to the supplied output stream.

     *

     * <p>

     * The binary format is versioned and preserves canonical shared compiled nodes,

     * therefore the serialized representation remains compact even for tries

     * reduced by subtree merging.

     *

     * <p>

     * The supplied codec is responsible for persisting individual values of type

     * {@code V}.

     *

     * @param outputStream target output stream

     * @param valueCodec   codec used to write values

     * @throws NullPointerException if any argument is {@code null}

     * @throws IOException          if writing fails

     */

    public void writeTo(final OutputStream outputStream, final ValueStreamCodec<V> valueCodec) throws IOException {

        final DataOutputStream dataOutput; // NOPMD

        } else {

        }

        }

    /**

     * Reads a compiled trie from the supplied input stream.

     *

     * <p>

     * The caller must provide the same value codec semantics that were used during

     * persistence as well as the array factory required for typed result arrays.

     *

     * @param inputStream  source input stream

     * @param arrayFactory factory used to create typed arrays

     * @param valueCodec   codec used to read values

     * @param <V>          value type

     * @return deserialized compiled trie

     * @throws NullPointerException if any argument is {@code null}

     * @throws IOException          if reading fails or the binary format is invalid

     */

    public static <V> FrequencyTrie<V> readFrom(final InputStream inputStream, final IntFunction<V[]> arrayFactory,

            final ValueStreamCodec<V> valueCodec) throws IOException {

    }

    /**

     * Reads a compiled trie from the supplied input stream, optionally overriding

     * dense child-index span configuration.

     * <p>

     * This setting is applied only while materializing the in-memory compiled

     * representation during load. It is not serialized in {@link TrieMetadata}, so

     * each load can independently choose its own runtime lookup trade-off.

     * </p>

     *

     * @param inputStream      source input stream

     * @param arrayFactory     array factory used to create typed arrays

     * @param valueCodec       codec used to read values

     * @param maxExpandedIndex dense lookup span override; zero disables dense

     *                         lookup, negative values use

     *                         {@link #DEFAULT_MAX_EXPANDED_INDEX}

     * @param <V>              value type

     * @return deserialized compiled trie

     * @throws NullPointerException if any argument is {@code null}

     * @throws IOException          if reading fails or the binary format is invalid

     */

    public static <V> FrequencyTrie<V> readFrom(final InputStream inputStream, final IntFunction<V[]> arrayFactory,

            final ValueStreamCodec<V> valueCodec, final int maxExpandedIndex) throws IOException {

    }

    /**

     * Writes persisted trie metadata.

     *

     * @param dataOutput output stream

     * @param metadata   metadata to serialize

     * @throws IOException if writing fails

     */

    private static void writeMetadata(final DataOutputStream dataOutput, final TrieMetadata metadata)

            throws IOException {

    /**

     * Returns the number of canonical compiled nodes reachable from the root.

     *

     * <p>

     * The returned value reflects the size of the final reduced immutable trie, not

     * the number of mutable build-time nodes inserted before reduction. Shared

     * canonical subtrees are counted only once.

     *

     * @return number of canonical compiled nodes in this trie

     */

    public int size() {