1 /*******************************************************************************
2  * Copyright (c) 2000, 2008 IBM Corporation and others.
3  *
4  * This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License 2.0
6  * which accompanies this distribution, and is available at
7  * https://www.eclipse.org/legal/epl-2.0/
8  *
9  * SPDX-License-Identifier: EPL-2.0
10  *
11  * Contributors:
12  *     IBM Corporation - initial API and implementation
13  *******************************************************************************/
14 package org.eclipse.jdt.internal.compiler.util;
15 
16 /**
17  * HashSet of Object[]
18  */
19 public final class HashSetOfInt implements Cloneable {
20 
21 	// to avoid using Enumerations, walk the individual tables skipping nulls
22 	public int[] set;
23 
24 	public int elementSize; // number of elements in the table
25 	int threshold;
26 
HashSetOfInt()27 	public HashSetOfInt() {
28 		this(13);
29 	}
30 
HashSetOfInt(int size)31 	public HashSetOfInt(int size) {
32 
33 		this.elementSize = 0;
34 		this.threshold = size; // size represents the expected number of elements
35 		int extraRoom = (int) (size * 1.75f);
36 		if (this.threshold == extraRoom)
37 			extraRoom++;
38 		this.set = new int[extraRoom];
39 	}
40 
41 	@Override
clone()42 	public Object clone() throws CloneNotSupportedException {
43 		HashSetOfInt result = (HashSetOfInt) super.clone();
44 		result.elementSize = this.elementSize;
45 		result.threshold = this.threshold;
46 
47 		int length = this.set.length;
48 		result.set = new int[length];
49 		System.arraycopy(this.set, 0, result.set, 0, length);
50 
51 		return result;
52 	}
53 
contains(int element)54 	public boolean contains(int element) {
55 		int length = this.set.length;
56 		int index = element % length;
57 		int currentElement;
58 		while ((currentElement = this.set[index]) != 0) {
59 			if (currentElement == element)
60 				return true;
61 			if (++index == length) {
62 				index = 0;
63 			}
64 		}
65 		return false;
66 	}
67 
add(int element)68 	public int add(int element) {
69 		int length = this.set.length;
70 		int index = element % length;
71 		int currentElement;
72 		while ((currentElement = this.set[index]) != 0) {
73 			if (currentElement == element)
74 				return this.set[index] = element;
75 			if (++index == length) {
76 				index = 0;
77 			}
78 		}
79 		this.set[index] = element;
80 
81 		// assumes the threshold is never equal to the size of the table
82 		if (++this.elementSize > this.threshold)
83 			rehash();
84 		return element;
85 	}
86 
remove(int element)87 	public int remove(int element) {
88 		int length = this.set.length;
89 		int index = element % length;
90 		int currentElement;
91 		while ((currentElement = this.set[index]) != 0) {
92 			if (currentElement == element) {
93 				int existing = this.set[index];
94 				this.elementSize--;
95 				this.set[index] = 0;
96 				rehash();
97 				return existing;
98 			}
99 			if (++index == length) {
100 				index = 0;
101 			}
102 		}
103 		return 0;
104 	}
105 
rehash()106 	private void rehash() {
107 
108 		HashSetOfInt newHashSet = new HashSetOfInt(this.elementSize * 2);		// double the number of expected elements
109 		int currentElement;
110 		for (int i = this.set.length; --i >= 0;)
111 			if ((currentElement = this.set[i]) != 0)
112 				newHashSet.add(currentElement);
113 
114 		this.set = newHashSet.set;
115 		this.threshold = newHashSet.threshold;
116 	}
117 
size()118 	public int size() {
119 		return this.elementSize;
120 	}
121 
122 	@Override
toString()123 	public String toString() {
124 		StringBuffer buffer = new StringBuffer();
125 		int element;
126 		for (int i = 0, length = this.set.length; i < length; i++)
127 			if ((element = this.set[i]) != 0) {
128 				buffer.append(element);
129 				if (i != length-1)
130 					buffer.append('\n');
131 			}
132 		return buffer.toString();
133 	}
134 }
135