net.sourceforge.phpeclipse/src/net/sourceforge/phpdt/internal/core/util/SimpleWordSet.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 import net.sourceforge.phpdt.core.compiler.CharOperation;
  14
  15 public final class SimpleWordSet {
  16
  17         // to avoid using Enumerations, walk the individual values skipping nulls
  18         public char[][] words;
  19
  20         public int elementSize; // number of elements in the table
  21
  22         public int threshold;
  23
  24         public SimpleWordSet(int size) {
  25                 this.elementSize = 0;
  26                 this.threshold = size; // size represents the expected number of
  27                                                                 // elements
  28                 int extraRoom = (int) (size * 1.5f);
  29                 if (this.threshold == extraRoom)
  30                         extraRoom++;
  31                 this.words = new char[extraRoom][];
  32         }
  33
  34         public char[] add(char[] word) {
  35                 int length = this.words.length;
  36                 int index = CharOperation.hashCode(word) % length;
  37                 char[] current;
  38                 while ((current = words[index]) != null) {
  39                         if (CharOperation.equals(current, word))
  40                                 return current;
  41                         if (++index == length)
  42                                 index = 0;
  43                 }
  44                 words[index] = word;
  45
  46                 // assumes the threshold is never equal to the size of the table
  47                 if (++elementSize > threshold)
  48                         rehash();
  49                 return word;
  50         }
  51
  52         public boolean includes(char[] word) {
  53                 int length = this.words.length;
  54                 int index = CharOperation.hashCode(word) % length;
  55                 char[] current;
  56                 while ((current = words[index]) != null) {
  57                         if (CharOperation.equals(current, word))
  58                                 return true;
  59                         if (++index == length)
  60                                 index = 0;
  61                 }
  62                 return false;
  63         }
  64
  65         private void rehash() {
  66                 SimpleWordSet newSet = new SimpleWordSet(elementSize * 2); // double
  67                                                                                                                                         // the
  68                                                                                                                                         // number of
  69                                                                                                                                         // expected
  70                                                                                                                                         // elements
  71                 char[] current;
  72                 for (int i = words.length; --i >= 0;)
  73                         if ((current = words[i]) != null)
  74                                 newSet.add(current);
  75
  76                 this.words = newSet.words;
  77                 this.elementSize = newSet.elementSize;
  78                 this.threshold = newSet.threshold;
  79         }
  80 }