[Rubyeclipse-commit] SF.net SVN: rubyeclipse: [2291] trunk/org.rubypeople.rdt.core/src/org/ rubypeople/rdt

[<caw...@us...>]

Revision: 2291
          http://svn.sourceforge.net/rubyeclipse/?rev=2291&view=rev
Author:   cawilliams
Date:     2007-04-06 07:22:22 -0700 (Fri, 06 Apr 2007)

Log Message:
-----------


Modified Paths:
--------------
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/util/CharOperation.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/util/Messages.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/util/Util.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/util/messages.properties

Added Paths:
-----------
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/search/SearchPattern.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/parser/
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/parser/ScannerHelper.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/DiskIndex.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/EntryResult.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/Index.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/MemoryIndex.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/search/BasicSearchEngine.java

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/search/SearchPattern.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/search/SearchPattern.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/search/SearchPattern.java	2007-04-06 14:22:22 UTC (rev 2291)
@@ -0,0 +1,132 @@
+package org.rubypeople.rdt.core.search;
+
+import org.rubypeople.rdt.internal.core.util.CharOperation;
+
+public class SearchPattern {
+//	 Rules for pattern matching: (exact, prefix, pattern) [ | case sensitive]
+	/**
+	 * Match rule: The search pattern matches exactly the search result,
+	 * that is, the source of the search result equals the search pattern.
+	 */
+	public static final int R_EXACT_MATCH = 0;
+
+	/**
+	 * Match rule: The search pattern is a prefix of the search result.
+	 */
+	public static final int R_PREFIX_MATCH = 0x0001;
+
+	/**
+	 * Match rule: The search pattern contains one or more wild cards ('*' or '?'). 
+	 * A '*' wild-card can replace 0 or more characters in the search result.
+	 * A '?' wild-card replaces exactly 1 character in the search result.
+	 */
+	public static final int R_PATTERN_MATCH = 0x0002;
+
+	/**
+	 * Match rule: The search pattern contains a regular expression.
+	 */
+	public static final int R_REGEXP_MATCH = 0x0004;
+
+	/**
+	 * Match rule: The search pattern matches the search result only if cases are the same.
+	 * Can be combined to previous rules, e.g. {@link #R_EXACT_MATCH} | {@link #R_CASE_SENSITIVE}
+	 */
+	public static final int R_CASE_SENSITIVE = 0x0008;
+
+	/**
+	 * Match rule: The search pattern matches search results as raw/parameterized types/methods with same erasure.
+	 * This mode has no effect on other java elements search.<br>
+	 * Type search example:
+	 * 	<ul>
+	 * 	<li>pattern: <code>List&lt;Exception&gt;</code></li>
+	 * 	<li>match: <code>List&lt;Object&gt;</code></li>
+	 * 	</ul>
+	 * Method search example:
+	 * 	<ul>
+	 * 	<li>declaration: <code>&lt;T&gt;foo(T t)</code></li>
+	 * 	<li>pattern: <code>&lt;Exception&gt;foo(new Exception())</code></li>
+	 * 	<li>match: <code>&lt;Object&gt;foo(new Object())</code></li>
+	 * 	</ul>
+	 * Can be combined to all other match rules, e.g. {@link #R_CASE_SENSITIVE} | {@link #R_ERASURE_MATCH}
+	 * This rule is not activated by default, so raw types or parameterized types with same erasure will not be found
+	 * for pattern List&lt;String&gt;,
+	 * Note that with this pattern, the match selection will be only on the erasure even for parameterized types.
+	 * @since 3.1
+	 */
+	public static final int R_ERASURE_MATCH = 0x0010;
+
+	/**
+	 * Match rule: The search pattern matches search results as raw/parameterized types/methods with equivalent type parameters.
+	 * This mode has no effect on other java elements search.<br>
+	 * Type search example:
+	 * <ul>
+	 * 	<li>pattern: <code>List&lt;Exception&gt;</code></li>
+	 * 	<li>match:
+	 * 		<ul>
+	 * 		<li><code>List&lt;? extends Throwable&gt;</code></li>
+	 * 		<li><code>List&lt;? super RuntimeException&gt;</code></li>
+	 * 		<li><code>List&lt;?&gt;</code></li>
+	 *			</ul>
+	 * 	</li>
+	 * 	</ul>
+	 * Method search example:
+	 * 	<ul>
+	 * 	<li>declaration: <code>&lt;T&gt;foo(T t)</code></li>
+	 * 	<li>pattern: <code>&lt;Exception&gt;foo(new Exception())</code></li>
+	 * 	<li>match:
+	 * 		<ul>
+	 * 		<li><code>&lt;? extends Throwable&gt;foo(new Exception())</code></li>
+	 * 		<li><code>&lt;? super RuntimeException&gt;foo(new Exception())</code></li>
+	 * 		<li><code>foo(new Exception())</code></li>
+	 *			</ul>
+	 * 	</ul>
+	 * Can be combined to all other match rules, e.g. {@link #R_CASE_SENSITIVE} | {@link #R_EQUIVALENT_MATCH}
+	 * This rule is not activated by default, so raw types or equivalent parameterized types will not be found
+	 * for pattern List&lt;String&gt;,
+	 * This mode is overridden by {@link  #R_ERASURE_MATCH} as erasure matches obviously include equivalent ones.
+	 * That means that pattern with rule set to {@link #R_EQUIVALENT_MATCH} | {@link  #R_ERASURE_MATCH}
+	 * will return same results than rule only set with {@link  #R_ERASURE_MATCH}.
+	 * @since 3.1
+	 */
+	public static final int R_EQUIVALENT_MATCH = 0x0020;
+
+	/**
+	 * Match rule: The search pattern matches exactly the search result,
+	 * that is, the source of the search result equals the search pattern.
+	 * @since 3.1
+	 */
+	public static final int R_FULL_MATCH = 0x0040;
+
+	/**
+	 * Match rule: The search pattern contains a Camel Case expression.
+	 * <br>
+	 * Examples:
+	 * <ul>
+	 * 	<li><code>NPE</code> type string pattern will match
+	 * 		<code>NullPointerException</code> and <code>NpPermissionException</code> types,</li>
+	 * 	<li><code>NuPoEx</code> type string pattern will only match
+	 * 		<code>NullPointerException</code> type.</li>
+	 * </ul>
+	 * @see CharOperation#camelCaseMatch(char[], char[]) for a detailed explanation
+	 * of Camel Case matching.
+	 *<br>
+	 * Can be combined to {@link #R_PREFIX_MATCH} match rule. For example,
+	 * when prefix match rule is combined with Camel Case match rule,
+	 * <code>"nPE"</code> pattern will match <code>nPException</code>.
+	 *<br>
+	 * Match rule {@link #R_PATTERN_MATCH} may also be combined but both rules
+	 * will not be used simultaneously as they are mutually exclusive.
+	 * Used match rule depends on whether string pattern contains specific pattern 
+	 * characters (e.g. '*' or '?') or not. If it does, then only Pattern match rule
+	 * will be used, otherwise only Camel Case match will be used.
+	 * For example, with <code>"NPE"</code> string pattern, search will only use
+	 * Camel Case match rule, but with <code>N*P*E*</code> string pattern, it will 
+	 * use only Pattern match rule.
+	 * 
+	 * @since 3.2
+	 */
+	public static final int R_CAMELCASE_MATCH = 0x0080;
+
+	private static final int MODE_MASK = R_EXACT_MATCH | R_PREFIX_MATCH | R_PATTERN_MATCH | R_REGEXP_MATCH;
+
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/parser/ScannerHelper.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/parser/ScannerHelper.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/parser/ScannerHelper.java	2007-04-06 14:22:22 UTC (rev 2291)
@@ -0,0 +1,105 @@
+package org.rubypeople.rdt.internal.compiler.parser;
+
+
+
+public class ScannerHelper {
+	public final static int MAX_OBVIOUS = 128;
+	public final static int[] OBVIOUS_IDENT_CHAR_NATURES = new int[MAX_OBVIOUS];
+
+	public final static int C_JLS_SPACE = 0x100;
+	public final static int C_SPECIAL = 0x80;
+	public final static int C_IDENT_START = 0x40;
+	public final static int C_UPPER_LETTER = 0x20;
+	public final static int C_LOWER_LETTER = 0x10;
+	public final static int C_IDENT_PART = 0x8;
+	public final static int C_DIGIT = 0x4;
+	public final static int C_SEPARATOR = 0x2;
+	public final static int C_SPACE = 0x1;
+
+	static {
+		OBVIOUS_IDENT_CHAR_NATURES[0] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[1] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[2] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[3] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[4] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[5] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[6] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[7] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[8] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[14] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[15] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[16] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[17] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[18] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[19] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[20] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[21] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[22] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[23] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[24] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[25] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[26] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[27] = C_IDENT_PART;
+		OBVIOUS_IDENT_CHAR_NATURES[127] = C_IDENT_PART;
+		
+		for (int i = '0'; i <= '9'; i++) 
+			OBVIOUS_IDENT_CHAR_NATURES[i] = C_DIGIT | C_IDENT_PART;
+		
+		for (int i = 'a'; i <= 'z'; i++) 
+			OBVIOUS_IDENT_CHAR_NATURES[i] = C_LOWER_LETTER | C_IDENT_PART | C_IDENT_START;
+		for (int i = 'A'; i <= 'Z'; i++) 
+			OBVIOUS_IDENT_CHAR_NATURES[i] = C_UPPER_LETTER | C_IDENT_PART | C_IDENT_START;
+
+		OBVIOUS_IDENT_CHAR_NATURES['_'] = C_SPECIAL | C_IDENT_PART | C_IDENT_START;
+		OBVIOUS_IDENT_CHAR_NATURES['$'] = C_SPECIAL | C_IDENT_PART | C_IDENT_START;
+		
+		OBVIOUS_IDENT_CHAR_NATURES[9] = C_SPACE | C_JLS_SPACE; // \ u0009: HORIZONTAL TABULATION
+		OBVIOUS_IDENT_CHAR_NATURES[10] = C_SPACE | C_JLS_SPACE; // \ u000a: LINE FEED
+		OBVIOUS_IDENT_CHAR_NATURES[11] = C_SPACE;
+		OBVIOUS_IDENT_CHAR_NATURES[12] = C_SPACE | C_JLS_SPACE; // \ u000c: FORM FEED
+		OBVIOUS_IDENT_CHAR_NATURES[13] = C_SPACE | C_JLS_SPACE; //  \ u000d: CARRIAGE RETURN
+		OBVIOUS_IDENT_CHAR_NATURES[28] = C_SPACE;
+		OBVIOUS_IDENT_CHAR_NATURES[29] = C_SPACE;
+		OBVIOUS_IDENT_CHAR_NATURES[30] = C_SPACE;
+		OBVIOUS_IDENT_CHAR_NATURES[31] = C_SPACE;
+		OBVIOUS_IDENT_CHAR_NATURES[32] = C_SPACE | C_JLS_SPACE; //  \ u0020: SPACE
+		
+		OBVIOUS_IDENT_CHAR_NATURES['.'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES[':'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES[';'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES[','] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['['] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES[']'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['('] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES[')'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['{'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['}'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['+'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['-'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['*'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['/'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['='] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['&'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['|'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['?'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['<'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['>'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['!'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['%'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['^'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['~'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['"'] = C_SEPARATOR;
+		OBVIOUS_IDENT_CHAR_NATURES['\''] = C_SEPARATOR;
+	}
+
+	public static char toLowerCase(char c) {
+	if (c < MAX_OBVIOUS) {
+		if ((ScannerHelper.OBVIOUS_IDENT_CHAR_NATURES[c] & ScannerHelper.C_LOWER_LETTER) != 0) {
+			return c;
+		} else if ((ScannerHelper.OBVIOUS_IDENT_CHAR_NATURES[c] & ScannerHelper.C_UPPER_LETTER) != 0) {
+			return (char) (32 + c); 
+		}
+	}
+	return Character.toLowerCase(c);
+}
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/DiskIndex.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/DiskIndex.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/DiskIndex.java	2007-04-06 14:22:22 UTC (rev 2291)
@@ -0,0 +1,933 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 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.rubypeople.rdt.internal.core.index;
+
+import java.io.BufferedInputStream;
+import java.io.BufferedOutputStream;
+import java.io.ByteArrayInputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+
+import org.rubypeople.rdt.core.search.SearchPattern;
+import org.rubypeople.rdt.internal.compiler.util.HashtableOfIntValues;
+import org.rubypeople.rdt.internal.compiler.util.HashtableOfObject;
+import org.rubypeople.rdt.internal.compiler.util.SimpleLookupTable;
+import org.rubypeople.rdt.internal.compiler.util.SimpleSet;
+import org.rubypeople.rdt.internal.core.util.CharOperation;
+import org.rubypeople.rdt.internal.core.util.Messages;
+import org.rubypeople.rdt.internal.core.util.SimpleWordSet;
+import org.rubypeople.rdt.internal.core.util.Util;
+
+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.115"; //$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 {
+		switch (matchRule) {
+			case 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);
+				}
+				break;
+			case SearchPattern.R_PREFIX_MATCH | SearchPattern.R_CASE_SENSITIVE:
+				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 && key[0] == word[0] && CharOperation.prefixEquals(key, word))
+								results = addQueryResult(results, word, wordsToDocNumbers, memoryIndex);
+						}
+					}
+				}
+				break;
+			default:
+				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.exists() && !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();
+		try {
+			if (size < 0) { // DEBUG
+				System.err.println("-------------------- DEBUG --------------------"); //$NON-NLS-1$
+				System.err.println("file = "+getIndexFile()); //$NON-NLS-1$
+				System.err.println("offset = "+offset); //$NON-NLS-1$
+				System.err.println("size = "+size); //$NON-NLS-1$
+				System.err.println("--------------------   END   --------------------"); //$NON-NLS-1$
+			}
+			categoryTable = new HashtableOfObject(size);
+		} catch (OutOfMemoryError oom) {
+			// DEBUG
+			oom.printStackTrace();
+			System.err.println("-------------------- DEBUG --------------------"); //$NON-NLS-1$
+			System.err.println("file = "+getIndexFile()); //$NON-NLS-1$
+			System.err.println("offset = "+offset); //$NON-NLS-1$
+			System.err.println("size = "+size); //$NON-NLS-1$
+			System.err.println("--------------------   END   --------------------"); //$NON-NLS-1$
+			throw oom;
+		}
+		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 (matchingWords != null && 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();
+		}
+	}
+}
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/EntryResult.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/EntryResult.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/EntryResult.java	2007-04-06 14:22:22 UTC (rev 2291)
@@ -0,0 +1,78 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 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.rubypeople.rdt.internal.core.index;
+
+import org.rubypeople.rdt.internal.compiler.util.HashtableOfObject;
+import org.rubypeople.rdt.internal.compiler.util.SimpleSet;
+
+public class EntryResult {
+
+private char[] word;
+private HashtableOfObject[] documentTables;
+private SimpleSet documentNames;
+
+public EntryResult(char[] word, HashtableOfObject table) {
+	this.word = word;
+	if (table != null)
+		this.documentTables = new HashtableOfObject[] {table};
+}
+public void addDocumentName(String documentName) {
+	if (this.documentNames == null)
+		this.documentNames = new SimpleSet(3);
+	this.documentNames.add(documentName);
+}
+public void addDocumentTable(HashtableOfObject table) {
+	if (this.documentTables != null) {
+		int length = this.documentTables.length;
+		System.arraycopy(this.documentTables, 0, this.documentTables = new HashtableOfObject[length + 1], 0, length);
+		this.documentTables[length] = table;
+	} else {
+		this.documentTables = new HashtableOfObject[] {table};
+	}
+}
+public char[] getWord() {
+	return this.word;
+}
+public String[] getDocumentNames(Index index) throws java.io.IOException {
+	if (this.documentTables != null) {
+		int length = this.documentTables.length;
+		if (length == 1 && this.documentNames == null) { // have a single table
+			Object offset = this.documentTables[0].get(word);
+			int[] numbers = index.diskIndex.readDocumentNumbers(offset);
+			String[] names = new String[numbers.length];
+			for (int i = 0, l = numbers.length; i < l; i++)
+				names[i] = index.diskIndex.readDocumentName(numbers[i]);
+			return names;
+		}
+
+		for (int i = 0; i < length; i++) {
+			Object offset = this.documentTables[i].get(word);
+			int[] numbers = index.diskIndex.readDocumentNumbers(offset);
+			for (int j = 0, k = numbers.length; j < k; j++)
+				addDocumentName(index.diskIndex.readDocumentName(numbers[j]));
+		}
+	}
+
+	if (this.documentNames == null)
+		return new String[0];
+
+	String[] names = new String[this.documentNames.elementSize];
+	int count = 0;
+	Object[] values = this.documentNames.values;
+	for (int i = 0, l = values.length; i < l; i++)
+		if (values[i] != null)
+			names[count++] = (String) values[i];
+	return names;
+}
+public boolean isEmpty() {
+	return this.documentTables == null && this.documentNames == null;
+}
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/Index.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/Index.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/index/Index.java	2007-04-06 14:22:22 UTC (rev 2291)
@@ -0,0 +1,196 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 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.rubypeople.rdt.internal.core.index;
+
+import java.io.File;
+import java.io.IOException;
+
+import org.rubypeople.rdt.core.search.SearchPattern;
+import org.rubypeople.rdt.internal.compiler.util.HashtableOfObject;
+import org.rubypeople.rdt.internal.compiler.util.SimpleSet;
+import org.rubypeople.rdt.internal.core.search.indexing.ReadWriteMonitor;
+import org.rubypeople.rdt.internal.core.util.CharOperation;
+
+/**
+ * An <code>Index</code> maps document names to their referenced words in various categories.
+ * 
+ * Queries can search a single category or several at the same time.
+ * 
+ * Indexes are not synchronized structures and should only be queried/updated one at a time.
+ */
+
+public class Index {
+
+public String containerPath;
+public ReadWriteMonitor monitor;
+
+protected DiskIndex diskIndex;
+protected MemoryIndex memoryIndex;
+
+/**
+ * Mask used on match rule for indexing.
+ */
+static final int MATCH_RULE_INDEX_MASK =
+	SearchPattern.R_EXACT_MATCH |
+	SearchPattern.R_PREFIX_MATCH |
+	SearchPattern.R_PATTERN_MATCH |
+	SearchPattern.R_REGEXP_MATCH |
+	SearchPattern.R_CASE_SENSITIVE |
+	SearchPattern.R_CAMELCASE_MATCH;
+
+public static boolean isMatch(char[] pattern, char[] word, int matchRule) {
+	if (pattern == null) return true;
+	int patternLength = pattern.length;
+	int wordLength = word.length;
+	if (patternLength == 0) return matchRule != SearchPattern.R_EXACT_MATCH;
+	if (wordLength == 0) return (matchRule & SearchPattern.R_PATTERN_MATCH) != 0 && patternLength == 1 && pattern[0] == '*';
+
+	// First test camel case if necessary
+	boolean isCamelCase = (matchRule & SearchPattern.R_CAMELCASE_MATCH) != 0;
+	if (isCamelCase &&  pattern[0] == word[0] && CharOperation.camelCaseMatch(pattern, word)) {
+		return true;
+	}
+
+	// need to mask some bits of pattern rule (bug 79790)
+	matchRule &= ~SearchPattern.R_CAMELCASE_MATCH;
+	switch(matchRule & MATCH_RULE_INDEX_MASK) {
+		case SearchPattern.R_EXACT_MATCH :
+			if (!isCamelCase) {
+				return patternLength == wordLength && CharOperation.equals(pattern, word, false);
+			}
+			// fall through prefix match if camel case failed
+		case SearchPattern.R_PREFIX_MATCH :
+			return patternLength <= wordLength && CharOperation.prefixEquals(pattern, word, false);
+		case SearchPattern.R_PATTERN_MATCH :
+			return CharOperation.match(pattern, word, false);
+		case SearchPattern.R_EXACT_MATCH | SearchPattern.R_CASE_SENSITIVE :
+			if (!isCamelCase) {
+				return pattern[0] == word[0] && patternLength == wordLength && CharOperation.equals(pattern, word);
+			}
+			// fall through prefix match if camel case failed
+		case SearchPattern.R_PREFIX_MATCH | SearchPattern.R_CASE_SENSITIVE :
+			return pattern[0] == word[0] && patternLength <= wordLength && CharOperation.prefixEquals(pattern, word);
+		case SearchPattern.R_PATTERN_MATCH | SearchPattern.R_CASE_SENSITIVE :
+			return CharOperation.match(pattern, word, true);
+	}
+	return false;
+}
+
+
+public Index(String fileName, String containerPath, boolean reuseExistingFile) throws IOException {
+	this.containerPath = containerPath;
+	this.monitor = new ReadWriteMonitor();
+
+	this.memoryIndex = new MemoryIndex();
+	this.diskIndex = new DiskIndex(fileName);
+	this.diskIndex.initialize(reuseExistingFile);
+}
+public void addIndexEntry(char[] category, char[] key, String containerRelativePath) {
+	this.memoryIndex.addIndexEntry(category, key, containerRelativePath);
+}
+public String containerRelativePath(String documentPath) {
+//	int index = documentPath.indexOf(IRubySearchScope.JAR_FILE_ENTRY_SEPARATOR); FIXME What do we do here since we don't have jars?
+	int index = -1;
+	if (index == -1) {
+		index = this.containerPath.length();
+		if (documentPath.length() <= index)
+			throw new IllegalArgumentException("Document path " + documentPath + " must be relative to " + this.containerPath); //$NON-NLS-1$ //$NON-NLS-2$
+	}
+	return documentPath.substring(index + 1);
+}
+public File getIndexFile() {
+	if (this.diskIndex == null) return null;
+
+	return this.diskIndex.getIndexFile();
+}
+public boolean hasChanged() {
+	return this.memoryIndex.hasChanged();
+}
+/**
+ * Returns the entries containing the given key in a group of categories, or null if no matches are found.
+ * The matchRule dictates whether its an exact, prefix or pattern match, as well as case sensitive or insensitive.
+ * If the key is null then all entries in specified categories are returned.
+ */
+public EntryResult[] query(char[][] categories, char[] key, int matchRule) throws IOException {
+	if (this.memoryIndex.shouldMerge() && monitor.exitReadEnterWrite()) {
+		try {
+			save();
+		} finally {
+			monitor.exitWriteEnterRead();
+		}
+	}
+
+	HashtableOfObject results;
+	int rule = matchRule & MATCH_RULE_INDEX_MASK;
+	if (this.memoryIndex.hasChanged()) {
+		results = this.diskIndex.addQueryResults(categories, key, rule, this.memoryIndex);
+		results = this.memoryIndex.addQueryResults(categories, key, rule, results);
+	} else {
+		results = this.diskIndex.addQueryResults(categories, key, rule, null);
+	}
+	if (results == null) return null;
+
+	EntryResult[] entryResults = new EntryResult[results.elementSize];
+	int count = 0;
+	Object[] values = results.valueTable;
+	for (int i = 0, l = values.length; i < l; i++) {
+		EntryResult result = (EntryResult) values[i];
+		if (result != null)
+			entryResults[count++] = result;
+	}
+	return entryResults;
+}
+/**
+ * Returns the document names that contain the given substring, if null then returns all of them.
+ */
+public String[] queryDocumentNames(String substring) throws IOException {
+	SimpleSet results;
+	if (this.memoryIndex.hasChanged()) {
+		results = this.diskIndex.addDocumentNames(substring, this.memoryIndex);
+		this.memoryIndex.addDocumentNames(substring, results);
+	} else {
+		results = this.diskIndex.addDocumentNames(substring, null);
+	}
+	if (results.elementSize == 0) return null;
+
+	String[] documentNames = new String[results.elementSize];
+	int count = 0;
+	Object[] paths = results.values;
+	for (int i = 0, l = paths.length; i < l; i++)
+		if (paths[i] != null)
+			documentNames[count++] = (String) paths[i];
+	return documentNames;
+}
+public void remove(String containerRelativePath) {
+	this.memoryIndex.remove(containerRelativePath);
+}
+public void save() throws IOException {
+	// must own the write lock of the monitor
+	if (!hasChanged()) return;
+
+	int numberOfChanges = this.memoryIndex.docsToReferences.elementSize;
+	this.diskIndex = this.diskIndex.mergeWith(this.memoryIndex);
+	this.memoryIndex = new ...
 
[truncated message content]