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


import it.unimi.dsi.Util;
import it.unimi.dsi.bits.LongArrayBitVector;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntHeapIndirectPriorityQueue;
import it.unimi.dsi.fastutil.longs.LongBigList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Modulo3System {
	private final static boolean DEBUG = false;
	
	/** A modulo-3 equation. */
	public static class Modulo3Equation {
		/** The constant term. */
		protected int c;
		private final int numVars;
		protected final LongArrayBitVector bv;
		protected final long[] bits;
		private final LongBigList list;
		protected int coeff;
		private int firstVar;
		private int firstCoeff;
		private int wordIndex;
		private long word;
		public IntArrayList initialVars;
		private boolean isEmpty;

		/** Creates a new equation.
		 * 
		 * @param c the constant term.
		 */
		public Modulo3Equation( final int c, final int numVars ){
			this.c = c;
			this.bv = LongArrayBitVector.ofLength( numVars * 2 );
			this.numVars = numVars;
			this.bits = bv.bits();
			this.list = bv.asLongBigList( 2 );
			this.firstVar = Integer.MAX_VALUE;
			this.initialVars = new IntArrayList();
			this.isEmpty = true;
		}
		
		protected Modulo3Equation( final Modulo3Equation equation ){
			this.c = equation.c;
			this.bv = equation.bv.copy();
			this.bits = this.bv.bits();
			this.numVars = equation.numVars;
			this.list = this.bv.asLongBigList( 2 );
			this.firstVar = equation.firstVar;
			this.firstCoeff = equation.firstCoeff;
			this.initialVars = equation.initialVars;
			this.isEmpty = equation.isEmpty;
		}
		
		public Modulo3Equation add( final int index, final int value ) {
			if ( list.set( index, value ) != 0 ) throw new IllegalArgumentException();
			initialVars.add( index );
			if ( index < firstVar ) {
				firstVar = index;
				firstCoeff = value;
			}
			isEmpty = false;
			return this;
		}
		
		public Modulo3Equation add( final int index ) {
			return add( index, 1 );
		}
		
		public int[] variables() {
			IntArrayList variables = new IntArrayList();
			for( int var = firstVar(); var != Integer.MAX_VALUE; var = nextVar() ) variables.add( var );
			return variables.toIntArray();
		}

		public int[] coefficients() {
			IntArrayList coefficients = new IntArrayList();
			for( int var = firstVar(); var != Integer.MAX_VALUE; var = nextVar() ) coefficients.add( coeff );
			return coefficients.toIntArray();
		}
		
		public Modulo3Equation eliminate( final Modulo3Equation equation, final int var ) {
			final int mul = this.list.get( var ) == equation.list.get( var ) ? 1 : 2;
			sub( equation, mul );
			return this;

			//System.err.println( this + " - " + mul + " * " + equation + "  =>  " + result );
			//assert result.sub( equation, 3 - mul ).equals( this ) : result.sub( equation, 3 - mul ) + " != " + this;
		}

		protected final static long addMod3( final long x, final long y ) {
	        // mask the high bit of each pair set iff the result of the
	        // sum in that position is >= 3
	        // check if x is 2 and y is nonzero ...
	        long mask = x & (y | (y << 1));
	        // ... or x is 1 and y is 2
	        mask |= (x << 1) & y;
	        // clear the low bits
	        mask &= 0x5555555555555555L << 1;
	        // and turn 2s into 3s
	        mask |= mask >> 1;
	        return (x + y) - mask;
	    }

		protected final static long subMod3( final long x, long y ) {
	        // Change of sign
	        y = ( y & 0x5555555555555555L ) << 1 | ( y & 0xAAAAAAAAAAAAAAAAL ) >>> 1;
	        // mask the high bit of each pair set iff the result of the
	        // sum in that position is >= 3
	        // check if x is 2 and y is nonzero ...
			long mask = x & ( y | (y << 1) );
	        // ... or x is 1 and y is 2
	        mask |= (x << 1) & y;
	        // clear the low bits
	        mask &= 0x5555555555555555L << 1;
	        // and turn 2s into 3s
	        mask |= mask >> 1;
	        return (x + y) - mask;
	    }

		public void setFirstVar() {
			if ( isEmpty ) firstVar = Integer.MAX_VALUE;
			else {
				int i = -1;
				while( bits[ ++i ] == 0 );
				final int lsb = Long.numberOfTrailingZeros( bits[ i ] ) / 2;
				firstVar = lsb + 32 * i;
				firstCoeff = (int)( bits[ i ] >> lsb * 2 & 3 );
			}
		}

		private final void addMod3( final LongArrayBitVector x, final LongArrayBitVector y ) {
			final long[] bx = x.bits(), by = y.bits();
			boolean isNotEmpty = false;
			for( int i = (int)( ( x.length() + 63 ) / 64 ); i-- != 0; ) 
				isNotEmpty |= ( bx[ i ] = addMod3( bx[ i ], by[ i ] ) ) != 0;
			isEmpty = ! isNotEmpty;
		}
		
		private final void subMod3( final LongArrayBitVector x, final LongArrayBitVector y ) {
			final long[] bx = x.bits(), by = y.bits();
			boolean isNotEmpty = false;
			for( int i = (int)( ( x.length() + 63 ) / 64 ); i-- != 0; ) 
				isNotEmpty |= ( bx[ i ] = subMod3( bx[ i ], by[ i ] ) ) != 0;
			isEmpty = ! isNotEmpty;
		}
		
		/** Subtract from this equation another equation multiplied by a provided constant.
		 * 
		 * @param equation the subtrahend.
		 * @param mul a multiplier that will be applied to the subtrahend.
		 */
		
		public void sub( final Modulo3Equation equation, final int mul ) {
			// Explicit multiplication tables to avoid modulo operators.
			if ( mul == 1 ) {
				c = ( c + 2 * equation.c ) % 3;
				subMod3( bv, equation.bv );
			}
			else {
				c = ( c + equation.c ) % 3;
				addMod3( bv, equation.bv );
			}
		}
		<commit_msg>Improved bookkeeping<commit_after>package it.unimi.dsi.sux4j.mph;


import it.unimi.dsi.Util;
import it.unimi.dsi.bits.LongArrayBitVector;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntHeapIndirectPriorityQueue;
import it.unimi.dsi.fastutil.longs.LongBigList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Modulo3System {
	private final static boolean DEBUG = false;
	
	/** A modulo-3 equation. */
	public static class Modulo3Equation {
		/** The constant term. */
		protected int c;
		private final int numVars;
		protected final LongArrayBitVector bv;
		protected final long[] bits;
		private final LongBigList list;
		protected int coeff;
		private int firstVar;
		private int firstCoeff;
		private int wordIndex;
		private long word;
		public IntArrayList initialVars;
		private boolean isEmpty;

		/** Creates a new equation.
		 * 
		 * @param c the constant term.
		 */
		public Modulo3Equation( final int c, final int numVars ){
			this.c = c;
			this.bv = LongArrayBitVector.ofLength( numVars * 2 );
			this.numVars = numVars;
			this.bits = bv.bits();
			this.list = bv.asLongBigList( 2 );
			this.firstVar = Integer.MAX_VALUE;
			this.initialVars = new IntArrayList();
			this.isEmpty = true;
		}
		
		protected Modulo3Equation( final Modulo3Equation equation ){
			this.c = equation.c;
			this.bv = equation.bv.copy();
			this.bits = this.bv.bits();
			this.numVars = equation.numVars;
			this.list = this.bv.asLongBigList( 2 );
			this.firstVar = equation.firstVar;
			this.firstCoeff = equation.firstCoeff;
			this.initialVars = equation.initialVars;
			this.isEmpty = equation.isEmpty;
		}
		
		public Modulo3Equation add( final int index, final int value ) {
			if ( list.set( index, value ) != 0 ) throw new IllegalArgumentException();
			initialVars.add( index );
			if ( index < firstVar ) {
				firstVar = index;
				firstCoeff = value;
			}
			isEmpty = false;
			return this;
		}
		
		public Modulo3Equation add( final int index ) {
			return add( index, 1 );
		}
		
		public int[] variables() {
			IntArrayList variables = new IntArrayList();
			for( int var = firstVar(); var != Integer.MAX_VALUE; var = nextVar() ) variables.add( var );
			return variables.toIntArray();
		}

		public int[] coefficients() {
			IntArrayList coefficients = new IntArrayList();
			for( int var = firstVar(); var != Integer.MAX_VALUE; var = nextVar() ) coefficients.add( coeff );
			return coefficients.toIntArray();
		}
		
		public Modulo3Equation eliminate( final Modulo3Equation equation, final int var ) {
			final int mul = this.list.get( var ) == equation.list.get( var ) ? 1 : 2;
			sub( equation, mul );
			return this;

			//System.err.println( this + " - " + mul + " * " + equation + "  =>  " + result );
			//assert result.sub( equation, 3 - mul ).equals( this ) : result.sub( equation, 3 - mul ) + " != " + this;
		}

		protected final static long addMod3( final long x, final long y ) {
	        // mask the high bit of each pair set iff the result of the
	        // sum in that position is >= 3
	        // check if x is 2 and y is nonzero ...
	        long mask = x & (y | (y << 1));
	        // ... or x is 1 and y is 2
	        mask |= (x << 1) & y;
	        // clear the low bits
	        mask &= 0x5555555555555555L << 1;
	        // and turn 2s into 3s
	        mask |= mask >> 1;
	        return (x + y) - mask;
	    }

		protected final static long subMod3( final long x, long y ) {
	        // Change of sign
	        y = ( y & 0x5555555555555555L ) << 1 | ( y & 0xAAAAAAAAAAAAAAAAL ) >>> 1;
	        // mask the high bit of each pair set iff the result of the
	        // sum in that position is >= 3
	        // check if x is 2 and y is nonzero ...
			long mask = x & ( y | (y << 1) );
	        // ... or x is 1 and y is 2
	        mask |= (x << 1) & y;
	        // clear the low bits
	        mask &= 0x5555555555555555L << 1;
	        // and turn 2s into 3s
	        mask |= mask >> 1;
	        return (x + y) - mask;
	    }

		public void setFirstVar() {
			if ( isEmpty ) firstVar = Integer.MAX_VALUE;
			else {
				int i = -1;
				while( bits[ ++i ] == 0 );
				final int lsb = Long.numberOfTrailingZeros( bits[ i ] ) / 2;
				firstVar = lsb + 32 * i;
				firstCoeff = (int)( bits[ i ] >> lsb * 2 & 3 );
			}
		}

		private final void addMod3( final LongArrayBitVector x, final LongArrayBitVector y ) {
			final long[] bx = x.bits(), by = y.bits();
			long isNotEmpty = 0;
			for( int i = (int)( ( x.length() + 63 ) / 64 ); i-- != 0; ) 
				isNotEmpty |= ( bx[ i ] = addMod3( bx[ i ], by[ i ] ) );
			isEmpty = isNotEmpty == 0;
		}
		
		private final void subMod3( final LongArrayBitVector x, final LongArrayBitVector y ) {
			final long[] bx = x.bits(), by = y.bits();
			long isNotEmpty = 0;
			for( int i = (int)( ( x.length() + 63 ) / 64 ); i-- != 0; ) 
				isNotEmpty |= ( bx[ i ] = subMod3( bx[ i ], by[ i ] ) ); 
			isEmpty = isNotEmpty == 0;
		}
		
		/** Subtract from this equation another equation multiplied by a provided constant.
		 * 
		 * @param equation the subtrahend.
		 * @param mul a multiplier that will be applied to the subtrahend.
		 */
		
		public void sub( final Modulo3Equation equation, final int mul ) {
			// Explicit multiplication tables to avoid modulo operators.
			if ( mul == 1 ) {
				c = ( c + 2 * equation.c ) % 3;
				subMod3( bv, equation.bv );
			}
			else {
				c = ( c + equation.c ) % 3;
				addMod3( bv, equation.bv );
			}
		}
		
{'fraction_non_alphanumeric': 0.12674777555838024, 'fraction_numerical': 0.023061558017069186, 'mean_word_length': 2.434674150296227, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 8, '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': '2003341', 'n_tokens_mistral': 4282, 'n_tokens_neox': 3565, 'n_words': 1179}