<commit_before>package yuku.alkitab.base.util;

import android.graphics.Typeface;
import android.os.Parcel;
import android.os.Parcelable;
import android.text.SpannableStringBuilder;
import android.text.Spanned;
import android.text.style.ForegroundColorSpan;
import android.text.style.StyleSpan;
import android.util.Log;
import android.util.SparseBooleanArray;
import android.util.TimingLogger;
import yuku.alkitab.base.App;
import yuku.alkitab.base.config.AppConfig;
import yuku.alkitab.debug.BuildConfig;
import yuku.alkitab.model.Book;
import yuku.alkitab.model.SingleChapterVerses;
import yuku.alkitab.model.Version;
import yuku.alkitab.util.Ari;
import yuku.alkitab.util.IntArrayList;
import yuku.bintex.BintexReader;

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.lang.ref.SoftReference;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.Semaphore;

public class SearchEngine {
	public static final String TAG = SearchEngine.class.getSimpleName();

	public static class Query implements Parcelable {
		public String query_string;
		public SparseBooleanArray bookIds;
		
		@Override public int describeContents() {
			return 0;
		}
		
		@Override public void writeToParcel(Parcel dest, int flags) {
			dest.writeString(query_string);
			dest.writeSparseBooleanArray(bookIds);
		}

		public static final Parcelable.Creator<Query> CREATOR = new Parcelable.Creator<Query>() {
			@Override public Query createFromParcel(Parcel in) {
				Query res = new Query();
				res.query_string = in.readString();
				res.bookIds = in.readSparseBooleanArray();
				return res;
			}

			@Override public Query[] newArray(int size) {
				return new Query[size];
			}
		};
	}
	
	static class RevIndex extends HashMap<String, int[]> {
		public RevIndex() {
			super(32768);
		}
	}
	
	private static SoftReference<RevIndex> cache_revIndex;
	private static Semaphore revIndexLoading = new Semaphore(1);
	
	public static IntArrayList searchByGrep(final Version version, final Query query) {
		String[] words = QueryTokenizer.tokenize(query.query_string);
		
		// sort by word length, then alphabetically
		Arrays.sort(words, (object1, object2) -> {
			final int len1 = object1.length();
			final int len2 = object2.length();

			if (len1 > len2) return -1;
			if (len1 == len2) {
				return object1.compareTo(object2);
			}
			return 1;
		});
		
		// remove duplicates
		{
			ArrayList<String> awords = new ArrayList<>();
			String last = null;
			for (String word: words) {
				if (!word.equals(last)) {
					awords.add(word);
				}
				last = word;
			}
			words = awords.toArray(new String[awords.size()]);
			if (BuildConfig.DEBUG) Log.d(TAG, "words = " + Arrays.toString(words));
		}
		
		// really search
		IntArrayList result = null;

		for (final String word : words) {
			final IntArrayList prev = result;

			{
				long ms = System.currentTimeMillis();
				result = searchByGrepInside(version, word, prev, query.bookIds);
				Log.d(TAG, "search word '" + word + "' needed: " + (System.currentTimeMillis() - ms) + " ms");
			}

			if (prev != null) {
				Log.d(TAG, "Will intersect " + prev.size() + " elements with " + result.size() + " elements...");
				result = intersect(prev, result);
				Log.d(TAG, "... the result is " + result.size() + " elements");
			}
		}

		return result;
	}

	private static IntArrayList intersect(IntArrayList a, IntArrayList b) {
		IntArrayList res = new IntArrayList(a.size());
		
		int[] aa = a.buffer();
		int[] bb = b.buffer();
		int alen = a.size();
		int blen = b.size();
		
		int apos = 0;
		int bpos = 0;
		
		while (true) {
			if (apos >= alen) break;
			if (bpos >= blen) break;
			
			int av = aa[apos];
			int bv = bb[bpos];
			
			if (av == bv) {
				res.add(av);
				apos++;
				bpos++;
			} else if (av > bv) {
				bpos++;
			} else { // av < bv
				apos++;
			}
		}
		
		return res;
	}

	/**
	 * Return the next ari (with only book and chapter) after the lastAriBc by scanning the source starting from pos.
	 * @param ppos pointer to pos. pos will be changed to ONE AFTER THE FOUND POSITION. So do not do another increment (++) outside this method.
	 */
	private static int nextAri(IntArrayList source, int[] ppos, int lastAriBc) {
		int[] s = source.buffer();
		int len = source.size();
		int pos = ppos[0];
		
		while (true) {
			if (pos >= len) return 0x0;
			
			int curAri = s[pos];
			int curAriBc = Ari.toBookChapter(curAri);
			
			if (curAriBc != lastAriBc) {
				// found!
				pos++;
				ppos[0] = pos;
				return curAriBc;
			} else {
				// still the same one, move to next.
				pos++;
			}
		}
	}

	static IntArrayList searchByGrepInside(final Version version, String word, final IntArrayList source, final SparseBooleanArray bookIds) {
		final IntArrayList res = new IntArrayList();
		final boolean hasPlus = QueryTokenizer.isPlussedToken(word);

		if (hasPlus) {
			word = QueryTokenizer.tokenWithoutPlus(word);
		}

		if (source == null) {
			for (Book book: version.getConsecutiveBooks()) {
				if (!bookIds.get(book.bookId, false)) {
					continue; // the book is not included in selected books to be searched
				}

				for (int chapter_1 = 1; chapter_1 <= book.chapter_count; chapter_1++) {
					// try to find it wholly in a chapter
					final int ariBc = Ari.encode(book.bookId, chapter_1, 0);
					searchByGrepForOneChapter(version, book, chapter_1, word, hasPlus, ariBc, res);
				}
	
				if (BuildConfig.DEBUG) Log.d(TAG, "searchByGrepInside book " + book.shortName + " done. res.size = " + res.size());
			}
		} else {
			// search only on book-chapters that are in the source
			int count = 0; // for stats
			
			int[] ppos = new int[1];
			int curAriBc = 0x000000;
			
			while (true) {
				curAriBc = nextAri(source, ppos, curAriBc);
				if (curAriBc == 0) break; // no more
				
				// No need to check null book, because we go here only after searching a previous token which is based on
				// getConsecutiveBooks, which is impossible to have null books.
				final Book book = version.getBook(Ari.toBook(curAriBc));
				final int chapter_1 = Ari.toChapter(curAriBc);

				searchByGrepForOneChapter(version, book, chapter_1, word, hasPlus, curAriBc, res);
				
				count++;
			}
			
			if (BuildConfig.DEBUG) Log.d(TAG, "searchByGrepInside book with source " + source.size() + " needed to read as many as " + count + " book-chapter. res.size=" + res.size());
		}
		
		return res;
	}

	/**
	 * @param word searched word without plusses
	 * @param res (output) result aris
	 * @param ariBc book-chapter ari, with verse must be set to 0
	 * @param hasPlus whether the word had plus
	 */
	private static void searchByGrepForOneChapter(final Version version, final Book book, final int chapter_1, final String word, final boolean hasPlus, final int ariBc, final IntArrayList res) {
		// This is a string of one chapter with verses joined by 0x0a ('\n')
		final String oneChapter = version.loadChapterTextLowercasedWithoutSplit(book, chapter_1);
		if (oneChapter == null) {
			return;
		}

		int verse_0 = 0;
		int lastV = -1;

		// Initial search
		int posWord;
		if (hasPlus) {
			posWord = indexOfWholeWord(oneChapter, word, 0);
		} else {
			posWord = oneChapter.indexOf(word, 0);
		}

		if (posWord == -1) {
			// initial search does not return results. It means the whole chapter does not contain the word.
			return;
		}

		int posN = oneChapter.indexOf(0x0a);

		while (true) {
			if (posN < posWord) {
				verse_0++;
				posN = oneChapter.indexOf(0x0a, posN + 1);
				if (posN == -1) {
					return;
				}
			} else {
				if (verse_0 != lastV) {
					res.add(ariBc + verse_0 + 1); // +1 to make it verse_1
					lastV = verse_0;
				}
				if (hasPlus) {
					posWord = indexOfWholeWord(oneChapter, word, posWord+1);
				} else {
					posWord = oneChapter.indexOf(word, posWord + 1);
				}
				if (posWord == -1) {
					return;
				}
			}
		}
	}<commit_msg>Search optimization: do not advance search by 1 character, but consider the length of the searched word, and then advanced by the length of the word<commit_after>package yuku.alkitab.base.util;

import android.graphics.Typeface;
import android.os.Parcel;
import android.os.Parcelable;
import android.text.SpannableStringBuilder;
import android.text.Spanned;
import android.text.style.ForegroundColorSpan;
import android.text.style.StyleSpan;
import android.util.Log;
import android.util.SparseBooleanArray;
import android.util.TimingLogger;
import yuku.alkitab.base.App;
import yuku.alkitab.base.config.AppConfig;
import yuku.alkitab.debug.BuildConfig;
import yuku.alkitab.model.Book;
import yuku.alkitab.model.SingleChapterVerses;
import yuku.alkitab.model.Version;
import yuku.alkitab.util.Ari;
import yuku.alkitab.util.IntArrayList;
import yuku.bintex.BintexReader;

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.lang.ref.SoftReference;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.Semaphore;

public class SearchEngine {
	public static final String TAG = SearchEngine.class.getSimpleName();

