001: /*
002: * Helma License Notice
003: *
004: * The contents of this file are subject to the Helma License
005: * Version 2.0 (the "License"). You may not use this file except in
006: * compliance with the License. A copy of the License is available at
007: * http://adele.helma.org/download/helma/license.txt
008: *
009: * Copyright 1998-2003 Helma Software. All Rights Reserved.
010: *
011: * $RCSfile$
012: * $Author: root $
013: * $Revision: 8604 $
014: * $Date: 2007-09-28 15:16:38 +0200 (Fre, 28 Sep 2007) $
015: */
016: package helma.objectmodel.db;
017:
018: import java.util.Collection;
019: import java.util.HashMap;
020: import java.util.Iterator;
021: import java.util.List;
022:
023: /**
024: * @author manfred andres
025: * This subnode-collection may be used to add nodes in an ordered way depending on
026: * the given order. It is also possible to retrieve views of this list in a different
027: * order. These views will be cached and automatically updated if this List's add-
028: * or remove-methods are called.
029: */
030: public class OrderedSubnodeList extends SubnodeList {
031:
032: // the base subnode list, in case this is an ordered view
033: private SubnodeList origin;
034: // an array containing the order-fields
035: private String orderProperties[];
036: // an array containing the direction for ordering
037: private boolean orderIsDesc[];
038:
039: /**
040: * Construct a new OrderedSubnodeList. The Relation is needed
041: * to get the information about the ORDERING
042: */
043: public OrderedSubnodeList(WrappedNodeManager nmgr, Relation rel) {
044: super (nmgr, rel);
045: this .origin = null;
046: // check the order of this collection for automatically sorting
047: // in the values in the correct order
048: initOrder(rel.order);
049: }
050:
051: /**
052: * This constructor is used to create a view for the OrderedSubnodeList origin.
053: * @param origin the origin-list which holds the elements
054: * @param expr the new order for this view
055: * @param rel the relation given for the origin-list
056: */
057: public OrderedSubnodeList(WrappedNodeManager nmgr, Relation rel,
058: SubnodeList origin, String expr) {
059: super (nmgr, rel);
060: this .origin = origin;
061: initOrder(expr);
062: if (origin != null) {
063: sortIn(origin, false);
064: }
065: }
066:
067: private void initOrder(String order) {
068: if (order == null) {
069: orderProperties = null;
070: orderIsDesc = null;
071: } else {
072: String orderParts[] = order.split(",");
073: orderProperties = new String[orderParts.length];
074: orderIsDesc = new boolean[orderParts.length];
075: for (int i = 0; i < orderParts.length; i++) {
076: String part[] = orderParts[i].trim().split(" ");
077: orderProperties[i] = part[0].equals("_id") ? null
078: : part[0];
079: orderIsDesc[i] = part.length == 2
080: && "DESC".equalsIgnoreCase(part[1]);
081: }
082: }
083: }
084:
085: /**
086: * Adds the specified object to this list performing
087: * custom ordering
088: *
089: * @param obj element to be inserted.
090: */
091: public boolean add(Object obj) {
092: return add(obj, true);
093: }
094:
095: /**
096: * Adds the specified object to the list at the given position
097: * @param idx the index to insert the element at
098: * @param obj the object t add
099: */
100: public void add(int idx, Object obj) {
101: if (this .orderProperties != null)
102: throw new RuntimeException(
103: "Indexed add isn't alowed for ordered subnodes");
104: super .add(idx, obj);
105: addToViews(obj);
106: }
107:
108: /**
109: * Adds the specified object to this list without performing
110: * custom ordering.
111: *
112: * @param obj element to be inserted.
113: */
114: public boolean addSorted(Object obj) {
115: return add(obj, false);
116: }
117:
118: boolean add(Object obj, boolean sort) {
119: if (origin != null) {
120: return origin.add(obj);
121: }
122: addToViews(obj);
123: int maxSize = rel == null ? 0 : rel.maxSize;
124: while (maxSize > 0 && this .size() >= maxSize) {
125: remove(size() - 1);
126: }
127: // escape sorting for presorted adds and grouped nodes
128: if (sort && (rel == null || rel.groupby == null)) {
129: sortIn(obj);
130: } else {
131: super .add(obj);
132: }
133: return true;
134: }
135:
136: /**
137: * add a new node honoring the Nodes SQL-Order
138: * @param obj the object to add
139: */
140: public boolean sortIn(Object obj) {
141: // no order, just add
142: if (this .orderProperties == null)
143: return super .add(obj);
144: addToViews(obj);
145: Node node = ((NodeHandle) obj).getNode(nmgr);
146: int idx = this .determineNodePosition(node, 0);
147: // System.err.println("Position: " + idx);
148: if (idx < 0)
149: return super .add(obj);
150: else
151: super .add(idx, obj);
152: return true;
153: }
154:
155: public boolean addAll(Collection col) {
156: return sortIn(col, true) > 0;
157: }
158:
159: private void addAllToViews(Collection col) {
160: if (views == null || origin != null || views.isEmpty())
161: return;
162: for (Iterator i = views.values().iterator(); i.hasNext();) {
163: OrderedSubnodeList osl = (OrderedSubnodeList) i.next();
164: osl.addAll(col);
165: }
166: }
167:
168: /**
169: * Add all nodes contained inside the specified Collection to this
170: * UpdateableSubnodeList. The order of the added Nodes is assumed to
171: * be ordered according to the SQL-Order-Clause given for this
172: * Subnode collection but doesn't prevent adding of unordered Collections.
173: * Ordered Collections will be sorted in more efficiently than unordered ones.
174: *
175: * @param col the collection containing all elements to add in the order returned by the select-statement
176: * @param colHasDefaultOrder true if the given collection does have the default-order defined by the relation
177: */
178: public int sortIn(Collection col, boolean colHasDefaultOrder) {
179: addAllToViews(col);
180: int cntr = 0;
181: // there is no order specified, add on top
182: if (orderProperties == null) {
183: for (Iterator i = col.iterator(); i.hasNext();) {
184: super .add(cntr, i.next());
185: cntr++;
186: }
187: int maxSize = rel == null ? 0 : rel.maxSize;
188: if (maxSize > 0) {
189: int diff = this .size() - maxSize;
190: if (diff > 0)
191: super .removeRange(this .size() - 1 - diff, this
192: .size() - 1);
193: }
194: } else if (!colHasDefaultOrder || origin != null) {
195: // this collection is a view or the given collection doesn't have the
196: // default order
197: for (Iterator i = col.iterator(); i.hasNext();) {
198: Object obj = i.next();
199: if (obj == null)
200: continue;
201: sortIn(obj);
202: cntr++;
203: }
204: } else {
205: NodeHandle[] nhArr = (NodeHandle[]) col
206: .toArray(new NodeHandle[0]);
207: Node node = nhArr[0].getNode(nmgr);
208: int locIdx = determineNodePosition(node, 0); // determine start-point
209: if (locIdx == -1)
210: locIdx = this .size();
211: // int interval=Math.max(1, this.size()/2);
212: for (int addIdx = 0; addIdx < nhArr.length; addIdx++) {
213: node = nhArr[addIdx].getNode(nmgr);
214: while (locIdx < this .size()
215: && compareNodes(node, (NodeHandle) this
216: .get(locIdx)) >= 0)
217: locIdx++;
218: if (locIdx < this .size()) {
219: this .add(locIdx, nhArr[addIdx]);
220: } else {
221: this .add(nhArr[addIdx]);
222: }
223: cntr++;
224: }
225: }
226: return cntr;
227: }
228:
229: /**
230: * remove all elements contained inside the specified collection
231: * from this List
232: * @param c the Collection containing all Objects to remove from this List
233: * @return true if the List has been modified
234: */
235: public boolean removeAll(Collection c) {
236: removeAllFromViews(c);
237: return super .removeAll(c);
238: }
239:
240: private void removeAllFromViews(Collection c) {
241: if (views == null || origin != null || views.isEmpty())
242: return;
243: for (Iterator i = views.values().iterator(); i.hasNext();) {
244: OrderedSubnodeList osl = (OrderedSubnodeList) i.next();
245: osl.removeAll(c);
246: }
247: }
248:
249: /**
250: * remove all elements from this List, which are NOT specified
251: * inside the specified Collecion
252: * @param c the Collection containing all Objects to keep on the List
253: * @return true if the List has been modified
254: */
255: public boolean retainAll(Collection c) {
256: retainAllInViews(c);
257: return super .retainAll(c);
258: }
259:
260: private void retainAllInViews(Collection c) {
261: if (views == null || origin != null || views.isEmpty())
262: return;
263: for (Iterator i = views.values().iterator(); i.hasNext();) {
264: OrderedSubnodeList osl = (OrderedSubnodeList) i.next();
265: osl.retainAll(c);
266: }
267: }
268:
269: private int determineNodePosition(Node node, int startIdx) {
270: int size = this .size();
271: int interval = Math.max(1, (size - startIdx) / 2);
272: boolean dirUp = true;
273: int cntr = 0;
274: int maxSize = rel == null ? 0 : rel.maxSize;
275: for (int i = 0; i < size && (i < maxSize || maxSize <= 0)
276: && cntr < (size * 2); cntr++) { // cntr is used to avoid endless-loops which shouldn't happen
277: NodeHandle curr = (NodeHandle) this .get(i);
278: int comp = compareNodes(node, curr);
279: // current NodeHandle is below the given NodeHandle
280: // interval has to be 1 and
281: // idx must be zero or the node before the current node must be higher or equal
282: // all conditions must be met to determine the correct position of a node
283: if (comp < 0
284: && interval == 1
285: && (i == 0 || compareNodes(node, (NodeHandle) this
286: .get(i - 1)) >= 0)) {
287: return i;
288: } else if (comp < 0) {
289: dirUp = false;
290: } else if (comp > 0) {
291: dirUp = true;
292: } else if (comp == 0) {
293: dirUp = true;
294: interval = 1;
295: }
296: if (dirUp) {
297: i = i + interval;
298: if (i >= this .size()) {
299: if (compareNodes(node, (NodeHandle) this
300: .get(size - 1)) >= 0)
301: break;
302: interval = Math.max(1, (i - size - 1) / 2);
303: i = this .size() - 1;
304: } else {
305: interval = Math.max(1, interval / 2);
306: }
307: } else {
308: i = i - interval;
309: if (i < 0) { // shouldn't happen i think
310: interval = Math.max(1, (interval + i) / 2);
311: i = 0;
312: }
313: }
314:
315: }
316: if (cntr >= size * 2 && size > 1) {
317: System.err
318: .println("determineNodePosition needed more than the allowed iterations");
319: }
320: return -1;
321: }
322:
323: /**
324: * Compare two nodes depending on the specified ORDER for this collection.
325: * @param node the first Node
326: * @param nodeHandle the second Node
327: * @return an integer lesser than zero if nh1 is less than, zero if nh1 is equal to and a value greater than zero if nh1 is bigger than nh2.
328: */
329: private int compareNodes(Node node, NodeHandle nodeHandle) {
330: for (int i = 0; i < orderProperties.length; i++) {
331: if (orderProperties[i] == null) {
332: // we have the id as order-criteria-> avoid loading node
333: // and compare numerically instead of lexicographically
334: String s1 = node.getID();
335: String s2 = nodeHandle.getID();
336: int j = compareNumericString(s1, s2);
337: if (j == 0)
338: continue;
339: if (orderIsDesc[i])
340: j = j * -1;
341: return j;
342: }
343: Property p1 = node.getProperty(orderProperties[i]);
344: Property p2 = nodeHandle.getNode(nmgr).getProperty(
345: orderProperties[i]);
346: int j;
347: if (p1 == null && p2 == null) {
348: continue;
349: } else if (p1 == null) {
350: j = 1;
351: } else if (p2 == null) {
352: j = -1;
353: } else {
354: j = p1.compareTo(p2);
355: }
356: if (j == 0) {
357: continue;
358: }
359: if (orderIsDesc[i]) {
360: j = j * -1;
361: }
362: return j;
363: }
364: return -1;
365: }
366:
367: /**
368: * Compare two strings containing numbers depending on their numeric values
369: * instead of doing a lexicographical comparison.
370: * @param a the first String
371: * @param b the second String
372: */
373: public static int compareNumericString(String a, String b) {
374: if (a == null && b != null)
375: return -1;
376: if (a != null && b == null)
377: return 1;
378: if (a == null && b == null)
379: return 0;
380: if (a.length() < b.length())
381: return -1;
382: if (a.length() > b.length())
383: return 1;
384: for (int i = 0; i < a.length(); i++) {
385: if (a.charAt(i) < b.charAt(i))
386: return -1;
387: if (a.charAt(i) > b.charAt(i))
388: return 1;
389: }
390: return 0;
391: }
392:
393: public List getOrderedView(String order) {
394: if (origin != null) {
395: return origin.getOrderedView(order);
396: } else {
397: return super.getOrderedView(order);
398: }
399: }
400: }
|