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}