	public static class Query implements Parcelable {
		public String query_string;
		public SparseBooleanArray bookIds;
		
		@Override public int describeContents() {
			return 0;
		}
		
		@Override public void writeToParcel(Parcel dest, int flags) {
			dest.writeString(query_string);
			dest.writeSparseBooleanArray(bookIds);
		}

		public static final Parcelable.Creator<Query> CREATOR = new Parcelable.Creator<Query>() {
			@Override public Query createFromParcel(Parcel in) {
				Query res = new Query();
				res.query_string = in.readString();
				res.bookIds = in.readSparseBooleanArray();
				return res;
			}

			@Override public Query[] newArray(int size) {
				return new Query[size];
			}
		};
	}
	
	static class RevIndex extends HashMap<String, int[]> {
		public RevIndex() {
			super(32768);
		}
	}
	
	private static SoftReference<RevIndex> cache_revIndex;
	private static Semaphore revIndexLoading = new Semaphore(1);
	
	public static IntArrayList searchByGrep(final Version version, final Query query) {
		String[] words = QueryTokenizer.tokenize(query.query_string);
		
		// sort by word length, then alphabetically
		Arrays.sort(words, (object1, object2) -> {
			final int len1 = object1.length();
			final int len2 = object2.length();

			if (len1 > len2) return -1;
			if (len1 == len2) {
				return object1.compareTo(object2);
			}
			return 1;
		});
		
		// remove duplicates
		{
			ArrayList<String> awords = new ArrayList<>();
			String last = null;
			for (String word: words) {
				if (!word.equals(last)) {
					awords.add(word);
				}
				last = word;
			}
			words = awords.toArray(new String[awords.size()]);
			if (BuildConfig.DEBUG) Log.d(TAG, "words = " + Arrays.toString(words));
		}
		
		// really search
		IntArrayList result = null;

		for (final String word : words) {
			final IntArrayList prev = result;

			{
				long ms = System.currentTimeMillis();
				result = searchByGrepInside(version, word, prev, query.bookIds);
				Log.d(TAG, "search word '" + word + "' needed: " + (System.currentTimeMillis() - ms) + " ms");
			}

			if (prev != null) {
				Log.d(TAG, "Will intersect " + prev.size() + " elements with " + result.size() + " elements...");
				result = intersect(prev, result);
				Log.d(TAG, "... the result is " + result.size() + " elements");
			}
		}

		return result;
	}

	private static IntArrayList intersect(IntArrayList a, IntArrayList b) {
		IntArrayList res = new IntArrayList(a.size());
		
		int[] aa = a.buffer();
		int[] bb = b.buffer();
		int alen = a.size();
		int blen = b.size();
		
		int apos = 0;
		int bpos = 0;
		
		while (true) {
			if (apos >= alen) break;
			if (bpos >= blen) break;
			
			int av = aa[apos];
			int bv = bb[bpos];
			
			if (av == bv) {
				res.add(av);
				apos++;
				bpos++;
			} else if (av > bv) {
				bpos++;
			} else { // av < bv
				apos++;
			}
		}
		
		return res;
	}

	/**
	 * Return the next ari (with only book and chapter) after the lastAriBc by scanning the source starting from pos.
	 * @param ppos pointer to pos. pos will be changed to ONE AFTER THE FOUND POSITION. So do not do another increment (++) outside this method.
	 */
	private static int nextAri(IntArrayList source, int[] ppos, int lastAriBc) {
		int[] s = source.buffer();
		int len = source.size();
		int pos = ppos[0];
		
		while (true) {
			if (pos >= len) return 0x0;
			
			int curAri = s[pos];
			int curAriBc = Ari.toBookChapter(curAri);
			
			if (curAriBc != lastAriBc) {
				// found!
				pos++;
				ppos[0] = pos;
				return curAriBc;
			} else {
				// still the same one, move to next.
				pos++;
			}
		}
	}

