<commit_before>/*
 * Copyright 2012 <NAME>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.trie4j.louds;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import org.trie4j.AbstractTrie;
import org.trie4j.Node;
import org.trie4j.Trie;
import org.trie4j.tail.SuffixTrieTailBuilder;
import org.trie4j.tail.TailBuilder;
import org.trie4j.tail.TailCharIterator;
import org.trie4j.tail.TailUtil;
import org.trie4j.util.Pair;
import org.trie4j.util.SuccinctBitVector;

public class LOUDSTrie extends AbstractTrie implements Trie {
	public LOUDSTrie(){
	}

	public LOUDSTrie(Trie orig){
		this(orig, 65536);
	}

	public LOUDSTrie(Trie orig, int bitSize){
		this(orig, bitSize, new SuffixTrieTailBuilder());
	}

	public LOUDSTrie(Trie orig, int bitSize, TailBuilder tb){
		bv = new SuccinctBitVector(bitSize);
		labels = new char[bitSize / 2];
		tail = new int[bitSize / 2];
		term = new BitSet(bitSize / 2);
		LinkedList<Node> queue = new LinkedList<Node>();
		int count = 0;
		if(orig.getRoot() != null) queue.add(orig.getRoot());
		while(!queue.isEmpty()){
			Node node = queue.pollFirst();
			int index = count++;
			if(index >= labels.length){
				extend();
			}
			if(node.isTerminate()){
				term.set(index);
			}
			Node[] children = node.getChildren();
			if(children != null){
				for(Node c : children){
					bv.append1();
					queue.offerLast(c);
				}
			}
			bv.append0();
			char[] letters = node.getLetters();
			if(letters.length == 0){
				labels[index] = 0xffff;
				tail[index] = -1;
			} else{
				labels[index] = letters[0];
				if(letters.length >= 2){
					tail[index] = tb.insert(letters, 1, letters.length - 1);
				} else{
					tail[index] = -1;
				}
			}
		}
		size = count;
		tails = tb.getTails();
	}

	public SuccinctBitVector getBv() {
		return bv;
	}

	public Node getRoot(){
		return new LOUDSNode(0);
	}

	@Override
	public void dump() {
		super.dump();
		String bvs = bv.toString();
		System.out.println("bitvec: " + ((bvs.length() > 100) ? bvs.substring(0, 100) : bvs));
		System.out.print("labels: ");
		int count = 0;
		for(char c : labels){
			System.out.print(c);
			if(count++ == 99) break;
		}
		System.out.println();
	}

	@Override
	public boolean contains(String word){
		char[] chars = word.toCharArray();
		int charsLen = chars.length;
		int nodeId = 0; // root
		TailCharIterator tci = new TailCharIterator(tails, -1);
		for(int charsIndex = 0; charsIndex < charsLen; charsIndex++){
			int child = getChildNode(nodeId, chars[charsIndex]);
			if(child == -1) return false;
			int ti = tail[child];
			if(ti != -1){
				tci.setIndex(ti);
				while(tci.hasNext()){
					charsIndex++;
					if(charsLen <= charsIndex) return false;
					if(chars[charsIndex] != tci.next()) return false;
				}
			}
			if(charsLen == (charsIndex + 1)){
				return term.get(child);
			}
			nodeId = child;
		}
		return false;
	}

	@Override
	public Iterable<String> commonPrefixSearch(String query) {
		List<String> ret = new ArrayList<String>();
		char[] chars = query.toCharArray();
		int charsLen = chars.length;
		int nodeId = 0; // root
		TailCharIterator tci = new TailCharIterator(tails, -1);
		for(int charsIndex = 0; charsIndex < charsLen; charsIndex++){
			int child = getChildNode(nodeId, chars[charsIndex]);
			if(child == -1) return ret;
			int ti = tail[child];
			if(ti != -1){
				tci.setIndex(ti);
				while(tci.hasNext()){
					charsIndex++;
					if(charsLen <= charsIndex) return ret;
					if(chars[charsIndex] != tci.next()) return ret;
				}
			}
			if(term.get(child)){
				ret.add(new String(chars, 0, charsIndex + 1));
			}
			nodeId = child;
		}
		return ret;
	}

	@Override
	public Iterable<String> predictiveSearch(String query) {
		List<String> ret = new ArrayList<String>();
		char[] chars = query.toCharArray();
		int charsLen = chars.length;
		int nodeId = 0; // root
		TailCharIterator tci = new TailCharIterator(tails, -1);
		String pfx = null;
		for(int charsIndex = 0; charsIndex < charsLen; charsIndex++){
			int child = getChildNode(nodeId, chars[charsIndex]);
			if(child == -1) return ret;
			int ti = tail[child];
			if(ti != -1){
				tci.setIndex(ti);
				int charsIndexBack = charsIndex;
				while(tci.hasNext()){
					charsIndex++;
					if(charsIndex >= charsLen){
						pfx = new String(chars, 0, charsIndexBack);
						break;
					}
					if(chars[charsIndex] != tci.next()) return ret;
				}
			}
			nodeId = child;
		}
		if(pfx == null) pfx = query;

		Deque<Pair<Integer, String>> queue = new LinkedList<Pair<Integer,String>>();
		queue.offerLast(Pair.create(nodeId, pfx));
		while(queue.size() > 0){
			Pair<Integer, String> element = queue.pollFirst();
			int nid = element.getFirst();
<commit_msg>fix bug of predictiveSearch.<commit_after>/*
 * Copyright 2012 <NAME>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.trie4j.louds;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import org.trie4j.AbstractTrie;
import org.trie4j.Node;
import org.trie4j.Trie;
import org.trie4j.tail.SuffixTrieTailBuilder;
import org.trie4j.tail.TailBuilder;
import org.trie4j.tail.TailCharIterator;
import org.trie4j.tail.TailUtil;
import org.trie4j.util.Pair;
import org.trie4j.util.SuccinctBitVector;

public class LOUDSTrie extends AbstractTrie implements Trie {
	public LOUDSTrie(){
	}

	public LOUDSTrie(Trie orig){
		this(orig, 65536);
	}

	public LOUDSTrie(Trie orig, int bitSize){
		this(orig, bitSize, new SuffixTrieTailBuilder());
	}

	public LOUDSTrie(Trie orig, int bitSize, TailBuilder tb){
		bv = new SuccinctBitVector(bitSize);
		labels = new char[bitSize / 2];
		tail = new int[bitSize / 2];
		term = new BitSet(bitSize / 2);
		LinkedList<Node> queue = new LinkedList<Node>();
		int count = 0;
		if(orig.getRoot() != null) queue.add(orig.getRoot());
		while(!queue.isEmpty()){
			Node node = queue.pollFirst();
			int index = count++;
			if(index >= labels.length){
				extend();
			}
			if(node.isTerminate()){
				term.set(index);
			}
			Node[] children = node.getChildren();
			if(children != null){
				for(Node c : children){
					bv.append1();
					queue.offerLast(c);
				}
			}
			bv.append0();
			char[] letters = node.getLetters();
			if(letters.length == 0){
				labels[index] = 0xffff;
				tail[index] = -1;
			} else{
				labels[index] = letters[0];
				if(letters.length >= 2){
					tail[index] = tb.insert(letters, 1, letters.length - 1);
				} else{
					tail[index] = -1;
				}
			}
		}
		size = count;
		tails = tb.getTails();
	}

	public SuccinctBitVector getBv() {
		return bv;
	}

	public Node getRoot(){
		return new LOUDSNode(0);
	}

	@Override
	public void dump() {
		super.dump();
		String bvs = bv.toString();
		System.out.println("bitvec: " + ((bvs.length() > 100) ? bvs.substring(0, 100) : bvs));
		System.out.print("labels: ");
		int count = 0;
		for(char c : labels){
			System.out.print(c);
			if(count++ == 99) break;
		}
		System.out.println();
	}

	@Override
	public boolean contains(String word){
		char[] chars = word.toCharArray();
		int charsLen = chars.length;
		int nodeId = 0; // root
		TailCharIterator tci = new TailCharIterator(tails, -1);
		for(int charsIndex = 0; charsIndex < charsLen; charsIndex++){
			int child = getChildNode(nodeId, chars[charsIndex]);
			if(child == -1) return false;
			int ti = tail[child];
			if(ti != -1){
				tci.setIndex(ti);
				while(tci.hasNext()){
					charsIndex++;
					if(charsLen <= charsIndex) return false;
					if(chars[charsIndex] != tci.next()) return false;
				}
			}
			if(charsLen == (charsIndex + 1)){
				return term.get(child);
			}
			nodeId = child;
		}
		return false;
	}

	@Override
	public Iterable<String> commonPrefixSearch(String query) {
		List<String> ret = new ArrayList<String>();
		char[] chars = query.toCharArray();
		int charsLen = chars.length;
		int nodeId = 0; // root
		TailCharIterator tci = new TailCharIterator(tails, -1);
		for(int charsIndex = 0; charsIndex < charsLen; charsIndex++){
			int child = getChildNode(nodeId, chars[charsIndex]);
			if(child == -1) return ret;
			int ti = tail[child];
			if(ti != -1){
				tci.setIndex(ti);
				while(tci.hasNext()){
					charsIndex++;
					if(charsLen <= charsIndex) return ret;
					if(chars[charsIndex] != tci.next()) return ret;
				}
			}
			if(term.get(child)){
				ret.add(new String(chars, 0, charsIndex + 1));
			}
			nodeId = child;
		}
		return ret;
	}

	@Override
	public Iterable<String> predictiveSearch(String query) {
		List<String> ret = new ArrayList<String>();
		char[] chars = query.toCharArray();
		int charsLen = chars.length;
		int nodeId = 0; // root
		TailCharIterator tci = new TailCharIterator(tails, -1);
		String pfx = null;
		int charsIndexBack = 0;
		for(int charsIndex = 0; charsIndex < charsLen; charsIndex++){
			charsIndexBack = charsIndex;
			int child = getChildNode(nodeId, chars[charsIndex]);
			if(child == -1) return ret;
			int ti = tail[child];
			if(ti != -1){
				tci.setIndex(ti);
				while(tci.hasNext()){
					charsIndex++;
					if(charsIndex >= charsLen) break;
					if(chars[charsIndex] != tci.next()) return ret;
				}
			}
			nodeId = child;
		}
		pfx = new String(chars, 0, charsIndexBack);

		Deque<Pair<Integer, String>> queue = new LinkedList<Pair<Integer,String>>();
		queue.offerLast(Pair.create(nodeId, pfx));
		while(queue.size() > 0){
			Pair<Integer, String> element = queue.pollFirst();
			int nid = element.getFirst();

{'fraction_non_alphanumeric': 0.14262250205310703, 'fraction_numerical': 0.01250114061501962, 'mean_word_length': 3.60697772173182, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '121924', 'n_tokens_mistral': 4448, 'n_tokens_neox': 3755, 'n_words': 953}