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

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")

public final class FrequencyTrie<V> {

    /**

     * Logger of this class.

     */

    /**

     * Factory used to create correctly typed arrays for {@link #getAll(String)}.

     */

    private final IntFunction<V[]> arrayFactory;

    /**

     * Root node of the compiled read-only trie.

     */

    private final CompiledNode<V> root;

    /**

     * Metadata persisted together with this trie.

     */

    private final TrieMetadata metadata;

    /**

     * Binary format magic header.

     */

    private static final int STREAM_MAGIC = 0x45475452;

    /**

     * Binary format version.

     */

    private static final int STREAM_VERSION = 5;

    /**

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

    }

    /**

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

    /**

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

     */

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

        }

        }

    }

    /**

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

        final DataInputStream dataInput; // NOPMD

        } else {

        }

        }

        }

        }

        }

        }

    }

    /**

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

    /**

     * Reads persisted trie metadata while remaining backward compatible with

     * earlier stream versions.

     *

     * @param dataInput input stream

     * @param version   persisted stream version

     * @return deserialized metadata

     * @throws IOException if the metadata section is invalid

     */

    private static TrieMetadata readMetadata(final DataInputStream dataInput, final int version) throws IOException {

            try {

            }

        }

        final WordTraversalDirection traversalDirection;

            }

        }

        }

        }

        }

        final CaseProcessingMode caseProcessingMode;

            }

        }

                new ReductionSettings(reductionModes[reductionModeOrdinal], dominantWinnerMinPercent,

                        dominantWinnerOverSecondRatio),

                diacriticProcessingModes[diacriticProcessingModeOrdinal], caseProcessingMode);

    }

    /**

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

    }

    /**

     * Assigns deterministic identifiers to all canonical compiled nodes reachable

     * from the supplied root.

     *

     * @param node         current node

     * @param nodeIds      assigned node identifiers

     * @param orderedNodes ordered nodes in identifier order

     */

    private static <V> void assignNodeIds(final CompiledNode<V> node, final Map<CompiledNode<V>, Integer> nodeIds,

            final List<CompiledNode<V>> orderedNodes) {

        }

        }

    /**

     * Writes one compiled node.

     *

     * @param dataOutput output

     * @param valueCodec value codec

     * @param node       node to write

     * @param nodeIds    node identifiers

     * @throws IOException if writing fails

     */

    private static <V> void writeNode(final DataOutputStream dataOutput, final ValueStreamCodec<V> valueCodec,

            final CompiledNode<V> node, final Map<CompiledNode<V>, Integer> nodeIds) throws IOException {

            }

        }

        }

    /**

     * Reads all compiled nodes and resolves child references.

     *

     * @param dataInput    input

     * @param arrayFactory array factory

     * @param valueCodec   value codec

     * @param nodeCount    number of nodes

     * @param <V>          value type

     * @return array of nodes indexed by serialized node identifier

     * @throws IOException if reading fails or the stream is invalid

     */

    @SuppressWarnings("PMD.AvoidInstantiatingObjectsInLoops")

    private static <V> CompiledNode<V>[] readNodes(final DataInputStream dataInput, final IntFunction<V[]> arrayFactory,

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

            }

            }

            }

                            + valueIndex + ": " + orderedCounts[valueIndex]);

                }

            }

        }

        @SuppressWarnings("unchecked")

            @SuppressWarnings("unchecked")

        }

                            + ": " + childNodeId);

                }

            }

        }

    }

    /**

     * Validates the serialized edge-label sequence for one node.

     *

     * <p>

     * Compiled nodes rely on binary search for child lookup and therefore require

     * edge labels to be stored in strict ascending order without duplicates.

     * Rejecting malformed streams here keeps lookup semantics deterministic and

     * avoids silently constructing a trie whose search behavior would be undefined.

     *

     * @param nodeIndex  serialized node identifier

     * @param edgeLabels serialized edge labels

     * @throws IOException if the edge labels are not strictly ascending

     */

    private static void validateSerializedEdges(final int nodeIndex, final char... edgeLabels) throws IOException {

                        + edgeIndex + ": '" + edgeLabels[edgeIndex - 1] + "' then '" + edgeLabels[edgeIndex] + "'.");

            }

        }

    /**

     * Locates the compiled node for the supplied key.

     *

     * @param key already-normalized key to resolve

     * @return compiled node, or {@code null} if the path does not exist

     */

    private CompiledNode<V> findNode(final String key) {

            }

        }

    }

    /**

     * Applies lookup-time case normalization according to persisted metadata.

     *

     * @param key lookup key

     * @return normalized key for trie traversal

     */

    private String normalizeLookupKey(final String key) {

        }

                    "Diacritic processing mode AS_IS_AND_STRIPPED_FALLBACK is not supported yet.");

        }

    }

    /**

     * Builder of {@link FrequencyTrie}.

     *

     * <p>

     * The builder is intentionally mutable and optimized for repeated

     * {@link #put(String, Object)} calls. The final trie is created by

     * {@link #build()}, which performs bottom-up subtree reduction and converts the

     * structure to a compact immutable representation optimized for read

     * operations.

     *

     * @param <V> value type

     */

    public static final class Builder<V> {

        /**

         * Logger of this class.

         */

        /**

         * Factory used to create typed arrays.

         */

        private final IntFunction<V[]> arrayFactory;

        /**

         * Reduction configuration.

         */

        private final ReductionSettings reductionSettings;

        /**

         * Logical key traversal direction used by this builder.

         */

        private final WordTraversalDirection traversalDirection;

        /**

         * Dictionary case processing mode associated with this builder.

         */

        private final CaseProcessingMode caseProcessingMode;

        /**

         * Dictionary diacritic processing mode associated with this builder.

         */

        private final DiacriticProcessingMode diacriticProcessingMode;

        /**

         * Mutable root node.

         */

        private final MutableNode<V> root;

        /**

         * Creates a new builder with the provided settings.

         *

         * <p>

         * This constructor preserves the historical Egothor behavior and therefore

         * traverses logical keys from their end toward their beginning.

         * </p>

         *

         * @param arrayFactory      array factory

         * @param reductionSettings reduction configuration

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

         */

        public Builder(final IntFunction<V[]> arrayFactory, final ReductionSettings reductionSettings) {

        /**

         * Creates a new builder with the provided settings and explicit traversal

         * direction.

         *

         * @param arrayFactory       array factory

         * @param reductionSettings  reduction configuration

         * @param traversalDirection logical key traversal direction

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

         */

        public Builder(final IntFunction<V[]> arrayFactory, final ReductionSettings reductionSettings,

                final WordTraversalDirection traversalDirection) {

        /**

         * Creates a new builder with the provided settings, explicit traversal

         * direction, and explicit case processing mode.

         *

         * @param arrayFactory       array factory

         * @param reductionSettings  reduction configuration

         * @param traversalDirection logical key traversal direction

         * @param caseProcessingMode dictionary case processing mode

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

         */

        public Builder(final IntFunction<V[]> arrayFactory, final ReductionSettings reductionSettings,

                final WordTraversalDirection traversalDirection, final CaseProcessingMode caseProcessingMode) {

                    DiacriticProcessingMode.AS_IS);

        /**

         * Creates a new builder with the provided settings, explicit traversal

         * direction, explicit case processing mode, and explicit diacritic processing

         * mode.

         *

         * @param arrayFactory            array factory

         * @param reductionSettings       reduction configuration

         * @param traversalDirection      logical key traversal direction

         * @param caseProcessingMode      dictionary case processing mode

         * @param diacriticProcessingMode dictionary diacritic processing mode

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

         */

        public Builder(final IntFunction<V[]> arrayFactory, final ReductionSettings reductionSettings,