net.sourceforge.phpeclipse/src/net/sourceforge/phpdt/internal/core/util/SimpleSet.java

   1 /*******************************************************************************
   2  * Copyright (c) 2000, 2004 IBM Corporation and others.
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Common Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/cpl-v10.html
   7  *
   8  * Contributors:
   9  *     IBM Corporation - initial API and implementation
  10  *******************************************************************************/
  11 package net.sourceforge.phpdt.internal.core.util;
  12
  13 /**
  14  * A simple lookup table is a non-synchronized Hashtable, whose keys and values
  15  * are Objects. It also uses linear probing to resolve collisions rather than a
  16  * linked list of hash table entries.
  17  */
  18 public final class SimpleSet implements Cloneable {
  19
  20         // to avoid using Enumerations, walk the individual values skipping nulls
  21         public Object[] values;
  22
  23         public int elementSize; // number of elements in the table
  24
  25         public int threshold;
  26
  27         public SimpleSet() {
  28                 this(13);
  29         }
  30
  31         public SimpleSet(int size) {
  32                 if (size < 3)
  33                         size = 3;
  34                 this.elementSize = 0;
  35                 this.threshold = size + 1; // size is the expected number of elements
  36                 this.values = new Object[2 * size + 1];
  37         }
  38
  39         public Object add(Object object) {
  40                 int length = values.length;
  41                 int index = (object.hashCode() & 0x7FFFFFFF) % length;
  42                 Object current;
  43                 while ((current = values[index]) != null) {
  44                         if (current.equals(object))
  45                                 return values[index] = object;
  46                         if (++index == length)
  47                                 index = 0;
  48                 }
  49                 values[index] = object;
  50
  51                 // assumes the threshold is never equal to the size of the table
  52                 if (++elementSize > threshold)
  53                         rehash();
  54                 return object;
  55         }
  56
  57         public Object clone() throws CloneNotSupportedException {
  58                 SimpleSet result = (SimpleSet) super.clone();
  59                 result.elementSize = this.elementSize;
  60                 result.threshold = this.threshold;
  61
  62                 int length = this.values.length;
  63                 result.values = new Object[length];
  64                 System.arraycopy(this.values, 0, result.values, 0, length);
  65                 return result;
  66         }
  67
  68         public boolean includes(Object object) {
  69                 int length = values.length;
  70                 int index = (object.hashCode() & 0x7FFFFFFF) % length;
  71                 Object current;
  72                 while ((current = values[index]) != null) {
  73                         if (current.equals(object))
  74                                 return true;
  75                         if (++index == length)
  76                                 index = 0;
  77                 }
  78                 return false;
  79         }
  80
  81         public Object remove(Object object) {
  82                 int length = values.length;
  83                 int index = (object.hashCode() & 0x7FFFFFFF) % length;
  84                 Object current;
  85                 while ((current = values[index]) != null) {
  86                         if (current.equals(object)) {
  87                                 elementSize--;
  88                                 Object oldValue = values[index];
  89                                 values[index] = null;
  90                                 if (values[index + 1 == length ? 0 : index + 1] != null)
  91                                         rehash(); // only needed if a possible collision existed
  92                                 return oldValue;
  93                         }
  94                         if (++index == length)
  95                                 index = 0;
  96                 }
  97                 return null;
  98         }
  99
 100         private void rehash() {
 101                 SimpleSet newSet = new SimpleSet(elementSize * 2); // double the number
 102                                                                                                                         // of expected
 103                                                                                                                         // elements
 104                 Object current;
 105                 for (int i = values.length; --i >= 0;)
 106                         if ((current = values[i]) != null)
 107                                 newSet.add(current);
 108
 109                 this.values = newSet.values;
 110                 this.elementSize = newSet.elementSize;
 111                 this.threshold = newSet.threshold;
 112         }
 113
 114         public String toString() {
 115                 String s = ""; //$NON-NLS-1$
 116                 Object object;
 117                 for (int i = 0, l = values.length; i < l; i++)
 118                         if ((object = values[i]) != null)
 119                                 s += object.toString() + "\n"; //$NON-NLS-1$
 120                 return s;
 121         }
 122 }