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
  15  * and values are Objects. It also uses linear probing to resolve collisions
  16  * rather than a 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 public int elementSize; // number of elements in the table
  23 public int threshold;
  24
  25 public SimpleSet() {
  26         this(13);
  27 }
  28
  29 public SimpleSet(int size) {
  30         if (size < 3) size = 3;
  31         this.elementSize = 0;
  32         this.threshold = size + 1; // size is the expected number of elements
  33         this.values = new Object[2 * size + 1];
  34 }
  35
  36 public Object add(Object object) {
  37         int length = values.length;
  38         int index = (object.hashCode() & 0x7FFFFFFF) % length;
  39         Object current;
  40         while ((current = values[index]) != null) {
  41                 if (current.equals(object)) return values[index] = object;
  42                 if (++index == length) index = 0;
  43         }
  44         values[index] = object;
  45
  46         // assumes the threshold is never equal to the size of the table
  47         if (++elementSize > threshold) rehash();
  48         return object;
  49 }
  50
  51 public Object clone() throws CloneNotSupportedException {
  52         SimpleSet result = (SimpleSet) super.clone();
  53         result.elementSize = this.elementSize;
  54         result.threshold = this.threshold;
  55
  56         int length = this.values.length;
  57         result.values = new Object[length];
  58         System.arraycopy(this.values, 0, result.values, 0, length);
  59         return result;
  60 }
  61
  62 public boolean includes(Object object) {
  63         int length = values.length;
  64         int index = (object.hashCode() & 0x7FFFFFFF) % length;
  65         Object current;
  66         while ((current = values[index]) != null) {
  67                 if (current.equals(object)) return true;
  68                 if (++index == length) index = 0;
  69         }
  70         return false;
  71 }
  72
  73 public Object remove(Object object) {
  74         int length = values.length;
  75         int index = (object.hashCode() & 0x7FFFFFFF) % length;
  76         Object current;
  77         while ((current = values[index]) != null) {
  78                 if (current.equals(object)) {
  79                         elementSize--;
  80                         Object oldValue = values[index];
  81                         values[index] = null;
  82                         if (values[index + 1 == length ? 0 : index + 1] != null)
  83                                 rehash(); // only needed if a possible collision existed
  84                         return oldValue;
  85                 }
  86                 if (++index == length) index = 0;
  87         }
  88         return null;
  89 }
  90
  91 private void rehash() {
  92         SimpleSet newSet = new SimpleSet(elementSize * 2); // double the number of expected elements
  93         Object current;
  94         for (int i = values.length; --i >= 0;)
  95                 if ((current = values[i]) != null)
  96                         newSet.add(current);
  97
  98         this.values = newSet.values;
  99         this.elementSize = newSet.elementSize;
 100         this.threshold = newSet.threshold;
 101 }
 102
 103 public String toString() {
 104         String s = ""; //$NON-NLS-1$
 105         Object object;
 106         for (int i = 0, l = values.length; i < l; i++)
 107                 if ((object = values[i]) != null)
 108                         s += object.toString() + "\n"; //$NON-NLS-1$
 109         return s;
 110 }
 111 }