KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > resources > MarkerSet


1 /*******************************************************************************
2  * Copyright (c) 2000, 2005 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.core.internal.resources;
12
13 import org.eclipse.core.internal.utils.IStringPoolParticipant;
14 import org.eclipse.core.internal.utils.StringPool;
15
16 public class MarkerSet implements Cloneable JavaDoc, IStringPoolParticipant {
17     protected static final int MINIMUM_SIZE = 5;
18     protected int elementCount = 0;
19     protected IMarkerSetElement[] elements;
20
21     public MarkerSet() {
22         this(MINIMUM_SIZE);
23     }
24
25     public MarkerSet(int capacity) {
26         super();
27         this.elements = new IMarkerSetElement[Math.max(MINIMUM_SIZE, capacity * 2)];
28     }
29
30     public void add(IMarkerSetElement element) {
31         if (element == null)
32             return;
33         int hash = hashFor(element.getId()) % elements.length;
34
35         // search for an empty slot at the end of the array
36 for (int i = hash; i < elements.length; i++) {
37             if (elements[i] == null) {
38                 elements[i] = element;
39                 elementCount++;
40                 // grow if necessary
41 if (shouldGrow())
42                     expand();
43                 return;
44             }
45         }
46
47         // search for an empty slot at the beginning of the array
48 for (int i = 0; i < hash - 1; i++) {
49             if (elements[i] == null) {
50                 elements[i] = element;
51                 elementCount++;
52                 // grow if necessary
53 if (shouldGrow())
54                     expand();
55                 return;
56             }
57         }
58
59         // if we didn't find a free slot, then try again with the expanded set
60 expand();
61         add(element);
62     }
63
64     public void addAll(IMarkerSetElement[] toAdd) {
65         for (int i = 0; i < toAdd.length; i++)
66             add(toAdd[i]);
67     }
68
69     protected Object JavaDoc clone() {
70         try {
71             MarkerSet copy = (MarkerSet) super.clone();
72             //copy the attribute array
73 copy.elements = (IMarkerSetElement[]) elements.clone();
74             return copy;
75         } catch (CloneNotSupportedException JavaDoc e) {
76             //cannot happen because this class implements Cloneable
77 return null;
78         }
79     }
80
81     public boolean contains(long id) {
82         return get(id) != null;
83     }
84
85     public IMarkerSetElement[] elements() {
86         IMarkerSetElement[] result = new IMarkerSetElement[elementCount];
87         int j = 0;
88         for (int i = 0; i < elements.length; i++) {
89             IMarkerSetElement element = elements[i];
90             if (element != null)
91                 result[j++] = element;
92         }
93         return result;
94     }
95
96     /**
97      * The array isn't large enough so double its size and rehash
98      * all its current values.
99      */
100     protected void expand() {
101         IMarkerSetElement[] array = new IMarkerSetElement[elements.length * 2];
102         int maxArrayIndex = array.length - 1;
103         for (int i = 0; i < elements.length; i++) {
104             IMarkerSetElement element = elements[i];
105             if (element != null) {
106                 int hash = hashFor(element.getId()) % array.length;
107                 while (array[hash] != null) {
108                     hash++;
109                     if (hash > maxArrayIndex)
110                         hash = 0;
111                 }
112                 array[hash] = element;
113             }
114         }
115         elements = array;
116     }
117
118     /**
119      * Returns the set element with the given id, or null
120      * if not found.
121      */
122     public IMarkerSetElement get(long id) {
123         if (elementCount == 0)
124             return null;
125         int hash = hashFor(id) % elements.length;
126
127         // search the last half of the array
128 for (int i = hash; i < elements.length; i++) {
129             IMarkerSetElement element = elements[i];
130             if (element == null)
131                 return null;
132             if (element.getId() == id)
133                 return element;
134         }
135
136         // search the beginning of the array
137 for (int i = 0; i < hash - 1; i++) {
138             IMarkerSetElement element = elements[i];
139             if (element == null)
140                 return null;
141             if (element.getId() == id)
142                 return element;
143         }
144
145         // marker info not found so return null
146 return null;
147     }
148
149     private int hashFor(long id) {
150         return Math.abs((int) id);
151     }
152
153     public boolean isEmpty() {
154         return elementCount == 0;
155     }
156
157     /**
158      * The element at the given index has been removed so move
159      * elements to keep the set properly hashed.
160      */
161     protected void rehashTo(int anIndex) {
162
163         int target = anIndex;
164         int index = anIndex + 1;
165         if (index >= elements.length)
166             index = 0;
167         IMarkerSetElement element = elements[index];
168         while (element != null) {
169             int hashIndex = hashFor(element.getId()) % elements.length;
170             boolean match;
171             if (index < target)
172                 match = !(hashIndex > target || hashIndex <= index);
173             else
174                 match = !(hashIndex > target && hashIndex <= index);
175             if (match) {
176                 elements[target] = element;
177                 target = index;
178             }
179             index++;
180             if (index >= elements.length)
181                 index = 0;
182             element = elements[index];
183         }
184         elements[target] = null;
185     }
186
187     public void remove(long id) {
188         int hash = hashFor(id) % elements.length;
189
190         for (int i = hash; i < elements.length; i++) {
191             IMarkerSetElement element = elements[i];
192             if (element == null)
193                 return;
194             if (element.getId() == id) {
195                 rehashTo(i);
196                 elementCount--;
197             }
198         }
199
200         for (int i = 0; i < hash - 1; i++) {
201             IMarkerSetElement element = elements[i];
202             if (element == null)
203                 return;
204             if (element.getId() == id) {
205                 rehashTo(i);
206                 elementCount--;
207             }
208         }
209     }
210
211     public void remove(IMarkerSetElement element) {
212         remove(element.getId());
213     }
214
215     public void removeAll(IMarkerSetElement[] toRemove) {
216         for (int i = 0; i < toRemove.length; i++)
217             remove(toRemove[i]);
218     }
219
220     private boolean shouldGrow() {
221         return elementCount > elements.length * 0.75;
222     }
223
224     public int size() {
225         return elementCount;
226     }
227
228     /* (non-Javadoc
229      * Method declared on IStringPoolParticipant
230      */
231     public void shareStrings(StringPool set) {
232         //copy elements for thread safety
233 Object JavaDoc[] array = elements;
234         if (array == null)
235             return;
236         for (int i = 0; i < array.length; i++) {
237             Object JavaDoc o = array[i];
238             if (o instanceof String JavaDoc)
239                 array[i] = set.add((String JavaDoc) o);
240             if (o instanceof IStringPoolParticipant)
241                 ((IStringPoolParticipant) o).shareStrings(set);
242         }
243     }
244 }
245
Popular Tags