001/*
002 * $Id: PdfNameTree.java 4784 2011-03-15 08:33:00Z blowagie $
003 *
004 * This file is part of the iText (R) project.
005 * Copyright (c) 1998-2011 1T3XT BVBA
006 * Authors: Bruno Lowagie, Paulo Soares, et al.
007 *
008 * This program is free software; you can redistribute it and/or modify
009 * it under the terms of the GNU Affero General Public License version 3
010 * as published by the Free Software Foundation with the addition of the
011 * following permission added to Section 15 as permitted in Section 7(a):
012 * FOR ANY PART OF THE COVERED WORK IN WHICH THE COPYRIGHT IS OWNED BY 1T3XT,
013 * 1T3XT DISCLAIMS THE WARRANTY OF NON INFRINGEMENT OF THIRD PARTY RIGHTS.
014 *
015 * This program is distributed in the hope that it will be useful, but
016 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
017 * or FITNESS FOR A PARTICULAR PURPOSE.
018 * See the GNU Affero General Public License for more details.
019 * You should have received a copy of the GNU Affero General Public License
020 * along with this program; if not, see http://www.gnu.org/licenses or write to
021 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
022 * Boston, MA, 02110-1301 USA, or download the license from the following URL:
023 * http://itextpdf.com/terms-of-use/
024 *
025 * The interactive user interfaces in modified source and object code versions
026 * of this program must display Appropriate Legal Notices, as required under
027 * Section 5 of the GNU Affero General Public License.
028 *
029 * In accordance with Section 7(b) of the GNU Affero General Public License,
030 * a covered work must retain the producer line in every PDF that is created
031 * or manipulated using iText.
032 *
033 * You can be released from the requirements of the license by purchasing
034 * a commercial license. Buying such a license is mandatory as soon as you
035 * develop commercial activities involving the iText software without
036 * disclosing the source code of your own applications.
037 * These activities include: offering paid services to customers as an ASP,
038 * serving PDFs on the fly in a web application, shipping iText with a closed
039 * source product.
040 *
041 * For more information, please contact iText Software Corp. at this
042 * address: sales@itextpdf.com
043 */
044package com.itextpdf.text.pdf;
045
046import java.io.IOException;
047import java.util.Arrays;
048import java.util.HashMap;
049
050/**
051 * Creates a name tree.
052 * @author Paulo Soares
053 */
054public class PdfNameTree {
055
056    private static final int leafSize = 64;
057
058    /**
059     * Writes a name tree to a PdfWriter.
060     * @param items the item of the name tree. The key is a <CODE>String</CODE>
061     * and the value is a <CODE>PdfObject</CODE>. Note that although the
062     * keys are strings only the lower byte is used and no check is made for chars
063     * with the same lower byte and different upper byte. This will generate a wrong
064     * tree name.
065     * @param writer the writer
066     * @throws IOException on error
067     * @return the dictionary with the name tree. This dictionary is the one
068     * generally pointed to by the key /Dests, for example
069     */
070    public static PdfDictionary writeTree(HashMap<String, ? extends PdfObject> items, PdfWriter writer) throws IOException {
071        if (items.isEmpty())
072            return null;
073        String names[] = new String[items.size()];
074        names = items.keySet().toArray(names);
075        Arrays.sort(names);
076        if (names.length <= leafSize) {
077            PdfDictionary dic = new PdfDictionary();
078            PdfArray ar = new PdfArray();
079            for (int k = 0; k < names.length; ++k) {
080                ar.add(new PdfString(names[k], null));
081                ar.add(items.get(names[k]));
082            }
083            dic.put(PdfName.NAMES, ar);
084            return dic;
085        }
086        int skip = leafSize;
087        PdfIndirectReference kids[] = new PdfIndirectReference[(names.length + leafSize - 1) / leafSize];
088        for (int k = 0; k < kids.length; ++k) {
089            int offset = k * leafSize;
090            int end = Math.min(offset + leafSize, names.length);
091            PdfDictionary dic = new PdfDictionary();
092            PdfArray arr = new PdfArray();
093            arr.add(new PdfString(names[offset], null));
094            arr.add(new PdfString(names[end - 1], null));
095            dic.put(PdfName.LIMITS, arr);
096            arr = new PdfArray();
097            for (; offset < end; ++offset) {
098                arr.add(new PdfString(names[offset], null));
099                arr.add(items.get(names[offset]));
100            }
101            dic.put(PdfName.NAMES, arr);
102            kids[k] = writer.addToBody(dic).getIndirectReference();
103        }
104        int top = kids.length;
105        while (true) {
106            if (top <= leafSize) {
107                PdfArray arr = new PdfArray();
108                for (int k = 0; k < top; ++k)
109                    arr.add(kids[k]);
110                PdfDictionary dic = new PdfDictionary();
111                dic.put(PdfName.KIDS, arr);
112                return dic;
113            }
114            skip *= leafSize;
115            int tt = (names.length + skip - 1 )/ skip;
116            for (int k = 0; k < tt; ++k) {
117                int offset = k * leafSize;
118                int end = Math.min(offset + leafSize, top);
119                PdfDictionary dic = new PdfDictionary();
120                PdfArray arr = new PdfArray();
121                arr.add(new PdfString(names[k * skip], null));
122                arr.add(new PdfString(names[Math.min((k + 1) * skip, names.length) - 1], null));
123                dic.put(PdfName.LIMITS, arr);
124                arr = new PdfArray();
125                for (; offset < end; ++offset) {
126                    arr.add(kids[offset]);
127                }
128                dic.put(PdfName.KIDS, arr);
129                kids[k] = writer.addToBody(dic).getIndirectReference();
130            }
131            top = tt;
132        }
133    }
134
135    private static void iterateItems(PdfDictionary dic, HashMap<String, PdfObject> items) {
136        PdfArray nn = (PdfArray)PdfReader.getPdfObjectRelease(dic.get(PdfName.NAMES));
137        if (nn != null) {
138            for (int k = 0; k < nn.size(); ++k) {
139                PdfString s = (PdfString)PdfReader.getPdfObjectRelease(nn.getPdfObject(k++));
140                items.put(PdfEncodings.convertToString(s.getBytes(), null), nn.getPdfObject(k));
141            }
142        }
143        else if ((nn = (PdfArray)PdfReader.getPdfObjectRelease(dic.get(PdfName.KIDS))) != null) {
144            for (int k = 0; k < nn.size(); ++k) {
145                PdfDictionary kid = (PdfDictionary)PdfReader.getPdfObjectRelease(nn.getPdfObject(k));
146                iterateItems(kid, items);
147            }
148        }
149    }
150
151    public static HashMap<String, PdfObject> readTree(PdfDictionary dic) {
152        HashMap<String, PdfObject> items = new HashMap<String, PdfObject>();
153        if (dic != null)
154            iterateItems(dic, items);
155        return items;
156    }
157}