SparseIntList


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  /*
20   * SparseIntList.java
21   *
22   * Created on August 15, 2004, 12:18 AM
23   */
24  
25  package org.netbeans.core.output2;
26  
27  import java.util.Arrays  ;
28  
29  /**
30   * A sparsely populated list of integers, internally implemented as two
31   * arrays of integers - one containing sequential indices that have been entered,
32   * and one the values associated with those integers.  Calls to get() for values
33   * in between or greater than values that have really been added will return
34   * the value of the nearest lower added entry that has been added plus the interval
35   * between that entry and the index requested.  So, if you have such a list, 
36   * it works as follows:
37   * <p>
38   * Entries are added with an associated index.  If get() is called for a 
39   * value > the last entered index, the value returned is the last entered 
40   * index + the difference between the requested index and the last entered
41   * index.  When a value is requested that is between recorded indices, it
42   * will find the nearest lower recorded index.
43   * <p>
44   * So, if you call add (20, 10), then get(0)==0, get(9) == 9, get(10) == 10 (no
45   * that is not a typo! After adding <i>at</i> 10, get(10) returns 10 - indices
46   * <i>after</i> that are what's affected),
47   * get(11) == 21, get(12) == 22, and so forth.  Elements must be added in
48   * sequential order - that is, on any call to add, the index argument must
49   * be > the index argument the last time it was called, and the same for the
50   * value argument.
51   * <p>
52   * This is used to handle caching of logical line lengths in OutWriter -
53   * if we have a 400000 line file, most lines will typically not need to be
54   * word wrapped.  So we don't want to create a 400000 element int[] if most
55   * of the time the number of wrapped lines will turn out to be 1 - instead,
56   * only lines that are actually wrapped will have a line count added to a
57   * SparseIntList; its get() behavior takes care of returning correct values
58   * for the non-wrapped lines in between.
59   *
60   * @author  Tim Boudreau
61   */
62  final class SparseIntList {
63      private int[] keys;
64      private int[] values;
65      private int used = 0;
66      private int lastAdded = Integer.MIN_VALUE;
67      private int lastIndex = Integer.MIN_VALUE;
68      
69      /** Creates a new instance of IntMap */
70      SparseIntList(int capacity) {
71          allocArrays (capacity);
72      }
73      
74      /** Add an integer to the list.  The value must be > than the last value passed
75       * to this methodd, and the index must be > than the last index passed to
76       * this method.  Note that when you add <i>at</i> an index, you are really
77       * adding numbers to the returned value <i>after</i> that index.  In other
78       * words, if you call add(20, 11) as the first entry, get(11) will still return 11.
79       * But get(12) will return 21.
80       */
81      public synchronized void add (int value, int idx) {
82          if (value <= lastAdded) {
83              throw new IllegalArgumentException   ("Contents must be presorted - " + //NOI18N
84                  "added value " + value + " is less than preceding " + //NOI18N
85                  "value " + lastAdded); //NOI18N
86          }
87          if (idx <= lastIndex) {
88              throw new IllegalArgumentException   ("Contents must be presorted - " + //NOI18N
89                  "added index " + idx + " is less than preceding " + //NOI18N
90                  "index " + lastIndex); //NOI18N
91          }
92          if (used >= keys.length) {
93              growArrays();
94          }
95          values[used] = value;
96          keys[used++] = idx;
97          lastAdded = value;
98          lastIndex = idx;
99      }
100     
101     int lastAdded() {
102         return lastAdded;
103     }
104     
105     int lastIndex() {
106         return lastIndex;
107     }
108     
109     private void allocArrays (int size) {
110         keys = new int[size];
111         values = new int[size];
112         //Fill it with Integer.MAX_VALUE so binarySearch works properly (must
113         //be sorted, cannot have 0's after the actual data
114         Arrays.fill(keys, Integer.MAX_VALUE);
115         Arrays.fill(values, -1);
116     }
117     
118     /** Caches the last requested value.  Often we will be called repeatedly 
119      * for the same value - since finding the value involves two binary searches,
120      * cache it */
121     private int lastGet = -1;
122     /**
123      * Caches the last requested result for the same reasons.
124      */
125     private int lastResult;
126     /**
127      * Get an entry in the list.  If the list is empty, it will simply return
128      * the passed index value; if the index is lower than the first entry entered
129      * by a call to add (index, value) in the list, it will do the same.
130      * <p>
131      * If the index is greater than an added value's index, the return result
132      * will be the value of that index + the requested index minus the added
133      * index.
134      */
135     public synchronized int get(int index) {
136         if (index < 0) {
137             return 0;
138         }
139         
140         if ((used == 0) || (used > 0 && index < keys[0])) {
141             return index;
142         }
143         
144         if (index == lastGet) {
145             return lastResult;
146         } else {
147             lastGet = index;
148         }
149         
150         int result;
151         //First, see if we have a real entry for this index - if add() was
152         //called passing this exact index as a value
153         int idx = Arrays.binarySearch(keys, index);
154         
155         if (idx < 0) {
156             //Nope, not an exact match.  Divide and conquer the keys array to
157             //find the nearest index to our value
158             int nearest = findInRange(index, 0, used);
159             
160             //Make sure it's not bigger than the one we're looking for
161             if (keys[nearest] > index) nearest--;
162             if (nearest == -1) {
163                 result = index; 
164             } else {
165                 //Result is the nearest value + the number of entries after it
166                 //that the passed index is
167                 result = values[nearest] + (index - keys[nearest]);
168             }
169         } else {
170             //Just fetch the value and return it
171             result = idx == 0 ? index : values[idx-1] + (index - keys[idx-1]);
172         }
173         lastResult = result;
174         return result;
175     }
176     
177     /** Recursive binary search - finds the index in the keys array of the
178      * nearest value to the passed value.
179      */
180     private int findInRange (int val, int start, int end) {
181         if (end - start <= 1) {
182             return start;
183         }
184         int midPoint = start + ((end - start) >> 1);
185         int idxAtMidpoint = keys[midPoint];
186         if (idxAtMidpoint > val) {
187             return findInRange (val, start, start + ((end - start) >> 1));
188         } else {
189             return findInRange (val, start + ((end - start) >> 1), end);
190         }
191     }    
192     
193     /**
194      * Grow the arrays we're using to store keys/values
195      */
196     private void growArrays() {
197         int[] oldkeys = keys;
198         int[] oldvals = values;
199         allocArrays(Math.round(keys.length * 1.5f));
200         System.arraycopy(oldkeys, 0, keys, 0, oldkeys.length);
201         System.arraycopy(oldvals, 0, values, 0, oldvals.length);
202     }
203     
204     public String   toString() {
205         StringBuffer   result = new StringBuffer   ("SparseIntList ["); //NOI18N
206         result.append ("used="); //NOI18N
207         result.append (used);
208         result.append (" capacity="); //NOI18N
209         result.append (keys.length);
210         result.append (" keyValuePairs:"); //NOI18N
211         for (int i=0; i < used; i++) {
212             result.append (keys[i]);
213             result.append (':'); //NOI18N
214             result.append (values[i]);
215             if (i != used-1) {
216                 result.append(','); //NOI18N
217             }
218         }
219         result.append (']');
220         return result.toString();
221     }
222     
223 }
224
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags