IntList


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   * IntList.java
21   *
22   * Created on March 21, 2004, 12:18 AM
23   */
24  
25  package org.netbeans.core.output2;
26  
27  import java.util.Arrays  ;
28  
29  /** A collections-like lineStartList of primitive integers.  Entries may be added only
30   * in ascending order.  This is used to map lines to file offsets.
31   *
32   * @author  Tim Boudreau
33   */
34  final class IntList {
35      private int[] array;
36      private int used = 0;
37      private int lastAdded = Integer.MIN_VALUE;
38  
39      /** Creates a new instance of IntMap */
40      IntList(int capacity) {
41          array = allocArray (capacity);
42      }
43      
44      /** Add an integer to the lineStartList.  Must be greater than the preceding value
45       * or an exception is thrown. */
46      public synchronized void add (int value) {
47          if (value < lastAdded) {
48              throw new IllegalArgumentException   ("Contents must be presorted - " + //NOI18N
49                  "added value " + value + " is less than preceding " + //NOI18N
50                  "value " + lastAdded); //NOI18N
51          }
52          if (used >= array.length) {
53              growArray();
54          }
55          array[used++] = value;
56          lastAdded = value;
57      }
58      
59      private int[] allocArray (int size) {
60          int[] result = new int[size];
61          //Fill it with Integer.MAX_VALUE so binarySearch works properly (must
62          //be sorted, cannot have 0's after the actual data
63          Arrays.fill(result, Integer.MAX_VALUE);
64          return result;
65      }
66      
67      public synchronized int get(int index) {
68          if (index >= used) {
69              throw new ArrayIndexOutOfBoundsException  ("List contains " + used 
70                  + " items, but tried to fetch item " + index);
71          }
72          return array[index];
73      }
74      
75      public boolean contains (int val) {
76          return Arrays.binarySearch(array, val) >= 0;
77      }
78      
79      /** Return the <strong>index</strong> of the value closest to but lower than
80       * the passed value */
81      public int findNearest (int val) {
82          if (size() == 0) {
83              return -1;
84          }
85          return findInRange (val, 0, size());
86      }
87      
88      /** Recursive binary search */
89      private int findInRange (int val, int start, int end) {
90          if (end - start <= 1) {
91              return start;
92          }
93          int midPoint = start + ((end - start) / 2);
94          int valAtMidpoint = get (midPoint);
95          if (valAtMidpoint > val) {
96              return findInRange (val, start, start + ((end - start) / 2));
97          } else {
98              return findInRange (val, start + ((end - start) / 2), end);
99          }
100     }
101     
102     public int indexOf (int val) {
103         int result = Arrays.binarySearch(array, val);
104         if (result < 0) {
105             result = -1;
106         }
107         if (result >= used) {
108             result = -1;
109         }
110         return result;
111     }
112     
113     
114     public synchronized int size() {
115         return used;
116     }
117     
118     private void growArray() {
119         int[] old = array;
120         array = allocArray(Math.round(array.length * 1.5f));
121         System.arraycopy(old, 0, array, 0, old.length);
122     }
123     
124     public String   toString() {
125         StringBuffer   result = new StringBuffer   ("IntList [");
126         for (int i=0; i < used; i++) {
127             result.append (i);
128             result.append (':');
129             result.append (array[i]);
130             if (i != used-1) {
131                 result.append(',');
132             }
133         }
134         result.append (']');
135         return result.toString();
136     }
137     
138 }
139
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags