/*******************************************************************************
 * Copyright (c) 2000, 2005 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.jdt.internal.core.index;

import java.io.*;

import org.eclipse.jdt.core.search.*;
import org.eclipse.jdt.internal.core.util.*;
import org.eclipse.jdt.internal.compiler.util.HashtableOfIntValues;
import org.eclipse.jdt.internal.compiler.util.HashtableOfObject;
import org.eclipse.jdt.internal.compiler.util.SimpleLookupTable;

public class DiskIndex {

String fileName;

private int headerInfoOffset;
private int numberOfChunks;
private int sizeOfLastChunk;
private int[] chunkOffsets;
private int documentReferenceSize; // 1, 2 or more bytes... depends on # of document names
private int startOfCategoryTables;
private HashtableOfIntValues categoryOffsets;

private int cacheUserCount;
private String[][] cachedChunks; // decompressed chunks of document names
private HashtableOfObject categoryTables; // category name -> HashtableOfObject(words -> int[] of document #'s) or offset if not read yet
private char[] cachedCategoryName;

public static final String SIGNATURE= "INDEX VERSION 1.100"; //$NON-NLS-1$
public static boolean DEBUG = false;

private static final int RE_INDEXED = -1;
private static final int DELETED = -2;

private static final int CHUNK_SIZE = 100;

class IntList {

int size;
int[] elements;

IntList(int[] elements) {
	this.elements = elements;
	this.size = elements.length;
}
void add(int newElement) {
	if (this.size == this.elements.length) {
		int newSize = this.size * 3;
		if (newSize < 7) newSize = 7;
		System.arraycopy(this.elements, 0, this.elements = new int[newSize], 0, this.size);
	}
	this.elements[this.size++] = newElement;
}
int[] asArray() {
	int[] result = new int[this.size];
	System.arraycopy(this.elements, 0, result, 0, this.size);
	return result;
}	
}


DiskIndex(String fileName) {
	this.fileName = fileName;

	// clear cached items
	this.headerInfoOffset = -1;
	this.numberOfChunks = -1;
	this.sizeOfLastChunk = -1;
	this.chunkOffsets = null;
	this.documentReferenceSize = -1;
	this.cacheUserCount = -1;
	this.cachedChunks = null;
	this.categoryTables = null;
	this.cachedCategoryName = null;
	this.categoryOffsets = null;
}
SimpleSet addDocumentNames(String substring, MemoryIndex memoryIndex) throws IOException {
	// must skip over documents which have been added/changed/deleted in the memory index
	String[] docNames = readAllDocumentNames();
	SimpleSet results = new SimpleSet(docNames.length);
	if (substring == null) {
		if (memoryIndex == null) {
			for (int i = 0, l = docNames.length; i < l; i++)
				results.add(docNames[i]);
		} else {
			SimpleLookupTable docsToRefs = memoryIndex.docsToReferences;
			for (int i = 0, l = docNames.length; i < l; i++) {
				String docName = docNames[i];
				if (!docsToRefs.containsKey(docName))
					results.add(docName);
			}
		}
	} else {
		if (memoryIndex == null) {
			for (int i = 0, l = docNames.length; i < l; i++)
				if (docNames[i].startsWith(substring, 0))
					results.add(docNames[i]);
		} else {
			SimpleLookupTable docsToRefs = memoryIndex.docsToReferences;
			for (int i = 0, l = docNames.length; i < l; i++) {
				String docName = docNames[i];
				if (docName.startsWith(substring, 0) && !docsToRefs.containsKey(docName))
					results.add(docName);
			}
		}
	}
	return results;
}
private HashtableOfObject addQueryResult(HashtableOfObject results, char[] word, HashtableOfObject wordsToDocNumbers, MemoryIndex memoryIndex) throws IOException {
	// must skip over documents which have been added/changed/deleted in the memory index
	if (results == null)
		results = new HashtableOfObject(13);
	EntryResult result = (EntryResult) results.get(word);
	if (memoryIndex == null) {
		if (result == null)
			results.put(word, new EntryResult(word, wordsToDocNumbers));
		else
			result.addDocumentTable(wordsToDocNumbers);
	} else {
		SimpleLookupTable docsToRefs = memoryIndex.docsToReferences;
		if (result == null)
			result = new EntryResult(word, null);
		int[] docNumbers = readDocumentNumbers(wordsToDocNumbers.get(word));
		for (int i = 0, l = docNumbers.length; i < l; i++) {
			String docName = readDocumentName(docNumbers[i]);
			if (!docsToRefs.containsKey(docName))
				result.addDocumentName(docName);
		}
		if (!result.isEmpty())
			results.put(word, result);
	}
	return results;
}
HashtableOfObject addQueryResults(char[][] categories, char[] key, int matchRule, MemoryIndex memoryIndex) throws IOException {
	// assumes sender has called startQuery() & will call stopQuery() when finished
	if (this.categoryOffsets == null) return null; // file is empty

	HashtableOfObject results = null; // initialized if needed
	if (key == null) {
		for (int i = 0, l = categories.length; i < l; i++) {
			HashtableOfObject wordsToDocNumbers = readCategoryTable(categories[i], true); // cache if key is null since its a definite match
			if (wordsToDocNumbers != null) {
				char[][] words = wordsToDocNumbers.keyTable;
				if (results == null)
					results = new HashtableOfObject(wordsToDocNumbers.elementSize);
				for (int j = 0, m = words.length; j < m; j++)
					if (words[j] != null)
						results = addQueryResult(results, words[j], wordsToDocNumbers, memoryIndex);
			}
		}
		if (results != null && this.cachedChunks == null)
			cacheDocumentNames();
	} else if (matchRule == SearchPattern.R_EXACT_MATCH + SearchPattern.R_CASE_SENSITIVE) {
		for (int i = 0, l = categories.length; i < l; i++) {
			HashtableOfObject wordsToDocNumbers = readCategoryTable(categories[i], false);
			if (wordsToDocNumbers != null && wordsToDocNumbers.containsKey(key))
				results = addQueryResult(results, key, wordsToDocNumbers, memoryIndex);
		}
	} else {
		for (int i = 0, l = categories.length; i < l; i++) {
			HashtableOfObject wordsToDocNumbers = readCategoryTable(categories[i], false);
			if (wordsToDocNumbers != null) {
				char[][] words = wordsToDocNumbers.keyTable;
				for (int j = 0, m = words.length; j < m; j++) {
					char[] word = words[j];
					if (word != null && Index.isMatch(key, word, matchRule))
						results = addQueryResult(results, word, wordsToDocNumbers, memoryIndex);
				}
			}
		}
	}

	if (results == null) return null;
	return results;
}
private void cacheDocumentNames() throws IOException {
	// will need all document names so get them now
	this.cachedChunks = new String[this.numberOfChunks][];
	DataInputStream stream = new DataInputStream(new BufferedInputStream(new FileInputStream(getIndexFile()), this.numberOfChunks > 5 ? 4096 : 2048));
	try {
		stream.skip(this.chunkOffsets[0]);
		for (int i = 0; i < this.numberOfChunks; i++) {
			int size = i == this.numberOfChunks - 1 ? this.sizeOfLastChunk : CHUNK_SIZE;
			readChunk(this.cachedChunks[i] = new String[size], stream, 0, size);
		}
	} finally {
		stream.close();
	}
}
private String[] computeDocumentNames(String[] onDiskNames, int[] positions, SimpleLookupTable indexedDocuments, MemoryIndex memoryIndex) {
	int onDiskLength = onDiskNames.length;
	Object[] docNames = memoryIndex.docsToReferences.keyTable;
	Object[] referenceTables = memoryIndex.docsToReferences.valueTable;
	if (onDiskLength == 0) {
		// disk index was empty, so add every indexed document
		for (int i = 0, l = referenceTables.length; i < l; i++)
			if (referenceTables[i] != null)
				indexedDocuments.put(docNames[i], null); // remember each new document

		String[] newDocNames = new String[indexedDocuments.elementSize];
		int count = 0;
		Object[] added = indexedDocuments.keyTable;
		for (int i = 0, l = added.length; i < l; i++)
			if (added[i] != null)
				newDocNames[count++] = (String) added[i];
		Util.sort(newDocNames);
		for (int i = 0, l = newDocNames.length; i < l; i++)
			indexedDocuments.put(newDocNames[i], new Integer(i));
		return newDocNames;
	}

	// initialize positions as if each document will remain in the same position
	for (int i = 0; i < onDiskLength; i++)
		positions[i] = i;

	// find out if the memory index has any new or deleted documents, if not then the names & positions are the same
	int numDeletedDocNames = 0;
	int numReindexedDocNames = 0;
	nextPath : for (int i = 0, l = docNames.length; i < l; i++) {
		String docName = (String) docNames[i];
		if (docName != null) {
			for (int j = 0; j < onDiskLength; j++) {
				if (docName.equals(onDiskNames[j])) {
					if (referenceTables[i] == null) {
						positions[j] = DELETED;
						numDeletedDocNames++;
					} else {
						positions[j] = RE_INDEXED;
						numReindexedDocNames++;
					}
					continue nextPath;
				}
			}
			if (referenceTables[i] != null)
				indexedDocuments.put(docName, null); // remember each new document, skip deleted documents which were never saved
		}
	}

	String[] newDocNames = onDiskNames;
	if (numDeletedDocNames > 0 || indexedDocuments.elementSize > 0) {
		// some new documents have been added or some old ones deleted
		newDocNames = new String[onDiskLength + indexedDocuments.elementSize - numDeletedDocNames];
		int count = 0;
		for (int i = 0; i < onDiskLength; i++)
			if (positions[i] >= RE_INDEXED)
				newDocNames[count++] = onDiskNames[i]; // keep each unchanged document
		Object[] added = indexedDocuments.keyTable;
		for (int i = 0, l = added.length; i < l; i++)
			if (added[i] != null)
				newDocNames[count++] = (String) added[i]; // add each new document
		Util.sort(newDocNames);
		for (int i = 0, l = newDocNames.length; i < l; i++)
			if (indexedDocuments.containsKey(newDocNames[i]))
				indexedDocuments.put(newDocNames[i], new Integer(i)); // remember the position for each new document
	}

	// need to be able to look up an old position (ref# from a ref[]) and map it to its new position
	// if its old position == DELETED then its forgotton
	// if its old position == ReINDEXED then its also forgotten but its new position is needed to map references
	int count = -1;
	for (int i = 0; i < onDiskLength;) {
		switch(positions[i]) {
			case DELETED :
				i++; // skip over deleted... references are forgotten
				break;
			case RE_INDEXED :
				String newName = newDocNames[++count];
				if (newName.equals(onDiskNames[i])) {
					indexedDocuments.put(newName, new Integer(count)); // the reindexed docName that was at position i is now at position count
					i++;
				}
				break;
			default :
				if (newDocNames[++count].equals(onDiskNames[i]))
					positions[i++] = count; // the unchanged docName that was at position i is now at position count
		}
	}
	return newDocNames;
}
private void copyQueryResults(HashtableOfObject categoryToWords, int newPosition) {
	char[][] categoryNames = categoryToWords.keyTable;
	Object[] wordSets = categoryToWords.valueTable;
	for (int i = 0, l = categoryNames.length; i < l; i++) {
		char[] categoryName = categoryNames[i];
		if (categoryName != null) {
			SimpleWordSet wordSet = (SimpleWordSet) wordSets[i];
			HashtableOfObject wordsToDocs = (HashtableOfObject) this.categoryTables.get(categoryName);
			if (wordsToDocs == null)
				this.categoryTables.put(categoryName, wordsToDocs = new HashtableOfObject(wordSet.elementSize));

			char[][] words = wordSet.words;
			for (int j = 0, m = words.length; j < m; j++) {
				char[] word = words[j];
				if (word != null) {
					Object o = wordsToDocs.get(word);
					if (o == null) {
						wordsToDocs.put(word, new int[] {newPosition});
					} else if (o instanceof IntList) {
						((IntList) o).add(newPosition);
					} else {
						IntList list = new IntList((int[]) o);
						list.add(newPosition);
						wordsToDocs.put(word, list);
					}
				}
			}
		}
	}
}
File getIndexFile() {
	if (this.fileName == null) return null;

	return new File(this.fileName);
}
void initialize(boolean reuseExistingFile) throws IOException {
	File indexFile = getIndexFile();
	if (indexFile.exists()) {
		if (reuseExistingFile) {
			RandomAccessFile file = new RandomAccessFile(this.fileName, "r"); //$NON-NLS-1$
			try {
				String signature = file.readUTF();
				if (!signature.equals(SIGNATURE))
					throw new IOException(Messages.exception_wrongFormat); 

				this.headerInfoOffset = file.readInt();
				if (this.headerInfoOffset > 0) // file is empty if its not set
					readHeaderInfo(file);
			} finally {
				file.close();
			}
			return;
		}
		if (!indexFile.delete()) {
			if (DEBUG)
				System.out.println("initialize - Failed to delete index " + this.fileName); //$NON-NLS-1$
			throw new IOException("Failed to delete index " + this.fileName); //$NON-NLS-1$
		}
	}
	if (indexFile.createNewFile()) {
		RandomAccessFile file = new RandomAccessFile(this.fileName, "rw"); //$NON-NLS-1$
		try {
			file.writeUTF(SIGNATURE);
			file.writeInt(-1); // file is empty
		} finally {
			file.close();
		}
	} else {
		if (DEBUG)
			System.out.println("initialize - Failed to create new index " + this.fileName); //$NON-NLS-1$
		throw new IOException("Failed to create new index " + this.fileName); //$NON-NLS-1$
	}
}
private void initializeFrom(DiskIndex diskIndex, File newIndexFile) throws IOException {
	if (newIndexFile.exists() && !newIndexFile.delete()) { // delete the temporary index file
		if (DEBUG)
			System.out.println("initializeFrom - Failed to delete temp index " + this.fileName); //$NON-NLS-1$
	} else if (!newIndexFile.createNewFile()) {
		if (DEBUG)
			System.out.println("initializeFrom - Failed to create temp index " + this.fileName); //$NON-NLS-1$
		throw new IOException("Failed to create temp index " + this.fileName); //$NON-NLS-1$
	}

	int size = diskIndex.categoryOffsets == null ? 8 : diskIndex.categoryOffsets.elementSize;
	this.categoryOffsets = new HashtableOfIntValues(size);
	this.categoryTables = new HashtableOfObject(size);
}
private void mergeCategories(DiskIndex onDisk, int[] positions, DataOutputStream stream) throws IOException {
	// at this point, this.categoryTables contains the names -> wordsToDocs added in copyQueryResults()
	char[][] oldNames = onDisk.categoryOffsets.keyTable;
	for (int i = 0, l = oldNames.length; i < l; i++) {
		char[] oldName = oldNames[i];
		if (oldName != null && !this.categoryTables.containsKey(oldName))
			this.categoryTables.put(oldName, null);
	}

	char[][] categoryNames = this.categoryTables.keyTable;
	for (int i = 0, l = categoryNames.length; i < l; i++)
		if (categoryNames[i] != null)
			mergeCategory(categoryNames[i], onDisk, positions, stream);
	this.categoryTables = null;
}
private void mergeCategory(char[] categoryName, DiskIndex onDisk, int[] positions, DataOutputStream stream) throws IOException {
	HashtableOfObject wordsToDocs = (HashtableOfObject) this.categoryTables.get(categoryName);
	if (wordsToDocs == null)
		wordsToDocs = new HashtableOfObject(3);

	HashtableOfObject oldWordsToDocs = onDisk.readCategoryTable(categoryName, true);
	if (oldWordsToDocs != null) {
		char[][] oldWords = oldWordsToDocs.keyTable;
		Object[] oldArrayOffsets = oldWordsToDocs.valueTable;
		nextWord: for (int i = 0, l = oldWords.length; i < l; i++) {
			char[] oldWord = oldWords[i];
			if (oldWord != null) {
				int[] oldDocNumbers = (int[]) oldArrayOffsets[i];
				int length = oldDocNumbers.length;
				int[] mappedNumbers = new int[length];
				int count = 0;
				for (int j = 0; j < length; j++) {
					int pos = positions[oldDocNumbers[j]];
					if (pos > RE_INDEXED) // forget any reference to a document which was deleted or re_indexed
						mappedNumbers[count++] = pos;
				}
				if (count < length) {
					if (count == 0) continue nextWord; // skip words which no longer have any references
					System.arraycopy(mappedNumbers, 0, mappedNumbers = new int[count], 0, count);
				}

				Object o = wordsToDocs.get(oldWord);
				if (o == null) {
					wordsToDocs.put(oldWord, mappedNumbers);
				} else {
					IntList list = null;
					if (o instanceof IntList) {
						list = (IntList) o;
					} else {
						list = new IntList((int[]) o);
						wordsToDocs.put(oldWord, list);
					}
					for (int j = 0; j < count; j++)
						list.add(mappedNumbers[j]);
				}
			}
		}
		onDisk.categoryTables.put(categoryName, null); // flush cached table
	}
	writeCategoryTable(categoryName, wordsToDocs, stream);
}
DiskIndex mergeWith(MemoryIndex memoryIndex) throws IOException {
 	// assume write lock is held
	// compute & write out new docNames
	String[] docNames = readAllDocumentNames();
	int previousLength = docNames.length;
	int[] positions = new int[previousLength]; // keeps track of the position of each document in the new sorted docNames
	SimpleLookupTable indexedDocuments = new SimpleLookupTable(3); // for each new/changed document in the memoryIndex
	docNames = computeDocumentNames(docNames, positions, indexedDocuments, memoryIndex);
	if (docNames.length == 0) {
		if (previousLength == 0) return this; // nothing to do... memory index contained deleted documents that had never been saved

		// index is now empty since all the saved documents were removed
		DiskIndex newDiskIndex = new DiskIndex(this.fileName);
		newDiskIndex.initialize(false);
		return newDiskIndex;
	}

	DiskIndex newDiskIndex = new DiskIndex(this.fileName + ".tmp"); //$NON-NLS-1$
	File newIndexFile = newDiskIndex.getIndexFile();
	try {
		newDiskIndex.initializeFrom(this, newIndexFile);
		DataOutputStream stream = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(newIndexFile, false), 2048));
		int offsetToHeader = -1;
		try {
			newDiskIndex.writeAllDocumentNames(docNames, stream);
			docNames = null; // free up the space

			// add each new/changed doc to empty category tables using its new position #
			if (indexedDocuments.elementSize > 0) {
				Object[] names = indexedDocuments.keyTable;
				Object[] integerPositions = indexedDocuments.valueTable;
				for (int i = 0, l = names.length; i < l; i++)
					if (names[i] != null)
						newDiskIndex.copyQueryResults(
							(HashtableOfObject) memoryIndex.docsToReferences.get(names[i]),
							((Integer) integerPositions[i]).intValue());
			}
			indexedDocuments = null; // free up the space

			// merge each category table with the new ones & write them out
			if (previousLength == 0)
				newDiskIndex.writeCategories(stream);
			else
				newDiskIndex.mergeCategories(this, positions, stream);
			offsetToHeader = stream.size();
			newDiskIndex.writeHeaderInfo(stream);
			positions = null; // free up the space
		} finally {
			stream.close();
		}
		newDiskIndex.writeOffsetToHeader(offsetToHeader);

		// rename file by deleting previous index file & renaming temp one
		File old = getIndexFile();
		if (!old.delete()) {
			if (DEBUG)
				System.out.println("mergeWith - Failed to delete " + this.fileName); //$NON-NLS-1$
			throw new IOException("Failed to delete index file " + this.fileName); //$NON-NLS-1$
		}
		if (!newIndexFile.renameTo(old)) {
			if (DEBUG)
				System.out.println("mergeWith - Failed to rename " + this.fileName); //$NON-NLS-1$
			throw new IOException("Failed to rename index file " + this.fileName); //$NON-NLS-1$
		}
	} catch (IOException e) {
		if (newIndexFile.exists() && !newIndexFile.delete())
			if (DEBUG)
				System.out.println("mergeWith - Failed to delete temp index " + newDiskIndex.fileName); //$NON-NLS-1$
		throw e;
	}

	newDiskIndex.fileName = this.fileName;
	return newDiskIndex;
}
private synchronized String[] readAllDocumentNames() throws IOException {
	if (this.numberOfChunks <= 0)
		return new String[0];

	DataInputStream stream = new DataInputStream(new BufferedInputStream(new FileInputStream(getIndexFile()), this.numberOfChunks > 5 ? 4096 : 2048));
	try {
		stream.skip(this.chunkOffsets[0]);
		int lastIndex = this.numberOfChunks - 1;
		String[] docNames = new String[lastIndex * CHUNK_SIZE + sizeOfLastChunk];
		for (int i = 0; i < this.numberOfChunks; i++)
			readChunk(docNames, stream, i * CHUNK_SIZE, i < lastIndex ? CHUNK_SIZE : sizeOfLastChunk);
		return docNames;
	} finally {
		stream.close();
	}
}
private synchronized HashtableOfObject readCategoryTable(char[] categoryName, boolean readDocNumbers) throws IOException {
	// result will be null if categoryName is unknown
	int offset = this.categoryOffsets.get(categoryName);
	if (offset == HashtableOfIntValues.NO_VALUE)
		return null;

	if (this.categoryTables == null) {
		this.categoryTables = new HashtableOfObject(3);
	} else {
		HashtableOfObject cachedTable = (HashtableOfObject) this.categoryTables.get(categoryName);
		if (cachedTable != null) {
			if (readDocNumbers) { // must cache remaining document number arrays
				Object[] arrayOffsets = cachedTable.valueTable;
				for (int i = 0, l = arrayOffsets.length; i < l; i++)
					if (arrayOffsets[i] instanceof Integer)
						arrayOffsets[i] = readDocumentNumbers(arrayOffsets[i]);
			}
			return cachedTable;
		}
	}

	DataInputStream stream = new DataInputStream(new BufferedInputStream(new FileInputStream(getIndexFile()), 2048));
	HashtableOfObject categoryTable = null;
	char[][] matchingWords = null;
	int count = 0;
	int firstOffset = -1;
	try {
		stream.skip(offset);
		int size = stream.readInt();
		categoryTable = new HashtableOfObject(size);
		int largeArraySize = 256;
		for (int i = 0; i < size; i++) {
			char[] word = Util.readUTF(stream);
			int arrayOffset = stream.readInt();
			// if arrayOffset is:
			//		<= 0 then the array size == 1 with the value -> -arrayOffset
			//		> 1 & < 256 then the size of the array is > 1 & < 256, the document array follows immediately
			//		256 if the array size >= 256 followed by another int which is the offset to the array (written prior to the table)
			if (arrayOffset <= 0) {
				categoryTable.put(word, new int[] {-arrayOffset}); // store 1 element array by negating documentNumber
			} else if (arrayOffset < largeArraySize) {
				categoryTable.put(word, readDocumentArray(stream, arrayOffset)); // read in-lined array providing size
			} else {
				arrayOffset = stream.readInt(); // read actual offset
				if (readDocNumbers) {
					if (matchingWords == null)
						matchingWords = new char[size][];
					if (count == 0)
						firstOffset = arrayOffset;
					matchingWords[count++] = word;
				}
				categoryTable.put(word, new Integer(arrayOffset)); // offset to array in the file
			}
		}
		this.categoryTables.put(categoryName, categoryTable);
		// cache the table as long as its not too big
		// in practise, some tables can be greater than 500K when the contain more than 10K elements
		this.cachedCategoryName = categoryTable.elementSize < 10000 ? categoryName : null;
	} finally {
		stream.close();
	}

	if (count > 0) {
		stream = new DataInputStream(new BufferedInputStream(new FileInputStream(getIndexFile()), 2048));
		try {
			stream.skip(firstOffset);
			for (int i = 0; i < count; i++) // each array follows the previous one
				categoryTable.put(matchingWords[i], readDocumentArray(stream, stream.readInt()));
		} finally {
			stream.close();
		}
	}
	return categoryTable;
}
private void readChunk(String[] docNames, DataInputStream stream, int index, int size) throws IOException {
	String current = stream.readUTF();
	docNames[index++] = current;
	for (int i = 1; i < size; i++) {
		int start = stream.readUnsignedByte(); // number of identical characters at the beginning
		int end = stream.readUnsignedByte(); // number of identical characters at the end
		String next = stream.readUTF();
		if (start > 0) {
			if (end > 0) {
				int length = current.length();
				next = current.substring(0, start) + next + current.substring(length - end, length);
			} else {
				next = current.substring(0, start) + next;
			}
		} else if (end > 0) {
			int length = current.length();
			next = next + current.substring(length - end, length);
		}
		docNames[index++] = next;
		current = next;
	}
}
private int[] readDocumentArray(DataInputStream stream, int arraySize) throws IOException {
	int[] result = new int[arraySize];
	switch (this.documentReferenceSize) {
		case 1 :
			for (int i = 0; i < arraySize; i++)
				result[i] = stream.readUnsignedByte();
			break;
		case 2 :
			for (int i = 0; i < arraySize; i++)
				result[i] = stream.readUnsignedShort();
			break;
		default :
			for (int i = 0; i < arraySize; i++)
				result[i] = stream.readInt();
			break;
	}
	return result;
}
synchronized String readDocumentName(int docNumber) throws IOException {
	if (this.cachedChunks == null)
		this.cachedChunks = new String[this.numberOfChunks][];

	int chunkNumber = docNumber / CHUNK_SIZE;
	String[] chunk = this.cachedChunks[chunkNumber];
	if (chunk == null) {
		boolean isLastChunk = chunkNumber == this.numberOfChunks - 1;
		int start = this.chunkOffsets[chunkNumber];
		int numberOfBytes = (isLastChunk ? this.startOfCategoryTables : this.chunkOffsets[chunkNumber + 1]) - start;
		if (numberOfBytes < 0)
			throw new IllegalArgumentException();
		byte[] bytes = new byte[numberOfBytes];
		FileInputStream file = new FileInputStream(getIndexFile());
		try {
			file.skip(start);
			if (file.read(bytes, 0, numberOfBytes) != numberOfBytes)
				throw new IOException();
		} finally {
			file.close();
		}
		DataInputStream stream = new DataInputStream(new ByteArrayInputStream(bytes));
		int numberOfNames = isLastChunk ? this.sizeOfLastChunk : CHUNK_SIZE;
		chunk = this.cachedChunks[chunkNumber] = new String[numberOfNames];
		readChunk(chunk, stream, 0, numberOfNames);
	}
	return chunk[docNumber - (chunkNumber * CHUNK_SIZE)];
}
synchronized int[] readDocumentNumbers(Object arrayOffset) throws IOException {
	// arrayOffset is either a cached array of docNumbers or an Integer offset in the file
	if (arrayOffset instanceof int[])
		return (int[]) arrayOffset;

	DataInputStream stream = new DataInputStream(new BufferedInputStream(new FileInputStream(getIndexFile()), 2048));
	try {
		stream.skip(((Integer) arrayOffset).intValue());
		return readDocumentArray(stream, stream.readInt());
	} finally {
		stream.close();
	}
}
private void readHeaderInfo(RandomAccessFile file) throws IOException {
	file.seek(this.headerInfoOffset);

	// must be same order as writeHeaderInfo()
	this.numberOfChunks = file.readInt();
	this.sizeOfLastChunk = file.readUnsignedByte();
	this.documentReferenceSize = file.readUnsignedByte();

	this.chunkOffsets = new int[this.numberOfChunks];
	for (int i = 0; i < this.numberOfChunks; i++)
		this.chunkOffsets[i] = file.readInt();

	this.startOfCategoryTables = file.readInt();

	int size = file.readInt();
	this.categoryOffsets = new HashtableOfIntValues(size);
	for (int i = 0; i < size; i++)
		this.categoryOffsets.put(Util.readUTF(file), file.readInt()); // cache offset to category table
	this.categoryTables = new HashtableOfObject(3);
}
synchronized void startQuery() {
	this.cacheUserCount++;
}
synchronized void stopQuery() {
	if (--this.cacheUserCount < 0) {
		// clear cached items
		this.cacheUserCount = -1;
		this.cachedChunks = null;
		if (this.categoryTables != null) {
			if (this.cachedCategoryName == null) {
				this.categoryTables = null;
			} else if (this.categoryTables.elementSize > 1) {
				HashtableOfObject newTables = new HashtableOfObject(3);
				newTables.put(this.cachedCategoryName, this.categoryTables.get(this.cachedCategoryName));
				this.categoryTables = newTables;
			}
		}
	}
}
private void writeAllDocumentNames(String[] sortedDocNames, DataOutputStream stream) throws IOException {
	if (sortedDocNames.length == 0)
		throw new IllegalArgumentException();

	// assume the file was just created by initializeFrom()
	// in order, write: SIGNATURE & headerInfoOffset place holder, then each compressed chunk of document names
	stream.writeUTF(SIGNATURE);
	this.headerInfoOffset = stream.size();
	stream.writeInt(-1); // will overwrite with correct value later

	int size = sortedDocNames.length;
	this.numberOfChunks = (size / CHUNK_SIZE) + 1;
	this.sizeOfLastChunk = size % CHUNK_SIZE;
	if (this.sizeOfLastChunk == 0) {
		this.numberOfChunks--;
		this.sizeOfLastChunk = CHUNK_SIZE;
	}
	this.documentReferenceSize = size <= 0x7F ? 1 : (size <= 0x7FFF ? 2 : 4); // number of bytes used to encode a reference

	this.chunkOffsets = new int[this.numberOfChunks];
	int lastIndex = this.numberOfChunks - 1;
	for (int i = 0; i < this.numberOfChunks; i++) {
		this.chunkOffsets[i] = stream.size();

		int chunkSize = i == lastIndex ? this.sizeOfLastChunk : CHUNK_SIZE;
		int chunkIndex = i * CHUNK_SIZE;
		String current = sortedDocNames[chunkIndex];
		stream.writeUTF(current);
		for (int j = 1; j < chunkSize; j++) {
			String next = sortedDocNames[chunkIndex + j];
			int len1 = current.length();
			int len2 = next.length();
			int max = len1 < len2 ? len1 : len2;
			int start = 0; // number of identical characters at the beginning (also the index of first character that is different)
			while (current.charAt(start) == next.charAt(start)) {
				start++;
				if (max == start) break; // current is 'abba', next is 'abbab'
			}
			if (start > 255) start = 255;

			int end = 0; // number of identical characters at the end
			while (current.charAt(--len1) == next.charAt(--len2)) {
				end++;
				if (len2 == start) break; // current is 'abbba', next is 'abba'
				if (len1 == 0) break; // current is 'xabc', next is 'xyabc'
			}
			if (end > 255) end = 255;
			stream.writeByte(start);
			stream.writeByte(end);

			int last = next.length() - end;
			stream.writeUTF(start < last ? next.substring(start, last) : ""); //$NON-NLS-1$
			current = next;
		}
	}
	this.startOfCategoryTables = stream.size() + 1;
}
private void writeCategories(DataOutputStream stream) throws IOException {
	char[][] categoryNames = this.categoryTables.keyTable;
	Object[] tables = this.categoryTables.valueTable;
	for (int i = 0, l = categoryNames.length; i < l; i++)
		if (categoryNames[i] != null)
			writeCategoryTable(categoryNames[i], (HashtableOfObject) tables[i], stream);
	this.categoryTables = null;
}
private void writeCategoryTable(char[] categoryName, HashtableOfObject wordsToDocs, DataOutputStream stream) throws IOException {
	// the format of a category table is as follows:
	// any document number arrays with >= 256 elements are written before the table (the offset to each array is remembered)
	// then the number of word->int[] pairs in the table is written
	// for each word -> int[] pair, the word is written followed by:
	//		an int <= 0 if the array size == 1
	//		an int > 1 & < 256 for the size of the array if its > 1 & < 256, the document array follows immediately
	//		256 if the array size >= 256 followed by another int which is the offset to the array (written prior to the table)

	int largeArraySize = 256;
	Object[] values = wordsToDocs.valueTable;
	for (int i = 0, l = values.length; i < l; i++) {
		Object o = values[i];
		if (o != null) {
			if (o instanceof IntList)
				o = values[i] = ((IntList) values[i]).asArray();
			int[] documentNumbers = (int[]) o;
			if (documentNumbers.length >= largeArraySize) {
				values[i] = new Integer(stream.size());
				writeDocumentNumbers(documentNumbers, stream);
			}
		}
	}

	this.categoryOffsets.put(categoryName, stream.size()); // remember the offset to the start of the table
	this.categoryTables.put(categoryName, null); // flush cached table
	stream.writeInt(wordsToDocs.elementSize);
	char[][] words = wordsToDocs.keyTable;
	for (int i = 0, l = words.length; i < l; i++) {
		Object o = values[i];
		if (o != null) {
			Util.writeUTF(stream, words[i]);
			if (o instanceof int[]) {
				int[] documentNumbers = (int[]) o;
				if (documentNumbers.length == 1)
					stream.writeInt(-documentNumbers[0]); // store an array of 1 element by negating the documentNumber (can be zero)
				else
					writeDocumentNumbers(documentNumbers, stream);
			} else {
				stream.writeInt(largeArraySize); // mark to identify that an offset follows
				stream.writeInt(((Integer) o).intValue()); // offset in the file of the array of document numbers
			}
		}
	}
}
private void writeDocumentNumbers(int[] documentNumbers, DataOutputStream stream) throws IOException {
	// must store length as a positive int to detect in-lined array of 1 element
	int length = documentNumbers.length;
	stream.writeInt(length);
	Util.sort(documentNumbers);
	switch (this.documentReferenceSize) {
		case 1 :
			for (int i = 0; i < length; i++)
				stream.writeByte(documentNumbers[i]);
			break;
		case 2 :
			for (int i = 0; i < length; i++)
				stream.writeShort(documentNumbers[i]);
			break;
		default :
			for (int i = 0; i < length; i++)
				stream.writeInt(documentNumbers[i]);
			break;
	}
}
private void writeHeaderInfo(DataOutputStream stream) throws IOException {
	stream.writeInt(this.numberOfChunks);
	stream.writeByte(this.sizeOfLastChunk);
	stream.writeByte(this.documentReferenceSize);

	// apend the file with chunk offsets
	for (int i = 0; i < this.numberOfChunks; i++)
		stream.writeInt(this.chunkOffsets[i]);

	stream.writeInt(this.startOfCategoryTables);

	// append the file with the category offsets... # of name -> offset pairs, followed by each name & an offset to its word->doc# table
	stream.writeInt(this.categoryOffsets.elementSize);
	char[][] categoryNames = this.categoryOffsets.keyTable;
	int[] offsets = this.categoryOffsets.valueTable;
	for (int i = 0, l = categoryNames.length; i < l; i++) {
		if (categoryNames[i] != null) {
			Util.writeUTF(stream, categoryNames[i]);
			stream.writeInt(offsets[i]);
		}
	}
}
private void writeOffsetToHeader(int offsetToHeader) throws IOException {
	if (offsetToHeader > 0) {
		RandomAccessFile file = new RandomAccessFile(this.fileName, "rw"); //$NON-NLS-1$
		try {
			file.seek(this.headerInfoOffset); // offset to position in header
			file.writeInt(offsetToHeader);
			this.headerInfoOffset = offsetToHeader; // update to reflect the correct offset
		} finally {
			file.close();
		}
	}
}
}