package org.eclipse.core.internal.dtree;
import org.eclipse.core.internal.utils.Messages;
import org.eclipse.core.internal.utils.StringPool;
import org.eclipse.core.runtime.IPath;
import org.eclipse.osgi.util.NLS;
public abstract class AbstractDataTreeNode {
static final AbstractDataTreeNode[] NO_CHILDREN = new AbstractDataTreeNode[0];
protected AbstractDataTreeNode children[];
protected String name;
public static final int T_COMPLETE_NODE = 0;
public static final int T_DELTA_NODE = 1;
public static final int T_DELETED_NODE = 2;
public static final int T_NO_DATA_DELTA_NODE = 3;
AbstractDataTreeNode(String name, AbstractDataTreeNode[] children) {
this.name = name;
if (children == null || children.length == 0)
this.children = AbstractDataTreeNode.NO_CHILDREN;
else
this.children = children;
}
abstract AbstractDataTreeNode asBackwardDelta(DeltaDataTree myTree, DeltaDataTree parentTree, IPath key);
AbstractDataTreeNode asReverseComparisonNode(IComparator comparator) {
return this;
}
static AbstractDataTreeNode[] assembleWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, boolean keepDeleted) {
if (newNodes.length == 0)
return oldNodes;
AbstractDataTreeNode[] resultNodes = new AbstractDataTreeNode[oldNodes.length + newNodes.length];
int oldIndex = 0;
int newIndex = 0;
int resultIndex = 0;
while (oldIndex < oldNodes.length && newIndex < newNodes.length) {
int log2 = 31 - Integer.numberOfLeadingZeros(oldNodes.length - oldIndex);
if (log2 > 1 && (newNodes.length - newIndex) <= (oldNodes.length - oldIndex) / log2) {
String key = newNodes[newIndex].name;
int left = oldIndex;
int right = oldNodes.length - 1;
boolean found = false;
while (left <= right) {
int mid = (left + right) / 2;
int compare = key.compareTo(oldNodes[mid].name);
if (compare < 0) {
right = mid - 1;
} else if (compare > 0) {
left = mid + 1;
} else {
left = mid;
found = true;
break;
}
}
int toCopy = left - oldIndex;
System.arraycopy(oldNodes, oldIndex, resultNodes, resultIndex, toCopy);
resultIndex += toCopy;
if (found) {
AbstractDataTreeNode node = oldNodes[left++].assembleWith(newNodes[newIndex++]);
if (node != null && (!node.isDeleted() || keepDeleted)) {
resultNodes[resultIndex++] = node;
}
} else {
AbstractDataTreeNode node = newNodes[newIndex++];
if (!node.isDeleted() || keepDeleted) {
resultNodes[resultIndex++] = node;
}
}
oldIndex = left;
} else {
int compare = oldNodes[oldIndex].name.compareTo(newNodes[newIndex].name);
if (compare == 0) {
AbstractDataTreeNode node = oldNodes[oldIndex++].assembleWith(newNodes[newIndex++]);
if (node != null && (!node.isDeleted() || keepDeleted)) {
resultNodes[resultIndex++] = node;
}
} else if (compare < 0) {
resultNodes[resultIndex++] = oldNodes[oldIndex++];
} else if (compare > 0) {
AbstractDataTreeNode node = newNodes[newIndex++];
if (!node.isDeleted() || keepDeleted) {
resultNodes[resultIndex++] = node;
}
}
}
}
while (oldIndex < oldNodes.length) {
resultNodes[resultIndex++] = oldNodes[oldIndex++];
}
while (newIndex < newNodes.length) {
AbstractDataTreeNode resultNode = newNodes[newIndex++];
if (!resultNode.isDeleted() || keepDeleted) {
resultNodes[resultIndex++] = resultNode;
}
}
if (resultIndex < resultNodes.length) {
System.arraycopy(resultNodes, 0, resultNodes = new AbstractDataTreeNode[resultIndex], 0, resultIndex);
}
return resultNodes;
}
AbstractDataTreeNode assembleWith(AbstractDataTreeNode node) {
if (!node.isDelta() || this.isDeleted()) {
return node;
}
if (node.hasData()) {
if (this.isDelta()) {
AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
return new DataDeltaNode(name, node.getData(), assembledChildren);
}
AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
return new DataTreeNode(name, node.getData(), assembledChildren);
}
if (this.isDelta()) {
AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
if (this.hasData())
return new DataDeltaNode(name, this.getData(), assembledChildren);
return new NoDataDeltaNode(name, assembledChildren);
}
AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
return new DataTreeNode(name, this.getData(), assembledChildren);
}
AbstractDataTreeNode assembleWith(AbstractDataTreeNode node, IPath key, int keyIndex) {
int keyLen = key.segmentCount();
if (keyIndex == keyLen) {
return assembleWith(node);
}
int childIndex = indexOfChild(key.segment(keyIndex));
if (childIndex >= 0) {
AbstractDataTreeNode copy = copy();
copy.children[childIndex] = children[childIndex].assembleWith(node, key, keyIndex + 1);
return copy;
}
for (int i = keyLen - 2; i >= keyIndex; --i) {
node = new NoDataDeltaNode(key.segment(i), node);
}
node = new NoDataDeltaNode(name, node);
return assembleWith(node);
}
AbstractDataTreeNode childAt(String localName) {
AbstractDataTreeNode node = childAtOrNull(localName);
if (node != null) {
return node;
}
throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
}
AbstractDataTreeNode childAtOrNull(String localName) {
int index = indexOfChild(localName);
return index >= 0 ? children[index] : null;
}
AbstractDataTreeNode childAtIgnoreCase(String localName) {
AbstractDataTreeNode result = null;
for (AbstractDataTreeNode element : children) {
if (element.getName().equalsIgnoreCase(localName)) {
if (element.isDeleted())
result = element;
else
return element;
}
}
return result;
}
protected static AbstractDataTreeNode[] compareWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, IComparator comparator) {
int oldLen = oldNodes.length;
int newLen = newNodes.length;
int oldIndex = 0;
int newIndex = 0;
AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[oldLen + newLen];
int count = 0;
while (oldIndex < oldLen && newIndex < newLen) {
DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex];
DataTreeNode newNode = (DataTreeNode) newNodes[newIndex];
int compare = oldNode.name.compareTo(newNode.name);
if (compare < 0) {
int userComparison = comparator.compare(oldNode.getData(), null);
if (userComparison != 0) {
comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
}
++oldIndex;
} else if (compare > 0) {
int userComparison = comparator.compare(null, newNode.getData());
if (userComparison != 0) {
comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
}
++newIndex;
} else {
AbstractDataTreeNode comparedNode = oldNode.compareWith(newNode, comparator);
NodeComparison comparison = (NodeComparison) comparedNode.getData();
if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
comparedNodes[count++] = comparedNode;
}
++oldIndex;
++newIndex;
}
}
while (oldIndex < oldLen) {
DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex++];
int userComparison = comparator.compare(oldNode.getData(), null);
if (userComparison != 0) {
comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
}
}
while (newIndex < newLen) {
DataTreeNode newNode = (DataTreeNode) newNodes[newIndex++];
int userComparison = comparator.compare(null, newNode.getData());
if (userComparison != 0) {
comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
}
}
if (count == 0) {
return NO_CHILDREN;
}
if (count < comparedNodes.length) {
System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
}
return comparedNodes;
}
protected static AbstractDataTreeNode[] compareWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparator) {
AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[nodes.length];
int count = 0;
for (AbstractDataTreeNode node : nodes) {
AbstractDataTreeNode comparedNode = node.compareWithParent(key.append(node.getName()), parent, comparator);
NodeComparison comparison = (NodeComparison) comparedNode.getData();
if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
comparedNodes[count++] = comparedNode;
}
}
if (count == 0) {
return NO_CHILDREN;
}
if (count < comparedNodes.length) {
System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
}
return comparedNodes;
}
abstract AbstractDataTreeNode compareWithParent(IPath key, DeltaDataTree parent, IComparator comparator);
static AbstractDataTreeNode convertToAddedComparisonNode(AbstractDataTreeNode newNode, int userComparison) {
AbstractDataTreeNode[] children = newNode.getChildren();
int n = children.length;
AbstractDataTreeNode[] convertedChildren;
if (n == 0) {
convertedChildren = NO_CHILDREN;
} else {
convertedChildren = new AbstractDataTreeNode[n];
for (int i = 0; i < n; ++i) {
convertedChildren[i] = convertToAddedComparisonNode(children[i], userComparison);
}
}
return new DataTreeNode(newNode.name, new NodeComparison(null, newNode.getData(), NodeComparison.K_ADDED, userComparison), convertedChildren);
}
static AbstractDataTreeNode convertToRemovedComparisonNode(AbstractDataTreeNode oldNode, int userComparison) {
AbstractDataTreeNode[] children = oldNode.getChildren();
int n = children.length;
AbstractDataTreeNode[] convertedChildren;
if (n == 0) {
convertedChildren = NO_CHILDREN;
} else {
convertedChildren = new AbstractDataTreeNode[n];
for (int i = 0; i < n; ++i) {
convertedChildren[i] = convertToRemovedComparisonNode(children[i], userComparison);
}
}
return new DataTreeNode(oldNode.name, new NodeComparison(oldNode.getData(), null, NodeComparison.K_REMOVED, userComparison), convertedChildren);
}
abstract AbstractDataTreeNode copy();
protected void copyChildren(int from, int to, AbstractDataTreeNode otherNode, int start) {
int other = start;
for (int i = from; i <= to; i++, other++) {
this.children[i] = otherNode.children[other];
}
}
public AbstractDataTreeNode[] getChildren() {
return children;
}
Object getData() {
throw new AbstractMethodError(Messages.dtree_subclassImplement);
}
public String getName() {
return name;
}
boolean hasData() {
return false;
}
boolean includesChild(String localName) {
return indexOfChild(localName) != -1;
}
protected int indexOfChild(String localName) {
AbstractDataTreeNode[] nodes = this.children;
int left = 0;
int right = nodes.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
int compare = localName.compareTo(nodes[mid].name);
if (compare < 0) {
right = mid - 1;
} else if (compare > 0) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
boolean isDeleted() {
return false;
}
boolean isDelta() {
return false;
}
boolean isEmptyDelta() {
return false;
}
String[] namesOfChildren() {
String names[] = new String[children.length];
for (int i = children.length; --i >= 0;)
names[i] = children[i].getName();
return names;
}
void replaceChild(String localName, DataTreeNode node) {
int i = indexOfChild(localName);
if (i >= 0) {
children[i] = node;
} else {
throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
}
}
protected void setChildren(AbstractDataTreeNode newChildren[]) {
children = newChildren;
}
void setName(String s) {
name = s;
}
protected static AbstractDataTreeNode[] simplifyWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparer) {
int nodeCount = nodes.length;
if (nodeCount == 0)
return NO_CHILDREN;
AbstractDataTreeNode[] simplifiedNodes = new AbstractDataTreeNode[nodeCount];
int simplifiedCount = 0;
for (int i = 0; i < nodeCount; ++i) {
AbstractDataTreeNode node = nodes[i];
AbstractDataTreeNode simplifiedNode = node.simplifyWithParent(key.append(node.getName()), parent, comparer);
if (!simplifiedNode.isEmptyDelta()) {
simplifiedNodes[simplifiedCount++] = simplifiedNode;
}
}
if (simplifiedCount == 0) {
return NO_CHILDREN;
}
if (simplifiedCount < simplifiedNodes.length) {
System.arraycopy(simplifiedNodes, 0, simplifiedNodes = new AbstractDataTreeNode[simplifiedCount], 0, simplifiedCount);
}
return simplifiedNodes;
}
abstract AbstractDataTreeNode simplifyWithParent(IPath key, DeltaDataTree parent, IComparator comparer);
int size() {
return children.length;
}
public void storeStrings(StringPool set) {
name = set.add(name);
AbstractDataTreeNode[] nodes = children;
if (nodes != null)
for (int i = nodes.length; --i >= 0;)
nodes[i].storeStrings(set);
}
@Override
public String toString() {
return "an AbstractDataTreeNode(" + this.getName() + ") with " + getChildren().length + " children.";
}
abstract int type();
}