001: /*
002: * $Id: NameTree.java,v 1.2 2007/12/20 18:17:41 rbair Exp $
003: *
004: * Copyright 2004 Sun Microsystems, Inc., 4150 Network Circle,
005: * Santa Clara, California 95054, U.S.A. All rights reserved.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation; either
010: * version 2.1 of the License, or (at your option) any later version.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: *
017: * You should have received a copy of the GNU Lesser General Public
018: * License along with this library; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
020: */
021:
022: package com.sun.pdfview;
023:
024: import java.io.IOException;
025:
026: /**
027: * A PDF name tree consists of three kinds of nodes:
028: * <ul>
029: * <li> The root node contains only a kids entry, pointing to many
030: * other objects
031: * <li> An intermediate node contains the limits of all the children in
032: * its subtree, and a kids entry for each child
033: * <li> A leaf node contains a set of name-to-object mappings in a dictionary,
034: * as well as the limits of the data contained in that child.
035: * </ul>
036: * A PDF name tree is sorted in accordance with the String.compareTo() method.
037: */
038: public class NameTree {
039: /** the root object */
040: private PDFObject root;
041:
042: /** Creates a new instance of NameTree */
043: public NameTree(PDFObject root) {
044: this .root = root;
045: }
046:
047: /**
048: * Find the PDF object corresponding to the given String in a name tree
049: *
050: * @param key the key we are looking for in the name tree
051: * @return the object associated with str, if found, or null if not
052: */
053: public PDFObject find(String key) throws IOException {
054: return find(root, key);
055: }
056:
057: /**
058: * Recursively walk the name tree looking for a given value
059: */
060: private PDFObject find(PDFObject root, String key)
061: throws IOException {
062: // first, look for a Names entry, meaning this is a leaf
063: PDFObject names = root.getDictRef("Names");
064: if (names != null) {
065: return findInArray(names.getArray(), key);
066: }
067:
068: // no names given, look for kids
069: PDFObject kidsObj = root.getDictRef("Kids");
070: if (kidsObj != null) {
071: PDFObject[] kids = kidsObj.getArray();
072:
073: for (int i = 0; i < kids.length; i++) {
074: // find the limits of this kid
075: PDFObject limitsObj = kids[i].getDictRef("Limits");
076: if (limitsObj != null) {
077: String lowerLimit = limitsObj.getAt(0)
078: .getStringValue();
079: String upperLimit = limitsObj.getAt(1)
080: .getStringValue();
081:
082: // are we in range?
083: if ((key.compareTo(lowerLimit) >= 0)
084: && (key.compareTo(upperLimit) <= 0)) {
085:
086: // we are, so find in this child
087: return find(kids[i], key);
088: }
089: }
090: }
091: }
092:
093: // no luck
094: return null;
095: }
096:
097: /**
098: * Find an object in a (key,value) array. Do this by splitting in half
099: * repeatedly.
100: */
101: private PDFObject findInArray(PDFObject[] array, String key)
102: throws IOException {
103: int start = 0;
104: int end = array.length / 2;
105:
106: while (end >= start && start >= 0 && end < array.length) {
107: // find the key at the midpoint
108: int pos = start + ((end - start) / 2);
109: String posKey = array[pos * 2].getStringValue();
110:
111: // compare the key to the key we are looking for
112: int comp = key.compareTo(posKey);
113: if (comp == 0) {
114: // they match. Return the value
115: return array[(pos * 2) + 1];
116: } else if (comp > 0) {
117: // too big, search the top half of the tree
118: start = pos + 1;
119: } else if (comp < 0) {
120: // too small, search the bottom half of the tree
121: end = pos - 1;
122: }
123: }
124:
125: // not found
126: return null;
127: }
128:
129: }
|