org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/field/FieldSearchIndex.java - jdt/eclipse.jdt.core - Git at Google

 /*******************************************************************************
  * Copyright (c) 2015, 2016 Google, Inc 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:
  *   Stefan Xenos (Google) - Initial implementation
  *******************************************************************************/
 package org.eclipse.jdt.internal.core.nd.field;

 import java.util.ArrayList;
 import java.util.List;

 import org.eclipse.jdt.internal.core.nd.ITypeFactory;
 import org.eclipse.jdt.internal.core.nd.Nd;
 import org.eclipse.jdt.internal.core.nd.NdNode;
 import org.eclipse.jdt.internal.core.nd.db.BTree;
 import org.eclipse.jdt.internal.core.nd.db.IBTreeComparator;
 import org.eclipse.jdt.internal.core.nd.db.IBTreeVisitor;
 import org.eclipse.jdt.internal.core.nd.db.IString;
 import org.eclipse.jdt.internal.core.nd.db.IndexException;

 /**
  * Declares a field representing a case-insensitive search tree over elements which are a subtype of NdNode.
  */
 public class FieldSearchIndex<T extends NdNode> implements IField, IDestructableField {
 	private int offset;
 	private final ITypeFactory<BTree> btreeFactory;
 	FieldSearchKey<?> searchKey;
 	private static IResultRank anything = new IResultRank() {
 		@Override
 		public long getRank(Nd nd, long address) {
 			return 1;
 		}
 	};

 	public static final class SearchCriteria {
 		private boolean matchCase = true;
 		private boolean isPrefix = false;
 		private char[] searchString;
 		private short requiredNodeType = -1;
 		private boolean matchingParentNodeAddress = false;

 		private SearchCriteria(char[] searchString) {
 			this.searchString = searchString;
 		}

 		public static SearchCriteria create(String searchString) {
 			return create(searchString.toCharArray());
 		}

 		public static SearchCriteria create(char[] searchString) {
 			return new SearchCriteria(searchString);
 		}

 		public SearchCriteria requireNodeType(short type) {
 			this.requiredNodeType = type;
 			return this;
 		}

 		public SearchCriteria allowAnyNodeType() {
 			this.requiredNodeType = -1;
 			return this;
 		}

 		public SearchCriteria matchCase(boolean match) {
 			this.matchCase = match;
 			return this;
 		}

 		public SearchCriteria prefix(boolean isPrefixSearch) {
 			this.isPrefix = isPrefixSearch;
 			return this;
 		}
 //
 //		public SearchCriteria requireParentNode(long parentNameAddress) {
 //			this.requiredParentNodeAddress = parentNameAddress;
 //			return this;
 //		}

 		public boolean isMatchingParentNodeAddress() {
 			return this.matchingParentNodeAddress;
 		}

 		public boolean isMatchingCase() {
 			return this.matchCase;
 		}

 		public boolean isPrefixSearch() {
 			return this.isPrefix;
 		}

 		public char[] getSearchString() {
 			return this.searchString;
 		}
 //
 //		public long getRequiredParentAddress() {
 //			return this.requiredParentNodeAddress;
 //		}

 		public boolean acceptsNodeType(short nodeType) {
 			return this.requiredNodeType == -1 || this.requiredNodeType == nodeType;
 		}

 		public boolean requiresSpecificNodeType() {
 			return this.requiredNodeType != -1;
 		}
 	}

 	public static interface IResultRank {
 		public long getRank(Nd nd, long address);
 	}

 	private abstract class SearchCriteriaToBtreeVisitorAdapter implements IBTreeVisitor {
 		private final SearchCriteria searchCriteria;
 		private final Nd nd;

 		public SearchCriteriaToBtreeVisitorAdapter(SearchCriteria searchCriteria, Nd nd) {
 			this.searchCriteria = searchCriteria;
 			this.nd = nd;
 		}

 		@Override
 		public int compare(long address) throws IndexException {
 			IString key = FieldSearchIndex.this.searchKey.get(this.nd, address);

 			if (this.searchCriteria.isPrefixSearch()) {
 				return key.comparePrefix(this.searchCriteria.getSearchString(), false);
 			} else {
 				return key.compareCompatibleWithIgnoreCase(this.searchCriteria.getSearchString());
 			}
 		}

 		@Override
 		public boolean visit(long address) throws IndexException {
 			if (this.searchCriteria.requiresSpecificNodeType()) {
 				short nodeType = NdNode.NODE_TYPE.get(this.nd, address);

 				if (!this.searchCriteria.acceptsNodeType(nodeType)) {
 					return true;
 				}
 			}

 			IString key = FieldSearchIndex.this.searchKey.get(this.nd, address);

 			if (this.searchCriteria.isMatchingCase()) {
 				if (this.searchCriteria.isPrefixSearch()) {
 					if (key.comparePrefix(this.searchCriteria.getSearchString(), true) != 0) {
 						return true;
 					}
 				} else {
 					if (key.compare(this.searchCriteria.getSearchString(), true) != 0) {
 						return true;
 					}
 				}
 			}

 			return acceptResult(address);
 		}

 		protected abstract boolean acceptResult(long address);
 	}

 	private FieldSearchIndex(FieldSearchKey<?> searchKey) {
 		this.btreeFactory = BTree.getFactory(new IBTreeComparator() {
 			@Override
 			public int compare(Nd nd, long record1, long record2) {
 				IString key1 = FieldSearchIndex.this.searchKey.get(nd, record1);
 				IString key2 = FieldSearchIndex.this.searchKey.get(nd, record2);

 				int cmp = key1.compareCompatibleWithIgnoreCase(key2);
 				if (cmp == 0) {
 					cmp = Long.signum(record1 - record2);
 				}

 				return cmp;
 			}
 		});

 		if (searchKey != null) {
 			if (searchKey.searchIndex != null && searchKey.searchIndex != this) {
 				throw new IllegalArgumentException(
 					"Attempted to construct a FieldSearchIndex referring to a search key that " //$NON-NLS-1$
 					+ "is already in use by a different index"); //$NON-NLS-1$
 			}
 			searchKey.searchIndex = this;
 		}
 		this.searchKey = searchKey;
 	}

 	public static <T extends NdNode, B> FieldSearchIndex<T> create(StructDef<B> builder,
 			final FieldSearchKey<B> searchKey) {

 		FieldSearchIndex<T> result = new FieldSearchIndex<T>(searchKey);

 		builder.add(result);
 		builder.addDestructableField(result);

 		return result;
 	}

 	public BTree get(Nd nd, long address) {
 		return this.btreeFactory.create(nd, address + this.offset);
 	}

 	@Override
 	public void destruct(Nd nd, long address) {
 		this.btreeFactory.destruct(nd, address);
 	}

 	@Override
 	public void setOffset(int offset) {
 		this.offset = offset;
 	}

 	@Override
 	public int getRecordSize() {
 		return this.btreeFactory.getRecordSize();
 	}

 	public T findFirst(final Nd nd, long address, final SearchCriteria searchCriteria) {
 		return findBest(nd, address, searchCriteria, anything);
 	}

 	@SuppressWarnings("unchecked")
 	public T findBest(final Nd nd, long address, final SearchCriteria searchCriteria, final IResultRank rankFunction) {
 		final long[] resultRank = new long[1];
 		final long[] result = new long[1];
 		get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) {
 			@Override
 			protected boolean acceptResult(long resultAddress) {
 				long rank = rankFunction.getRank(nd, resultAddress);
 				if (rank >= resultRank[0]) {
 					resultRank[0] = rank;
 					result[0] = resultAddress;
 				}
 				return true;
 			}
 		});

 		if (result[0] == 0) {
 			return null;
 		}
 		return (T)NdNode.load(nd, result[0]);
 	}

 	public interface Visitor<T> {
 		boolean visit(T toVisit);
 	}

 	public boolean visitAll(final Nd nd, long address, final SearchCriteria searchCriteria, final Visitor<T> visitor) {
 		return get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) {
 			@SuppressWarnings("unchecked")
 			@Override
 			protected boolean acceptResult(long resultAddress) {
 				return visitor.visit((T)NdNode.load(nd, resultAddress));
 			}
 		});
 	}

 	public List<T> findAll(final Nd nd, long address, final SearchCriteria searchCriteria) {
 		final List<T> result = new ArrayList<T>();
 		get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) {
 			@SuppressWarnings("unchecked")
 			@Override
 			protected boolean acceptResult(long resultAddress) {
 				result.add((T)NdNode.load(nd, resultAddress));
 				return true;
 			}
 		});

 		return result;
 	}

 	/**
 	 * Returns the entire contents of the index as a single list.
 	 */
 	public List<T> asList(final Nd nd, long address) {
 		final List<T> result = new ArrayList<T>();
 		get(nd, address).accept(new IBTreeVisitor() {
 			@Override
 			public int compare(long record) {
 				return 0;
 			}

 			@SuppressWarnings("unchecked")
 			@Override
 			public boolean visit(long resultAddress) {
 				result.add((T)NdNode.load(nd, resultAddress));
 				return true;
 			}
 		});

 		return result;
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2015, 2016 Google, Inc 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:
	* Stefan Xenos (Google) - Initial implementation
	*******************************************************************************/
	package org.eclipse.jdt.internal.core.nd.field;

	import java.util.ArrayList;
	import java.util.List;

	import org.eclipse.jdt.internal.core.nd.ITypeFactory;
	import org.eclipse.jdt.internal.core.nd.Nd;
	import org.eclipse.jdt.internal.core.nd.NdNode;
	import org.eclipse.jdt.internal.core.nd.db.BTree;
	import org.eclipse.jdt.internal.core.nd.db.IBTreeComparator;
	import org.eclipse.jdt.internal.core.nd.db.IBTreeVisitor;
	import org.eclipse.jdt.internal.core.nd.db.IString;
	import org.eclipse.jdt.internal.core.nd.db.IndexException;

	/**
	* Declares a field representing a case-insensitive search tree over elements which are a subtype of NdNode.
	*/
	public class FieldSearchIndex<T extends NdNode> implements IField, IDestructableField {
	private int offset;
	private final ITypeFactory<BTree> btreeFactory;
	FieldSearchKey<?> searchKey;
	private static IResultRank anything = new IResultRank() {
	@Override
	public long getRank(Nd nd, long address) {
	return 1;
	}
	};

	public static final class SearchCriteria {
	private boolean matchCase = true;
	private boolean isPrefix = false;
	private char[] searchString;
	private short requiredNodeType = -1;
	private boolean matchingParentNodeAddress = false;

	private SearchCriteria(char[] searchString) {
	this.searchString = searchString;
	}

	public static SearchCriteria create(String searchString) {
	return create(searchString.toCharArray());
	}

	public static SearchCriteria create(char[] searchString) {
	return new SearchCriteria(searchString);
	}

	public SearchCriteria requireNodeType(short type) {
	this.requiredNodeType = type;
	return this;
	}

	public SearchCriteria allowAnyNodeType() {
	this.requiredNodeType = -1;
	return this;
	}

	public SearchCriteria matchCase(boolean match) {
	this.matchCase = match;
	return this;
	}

	public SearchCriteria prefix(boolean isPrefixSearch) {
	this.isPrefix = isPrefixSearch;
	return this;
	}
	//
	// public SearchCriteria requireParentNode(long parentNameAddress) {
	// this.requiredParentNodeAddress = parentNameAddress;
	// return this;
	// }

	public boolean isMatchingParentNodeAddress() {
	return this.matchingParentNodeAddress;
	}

	public boolean isMatchingCase() {
	return this.matchCase;
	}

	public boolean isPrefixSearch() {
	return this.isPrefix;
	}

	public char[] getSearchString() {
	return this.searchString;
	}
	//
	// public long getRequiredParentAddress() {
	// return this.requiredParentNodeAddress;
	// }

	public boolean acceptsNodeType(short nodeType) {
	return this.requiredNodeType == -1 \|\| this.requiredNodeType == nodeType;
	}

	public boolean requiresSpecificNodeType() {
	return this.requiredNodeType != -1;
	}
	}

	public static interface IResultRank {
	public long getRank(Nd nd, long address);
	}

	private abstract class SearchCriteriaToBtreeVisitorAdapter implements IBTreeVisitor {
	private final SearchCriteria searchCriteria;
	private final Nd nd;

	public SearchCriteriaToBtreeVisitorAdapter(SearchCriteria searchCriteria, Nd nd) {
	this.searchCriteria = searchCriteria;
	this.nd = nd;
	}

	@Override
	public int compare(long address) throws IndexException {
	IString key = FieldSearchIndex.this.searchKey.get(this.nd, address);

	if (this.searchCriteria.isPrefixSearch()) {
	return key.comparePrefix(this.searchCriteria.getSearchString(), false);
	} else {
	return key.compareCompatibleWithIgnoreCase(this.searchCriteria.getSearchString());
	}
	}

	@Override
	public boolean visit(long address) throws IndexException {
	if (this.searchCriteria.requiresSpecificNodeType()) {
	short nodeType = NdNode.NODE_TYPE.get(this.nd, address);

	if (!this.searchCriteria.acceptsNodeType(nodeType)) {
	return true;
	}
	}

	IString key = FieldSearchIndex.this.searchKey.get(this.nd, address);

	if (this.searchCriteria.isMatchingCase()) {
	if (this.searchCriteria.isPrefixSearch()) {
	if (key.comparePrefix(this.searchCriteria.getSearchString(), true) != 0) {
	return true;
	}
	} else {
	if (key.compare(this.searchCriteria.getSearchString(), true) != 0) {
	return true;
	}
	}
	}

	return acceptResult(address);
	}

	protected abstract boolean acceptResult(long address);
	}

	private FieldSearchIndex(FieldSearchKey<?> searchKey) {
	this.btreeFactory = BTree.getFactory(new IBTreeComparator() {
	@Override
	public int compare(Nd nd, long record1, long record2) {
	IString key1 = FieldSearchIndex.this.searchKey.get(nd, record1);
	IString key2 = FieldSearchIndex.this.searchKey.get(nd, record2);

	int cmp = key1.compareCompatibleWithIgnoreCase(key2);
	if (cmp == 0) {
	cmp = Long.signum(record1 - record2);
	}

	return cmp;
	}
	});

	if (searchKey != null) {
	if (searchKey.searchIndex != null && searchKey.searchIndex != this) {
	throw new IllegalArgumentException(
	"Attempted to construct a FieldSearchIndex referring to a search key that " //$NON-NLS-1$
	+ "is already in use by a different index"); //$NON-NLS-1$
	}
	searchKey.searchIndex = this;
	}
	this.searchKey = searchKey;
	}

	public static <T extends NdNode, B> FieldSearchIndex<T> create(StructDef<B> builder,
	final FieldSearchKey<B> searchKey) {

	FieldSearchIndex<T> result = new FieldSearchIndex<T>(searchKey);

	builder.add(result);
	builder.addDestructableField(result);

	return result;
	}

	public BTree get(Nd nd, long address) {
	return this.btreeFactory.create(nd, address + this.offset);
	}

	@Override
	public void destruct(Nd nd, long address) {
	this.btreeFactory.destruct(nd, address);
	}

	@Override
	public void setOffset(int offset) {
	this.offset = offset;
	}

	@Override
	public int getRecordSize() {
	return this.btreeFactory.getRecordSize();
	}

	public T findFirst(final Nd nd, long address, final SearchCriteria searchCriteria) {
	return findBest(nd, address, searchCriteria, anything);
	}

	@SuppressWarnings("unchecked")
	public T findBest(final Nd nd, long address, final SearchCriteria searchCriteria, final IResultRank rankFunction) {
	final long[] resultRank = new long[1];
	final long[] result = new long[1];
	get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) {
	@Override
	protected boolean acceptResult(long resultAddress) {
	long rank = rankFunction.getRank(nd, resultAddress);
	if (rank >= resultRank[0]) {
	resultRank[0] = rank;
	result[0] = resultAddress;
	}
	return true;
	}
	});

	if (result[0] == 0) {
	return null;
	}
	return (T)NdNode.load(nd, result[0]);
	}

	public interface Visitor<T> {
	boolean visit(T toVisit);
	}

	public boolean visitAll(final Nd nd, long address, final SearchCriteria searchCriteria, final Visitor<T> visitor) {
	return get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) {
	@SuppressWarnings("unchecked")
	@Override
	protected boolean acceptResult(long resultAddress) {
	return visitor.visit((T)NdNode.load(nd, resultAddress));
	}
	});
	}

	public List<T> findAll(final Nd nd, long address, final SearchCriteria searchCriteria) {
	final List<T> result = new ArrayList<T>();
	get(nd, address).accept(new SearchCriteriaToBtreeVisitorAdapter(searchCriteria, nd) {
	@SuppressWarnings("unchecked")
	@Override
	protected boolean acceptResult(long resultAddress) {
	result.add((T)NdNode.load(nd, resultAddress));
	return true;
	}
	});

	return result;
	}

	/**
	* Returns the entire contents of the index as a single list.
	*/
	public List<T> asList(final Nd nd, long address) {
	final List<T> result = new ArrayList<T>();
	get(nd, address).accept(new IBTreeVisitor() {
	@Override
	public int compare(long record) {
	return 0;
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean visit(long resultAddress) {
	result.add((T)NdNode.load(nd, resultAddress));
	return true;
	}
	});

	return result;
	}
	}