<commit_before>package it.unimi.dsi.sux4j.mph;

/*		 
 * Sux4J: Succinct data structures for Java
 *
 * Copyright (C) 2008 <NAME> 
 *
 *  This library is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  This library is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 *  for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 */

import static it.unimi.dsi.sux4j.mph.HypergraphSorter.GAMMA;
import it.unimi.dsi.Util;
import it.unimi.dsi.bits.BitVector;
import it.unimi.dsi.bits.LongArrayBitVector;
import it.unimi.dsi.bits.TransformationStrategies;
import it.unimi.dsi.bits.TransformationStrategy;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction;
import it.unimi.dsi.fastutil.objects.AbstractObjectIterator;
import it.unimi.dsi.fastutil.objects.Object2LongFunction;
import it.unimi.dsi.fastutil.objects.Object2LongOpenHashMap;
import it.unimi.dsi.fastutil.objects.ObjectOpenHashSet;
import it.unimi.dsi.io.InputBitStream;
import it.unimi.dsi.io.OutputBitStream;
import it.unimi.dsi.lang.MutableString;
import it.unimi.dsi.sux4j.bits.BalancedParentheses;
import it.unimi.dsi.sux4j.bits.JacobsonBalancedParentheses;
import it.unimi.dsi.sux4j.util.EliasFanoLongBigList;
import it.unimi.dsi.util.LongBigList;

import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.apache.log4j.Logger;

/** A distributor based on a hollow trie.
 * 
 * <h2>Implementation details</h2>
 * 
 * <p>This class implements a distributor on top of a hollow trie. First, a compacted trie is built from the delimiter set.
 * Then, for each key we compute the node of the trie in which the bucket of the key is established. This gives us,
 * for each node of the trie, a set of paths to which we must associate an action (exit on the left,
 * go through, exit on the right). Overall, the number of such paths is equal to the number of keys plus the number of delimiters, so
 * the mapping from each pair node/path to the respective action takes linear space. Now, from the compacted trie we just
 * retain a hollow trie, as the path-length information is sufficient to rebuild the keys of the above mapping. 
 * By sizing the bucket size around the logarithm of the average length, we obtain a distributor that occupies linear space.
 */

public class HollowTrieDistributor2<T> extends AbstractObject2LongFunction<T> {
	private static final int SIGBITS = 2;
	private final static Logger LOGGER = Util.getLogger( HollowTrieDistributor2.class );
	private static final long serialVersionUID = 2L;
	private static final boolean DEBUG = false;
	private static final boolean DDEBUG = false;
	private static final boolean ASSERTS = true;

	/** An integer representing the exit-on-the-left behaviour. */
	private final static int LEFT = 0;
	/** An integer representing the exit-on-the-right behaviour. */
	private final static int RIGHT = 1;
	/** An integer representing the follow-the-try behaviour. */
	private final static int FOLLOW = 2;
	
	/** The transformation used to map object to bit vectors. */
	private final TransformationStrategy<? super T> transformationStrategy;
	/** The bitstream representing the hollow trie. */
	private final LongArrayBitVector trie;
	/** The list of skips, indexed by the internal nodes (we do not need skips on the leaves). */
	private final EliasFanoLongBigList skips;
	/** The signatures of the trie compacted paths. */
	private final LongBigList signatures;
	/** For each external node and each possible path, the related behaviour. */
	private final MWHCFunction<BitVector> externalBehaviour;<commit_msg>Tweaking<commit_after>package it.unimi.dsi.sux4j.mph;

/*		 
 * Sux4J: Succinct data structures for Java
 *
 * Copyright (C) 2008 <NAME> 
 *
 *  This library is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  This library is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 *  for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 */

import static it.unimi.dsi.sux4j.mph.HypergraphSorter.GAMMA;
import it.unimi.dsi.Util;
import it.unimi.dsi.bits.BitVector;
import it.unimi.dsi.bits.LongArrayBitVector;
import it.unimi.dsi.bits.TransformationStrategies;
import it.unimi.dsi.bits.TransformationStrategy;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction;
import it.unimi.dsi.fastutil.objects.AbstractObjectIterator;
import it.unimi.dsi.fastutil.objects.Object2LongFunction;
import it.unimi.dsi.fastutil.objects.Object2LongOpenHashMap;
import it.unimi.dsi.fastutil.objects.ObjectOpenHashSet;
import it.unimi.dsi.io.InputBitStream;
import it.unimi.dsi.io.OutputBitStream;
import it.unimi.dsi.lang.MutableString;
import it.unimi.dsi.sux4j.bits.BalancedParentheses;
import it.unimi.dsi.sux4j.bits.JacobsonBalancedParentheses;
import it.unimi.dsi.sux4j.util.EliasFanoLongBigList;
import it.unimi.dsi.util.LongBigList;

import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.apache.log4j.Logger;

/** A distributor based on a hollow trie.
 * 
 * <h2>Implementation details</h2>
 * 
 * <p>This class implements a distributor on top of a hollow trie. First, a compacted trie is built from the delimiter set.
 * Then, for each key we compute the node of the trie in which the bucket of the key is established. This gives us,
 * for each node of the trie, a set of paths to which we must associate an action (exit on the left,
 * go through, exit on the right). Overall, the number of such paths is equal to the number of keys plus the number of delimiters, so
 * the mapping from each pair node/path to the respective action takes linear space. Now, from the compacted trie we just
 * retain a hollow trie, as the path-length information is sufficient to rebuild the keys of the above mapping. 
 * By sizing the bucket size around the logarithm of the average length, we obtain a distributor that occupies linear space.
 */

public class HollowTrieDistributor2<T> extends AbstractObject2LongFunction<T> {
	private static final int SIGBITS = 2;
	private final static Logger LOGGER = Util.getLogger( HollowTrieDistributor2.class );
	private static final long serialVersionUID = 2L;
	private static final boolean DEBUG = false;
	private static final boolean DDEBUG = false;
	private static final boolean ASSERTS = false;

	/** An integer representing the exit-on-the-left behaviour. */
	private final static int LEFT = 0;
	/** An integer representing the exit-on-the-right behaviour. */
	private final static int RIGHT = 1;
	/** An integer representing the follow-the-try behaviour. */
	private final static int FOLLOW = 2;
	
	/** The transformation used to map object to bit vectors. */
	private final TransformationStrategy<? super T> transformationStrategy;
	/** The bitstream representing the hollow trie. */
	private final LongArrayBitVector trie;
	/** The list of skips, indexed by the internal nodes (we do not need skips on the leaves). */
	private final EliasFanoLongBigList skips;
	/** The signatures of the trie compacted paths. */
	private final LongBigList signatures;
	/** For each external node and each possible path, the related behaviour. */
	private final MWHCFunction<BitVector> externalBehaviour;
{'fraction_non_alphanumeric': 0.07633769322235434, 'fraction_numerical': 0.009512485136741973, 'mean_word_length': 4.37444089456869, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7245535', 'n_tokens_mistral': 2499, 'n_tokens_neox': 2431, 'n_words': 967}