<commit_before>package morfologik.fsa.bytes;

import java.io.IOException;
import java.io.OutputStream;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.IdentityHashMap;

import morfologik.fsa.FSA5;
import morfologik.fsa.Visitor;

/**
 * Serializes in-memory <code>byte</code>-labeled automata to FSA5 format.
 */
public final class FSA5Serializer {
	private final static int MAX_ARC_SIZE = 1 + 5;

	/**
	 * @see FSA5#filler
	 */
	public byte fillerByte = '|';

	/**
	 * @see FSA5#annotation
	 */
	public byte annotationByte = '_';

	/**
	 * Node data length. Must be zero (node data not supported).
	 */
	private final int nodeDataLength = 0;

	/**
	 * Mutable integer for offset calculation.
	 */
	final static class IntHolder {
		public int value;
	}

	/**
	 * Serialize root state <code>s</code> to an output stream.
	 * 
	 * @return Returns <code>os</code> for chaining.
	 */
	public <T extends OutputStream> T serialize(State s, T os)
	        throws IOException {

		final IdentityHashMap<State, IntHolder> offsets = new IdentityHashMap<State, IntHolder>();
		final ArrayList<State> linearized = new ArrayList<State>();

		// Add the "sink node", with a single arc pointing to itself.
		State sink = new State();
		sink.labels = new byte[] { 0 };
		sink.states = new State[] { sink };
		linearized.add(sink); // Sink is not part of the automaton.
		offsets.put(sink, new IntHolder());

		// Add a special, initial "meta state".
		State meta = new State();
		meta.labels = new byte[] { '^' };
		meta.states = new State[] { s };
		s = meta;

		// Prepare space for arc offsets and linearize all the states.
		s.preOrder(new Visitor<State>() {
			public void accept(State s) {
				offsets.put(s, new IntHolder());
				linearized.add(s);
			}
		});

		// Calculate minimal goto length.
		int gtl = 1;
		while (true) {
			// First pass: calculate offsets of states.
			if (!emitArcs(null, linearized, gtl, offsets)) {
				gtl++;
				continue;
			}

			// Second pass: check if goto overflows anywhere.
			if (emitArcs(null, linearized, gtl, offsets))
				break;

			gtl++;
		}

		/*
		 * Emit the header.
		 */
		os.write(new byte[] { '\\', 'f', 's', 'a' });
		os.write(FSA5.VERSION);
		os.write(fillerByte);
		os.write(annotationByte);
		os.write((nodeDataLength << 4) | gtl);

		/*
		 * Emit the automaton.
		 */
		assert emitArcs(os, linearized, gtl, offsets);
		return os;
	}

	final int SIZEOF_LABEL = 1;
	final int SIZEOF_FLAGS = 1;

	/**
	 * Update arc offsets assuming the given goto length.
	 */
	private boolean emitArcs(OutputStream os, ArrayList<State> linearized,
	        final int gtl, final IdentityHashMap<State, IntHolder> offsets)
	        throws IOException 
    {
		final ByteBuffer bb = ByteBuffer.allocate(MAX_ARC_SIZE);

		int offset = 0;
		for (State s : linearized) {
			if (os == null) {
				offsets.get(s).value = offset;
			} else {
				assert offsets.get(s).value == offset;
			}

			final byte[] labels = s.labels;
			final State[] states = s.states;

			final int max = labels.length - 1;
			for (int i = 0; i <= max; i++) {
				bb.put(labels[i]);

				int flags = 0;
				final State target = states[i];

				if (target.isFinal()) {
					flags |= FSA5.BIT_FINAL_ARC;
				}

				final int targetOffset;
				if (isTerminal(target)) {
					targetOffset = offsets.get(target).value;
				} else {
					targetOffset = 0;
				}

				if (i == max) {
					flags |= FSA5.BIT_LAST_ARC;
				}

				int combined = (targetOffset << 3) | flags;
				for (int b = 0; b < gtl; b++) {
					bb.put((byte) combined);
					combined >>>= 8;
				}

				if (combined != 0) {
					// gtl too small. interrupt eagerly.
					return false;
				}

				bb.flip();
				offset += bb.remaining();
				if (os != null) {
					os.write(bb.array(), bb.position(), bb.remaining());
				}
				bb.clear();
			}
		}

		return true;
	}

	/**
	 * A terminal state does not have any outgoing transitions. 
	 */
	private boolean isTerminal(State state) {
	    return state.hasChildren();
    }
}<commit_msg>Added support for NEXT bit. Interestingly, still suboptimal compression; Daciuk must be doing something I'm not doing... <commit_after>package morfologik.fsa.bytes;

import java.io.IOException;
import java.io.OutputStream;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.IdentityHashMap;

import morfologik.fsa.FSA5;
import morfologik.fsa.Visitor;

/**
 * Serializes in-memory <code>byte</code>-labeled automata to FSA5 format.
 */
