KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > localstore > PrefixPool


1 /*******************************************************************************
2  * Copyright (c) 2007 Wind River Systems, Inc. and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * Martin Oberhuber (Wind River) - initial API and implementation for [105554]
10  *******************************************************************************/
11
12 package org.eclipse.core.internal.localstore;
13
14 import java.util.Arrays JavaDoc;
15
16 /**
17  * A pool of Strings for doing prefix checks against multiple
18  * candidates.
19  * <p>
20  * Allows to enter a list of Strings, and then perform the
21  * following checks:
22  * <ul>
23  * <li>{@link #containsAsPrefix(String)} - check whether a given
24  * String s is a prefix of any String in the pool.</li>
25  * <li>{@link #hasPrefixOf(String)} - check whether any String
26  * in the pool is a prefix of the given String s.
27  * </ul>
28  * The prefix pool is always kept normalized, i.e. no element of
29  * the pool is a prefix of any other element in the pool. In order
30  * to maintain this constraint, there are two methods for adding
31  * Strings to the pool:
32  * <ul>
33  * <li>{@link #insertLonger(String)} - add a String s to the pool,
34  * and remove any existing prefix of s from the pool.</li>
35  * <li>{@link #insertShorter(String)} - add a String s to the pool,
36  * and remove any existing Strings sx from the pool which
37  * contain s as prefix.</li>
38  * </ul>
39  * The PrefixPool grows as needed when adding Strings. Typically,
40  * it is used for prefix checks on absolute paths of a tree.
41  * </p><p>
42  * This class is not thread-safe: no two threads may add or
43  * check items at the same time.
44  *
45  * @since 3.3
46  */
47 public class PrefixPool {
48     private String JavaDoc[] pool;
49     private int size;
50
51     /**
52      * Constructor.
53      * @param initialCapacity the initial size of the
54      * internal array holding the String pool. Must
55      * be greater than 0.
56      */
57     public PrefixPool(int initialCapacity) {
58         if (initialCapacity <= 0)
59             throw new IllegalArgumentException JavaDoc("Illegal Capacity: " + initialCapacity); //$NON-NLS-1$
60 pool = new String JavaDoc[initialCapacity];
61         size = 0;
62     }
63
64     /**
65      * Clears the prefix pool, allowing all items to be
66      * garbage collected. Does not change the capacity
67      * of the pool.
68      */
69     public/*synchronized*/void clear() {
70         Arrays.fill(pool, 0, size, null);
71         size = 0;
72     }
73
74     /**
75      * Return the current size of prefix pool.
76      * @return the number of elements in the pool.
77      */
78     public/*synchronized*/int size() {
79         return size;
80     }
81
82     /**
83      * Ensure that there is room for at least one more element.
84      */
85     private void checkCapacity() {
86         if (size + 1 >= pool.length) {
87             String JavaDoc[] newprefixList = new String JavaDoc[2 * pool.length];
88             System.arraycopy(pool, 0, newprefixList, 0, pool.length);
89             Arrays.fill(pool, null); //help the garbage collector
90 pool = newprefixList;
91         }
92     }
93
94     /**
95      * Insert a String s into the pool of known prefixes, removing
96      * any existing prefix of it.
97      * <p>
98      * If any existing prefix of this String is found in the pool,
99      * it is replaced by the new longer one in order to maintain
100      * the constraint of keeping the pool normalized.
101      * </p><p>
102      * If it turns out that s is actually a prefix or equal to
103      * an existing element in the pool (so it is essentially
104      * shorter), this method returns with no operation in order
105      * to maintain the constraint that the pool remains normalized.
106      * </p>
107      * @param s the String to insert.
108      */
109     public/*synchronized*/void insertLonger(String JavaDoc s) {
110         //check in reverse order since we expect some locality
111 for (int i = size - 1; i >= 0; i--) {
112             if (pool[i].startsWith(s)) {
113                 //prefix of an existing String --> no-op
114 return;
115             } else if (s.startsWith(pool[i])) {
116                 //replace, since a longer s has more prefixes than a short one
117 pool[i] = s;
118                 return;
119             }
120         }
121         checkCapacity();
122         pool[size] = s;
123         size++;
124     }
125
126     /**
127      * Insert a String s into the pool of known prefixes, removing
128      * any Strings that have s as prefix.
129      * <p>
130      * If this String is a prefix of any existing String in the pool,
131      * all elements that contain the new String as prefix are removed
132      * and return value <code>true</code> is returned.
133      * </p><p>
134      * Otherwise, the new String is added to the pool unless an
135      * equal String or e prefix of it exists there already (so
136      * it is essentially equal or longer than an existing prefix).
137      * In all these cases, <code>false</code> is returned since
138      * no prefixes were replaced.
139      * </p>
140      * @param s the String to insert.
141      * @return <code>true</code>if any longer elements have been
142      * removed.
143      */
144     public/*synchronized*/boolean insertShorter(String JavaDoc s) {
145         boolean replaced = false;
146         //check in reverse order since we expect some locality
147 for (int i = size - 1; i >= 0; i--) {
148             if (s.startsWith(pool[i])) {
149                 //longer or equal to an existing prefix - nothing to do
150 return false;
151             } else if (pool[i].startsWith(s)) {
152                 if (replaced) {
153                     //replaced before, so shrink the array.
154 //Safe since we are iterating in reverse order.
155 System.arraycopy(pool, i + 1, pool, i, size - i - 1);
156                     size--;
157                     pool[size] = null;
158                 } else {
159                     //replace, since this is a shorter s
160 pool[i] = s;
161                     replaced = true;
162                 }
163             }
164         }
165         if (!replaced) {
166             //append at the end
167 checkCapacity();
168             pool[size] = s;
169             size++;
170         }
171         return replaced;
172     }
173
174     /**
175      * Check if the given String s is a prefix of any of Strings
176      * in the pool.
177      * @param s a s to check for being a prefix
178      * @return <code>true</code> if the passed s is a prefix
179      * of any of the Strings contained in the pool.
180      */
181     public/*synchronized*/boolean containsAsPrefix(String JavaDoc s) {
182         //check in reverse order since we expect some locality
183 for (int i = size - 1; i >= 0; i--) {
184             if (pool[i].startsWith(s)) {
185                 return true;
186             }
187         }
188         return false;
189     }
190
191     /**
192      * Test if the String pool contains any one that is a prefix
193      * of the given String s.
194      * @param s the String to test
195      * @return <code>true</code> if the String pool contains a
196      * prefix of the given String.
197      */
198     public/*synchronized*/boolean hasPrefixOf(String JavaDoc s) {
199         for (int i = size - 1; i >= 0; i--) {
200             if (s.startsWith(pool[i])) {
201                 return true;
202             }
203         }
204         return false;
205     }
206
207 }
208
Popular Tags