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.CharBuffer;

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.concurrent.locks.ReentrantLock;

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.

 * </p>

 *

 * <p>

 * Instances are immutable and safe for concurrent lookup. A

 * {@linkplain #withLookupMode(LookupMode) lookup-mode view} shares the same

 * compiled node graph and changes only which applicable node or nodes a read

 * selects. Returned arrays and collections are caller-owned or immutable.

 * </p>

 *

 * @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;

    /**

     * Lazily initialized canonical SHA-256 fingerprint bytes. Every read and write

     * is guarded by {@link #fingerprintLock}. The value is assigned only after

     * calculation succeeds, so failed initialization leaves the cache empty. The

     * internal array is never exposed directly to callers.

     */

    private byte[] fingerprintBytes;

    /**

     * Guards all access to {@link #fingerprintBytes}. Holding this lock for every

     * cache read and write safely publishes successful lazy initialization to

     * subsequent callers.

     */

    /**

     * 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;

    /**

     * Read-time command-selection policy for the {@code get} / {@code getAll}

     * family. Never persisted; defaults to {@link LookupMode#FIRST}.

     */

    private final LookupMode lookupMode;

    /**

     * Cached {@code true} when {@link #lookupTraversalDirection} consumes keys

     * from the end (BACKWARD), used by the {@code LAST}/{@code ALL} traversals.

     */

    private final boolean backwardLookup;

    /**

     * 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 = 7;

    /**

     * 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;

    /**

     * Version where distinct values are persisted once in a stream-local table.

     */

    private static final int VALUE_TABLE_VERSION = 7;

    /**

     * 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() {

    }

    /**

     * Returns whether the supplied metadata identifies a stream format with a

     * serialized value table.

     *

     * @param metadata parsed trie metadata

     * @return {@code true} when values are stored in a stream-local table

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

     */

    /* default */ static boolean usesValueTableFormat(final TrieMetadata metadata) {

    }

    /**

     * 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 lookup-policy view over an existing compiled trie, sharing its

     * immutable compiled structure and metadata.

     *

     * @param source original trie

     * @param mode   lookup policy for the new view

     */

    /**

     * Returns the read-time command-selection policy of this trie.

     *

     * <p>

     * The operation is constant-time and performs no allocation.

     * </p>

     *

     * @return current lookup mode

     */

    public LookupMode lookupMode() {

    }

    /**

     * Returns a view of this trie that selects commands according to {@code mode}.

     *

     * <p>

     * The returned instance shares this trie's immutable compiled structure, so

     * the operation is cheap and thread-safe. The policy is a read-time concern

     * and is never persisted (see {@link LookupMode}). Returns {@code this} when

     * the mode is unchanged.

     * </p>

     *

     * @apiNote Serializing this view writes the shared trie structure and metadata,

     *          but not {@code mode}. A subsequently loaded trie therefore starts in

     *          {@link LookupMode#FIRST}.

     *

     * @param mode command-selection policy

     * @return a trie view applying {@code mode}; returns this instance when the

     *         requested mode is already active

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

     */

    public FrequencyTrie<V> withLookupMode(final LookupMode mode) {

        }

    }

    /**

     * 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 preferred value selected for the supplied key under this trie's

     * {@linkplain #lookupMode() lookup mode}.

     *

     * <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.

     * In {@link LookupMode#ALL}, this scalar operation uses the same

     * most-specific selection as {@link LookupMode#LAST}.

     * </p>

     *

     * @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 the values selected for the supplied key under this trie's

     * {@linkplain #lookupMode() lookup mode}.

     *

     * <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.

     * Under {@link LookupMode#ALL}, values from all applicable nodes are ordered

     * from the most-specific node to the least-specific accepting ancestor,

     * retain each node's local frequency order, and are de-duplicated by

     * {@link Object#equals(Object)}. Other modes return one selected node's values.

     * </p>

     *

     * <p>

     * The supplied key is normalized according to persisted

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

     * </p>

     *

     * @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 the selected values and 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.

     * Under {@link LookupMode#ALL}, a value occurring at multiple applicable nodes

     * appears once with the count from its most-specific occurrence.

     * </p>

     *

     * @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) {

        }

                    sink, 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>

     *

     * <p>

     * The fingerprint is calculated on first request and reused by later

     * fingerprint accessors.

     * </p>

     *

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