public final class FSA5Serializer {
	private final static int MAX_ARC_SIZE = 1 + 5;

	/**
	 * @see FSA5#filler
	 */
	public byte fillerByte = '|';

	/**
	 * @see FSA5#annotation
	 */
	public byte annotationByte = '_';

	/**
	 * Node data length. Must be zero (node data not supported).
	 */
	private final int nodeDataLength = 0;

	/**
	 * Mutable integer for offset calculation.
	 */
	final static class IntHolder {
		public int value;
	}

	/**
	 * Serialize root state <code>s</code> to an output stream.
	 * 
	 * @return Returns <code>os</code> for chaining.
	 */
	public <T extends OutputStream> T serialize(State s, T os)
	        throws IOException {

		final IdentityHashMap<State, IntHolder> offsets = new IdentityHashMap<State, IntHolder>();
		final ArrayList<State> linearized = new ArrayList<State>();

		// Add the "sink node", with a single arc pointing to itself.
		State sink = new State();
		sink.labels = new byte[] { 0 };
		sink.states = new State[] { sink };
		linearized.add(sink); // Sink is not part of the automaton.
		offsets.put(sink, new IntHolder());

		// Add a special, initial "meta state".
		State meta = new State();
		meta.labels = new byte[] { '^' };
		meta.states = new State[] { s };
		s = meta;

		// Prepare space for arc offsets and linearize all the states.
		s.preOrder(new Visitor<State>() {
			public void accept(State s) {
				offsets.put(s, new IntHolder());
				linearized.add(s);
			}
		});

		// Calculate minimal goto length.
		int gtl = 1;
		while (true) {
			// First pass: calculate offsets of states.
			if (!emitArcs(null, linearized, gtl, offsets)) {
				gtl++;
				continue;
			}

			// Second pass: check if goto overflows anywhere.
			if (emitArcs(null, linearized, gtl, offsets))
				break;

			gtl++;
		}

		/*
		 * Emit the header.
		 */
		os.write(new byte[] { '\\', 'f', 's', 'a' });
		os.write(FSA5.VERSION);
		os.write(fillerByte);
		os.write(annotationByte);
		os.write((nodeDataLength << 4) | gtl);

		/*
		 * Emit the automaton.
		 */
		assert emitArcs(os, linearized, gtl, offsets);
		return os;
	}

	final int SIZEOF_LABEL = 1;
	final int SIZEOF_FLAGS = 1;

	/**
	 * Update arc offsets assuming the given goto length.
	 */
	private boolean emitArcs(OutputStream os, ArrayList<State> linearized,
	        final int gtl, final IdentityHashMap<State, IntHolder> offsets)
	        throws IOException 
    {
		final ByteBuffer bb = ByteBuffer.allocate(MAX_ARC_SIZE);

		int offset = 0;
		int maxStates = linearized.size();
		for (int j = 0; j < maxStates; j++) {
			final State s = linearized.get(j);

			if (os == null) {
				offsets.get(s).value = offset;
			} else {
				assert offsets.get(s).value == offset;
			}

			final byte[] labels = s.labels;
			final State[] states = s.states;

			final int maxTransition = labels.length - 1;
			final int lastTransition = 0;
			for (int i = maxTransition; i >= 0; i--) {
				final State target = states[i];

				int targetOffset;
				if (isTerminal(target)) {
					targetOffset = offsets.get(target).value;
				} else {
					targetOffset = 0;
				}

				int combined = 0;
				int arcBytes = gtl;

				if (target.isFinal()) {
					combined |= FSA5.BIT_FINAL_ARC;
				}

				if (i == lastTransition) {
					combined |= FSA5.BIT_LAST_ARC;

					if (j + 1 < maxStates && target == linearized.get(j + 1) && targetOffset != 0) {
						combined |= FSA5.BIT_TARGET_NEXT;
						arcBytes = SIZEOF_FLAGS;
						targetOffset = 0;
					}
				}

				combined |= (targetOffset << 3);
				bb.put(labels[i]);
				for (int b = 0; b < arcBytes; b++) {
					bb.put((byte) combined);
					combined >>>= 8;
				}

				if (combined != 0) {
					// gtl too small. interrupt eagerly.
					return false;
				}

				bb.flip();
				offset += bb.remaining();
				if (os != null) {
					os.write(bb.array(), bb.position(), bb.remaining());
				}
				bb.clear();
			}
		}

		return true;
	}

	/**
	 * A terminal state does not have any outgoing transitions. 
	 */
	private boolean isTerminal(State state) {
	    return state.hasChildren();
    }
}
{'fraction_non_alphanumeric': 0.13759849464894744, 'fraction_numerical': 0.006703516405974362, 'mean_word_length': 2.794734493529674, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 38, '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': '665138', 'n_tokens_mistral': 3398, 'n_tokens_neox': 2778, 'n_words': 828}