|
1
4 package com.tctest.perf.collections;
5
6 import java.util.Arrays  ;
7 import java.util.Vector ;
8
9 public interface ElementType extends Comparable {
10 public void traverse();
11
12 public interface Factory {
13 ElementType create();
14
15 String describeType();
16 }
17
18 public static class LongFactory implements Factory {
19 long next = 0;
20
21 public ElementType create() {
22 Long l = new Long (next++);
23 return new WrappedComparable(l);
24 }
25
26 public String describeType() {
27 return "Long";
28 }
29
30 }
31
32 public static class StringFactory implements Factory {
33 long next = 0;
34 String prefix = "standard_";
35
36 public void setPrefix(String newPrefix) {
37 prefix = newPrefix;
38 }
39
40 public String describeType() {
41 return "String";
42 }
43
44 public ElementType create() {
45 return new WrappedComparable(prefix + next++);
46 }
47 }
48
49 public static class GraphFactory implements Factory {
50 ElementType.Factory contentFactory = null;
51 int graphSize = 10;
52
53 public GraphFactory(int size, ElementType.Factory valueFactory) {
54 graphSize = size;
55 contentFactory = valueFactory;
56 }
57
58 public ElementType create() {
59 return new GraphType(graphSize, contentFactory);
60 }
61
62 public String describeType() {
63 StringBuffer buf = new StringBuffer ("BinaryTree(");
64 buf.append(contentFactory.describeType());
65 buf.append("[");
66 buf.append(graphSize);
67 buf.append("])");
68 return buf.toString();
69 }
70
71 }
72
73 public class GraphType implements ElementType { class Node {
75 Node right = null, left = null;
76 ElementType value;
77
78 Node(ElementType e) {
79 value = e;
80 }
81
82 void addContents(Vector result) {
84 if (left != null) left.addContents(result);
85 result.add(value);
86 if (right != null) right.addContents(result);
87 }
88 }
89
90 Vector getContents() {
92 Vector ret = new Vector ();
93 if (top != null) top.addContents(ret);
94 return ret;
95 }
96
97 static int atMostCompare = 100;
98
99 public int compareTo(Object other) {
100 if (!(other instanceof GraphType)) return 0;
101
102 Vector contents1 = getContents();
103 Vector contents2 = ((GraphType) other).getContents();
104 int cnt1 = contents1.size(), cnt2 = contents2.size();
105 int cnt = Math.min(cnt1, cnt2);
106 if (cnt == 0) return (cnt1 > 0) ? 1 : ((cnt2 > 0) ? -1 : 0);
107 else {
108 int cmp = 0;
109 for (int i = 0; (cmp == 0) && (i < cnt); i++) {
110
111 cmp = ((Comparable ) contents1.get(i)).compareTo(contents2.get(i));
112
113 }
114 return cmp;
115 }
116 }
117
118 ElementType[] subArray(int start, int end, ElementType[] original) {
120 int size = end - start + 1;
121 ElementType[] ret = new ElementType[size];
122 for (int i = 0; i < size; i++)
123 ret[i] = original[i + start];
124 return ret;
125 }
126
127 Node nodeFromCollection(ElementType[] collection) {
129 int size = collection.length;
130 if (size == 0) return null;
131 int split = size / 2;
132 Node ret = new Node(collection[split]);
133 ret.left = nodeFromCollection(subArray(0, split - 1, collection));
134 ret.right = nodeFromCollection(subArray(split + 1, size - 1, collection));
135 return ret;
136 }
137
138 Node top = null;
139 ElementType.Factory elementFactory;
140
141 public void addNode(ElementType value) {
142 }
145
146 public GraphType(int size, ElementType.Factory factory) {
147 elementFactory = factory;
148 ElementType[] contents = new ElementType[size];
149 for (int i = 0; i < size; i++)
150 contents[i] = elementFactory.create();
151 Arrays.sort(contents);
152 top = nodeFromCollection(contents);
153 }
154
155 void traverse(Node node) {
156 if (node != null) {
157 traverse(node.left);
158 node.value.traverse();
159 traverse(node.right);
160 }
161 }
162
163 public void traverse() {
164 traverse(top);
165 }
166 }
167
168 public class WrappedComparable implements ElementType {
170 Comparable wrapped;
171
172 public Comparable getWrapped() {
173 return wrapped;
174 }
175
176 public WrappedComparable(Comparable c) {
177 wrapped = c;
178 }
179
180 public void traverse() {
181 }
183
184 public int compareTo(Object other) {
185 return (other instanceof WrappedComparable) ? ((WrappedComparable) other).getWrapped().compareTo(wrapped) : 0;
186 }
187 }
188
189 }
190 |
Popular Tags |
Java API By Example, From Geeks To Geeks.