// Path: src/main/java/de/mpii/gsm/writer/GsmWriter.java
// public interface GsmWriter {
// 	void write(int[] sequence, long count) throws IOException, InterruptedException;
// }
// 
// Path: src/main/java/de/mpii/gsm/utils/IntArrayStrategy.java
// public final class IntArrayStrategy implements Strategy<int[]> {  
// 
// 	
// 	 @Override
//      public boolean equals(int[] o1, int[] o2) {
//              return Arrays.equals(o1,  o2);
//      }
// 
//      @Override
//      public int hashCode(int[] o) {
//              return Arrays.hashCode(o);
//      }
// 
// 	
// }


import de.mpii.gsm.taxonomy.*;
import de.mpii.gsm.writer.GsmWriter;
import de.mpii.gsm.utils.IntArrayStrategy;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.bytes.ByteArrayList;
import it.unimi.dsi.fastutil.objects.Object2ObjectOpenCustomHashMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectOpenHashMap;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Map;
package de.mpii.gsm.localmining;






public class Bfs {

	// -- parameters
	// --------------------------------------------------------------------------------

	/** Minimum support */
	protected int sigma;

	/** Maximum gap */
	protected int gamma;

	/** Maximum length */
	protected int lambda;

	/**
	 * Start of pivot range (see class description). Set to 0 to mine all frequent
	 * sequences.
	 */
	protected int beginItem = 0;

	/**
	 * End of pivot range (see class description). Set to {@link Integer.MAXVALUE}
	 * to mine all frequent sequences.
	 */
	protected int endItem = Integer.MAX_VALUE;

	// -- internal variables
	// ------------------------------------------------------------------------

	// At any point of time, we store an inverted index that maps subsequences of
	// length k
	// to their posting lists.
	//
	// During data input, we have k=2. Every input transaction is added to the
	// index (by generating
	// all its (2,gamma)-subsequences and then discarded.
	//
	// During frequent sequence mining, we compute repeatedly compute length-(k+1)
	// subsequences
	// from the length-k subsequences.

	/** Length of subsequences currently being mined */
	protected int k;

	/**
	 * A list of sequences of length k; no sequence occurs more than once. Each
	 * sequence is stored in either uncompressed or compressed format.
	 * 
	 * In uncompressed format, each sequence is encoded as an array of exactly k
	 * item identifiers. When k=2, all sequences are stored in uncompressed
	 * format.
	 * 
	 * In compressed format, each sequence is encoded as a length-2 array (p, w).
	 * To reconstruct the uncompressed sequence, take the first k-1 items from the
	 * sequence at position p in kSequences (p is a "prefix pointer") and set the
	 * k-th item to w (suffix item). When k>2, an entry is compressed when it has
	 * two elements and uncompressed when it has k elements.
	 */
	protected ArrayList<int[]> kSequences = new ArrayList<int[]>();

	/**
	 * Maps 2-sequence to their position in kSequences (lowest 32 bits) and their
	 * largest transaction id (highest 32 bits). Only used during data input, k=2.
	 */
	Map<int[], KSequenceIndexEntry> kSequenceIndex = new Object2ObjectOpenCustomHashMap<int[], KSequenceIndexEntry>(
// Path: src/main/java/de/mpii/gsm/writer/GsmWriter.java
// public interface GsmWriter {
// 	void write(int[] sequence, long count) throws IOException, InterruptedException;
// }
// 
// Path: src/main/java/de/mpii/gsm/utils/IntArrayStrategy.java
// public final class IntArrayStrategy implements Strategy<int[]> {  
// 
// 	
// 	 @Override
//      public boolean equals(int[] o1, int[] o2) {
//              return Arrays.equals(o1,  o2);
//      }
// 
//      @Override
//      public int hashCode(int[] o) {
//              return Arrays.hashCode(o);
//      }
// 
// 	
// }


// Path: src/main/java/de/mpii/gsm/localmining/Bfs.java
import de.mpii.gsm.taxonomy.*;
import de.mpii.gsm.writer.GsmWriter;
import de.mpii.gsm.utils.IntArrayStrategy;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.bytes.ByteArrayList;
import it.unimi.dsi.fastutil.objects.Object2ObjectOpenCustomHashMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectOpenHashMap;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Map;

package de.mpii.gsm.localmining;






public class Bfs {

	// -- parameters
	// --------------------------------------------------------------------------------

	/** Minimum support */
	protected int sigma;

	/** Maximum gap */
	protected int gamma;

	/** Maximum length */
	protected int lambda;

	/**
	 * Start of pivot range (see class description). Set to 0 to mine all frequent
	 * sequences.
	 */
	protected int beginItem = 0;

	/**
	 * End of pivot range (see class description). Set to {@link Integer.MAXVALUE}
	 * to mine all frequent sequences.
	 */
	protected int endItem = Integer.MAX_VALUE;

	// -- internal variables
	// ------------------------------------------------------------------------

	// At any point of time, we store an inverted index that maps subsequences of
	// length k
	// to their posting lists.
	//
	// During data input, we have k=2. Every input transaction is added to the
	// index (by generating
	// all its (2,gamma)-subsequences and then discarded.
	//
	// During frequent sequence mining, we compute repeatedly compute length-(k+1)
	// subsequences
	// from the length-k subsequences.

	/** Length of subsequences currently being mined */
	protected int k;

	/**
	 * A list of sequences of length k; no sequence occurs more than once. Each
	 * sequence is stored in either uncompressed or compressed format.
	 * 
	 * In uncompressed format, each sequence is encoded as an array of exactly k
	 * item identifiers. When k=2, all sequences are stored in uncompressed
	 * format.
	 * 
	 * In compressed format, each sequence is encoded as a length-2 array (p, w).
	 * To reconstruct the uncompressed sequence, take the first k-1 items from the
	 * sequence at position p in kSequences (p is a "prefix pointer") and set the
	 * k-th item to w (suffix item). When k>2, an entry is compressed when it has
	 * two elements and uncompressed when it has k elements.
	 */
	protected ArrayList<int[]> kSequences = new ArrayList<int[]>();

	/**
	 * Maps 2-sequence to their position in kSequences (lowest 32 bits) and their
	 * largest transaction id (highest 32 bits). Only used during data input, k=2.
	 */
	Map<int[], KSequenceIndexEntry> kSequenceIndex = new Object2ObjectOpenCustomHashMap<int[], KSequenceIndexEntry>(
			new IntArrayStrategy());