001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
003: */
004: package com.tctest.perf.collections;
005:
006: import java.util.Arrays;
007: import java.util.Vector;
008:
009: public interface ElementType extends Comparable {
010: public void traverse();
011:
012: public interface Factory {
013: ElementType create();
014:
015: String describeType();
016: }
017:
018: public static class LongFactory implements Factory {
019: long next = 0;
020:
021: public ElementType create() {
022: Long l = new Long(next++);
023: return new WrappedComparable(l);
024: }
025:
026: public String describeType() {
027: return "Long";
028: }
029:
030: }
031:
032: public static class StringFactory implements Factory {
033: long next = 0;
034: String prefix = "standard_";
035:
036: public void setPrefix(String newPrefix) {
037: prefix = newPrefix;
038: }
039:
040: public String describeType() {
041: return "String";
042: }
043:
044: public ElementType create() {
045: return new WrappedComparable(prefix + next++);
046: }
047: }
048:
049: public static class GraphFactory implements Factory {
050: ElementType.Factory contentFactory = null;
051: int graphSize = 10;
052:
053: public GraphFactory(int size, ElementType.Factory valueFactory) {
054: graphSize = size;
055: contentFactory = valueFactory;
056: }
057:
058: public ElementType create() {
059: return new GraphType(graphSize, contentFactory);
060: }
061:
062: public String describeType() {
063: StringBuffer buf = new StringBuffer("BinaryTree(");
064: buf.append(contentFactory.describeType());
065: buf.append("[");
066: buf.append(graphSize);
067: buf.append("])");
068: return buf.toString();
069: }
070:
071: }
072:
073: public class GraphType implements ElementType { // simple lazy balanced binary tree minus insert, remove, etc.
074: class Node {
075: Node right = null, left = null;
076: ElementType value;
077:
078: Node(ElementType e) {
079: value = e;
080: }
081:
082: // in-order contents
083: void addContents(Vector result) {
084: if (left != null)
085: left.addContents(result);
086: result.add(value);
087: if (right != null)
088: right.addContents(result);
089: }
090: }
091:
092: // in order contents
093: Vector getContents() {
094: Vector ret = new Vector();
095: if (top != null)
096: top.addContents(ret);
097: return ret;
098: }
099:
100: static int atMostCompare = 100;
101:
102: public int compareTo(Object other) {
103: if (!(other instanceof GraphType))
104: return 0;
105:
106: Vector contents1 = getContents();
107: Vector contents2 = ((GraphType) other).getContents();
108: int cnt1 = contents1.size(), cnt2 = contents2.size();
109: int cnt = Math.min(cnt1, cnt2);
110: if (cnt == 0)
111: return (cnt1 > 0) ? 1 : ((cnt2 > 0) ? -1 : 0);
112: else {
113: int cmp = 0;
114: for (int i = 0; (cmp == 0) && (i < cnt); i++) {
115:
116: cmp = ((Comparable) contents1.get(i))
117: .compareTo(contents2.get(i));
118:
119: }
120: return cmp;
121: }
122: }
123:
124: // utility method
125: ElementType[] subArray(int start, int end,
126: ElementType[] original) {
127: int size = end - start + 1;
128: ElementType[] ret = new ElementType[size];
129: for (int i = 0; i < size; i++)
130: ret[i] = original[i + start];
131: return ret;
132: }
133:
134: // simple construction from array of values
135: Node nodeFromCollection(ElementType[] collection) {
136: int size = collection.length;
137: if (size == 0)
138: return null;
139: int split = size / 2;
140: Node ret = new Node(collection[split]);
141: ret.left = nodeFromCollection(subArray(0, split - 1,
142: collection));
143: ret.right = nodeFromCollection(subArray(split + 1,
144: size - 1, collection));
145: return ret;
146: }
147:
148: Node top = null;
149: ElementType.Factory elementFactory;
150:
151: public void addNode(ElementType value) {
152: // TBD: not used yet
153: // Node newNode = new Node(value);
154: }
155:
156: public GraphType(int size, ElementType.Factory factory) {
157: elementFactory = factory;
158: ElementType[] contents = new ElementType[size];
159: for (int i = 0; i < size; i++)
160: contents[i] = elementFactory.create();
161: Arrays.sort(contents);
162: top = nodeFromCollection(contents);
163: }
164:
165: void traverse(Node node) {
166: if (node != null) {
167: traverse(node.left);
168: node.value.traverse();
169: traverse(node.right);
170: }
171: }
172:
173: public void traverse() {
174: traverse(top);
175: }
176: }
177:
178: // useful for Numeric, String, Date, etc. types
179: public class WrappedComparable implements ElementType {
180: Comparable wrapped;
181:
182: public Comparable getWrapped() {
183: return wrapped;
184: }
185:
186: public WrappedComparable(Comparable c) {
187: wrapped = c;
188: }
189:
190: public void traverse() {
191: // nothing yet
192: }
193:
194: public int compareTo(Object other) {
195: return (other instanceof WrappedComparable) ? ((WrappedComparable) other)
196: .getWrapped().compareTo(wrapped)
197: : 0;
198: }
199: }
200:
201: }
|