001: /*
002: * Copyright 2004-2007 Gary Bentley
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may
005: * not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: * http://www.apache.org/licenses/LICENSE-2.0
008: *
009: * Unless required by applicable law or agreed to in writing, software
010: * distributed under the License is distributed on an "AS IS" BASIS,
011: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
012: * See the License for the specific language governing permissions and
013: * limitations under the License.
014: */
015: package org.josql.incubator;
016:
017: import java.util.List;
018: import java.util.ArrayList;
019: import java.util.Comparator;
020: import java.util.Collections;
021:
022: import com.gentlyweb.utils.Getter;
023:
024: /**
025: * This is an experimental class aimed at producing an index across a
026: * collection of homogeneous objects. It should be noted here that it is the "sorting"
027: * of the elements in the List of objects that takes nearly all the time here.
028: * Use the {@link #sort()} method yourself to only perform sort once. Everytime you
029: * add an object however the sort status of the List of objects will be invalidated and
030: * have to be re-sorted before you have retrieve the objects again.
031: */
032: public class ObjectIndex implements Comparator {
033:
034: private List objs = new ArrayList();
035: private List indices = new ArrayList();
036: private Class c = null;
037: private int size = -1;
038: private boolean dirty = false;
039: private boolean syncOnAdd = false;
040:
041: public ObjectIndex(Class c) {
042:
043: this .c = c;
044:
045: }
046:
047: public boolean isSyncOnAdd() {
048:
049: return this .syncOnAdd;
050:
051: }
052:
053: public void setSyncOnAdd(boolean v) {
054:
055: this .syncOnAdd = v;
056:
057: }
058:
059: public List getObjects(List keys) {
060:
061: if (this .dirty) {
062:
063: Collections.sort(this .objs, this );
064:
065: this .dirty = false;
066:
067: }
068:
069: List res = new ArrayList();
070:
071: int low = 0;
072: int os1 = this .objs.size() - 1;
073:
074: int high = os1;
075:
076: while (low <= high) {
077:
078: int mid = (low + high) / 2;
079:
080: Object o = this .objs.get(mid);
081:
082: int r = this .compare(o, keys);
083:
084: if (r != 0) {
085:
086: // They are not equal, so now determine whether we go "up" or "down".
087: if (r < 0) {
088:
089: low = mid + 1;
090:
091: } else {
092:
093: high = mid - 1;
094:
095: }
096:
097: } else {
098:
099: // Add it to the list...
100: res.add(o);
101:
102: int oi = mid;
103:
104: // Now we need to check either side for others that may
105: // match.
106: while (mid < os1) {
107:
108: mid++;
109:
110: o = this .objs.get(mid);
111:
112: r = this .compare(o, keys);
113:
114: if (r == 0) {
115:
116: res.add(o);
117:
118: } else {
119:
120: // Not equal...
121: break;
122:
123: }
124:
125: }
126:
127: mid = oi;
128:
129: while (mid > -1) {
130:
131: mid--;
132:
133: o = this .objs.get(mid);
134:
135: r = this .compare(o, keys);
136:
137: if (r == 0) {
138:
139: res.add(o);
140:
141: } else {
142:
143: // Not equal...
144: break;
145:
146: }
147:
148: }
149:
150: // If we are here then we've got 'em all.
151: break;
152:
153: }
154:
155: }
156:
157: return res;
158:
159: }
160:
161: public int size() {
162:
163: return this .size;
164:
165: }
166:
167: public void sort() {
168:
169: Collections.sort(this .objs, this );
170:
171: this .dirty = false;
172:
173: }
174:
175: public void add(String name) {
176:
177: if (this .syncOnAdd) {
178:
179: Collections.sort(this .objs, this );
180:
181: this .dirty = false;
182:
183: } else {
184:
185: this .dirty = true;
186:
187: }
188:
189: this .indices.add(new Getter(name, this .c));
190:
191: }
192:
193: public void removeObject(Object o) {
194:
195: this .objs.remove(o);
196:
197: }
198:
199: public void addObject(Object o) {
200:
201: if (this .objs.contains(o)) {
202:
203: return;
204:
205: }
206:
207: if (this .syncOnAdd) {
208:
209: Collections.sort(this .objs, this );
210:
211: this .dirty = false;
212:
213: } else {
214:
215: this .dirty = true;
216:
217: }
218:
219: this .objs.add(o);
220:
221: this .size = this .objs.size();
222:
223: }
224:
225: public int compare(Object o, List keys) {
226:
227: try {
228:
229: int ks = keys.size();
230:
231: for (int i = 0; i < ks; i++) {
232:
233: Getter g = (Getter) this .indices.get(i);
234:
235: Object eo1 = g.getValue(o);
236:
237: Object kso = keys.get(i);
238:
239: // Can't compare what's not there, return 0.
240: if ((eo1 == null) || (kso == null)) {
241:
242: return 0;
243:
244: }
245:
246: int v = 0;
247:
248: if (eo1 instanceof Comparable) {
249:
250: // We can use a simple compareTo.
251: Comparable comp = (Comparable) eo1;
252:
253: v = comp.compareTo(kso);
254:
255: } else {
256:
257: v = eo1.toString().compareTo(kso.toString());
258:
259: }
260:
261: if (v != 0) {
262:
263: return v;
264:
265: }
266:
267: // They are equal, so need to go to the next field...
268: continue;
269:
270: }
271:
272: } catch (Exception e) {
273:
274: }
275:
276: // All equal.
277: return 0;
278:
279: }
280:
281: public int compare(Object o1, Object o2) {
282:
283: try {
284:
285: for (int i = 0; i < this .size; i++) {
286:
287: Getter g = (Getter) this .indices.get(i);
288:
289: Object eo1 = g.getValue(o1);
290:
291: Object eo2 = g.getValue(o2);
292:
293: // Can't compare what's not there, return 0.
294: if ((eo1 == null) || (eo2 == null)) {
295:
296: return 0;
297:
298: }
299:
300: int v = 0;
301:
302: if (eo1 instanceof Comparable) {
303:
304: // We can use a simple compareTo.
305: Comparable comp = (Comparable) eo1;
306:
307: v = comp.compareTo(eo2);
308:
309: } else {
310:
311: v = eo1.toString().compareTo(eo2.toString());
312:
313: }
314:
315: if (v != 0) {
316:
317: return v;
318:
319: }
320:
321: // They are equal, so need to go to the next field...
322: continue;
323:
324: }
325:
326: } catch (Exception e) {
327:
328: }
329:
330: // All equal.
331: return 0;
332:
333: }
334:
335: }
|