001/*
002 * $Id: PdfNumberTree.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 number tree.
052 * @author Paulo Soares
053 */
054public class PdfNumberTree {
055
056    private static final int leafSize = 64;
057
058    /**
059     * Creates a number tree.
060     * @param items the item of the number tree. The key is an <CODE>Integer</CODE>
061     * and the value is a <CODE>PdfObject</CODE>.
062     * @param writer the writer
063     * @throws IOException on error
064     * @return the dictionary with the number tree.
065     */
066    public static <O extends PdfObject> PdfDictionary writeTree(HashMap<Integer, O> items, PdfWriter writer) throws IOException {
067        if (items.isEmpty())
068            return null;
069        Integer numbers[] = new Integer[items.size()];
070        numbers = items.keySet().toArray(numbers);
071        Arrays.sort(numbers);
072        if (numbers.length <= leafSize) {
073            PdfDictionary dic = new PdfDictionary();
074            PdfArray ar = new PdfArray();
075            for (int k = 0; k < numbers.length; ++k) {
076                ar.add(new PdfNumber(numbers[k].intValue()));
077                ar.add(items.get(numbers[k]));
078            }
079            dic.put(PdfName.NUMS, ar);
080            return dic;
081        }
082        int skip = leafSize;
083        PdfIndirectReference kids[] = new PdfIndirectReference[(numbers.length + leafSize - 1) / leafSize];
084        for (int k = 0; k < kids.length; ++k) {
085            int offset = k * leafSize;
086            int end = Math.min(offset + leafSize, numbers.length);
087            PdfDictionary dic = new PdfDictionary();
088            PdfArray arr = new PdfArray();
089            arr.add(new PdfNumber(numbers[offset].intValue()));
090            arr.add(new PdfNumber(numbers[end - 1].intValue()));
091            dic.put(PdfName.LIMITS, arr);
092            arr = new PdfArray();
093            for (; offset < end; ++offset) {
094                arr.add(new PdfNumber(numbers[offset].intValue()));
095                arr.add(items.get(numbers[offset]));
096            }
097            dic.put(PdfName.NUMS, arr);
098            kids[k] = writer.addToBody(dic).getIndirectReference();
099        }
100        int top = kids.length;
101        while (true) {
102            if (top <= leafSize) {
103                PdfArray arr = new PdfArray();
104                for (int k = 0; k < top; ++k)
105                    arr.add(kids[k]);
106                PdfDictionary dic = new PdfDictionary();
107                dic.put(PdfName.KIDS, arr);
108                return dic;
109            }
110            skip *= leafSize;
111            int tt = (numbers.length + skip - 1 )/ skip;
112            for (int k = 0; k < tt; ++k) {
113                int offset = k * leafSize;
114                int end = Math.min(offset + leafSize, top);
115                PdfDictionary dic = new PdfDictionary();
116                PdfArray arr = new PdfArray();
117                arr.add(new PdfNumber(numbers[k * skip].intValue()));
118                arr.add(new PdfNumber(numbers[Math.min((k + 1) * skip, numbers.length) - 1].intValue()));
119                dic.put(PdfName.LIMITS, arr);
120                arr = new PdfArray();
121                for (; offset < end; ++offset) {
122                    arr.add(kids[offset]);
123                }
124                dic.put(PdfName.KIDS, arr);
125                kids[k] = writer.addToBody(dic).getIndirectReference();
126            }
127            top = tt;
128        }
129    }
130
131    private static void iterateItems(PdfDictionary dic, HashMap<Integer, PdfObject> items) {
132        PdfArray nn = (PdfArray)PdfReader.getPdfObjectRelease(dic.get(PdfName.NUMS));
133        if (nn != null) {
134            for (int k = 0; k < nn.size(); ++k) {
135                PdfNumber s = (PdfNumber)PdfReader.getPdfObjectRelease(nn.getPdfObject(k++));
136                items.put(Integer.valueOf(s.intValue()), nn.getPdfObject(k));
137            }
138        }
139        else if ((nn = (PdfArray)PdfReader.getPdfObjectRelease(dic.get(PdfName.KIDS))) != null) {
140            for (int k = 0; k < nn.size(); ++k) {
141                PdfDictionary kid = (PdfDictionary)PdfReader.getPdfObjectRelease(nn.getPdfObject(k));
142                iterateItems(kid, items);
143            }
144        }
145    }
146
147    public static HashMap<Integer, PdfObject> readTree(PdfDictionary dic) {
148        HashMap<Integer, PdfObject> items = new HashMap<Integer, PdfObject>();
149        if (dic != null)
150            iterateItems(dic, items);
151        return items;
152    }
153}