	static IntArrayList searchByGrepInside(final Version version, String word, final IntArrayList source, final SparseBooleanArray bookIds) {
		final IntArrayList res = new IntArrayList();
		final boolean hasPlus = QueryTokenizer.isPlussedToken(word);

		if (hasPlus) {
			word = QueryTokenizer.tokenWithoutPlus(word);
		}

		if (source == null) {
			for (Book book: version.getConsecutiveBooks()) {
				if (!bookIds.get(book.bookId, false)) {
					continue; // the book is not included in selected books to be searched
				}

				for (int chapter_1 = 1; chapter_1 <= book.chapter_count; chapter_1++) {
					// try to find it wholly in a chapter
					final int ariBc = Ari.encode(book.bookId, chapter_1, 0);
					searchByGrepForOneChapter(version, book, chapter_1, word, hasPlus, ariBc, res);
				}
	
				if (BuildConfig.DEBUG) Log.d(TAG, "searchByGrepInside book " + book.shortName + " done. res.size = " + res.size());
			}
		} else {
			// search only on book-chapters that are in the source
			int count = 0; // for stats
			
			int[] ppos = new int[1];
			int curAriBc = 0x000000;
			
			while (true) {
				curAriBc = nextAri(source, ppos, curAriBc);
				if (curAriBc == 0) break; // no more
				
				// No need to check null book, because we go here only after searching a previous token which is based on
				// getConsecutiveBooks, which is impossible to have null books.
				final Book book = version.getBook(Ari.toBook(curAriBc));
				final int chapter_1 = Ari.toChapter(curAriBc);

				searchByGrepForOneChapter(version, book, chapter_1, word, hasPlus, curAriBc, res);
				
				count++;
			}
			
			if (BuildConfig.DEBUG) Log.d(TAG, "searchByGrepInside book with source " + source.size() + " needed to read as many as " + count + " book-chapter. res.size=" + res.size());
		}
		
		return res;
	}

	/**
	 * @param word searched word without plusses
	 * @param res (output) result aris
	 * @param ariBc book-chapter ari, with verse must be set to 0
	 * @param hasPlus whether the word had plus
	 */
	private static void searchByGrepForOneChapter(final Version version, final Book book, final int chapter_1, final String word, final boolean hasPlus, final int ariBc, final IntArrayList res) {
		// This is a string of one chapter with verses joined by 0x0a ('\n')
		final String oneChapter = version.loadChapterTextLowercasedWithoutSplit(book, chapter_1);
		if (oneChapter == null) {
			return;
		}

		int verse_0 = 0;
		int lastV = -1;

		// Initial search
		int consumedLength;
		String[] multiword = null;
		int posWord;
		if (hasPlus) {
			if (QueryTokenizer.isMultiwordToken(word)) {
				final List<String> tokenList = QueryTokenizer.tokenizeMultiwordToken(word);
				multiword = tokenList.toArray(new String[tokenList.size()]);
			}

			posWord = indexOfWholeWord(oneChapter, word, 0);
			consumedLength = word.length();
		} else {
			posWord = oneChapter.indexOf(word, 0);
			consumedLength = word.length();
		}

		if (posWord == -1) {
			// initial search does not return results. It means the whole chapter does not contain the word.
			return;
		}

		int posN = oneChapter.indexOf(0x0a);

		while (true) {
			if (posN < posWord) {
				verse_0++;
				posN = oneChapter.indexOf(0x0a, posN + 1);
				if (posN == -1) {
					return;
				}
			} else {
				if (verse_0 != lastV) {
					res.add(ariBc + verse_0 + 1); // +1 to make it verse_1
					lastV = verse_0;
				}
				if (hasPlus) {
					posWord = indexOfWholeWord(oneChapter, word, posWord + consumedLength);
					consumedLength = word.length();
				} else {
					posWord = oneChapter.indexOf(word, posWord + consumedLength);
					consumedLength = word.length();
				}
				if (posWord == -1) {
					return;
				}
			}
		}
	}
{'fraction_non_alphanumeric': 0.11970434469082387, 'fraction_numerical': 0.008713418664743705, 'mean_word_length': 3.2540899795501024, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 28, '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': '5324138', 'n_tokens_mistral': 6572, 'n_tokens_neox': 5431, 'n_words': 1580}