/*
 * IdentityHashSet class.
 *
 * Copyright (C) 2007 SATOH Takayuki All Rights Reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 */
package ts.util;

import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.IOException;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.AbstractSet;
import java.util.IdentityHashMap;

/**
 * このクラスは、要素の比較にオブジェクトの同一性ではなく参照の同一性を使用した
 * ハッシュ・セットを実装している。
 * 言い換えると、要素の比較を <tt>(e1==null ? e2==null : e1.equals(e2))</tt>
 * ではなく、<tt>(e1==e2)</tt>によって判定している。
 * <br>
 * このクラスは、内部に{@link java.util.IdentityHashMap IdentityHashMap}を
 * 持っており、これに要素オブジェクトが格納される。
 *
 * @param <E> このセットが扱う要素のタイプ。
 *
 * @author  佐藤隆之.
 * @version $Revision: 1.1.1.1 $, $Date: 2010-10-16 00:03:44 $
 * @see java.util.IdentityHashMap
 */
public class IdentityHashSet<E> extends AbstractSet<E>
  implements Set<E>, Cloneable, Serializable
{
  /** シリアル・バージョン番号。*/
  static final long serialVersionUID = 1423360409923613700L;

  /** 要素を格納するマップ。 */
  private transient IdentityHashMap<E,Object> map_ ;

  /** 要素を格納するマップに設定するダミー値。 */
  private static final Object PRESENT = new Object();

  /**
   * デフォルトコンストラクタ。
   * <br>
   * インスタンスの初期容量はデフォルト値(21)とする。
   */
  public IdentityHashSet()
  {
    map_ = new IdentityHashMap<E,Object>();
  }

  /**
   * コレクションを引数にとるコンストラクタ。
   * <br>
   * 引数のコレクションの要素を、このセットの要素としてインスタンスを構築する。
   * <br>
   * 初期容量は引数のコレクションのサイズとデフォルト値(21)の大きい方を設定
   * する。
   *
   * @param  c このセットの要素となるオブジェクトを格納したコレクション。
   * @throws AssertionError 引数がヌルの場合（デバッグ・モードのみ）。
   */
  public IdentityHashSet(Collection<? extends E> c)
  {
    map_ = new IdentityHashMap<E,Object>(Math.max(c.size(), 21));
    addAll(c);
  }

  /**
   * 初期容量を引数にとるコンストラクタ。
   *
   * @param  initialCapacity 初期容量。
   * @throws IllegalArgumentException 引数の初期容量が負の値の場合。
   */
  public IdentityHashSet(int initialCapacity)
  {
    map_ = new IdentityHashMap<E,Object>(initialCapacity);
  }

  /**
   * このセットに格納されている要素数を取得する。
   *
   * @return 要素数。
   */
  public int size()
  {
    return map_.size();
  }

  /**
   * このセットの要素数がゼロかどうかを確認する。
   *
   * @return 要素数がゼロの場合に<tt>true</tt>を返す。
   */
  public boolean isEmpty()
  {
    return map_.isEmpty();
  }

  /**
   * 指定された要素のこのセットに含まれているかどうかを確認する。
   *
   * @param  obj 確認対象のオブジェクト。
   * @return 引数の要素がこのセットに含まれている場合は<tt>true</tt>を返す。
   */
  public boolean contains(Object obj)
  {
    return map_.containsKey(obj);
  }

  /**
   * このセットに格納されている要素のイテレータを取得する。
   *
   * @return このセットに格納されている要素のイテレータ。
   */
  public Iterator<E> iterator()
  {
    return map_.keySet().iterator();
  }

  /**
   * 指定された要素をこのセットに追加する。
   * <br>
   * 但し、指定された要素が既にこのセットに存在した場合は追加しない。
   * <br>
   * 戻り値は、要素の追加が行われた場合は<tt>true</tt>を返し、要素が既に存在
   * していて追加が行われなかった場合は<tt>false</tt>を返す。
   *
   * @param  e 追加される要素。
   * @return 指定された要素がそれまでこのセットに存在せず、追加が行われた場合
   *         は<tt>true</tt>を返す。
   */
  public boolean add(E e)
  {
    return (map_.put(e, PRESENT) == null);
  }

  /**
   * このセットから全ての要素を削除する。
   * <br>
   * このメソッドを実行した後、このセットは空になる。
   */
  public void clear()
  {
    map_.clear();
  }

  /**
   * このセットのクローン・オブジェクトを作成する。
   *
   * @return このセットのクローン・オブジェクト。
   */
  @SuppressWarnings("unchecked")
  public Object clone()
  {
    try {
      IdentityHashSet<E> newSet = (IdentityHashSet<E>) super.clone();
      newSet.map_ = (IdentityHashMap<E,Object>) map_.clone();
      return newSet;
    }
    catch (CloneNotSupportedException e) {
      throw new InternalError();
    }
  }

  /**
   * このセット・インスタンスの状態をストリームに出力する。
   *
   * @param  ostream 出力先のストリーム。 
   */
  private void writeObject(ObjectOutputStream ostream) throws IOException
  {
    ostream.defaultWriteObject();
    ostream.writeInt(map_.size());

    for (E e : map_.keySet()) {
      ostream.writeObject(e);
    }
  }

  /**
   * ストリーム・データからセット・インスタンスを構築する。
   *
   * @param  istream 入力元のストリーム。
   */
  @SuppressWarnings("unchecked")
  private void readObject(ObjectInputStream istream)
    throws IOException, ClassNotFoundException
  {
    istream.defaultReadObject();
    int size = istream.readInt();

    map_ = new IdentityHashMap<E,Object>(size);

    for (int i=0; i<size; i++) {
      E e = (E) istream.readObject();
      map_.put(e, PRESENT);
    }
  }
}

