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 public int elementSize; // number of elements in the table
  20 public int threshold;
  21
  22 public SimpleWordSet(int size) {
  23         this.elementSize = 0;
  24         this.threshold = size; // size represents the expected number of elements
  25         int extraRoom = (int) (size * 1.5f);
  26         if (this.threshold == extraRoom)
  27                 extraRoom++;
  28         this.words = new char[extraRoom][];
  29 }
  30
  31 public char[] add(char[] word) {
  32         int length = this.words.length;
  33         int index = CharOperation.hashCode(word) % length;
  34         char[] current;
  35         while ((current = words[index]) != null) {
  36                 if (CharOperation.equals(current, word)) return current;
  37                 if (++index == length) index = 0;
  38         }
  39         words[index] = word;
  40
  41         // assumes the threshold is never equal to the size of the table
  42         if (++elementSize > threshold) rehash();
  43         return word;
  44 }
  45
  46 public boolean includes(char[] word) {
  47         int length = this.words.length;
  48         int index = CharOperation.hashCode(word) % length;
  49         char[] current;
  50         while ((current = words[index]) != null) {
  51                 if (CharOperation.equals(current, word)) return true;
  52                 if (++index == length) index = 0;
  53         }
  54         return false;
  55 }
  56
  57 private void rehash() {
  58         SimpleWordSet newSet = new SimpleWordSet(elementSize * 2); // double the number of expected elements
  59         char[] current;
  60         for (int i = words.length; --i >= 0;)
  61                 if ((current = words[i]) != null)
  62                         newSet.add(current);
  63
  64         this.words = newSet.words;
  65         this.elementSize = newSet.elementSize;
  66         this.threshold = newSet.threshold;
  67 }
  68 }