KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > jdt > internal > compiler > util > SimpleSetOfCharArray


1 /*******************************************************************************
2  * Copyright (c) 2006, 2007 IBM Corporation 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  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.jdt.internal.compiler.util;
12
13 import org.eclipse.jdt.core.compiler.CharOperation;
14
15 /**
16  * A simple lookup table is a non-synchronized Hashtable, whose keys
17  * and values are char[]. It also uses linear probing to resolve collisions
18  * rather than a linked list of hash table entries.
19  */
20 public final class SimpleSetOfCharArray implements Cloneable JavaDoc {
21
22 // to avoid using Enumerations, walk the individual values skipping nulls
23 public char[][] values;
24 public int elementSize; // number of elements in the table
25 public int threshold;
26
27 public SimpleSetOfCharArray() {
28     this(13);
29 }
30
31 public SimpleSetOfCharArray(int size) {
32     if (size < 3) size = 3;
33     this.elementSize = 0;
34     this.threshold = size + 1; // size is the expected number of elements
35 this.values = new char[2 * size + 1][];
36 }
37
38 public Object JavaDoc add(char[] object) {
39     int length = this.values.length;
40     int index = (CharOperation.hashCode(object) & 0x7FFFFFFF) % length;
41     char[] current;
42     while ((current = this.values[index]) != null) {
43         if (CharOperation.equals(current, object)) return this.values[index] = object;
44         if (++index == length) index = 0;
45     }
46     this.values[index] = object;
47
48     // assumes the threshold is never equal to the size of the table
49 if (++this.elementSize > this.threshold) rehash();
50     return object;
51 }
52
53 public void asArray(Object JavaDoc[] copy) {
54     if (this.elementSize != copy.length)
55         throw new IllegalArgumentException JavaDoc();
56     int index = this.elementSize;
57     for (int i = 0, l = this.values.length; i < l && index > 0; i++)
58         if (this.values[i] != null)
59             copy[--index] = this.values[i];
60 }
61
62 public void clear() {
63     for (int i = this.values.length; --i >= 0;)
64         this.values[i] = null;
65     this.elementSize = 0;
66 }
67
68 public Object JavaDoc clone() throws CloneNotSupportedException JavaDoc {
69     SimpleSetOfCharArray result = (SimpleSetOfCharArray) super.clone();
70     result.elementSize = this.elementSize;
71     result.threshold = this.threshold;
72
73     int length = this.values.length;
74     result.values = new char[length][];
75     System.arraycopy(this.values, 0, result.values, 0, length);
76     return result;
77 }
78
79 public char[] get(char[] object) {
80     int length = this.values.length;
81     int index = (CharOperation.hashCode(object) & 0x7FFFFFFF) % length;
82     char[] current;
83     while ((current = this.values[index]) != null) {
84         if (CharOperation.equals(current, object)) return current;
85         if (++index == length) index = 0;
86     }
87     this.values[index] = object;
88
89     // assumes the threshold is never equal to the size of the table
90 if (++this.elementSize > this.threshold) rehash();
91     return object;
92 }
93
94 public boolean includes(char[] object) {
95     int length = values.length;
96     int index = (CharOperation.hashCode(object) & 0x7FFFFFFF) % length;
97     char[] current;
98     while ((current = values[index]) != null) {
99         if (CharOperation.equals(current, object)) return true;
100         if (++index == length) index = 0;
101     }
102     return false;
103 }
104
105 public char[] remove(char[] object) {
106     int length = values.length;
107     int index = (CharOperation.hashCode(object) & 0x7FFFFFFF) % length;
108     char[] current;
109     while ((current = values[index]) != null) {
110         if (CharOperation.equals(current, object)) {
111             elementSize--;
112             char[] oldValue = values[index];
113             values[index] = null;
114             if (values[index + 1 == length ? 0 : index + 1] != null)
115                 rehash(); // only needed if a possible collision existed
116 return oldValue;
117         }
118         if (++index == length) index = 0;
119     }
120     return null;
121 }
122
123 private void rehash() {
124     SimpleSetOfCharArray newSet = new SimpleSetOfCharArray(elementSize * 2); // double the number of expected elements
125 char[] current;
126     for (int i = values.length; --i >= 0;)
127         if ((current = values[i]) != null)
128             newSet.add(current);
129
130     this.values = newSet.values;
131     this.elementSize = newSet.elementSize;
132     this.threshold = newSet.threshold;
133 }
134
135 public String JavaDoc toString() {
136     String JavaDoc s = ""; //$NON-NLS-1$
137 char[] object;
138     for (int i = 0, l = values.length; i < l; i++)
139         if ((object = values[i]) != null)
140             s += new String JavaDoc(object) + "\n"; //$NON-NLS-1$
141 return s;
142 }
143 }
144
Popular Tags