platform/util/src/com/intellij/util/containers/hash/HashSet.java

/*
 * Copyright 2000-2013 JetBrains s.r.o.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.intellij.util.containers.hash;



import org.jetbrains.annotations.NotNull;

import java.util.AbstractSet;

import java.util.Iterator;

import java.util.Set;



public class HashSet<E> extends AbstractSet<E> implements Set<E> {



  private Entry<E>[] table;

  private int capacity;

  private int size;

  private final float loadFactor;



  public HashSet() {

    this(0);

  }



  public HashSet(int capacity) {

    this(capacity, HashUtil.DEFAULT_LOAD_FACTOR);

  }



  public HashSet(int capacity, float loadFactor) {

    this.loadFactor = loadFactor;

    clear(capacity);

  }



  @Override
  public boolean contains(Object key) {

    final Entry<E>[] table = this.table;

    final int hash = HashUtil.hash(key);

    final int index = hash % table.length;



    for (Entry<E> e = table[index]; e != null; e = e.hashNext) {

      final E entryKey;

      if (e.keyHash == hash && ((entryKey = e.key) == key || entryKey.equals(key))) {

        return true;

      }

    }



    return false;

  }



  @Override
  public boolean add(E key) {

    final Entry<E>[] table = this.table;

    final int hash = HashUtil.hash(key);

    final int index = hash % table.length;



    for (Entry<E> e = table[index]; e != null; e = e.hashNext) {

      final E entryKey;

      if (e.keyHash == hash && ((entryKey = e.key) == key || entryKey.equals(key))) {

        return false;

      }

    }



    final Entry<E> e = new Entry<E>(key);

    e.hashNext = table[index];

    table[index] = e;

    size = size + 1;



    if (size > capacity) {

      rehash((int) (capacity * HashUtil.CAPACITY_MULTIPLE));

    }

    return true;

  }



  @Override
  public boolean remove(Object key) {

    final Entry<E>[] table = this.table;

    final int hash = HashUtil.hash(key);

    final int index = hash % table.length;

    Entry<E> e = table[index];



    if (e == null) return false;



    E entryKey;

    if (e.keyHash == hash && ((entryKey = e.key) == key || entryKey.equals(key))) {

      table[index] = e.hashNext;

    } else {

      for (; ;) {

        final Entry<E> last = e;

        e = e.hashNext;

        if (e == null) return false;

        if (e.keyHash == hash && ((entryKey = e.key) == key || entryKey.equals(key))) {

          last.hashNext = e.hashNext;

          break;

        }

      }

    }

    size = size - 1;

    return true;

  }



  @NotNull
  @Override
  public Iterator<E> iterator() {

    return new HashSetIterator<E>() {

      @Override
      public E next() {

        return nextEntry().key;

      }

    };

  }



  @Override
  public int size() {

    return size;

  }



  @Override
  public boolean isEmpty() {

    return size() == 0;

  }



  private void init(int capacity) {

    table = new Entry[HashUtil.adjustTableSize((int) (capacity / loadFactor))];

    this.capacity = capacity;

  }



  private void clear(int capacity) {

    if (capacity < HashUtil.MIN_CAPACITY) {

      capacity = HashUtil.MIN_CAPACITY;

    }

    init(capacity);

    size = 0;

  }



  private void rehash(int capacity) {

    final Iterator<Entry<E>> entries = new HashSetIterator<Entry<E>>() {

      @Override
      public Entry<E> next() {

        return nextEntry();

      }

    };

    init(capacity);

    final Entry<E>[] table = this.table;

    final int tableLen = table.length;

    while (entries.hasNext()) {

      final Entry<E> e = entries.next();

      final int hash = e.keyHash % tableLen;

      e.hashNext = table[hash];

      table[hash] = e;

    }

  }



  private static class Entry<E> {



    private final E key;

    private final int keyHash;

    private Entry<E> hashNext;



    public Entry(final E key) {

      this.key = key;

      keyHash = HashUtil.hash(key);

    }

  }



  private abstract class HashSetIterator<T> implements Iterator<T> {



    private final Entry<E>[] table = HashSet.this.table;

    private int index = 0;

    private Entry<E> e = null;

    private Entry<E> last;



    HashSetIterator() {

      initNextEntry();

    }



    @Override
    public boolean hasNext() {

      return e != null;

    }



    @Override
    public void remove() {

      if (last == null) {

        throw new IllegalStateException();

      }

      HashSet.this.remove(last.key);

      last = null;

    }



    protected Entry<E> nextEntry() {

      final Entry<E> result = last = e;

      initNextEntry();

      return result;

    }



    private void initNextEntry() {

      Entry<E> result = e;

      if (result != null) {

        result = result.hashNext;

      }

      final Entry<E>[] table = this.table;

      while (result == null && index < table.length) {

        result = table[index++];

      }

      e = result;

    }

  }

}