001: /*
002: * Copyright (c) 2007, intarsys consulting GmbH
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * - Redistributions of source code must retain the above copyright notice,
008: * this list of conditions and the following disclaimer.
009: *
010: * - Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * - Neither the name of intarsys nor the names of its contributors may be used
015: * to endorse or promote products derived from this software without specific
016: * prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
022: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
028: * POSSIBILITY OF SUCH DAMAGE.
029: */
030: package de.intarsys.pdf.cds;
031:
032: import java.util.ArrayList;
033: import java.util.Iterator;
034: import java.util.List;
035: import java.util.NoSuchElementException;
036:
037: import de.intarsys.pdf.cos.COSArray;
038: import de.intarsys.pdf.cos.COSDictionary;
039: import de.intarsys.pdf.cos.COSName;
040: import de.intarsys.pdf.cos.COSNull;
041: import de.intarsys.pdf.cos.COSObject;
042: import de.intarsys.pdf.cos.COSString;
043: import de.intarsys.tools.collection.EmptyIterator;
044:
045: /**
046: * Implementation of the PDF name tree.
047: *
048: */
049: public class CDSNameTreeNode extends CDSTreeNode {
050: // todo 2 rewrite to META
051:
052: static public final COSName DK_Names = COSName.constant("Names"); //$NON-NLS-1$
053:
054: /**
055: * Create the correct concrete CDSTreeNode implementation for
056: * <code>node</code>.
057: *
058: * @param node
059: * The {@link COSDictionary} defining a CDSTreeNode subclass
060: * instance
061: *
062: * @return The concrete CDSTreeNode implementation for <code>node</code>.
063: */
064: static public CDSNameTreeNode createFromCos(COSDictionary node) {
065: if (node == null) {
066: return null;
067: }
068: return new CDSNameTreeNode(node);
069: }
070:
071: static public CDSNameTreeNode createRootIntermediate() {
072: CDSNameTreeNode result = new CDSNameTreeNode(COSDictionary
073: .create());
074: result.createKids();
075: return result;
076: }
077:
078: static public CDSNameTreeNode createRootLeaf() {
079: CDSNameTreeNode result = new CDSNameTreeNode(COSDictionary
080: .create());
081: result.createNames();
082: return result;
083: }
084:
085: static public CDSTreeNode createIntermediate() {
086: CDSNameTreeNode result = new CDSNameTreeNode(COSDictionary
087: .create());
088: result.createLimits();
089: result.createKids();
090: return result;
091: }
092:
093: static public CDSNameTreeNode createLeaf() {
094: CDSNameTreeNode result = new CDSNameTreeNode(COSDictionary
095: .create());
096: result.createLimits();
097: result.createNames();
098: return result;
099: }
100:
101: public List getKids() {
102: if (kids == null) {
103: COSArray cosKids = cosGetDict().get(DK_Kids).asArray();
104: if (cosKids != null) {
105: kids = new ArrayList();
106: for (Iterator i = cosKids.iterator(); i.hasNext();) {
107: COSDictionary dict = ((COSObject) i.next())
108: .asDictionary();
109: if (dict != null) {
110: CDSTreeNode kid = CDSNameTreeNode
111: .createFromCos(dict);
112: kids.add(kid);
113: }
114: }
115: }
116: }
117: return kids;
118: }
119:
120: /**
121: * Create an initial value for the /Kids entry
122: */
123: protected void createKids() {
124: COSArray array = COSArray.create();
125: cosGetDict().put(DK_Kids, array);
126: }
127:
128: /**
129: * Create an initial value for the /Names entry
130: */
131: protected void createNames() {
132: COSArray array = COSArray.create();
133: cosGetDict().put(DK_Names, array);
134: }
135:
136: /**
137: * Create a CDSTreeNode based on the {@link COSDictionary}<code>
138: * dict</code>.
139: *
140: * @param dict
141: * The{@link COSDictionary} defining the receiver.
142: */
143: protected CDSNameTreeNode(COSDictionary dict) {
144: super (dict);
145: }
146:
147: /**
148: * Add all children from <code>node</code>.
149: *
150: * @param node
151: * A {@link CDSNameTreeNode} whose children are copied.
152: */
153: public void addAll(CDSNameTreeNode node) {
154: for (Iterator i = node.iterator(); i.hasNext();) {
155: CDSNameTreeEntry entry = (CDSNameTreeEntry) i.next();
156: COSString name = (COSString) entry.getName().copyOptional();
157: COSObject value = entry.getValue().copyOptional();
158: put(name, value);
159: }
160: }
161:
162: /**
163: * Answer <code>true</code> if the receiver subtree contains a key that
164: * matches the parameter.
165: *
166: * @param name
167: * The key that is searched in the receiver subtree.
168: *
169: * @return Answer <code>true</code> if the receiver subtree contains a key
170: * that matches the parameter.
171: */
172: public boolean contains(COSString name) {
173: if (!mayContain(name)) {
174: return false;
175: }
176: List tempKids = getKids();
177: if (tempKids != null) {
178: for (Iterator i = tempKids.iterator(); i.hasNext();) {
179: CDSNameTreeNode node = (CDSNameTreeNode) i.next();
180: if (node.contains(name)) {
181: return true;
182: }
183: }
184: return false;
185: }
186: List tempEntries = getEntries();
187: if (tempEntries != null) {
188: for (Iterator i = tempEntries.iterator(); i.hasNext();) {
189: CDSNameTreeEntry entry = (CDSNameTreeEntry) i.next();
190: int c = entry.getName().compareTo(name);
191: if (c == 0) {
192: return true;
193: }
194: if (c > 0) {
195: return false;
196: }
197: }
198: }
199: return false;
200: }
201:
202: /**
203: * Create an initial value for the limits of the receiver subtree.
204: */
205: protected void createLimits() {
206: COSArray array = COSArray.create(2);
207: array.add(COSNull.create());
208: array.add(COSNull.create());
209: cosGetDict().put(DK_Limits, array);
210: }
211:
212: /**
213: * Answer the value associated with the key <code>name</code>. If no key
214: * is available that matches the parameter, <code>COSNull</code> is
215: * returned.
216: *
217: * @param name
218: * The key whose value is looked up.
219: *
220: * @return Answer the value associated with the key <code>name</code>.
221: */
222: public COSObject get(COSString name) {
223: if (!mayContain(name)) {
224: return COSNull.NULL;
225: }
226: List tempKids = getKids();
227: if (tempKids != null) {
228: for (Iterator i = tempKids.iterator(); i.hasNext();) {
229: CDSNameTreeNode node = (CDSNameTreeNode) i.next();
230: COSObject result = node.get(name);
231: if (!result.isNull()) {
232: return result;
233: }
234: }
235: return COSNull.NULL;
236: }
237: List tempEntries = getEntries();
238: if (tempEntries != null) {
239: for (Iterator i = tempEntries.iterator(); i.hasNext();) {
240: CDSNameTreeEntry entry = (CDSNameTreeEntry) i.next();
241: int c = entry.getName().compareTo(name);
242: if (c == 0) {
243: return entry.getValue();
244: }
245: if (c > 0) {
246: return COSNull.NULL;
247: }
248: }
249: }
250: return COSNull.NULL;
251: }
252:
253: /**
254: * Return the two element array containing the smallest and the largest key
255: * within the receiver subtree.
256: *
257: * @return Return the two element array containing the smallest and the
258: * largest key within the receiver subtree.
259: */
260: public COSArray getLimits() {
261: if (limits == null) {
262: limits = cosGetDict().get(DK_Limits).asArray();
263: }
264: return limits;
265: }
266:
267: /**
268: * The maximum key within the receiver subtree.
269: *
270: * @return The maximum key within the receiver subtree.
271: */
272: public COSString getMax() {
273: if (getLimits() != null) {
274: return getLimits().get(1).asString();
275: }
276: return null;
277: }
278:
279: /**
280: * The minimum key within the receiver subtree.
281: *
282: * @return The minimum key within the receiver subtree.
283: */
284: public COSString getMin() {
285: if (getLimits() != null) {
286: return getLimits().get(0).asString();
287: }
288: return null;
289: }
290:
291: /**
292: * An {@link Iterator} on all leaf fields in the subtree.
293: *
294: * @return An {@link Iterator} on all leaf fields in the subtree.
295: */
296: public Iterator iterator() {
297: List tempKids = getKids();
298: if (tempKids != null) {
299: return new Iterator() {
300: private Iterator this Iterator = getKids().iterator();
301:
302: private Iterator childIterator;
303:
304: public void remove() {
305: throw new UnsupportedOperationException();
306: }
307:
308: public boolean hasNext() {
309: if ((childIterator != null)
310: && childIterator.hasNext()) {
311: return true;
312: }
313: if (this Iterator.hasNext()) {
314: CDSNameTreeNode current = (CDSNameTreeNode) this Iterator
315: .next();
316: childIterator = current.iterator();
317: return hasNext();
318: }
319: return false;
320: }
321:
322: public Object next() {
323: if ((childIterator != null)
324: && childIterator.hasNext()) {
325: return childIterator.next();
326: }
327: if (this Iterator.hasNext()) {
328: CDSNameTreeNode current = (CDSNameTreeNode) this Iterator
329: .next();
330: childIterator = current.iterator();
331: return next();
332: }
333: throw new NoSuchElementException();
334: }
335: };
336: }
337: List tempEntries = getEntries();
338: if (tempEntries != null) {
339: return tempEntries.iterator();
340: }
341: return EmptyIterator.UNIQUE;
342: }
343:
344: /**
345: * Answer <code>true</code> if the receiver MAY contain the key
346: * <code>name</code>.
347: *
348: * <p>
349: * Thi means, <code>name</code> lies between the range defined by the
350: * lower und upper limit key of the receiver.
351: * </p>
352: *
353: * @param name
354: * The key name to lookup.
355: *
356: * @return Answer <code>true</code> if the receiver MAY contain the key
357: * <code>name</code>.
358: */
359: public boolean mayContain(COSString name) {
360: if ((getMin() == null) || (getMax() == null)) {
361: return true;
362: }
363: if (name.compareTo(getMin()) < 0) {
364: return false;
365: }
366: if (name.compareTo(getMax()) > 0) {
367: return false;
368: }
369: return true;
370: }
371:
372: /**
373: * Store <code>value</code> under the key given in <code>name</code>.
374: *
375: * @param name
376: * The name with wich the value should be associated.
377: * @param value
378: * The value to associate with the name.
379: * @return The object previously associated with <code>name</code> or
380: * {@link COSNull}.
381: */
382: public COSObject put(COSString name, COSObject value) {
383: COSObject result = COSNull.NULL;
384: List tempKids = getKids();
385: if (tempKids != null) {
386: CDSNameTreeNode insertNode = null;
387: for (Iterator i = tempKids.iterator(); i.hasNext();) {
388: CDSNameTreeNode node = (CDSNameTreeNode) i.next();
389: insertNode = node;
390: if (node.getMax().compareTo(name) > 0) {
391: break;
392: }
393: }
394: if (insertNode == null) {
395: // no suitable kid found - create new
396: // todo this algorithm is quite simple....
397: insertNode = CDSNameTreeNode.createLeaf();
398: getKids().add(insertNode);
399: COSArray cosKids = cosGetDict().get(DK_Kids).asArray();
400: cosKids.add(insertNode.cosGetObject());
401: }
402: insertNode.put(name, value);
403: updateLimits();
404: return result;
405: }
406: List tempEntries = getEntries();
407: if (tempEntries != null) {
408: int index = 0;
409: for (Iterator i = tempEntries.iterator(); i.hasNext();) {
410: CDSNameTreeEntry entry = (CDSNameTreeEntry) i.next();
411: int c = entry.getName().compareTo(name);
412: if (c == 0) {
413: return entry.setValue(value);
414: }
415: if (c > 0) {
416: break;
417: }
418: index++;
419: }
420: CDSTreeEntry entry = new CDSNameTreeEntry(name, value);
421: tempEntries.add(index, entry);
422: COSArray cosEntries = cosGetDict().get(DK_Names).asArray();
423: int entryIndex = index * 2;
424: cosEntries.add(entryIndex, value);
425: cosEntries.add(entryIndex, name);
426: updateLimits();
427: return COSNull.NULL;
428: }
429: // ooops - should we create a /Names entry?
430: return result;
431: }
432:
433: /**
434: * Remove the mapping for key given in <code>name</code>.
435: *
436: * @param name
437: * The name fo the mapping to be removed
438: * @return The object previously associated with <code>name</code> or
439: * {@link COSNull}.
440: */
441: public COSObject remove(COSString name) {
442: List tempKids = getKids();
443: if (tempKids != null) {
444: for (Iterator i = tempKids.iterator(); i.hasNext();) {
445: CDSNameTreeNode node = (CDSNameTreeNode) i.next();
446: if (node.getMax().compareTo(name) > 0) {
447: COSObject result = node.remove(name);
448: updateLimits();
449: return result;
450: }
451: }
452: return COSNull.NULL;
453: }
454: List tempEntries = getEntries();
455: if (tempEntries != null) {
456: int index = 0;
457: for (Iterator it = tempEntries.iterator(); it.hasNext();) {
458: CDSNameTreeEntry entry = (CDSNameTreeEntry) it.next();
459: int c = entry.getName().compareTo(name);
460: if (c == 0) {
461: it.remove();
462: COSArray cosEntries = cosGetDict().get(DK_Names)
463: .asArray();
464: int entryIndex = index * 2;
465: cosEntries.remove(entryIndex);
466: cosEntries.remove(entryIndex);
467: COSObject result = (COSObject) entry.getValue();
468: updateLimits();
469: return result;
470: }
471: if (c > 0) {
472: break;
473: }
474: index++;
475: }
476: return COSNull.NULL;
477: }
478: return COSNull.NULL;
479: }
480:
481: public boolean isLeaf() {
482: return cosGetDict().containsKey(DK_Names);
483: }
484:
485: public List getEntries() {
486: if (entries == null) {
487: COSArray cosNames = cosGetDict().get(DK_Names).asArray();
488: if (cosNames != null) {
489: entries = new ArrayList();
490: for (Iterator i = cosNames.iterator(); i.hasNext();) {
491: COSString name = ((COSObject) i.next()).asString();
492: if (!i.hasNext()) {
493: break;
494: }
495: COSObject value = (COSObject) i.next();
496: if (name != null) {
497: CDSTreeEntry entry = new CDSNameTreeEntry(name,
498: value);
499: entries.add(entry);
500: }
501: }
502: }
503: }
504: return entries;
505: }
506:
507: protected void checkLimits() {
508: if (getLimits() == null || getLimits().size() != 2) {
509: createLimits();
510: updateLimits();
511: }
512: }
513:
514: protected void updateLimits() {
515: if (getLimits() == null) {
516: return;
517: }
518: List tempKids = getKids();
519: if (tempKids != null) {
520: if (tempKids.size() > 0) {
521: CDSNameTreeNode minNode = (CDSNameTreeNode) tempKids
522: .get(0);
523: minNode.checkLimits();
524: getLimits().set(0,
525: minNode.getLimits().get(0).copyOptional());
526: CDSNameTreeNode maxNode = (CDSNameTreeNode) tempKids
527: .get(tempKids.size() - 1);
528: maxNode.checkLimits();
529: getLimits().set(1,
530: maxNode.getLimits().get(1).copyOptional());
531: }
532: }
533: List tempEntries = getEntries();
534: if (tempEntries != null) {
535: if (tempEntries.size() > 0) {
536: CDSNameTreeEntry minEntry = (CDSNameTreeEntry) tempEntries
537: .get(0);
538: getLimits().set(0, minEntry.getName().copyOptional());
539: CDSNameTreeEntry maxEntry = (CDSNameTreeEntry) tempEntries
540: .get(tempEntries.size() - 1);
541: getLimits().set(1, maxEntry.getName().copyOptional());
542: }
543: }
544: }
545: }
|