001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.insane.model;
043:
044: import java.util.Iterator;
045: import java.util.NoSuchElementException;
046:
047: /** A set of objects with reflexive map behavior, using possibly
048: * an external hash implementation. Tries to minimize memory consumption.
049: *
050: * @author Nenik
051: */
052: class ObjectSet {
053:
054: private Hash hash;
055: private Object[] table;
056: private float loadFactor = 0.75f;
057: private int limit;
058: private int size;
059:
060: public ObjectSet() {
061: this (new Hash() {
062: public boolean equals(Object o1, Object o2) {
063: return o1.equals(o2);
064: }
065:
066: public int hashCodeFor(Object o) {
067: return o.hashCode();
068: }
069: });
070: }
071:
072: /** Creates a new instance of ObjectSet */
073: public ObjectSet(Hash hash) {
074: this .hash = hash;
075: table = new Object[11];
076: limit = (int) (table.length * loadFactor);
077: }
078:
079: public interface Hash {
080: public int hashCodeFor(Object o);
081:
082: public boolean equals(Object o1, Object o2);
083: }
084:
085: public Object get(Object key) {
086: int bucket = (hash.hashCodeFor(key) & 0x7FFFFFFF)
087: % table.length;
088:
089: while (table[bucket] != null) {
090: if (hash.equals(key, table[bucket]))
091: return table[bucket];
092: bucket = (bucket + 1) % table.length;
093: }
094:
095: return null; // XXX
096: }
097:
098: /* Always replaces exiting equals object */
099: public void put(Object key) {
100: //System.err.println("put: size=" + size + ", limit=" + limit + ", len=" + table.length);
101: if ((size + 1) > limit)
102: rehash(table.length * 2);
103:
104: size++;
105: int bucket = (hash.hashCodeFor(key) & 0x7FFFFFFF)
106: % table.length;
107:
108: while (table[bucket] != null
109: && !hash.equals(key, table[bucket])) {
110: bucket = (bucket + 1) % table.length;
111: }
112:
113: table[bucket] = key;
114: }
115:
116: public boolean contains(Object key) {
117: return get(key) != null;
118: }
119:
120: public Iterator iterator() {
121: return new Iterator() {
122: int ptr = 0;
123: Object next;
124:
125: public boolean hasNext() {
126: while (next == null && ptr < table.length) {
127: next = table[ptr++];
128: }
129: return next != null;
130: }
131:
132: public Object next() {
133: if (!hasNext())
134: throw new NoSuchElementException();
135: Object ret = next;
136: next = null;
137: return ret;
138: }
139:
140: public void remove() {
141: throw new UnsupportedOperationException();
142: }
143: };
144: }
145:
146: private void rehash(int newSize) {
147: Object[] newTable = new Object[newSize];
148: for (int i = 0; i < table.length; i++) {
149: Object act = table[i];
150: if (act != null) {
151: int bucket = (hash.hashCodeFor(act) & 0x7FFFFFFF)
152: % newTable.length;
153: while (newTable[bucket] != null) { // find an empty slot
154: bucket = (bucket + 1) % newTable.length;
155: }
156:
157: newTable[bucket] = act;
158: }
159: }
160:
161: table = newTable;
162: limit = (int) (table.length * loadFactor);
163: }
164: }
|