/*
 * Index 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.table;

import ts.util.IdentityHashSet;
import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.IOException;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Collections;
import java.util.NoSuchElementException;

/**
 * インデックス・クラス。
 * <br>
 * 指定されたカラムの値を使ってレコードのインデックスを作成し、レコードの検索の
 * 高速化を図る。
 * <br>
 * インデックスに使用するカラムは複数指定することができる。
 * <br>
 * <br>
 * このクラスは、{@link ts.util.table.Table Table}をインプリメントしており、
 * テーブル・オブジェクトと同様にレコードの追加・検索・削除・更新の操作を行う
 * ことができる。
 * <br>
 * このインデックスに対してレコードの追加・削除・更新を行うと、作成元のテーブル
 * にもその変更が反映される。
 * 反対に、作成元のテーブルに対してレコードの追加・削除・更新を行ったときも、
 * このインデックスにその変更が反映される。
 *
 * @author  佐藤隆之.
 * @version $Revision: 1.1.1.1 $, $Date: 2010-10-16 00:03:51 $
 */
public abstract class Index<C,V> implements Table<C,V>
{
  /** インデックス・キーの配列。 */
  private C[] indexKeys_ ;

  /** インデックス・ツリーのルート・ノード・マップ。 */
  private IndexNodeMap rootMap_ = new IndexNodeMap();

  /**
   * インデックス・キーとなるカラムの配列を引数にとるコンストラクタ。
   *
   * @param  indexKeys インデックス・キーの配列。
   * @throws IllegalArgumentException 引数の配列のサイズがゼロの場合。
   * @throws AssertionError 引数がヌルの場合。
   */
  protected Index(C[] indexKeys)
  {
    assert (indexKeys != null) : "@param:indexKeys is null.";

    if (indexKeys.length == 0) {
      throw new IllegalArgumentException("@param:indexKeys is an empty array.");
    }
    indexKeys_ = indexKeys;
  }

  /**
   * このインデックスの作成元であるテーブル・オブジェクトを取得する。
   *
   * @return 作成元のテーブル・オブジェクト。
   */
  protected abstract Table<C,V> getBaseTable();

  /**
   * 作成元のテーブルに格納されているカラムの数を取得する。
   *
   * @return カラム数。
   */
  public int columnCount()
  {
    return getBaseTable().columnCount();
  }

  /**
   * 作成元のテーブルに格納されているレコードの数を取得する。
   *
   * @return レコード数。
   */
  public int recordCount()
  {
    return getBaseTable().recordCount();
  }

  /**
   * インデックス・キーの数を取得する。
   *
   * @return インデックス・キーの数。
   */
  protected int indexKeyCount()
  {
    return indexKeys_.length;
  }

  /**
   * 作成元のテーブルを構成するカラム・キーを列挙する。
   *
   * @return カラム・キーの列挙オブジェクト。
   */
  public Enumeration<C> columns()
  {
    return getBaseTable().columns();
  }

  /**
   * 作成元のテーブルに格納されているレコードを順に取り出すためのイテレータを
   * 取得する。
   *
   * @return レコードのイテレータ。
   */
  public MapIterator<C,V> records()
  {
    return getBaseTable().records();
  }

  /**
   * 作成元のテーブルに格納されているレコードをソートして、順に取り出すための
   * イテレータを取得する。
   *
   * @param  comparator ソートに使用するレコード比較オブジェクト。
   * @return レコードのイテレータ。
   * @throws AssertionError 引数がヌルの場合（デバッグ・モードのみ）。
   */
  public MapIterator<C,V> records(MapComparator<C,V> comparator)
  {
    return getBaseTable().records(comparator);
  }

  /**
   * 作成元のテーブルに最初に格納されているレコードを取得する。
   *
   * @return 作成元のテーブルに最初に格納されているレコード。
   */
  public Map<C,V> recordFirst()
  {
    return getBaseTable().recordFirst();
  }

  /**
   * インデックス・キーを列挙する。
   *
   * @return インデックス・キーの列挙オブジェクト。
   */
  protected Enumeration<C> indexKeys()
  {
    return new Enumeration<C>() {
      private int ind_ = 0;
      public boolean hasMoreElements() {
        return (ind_ < indexKeys_.length);
      }
      public C nextElement() {
        try {
          C c = indexKeys_[ind_];
          ind_ ++;
          return c;
        }
        catch (Exception e) {
          throw new NoSuchElementException();
        }
      }
    };
  }

  /**
   * 指定された配列の要素をインデックス・キーとするインデックスを取得する。
   * <br>
   * 該当するインデックスが存在しない場合は、インデックスを作成して返す。
   *
   * @param  indexKeys インデックス・キーの配列。
   * @return このテーブルのインデックス・オブジェクト。
   */
  public Index<C,V> getIndex(C ... indexKeys)
  {
    return getBaseTable().getIndex(indexKeys);
  }

  /**
   * 作成元のテーブルにトリガを追加する。
   *
   * @param  trigger トリガ・オブジェクト。
   * @throws AssertionError 引数がヌルの場合（デバッグ・モードのみ）。
   */
  public void addTrigger(Trigger<C,V> trigger)
  {
    getBaseTable().addTrigger(trigger);
  }

  /**
   * 全てのレコードを削除する。
   */
  public void deleteAll()
  {
    getBaseTable().deleteAll();
  }

  /**
   * 新しいレコードを作成して、作成元のテーブルに追加する。
   * <br>
   * 追加されたレコードは、マップ・オブジェクトの戻り値として返される。
   *
   * @return 追加されたレコードを表すマップ・オブジェクト。
   */
  public Map<C,V> appendNew()
  {
    return getBaseTable().appendNew();
  }

  /**
   * 新しいレコードを作成して、作成元のテーブルに追加する。
   * <br>
   * 追加されたレコードは、マップ・オブジェクトの戻り値として返される。
   *
   * @param  initColCapacity レコードの初期カラム容量。
   * @return 追加されたレコードを表すマップ・オブジェクト。
   * @throws AssertionError 引数が負の値の場合（デバッグ・モードのみ）。
   */
  public Map<C,V> appendNew(int initColCapacity)
  {
    return getBaseTable().appendNew(initColCapacity);
  }

  /**
   * {@inheritDoc}
   */
  public boolean exists(C column, V value)
  {
    Map<C,V> condition = new HashMap<C,V>();
    condition.put(column, value);
    return exists(condition);
  }

  /**
   * {@inheritDoc}
   */
  public Map<C,V> selectFirst(C column, V value)
  {
    Map<C,V> condition = new HashMap<C,V>();
    condition.put(column, value);
    return selectFirst(condition);
  }

  /**
   * {@inheritDoc}
   */
  public List<Map<C,V>> select(C column, V value)
  {
    Map<C,V> condition = new HashMap<C,V>();
    condition.put(column, value);
    return select(condition);
  }

  /**
   * このインデックスのキーだけについて、条件に該当するレコードのコレクションを
   * 取得する。
   * <br>
   * 該当するレコードが１つもなかった場合は空のコレクションを返す。
   *
   * @param  condition 条件のカラムとその値を格納したマップ。
   * @return このインデックスのキーについて条件に該当するレコードの
   *         コレクション。
   * @throws AssertionError 引数がヌルの場合（デバッグ・モードのみ）。
   */
  protected Collection<Record<C,V>> collectRecords(Map<C,V> condition)
  {
    assert (condition != null) : "@param:condition is null.";
    return collectRecords(rootMap_, 0, condition);
  }

  /**
   * このインデックスのキーだけについて条件に該当するレコードのコレクションを
   * 再帰的に探索して取得する。
   * <br>
   * 該当するレコードが1つもなかった場合は空のコレクションを返す。
   *
   * @param  indexMap 探索中のインデックス・マップ。
   * @param  keyind 探索対象のインデックス・キーの配列位置。
   * @param  condition 条件のカラムとその値を格納したマップ・オブジェクト。
   * @return このインデックスのキーについて条件に該当するレコードの
   *         コレクション。
   */
  private Collection<Record<C,V>> collectRecords(
    IndexNodeMap indexMap, int keyind, Map<C,V> condition)
  {
    C key = indexKeys_[keyind];
    V val = condition.get(key);
    keyind ++;

    if (val == null && !condition.containsKey(key)) {
      RecordSet set = new RecordSet();
      for (Object o : indexMap.values()) {
        if (o instanceof HashMap) {
          set.addAll(collectRecords((IndexNodeMap) o, keyind, condition));
        }
        else if (o instanceof IdentityHashSet) {
          set.addAll((RecordSet) o);
        }
      }
      return set;
    }
    else {
      Object o = indexMap.get(val);
      if (o != null) {
        if (o instanceof HashMap) {
          return collectRecords((IndexNodeMap) o, keyind, condition);
        }
        else if (o instanceof IdentityHashSet) {
          return (RecordSet) o;
        }
      }
      return new RecordSet();
    }
  }

  /**
   * 指定されたレコードを格納する、インデックス・ツリーの末端に設定されている
   * コレクション・オブジェクトを取得する。
   * <br>
   * 指定されたレコードを格納するコレクション・オブジェクトが存在しない場合は、
   * 空のコレクション・オブジェクトを返す。
   *
   * @param  record レコード・オブジェクト。
   * @return 引数のレコード・オブジェクトを格納するコレクション・オブジェクト。
   * @throws AssertionError 引数がヌルの場合（デバッグ・モードのみ）。
   */
  protected Collection<Record<C,V>> getIndexedCollection(Record<C,V> record)
  {
    assert (record != null) : "@param:record is null.";

    IndexNodeMap map = rootMap_ ;

    for (int i=0; i<indexKeys_.length-1; i++) {
      Object obj = map.get(record.get(indexKeys_[i]));
      if (obj != null && (obj instanceof HashMap)) {
        map = (IndexNodeMap) obj;
      }
      else {
        return new RecordSet();
      }
    }

    Object last = map.get(record.get(indexKeys_[indexKeys_.length-1]));
    if (last != null && (last instanceof IdentityHashSet)) {
      return (RecordSet) last;
    }
    else {
      return new RecordSet();
    }
  }

  /**
   * 指定されたレコードを格納する、インデックス・ツリーの末端に設定されている
   * コレクション・オブジェクトを取得する。
   * <br>
   * 指定されたレコードを格納するコレクション・オブジェクトが存在しない場合は、
   * そのコレクション・オブジェクトを作成して返す。
   *
   * @param  record レコード・オブジェクト。
   * @return 引数のレコード・オブジェクトを格納するコレクション・オブジェクト。
   * @throws AssertionError 引数がヌルの場合（デバッグ・モードのみ）。
   */
  protected Collection<Record<C,V>> getIndexedCollectionByForce(
    Record<C,V> record)
  {
    assert (record != null) : "@param:record is null.";

    IndexNodeMap map = rootMap_ ;

    for (int i=0; i<indexKeys_.length-1; i++) {
      V val = record.get(indexKeys_[i]);
      Object obj = map.get(val);
      if (obj != null && (obj instanceof HashMap)) {
        map = (IndexNodeMap) obj;
      }
      else {
        IndexNodeMap m = new IndexNodeMap();
        map.put(val, m);
        map = m;
      }
    }

    RecordSet set;
    V lastVal = record.get(indexKeys_[indexKeys_.length - 1]);
    Object lastObj = map.get(lastVal);
    if (lastObj != null && (lastObj instanceof IdentityHashSet)) {
      set = (RecordSet) lastObj;
    }
    else {
      set = new RecordSet();
      map.put(lastVal, set);
    }
    set.add(record);
    return set;
  }

  /**
   * このインデックスから全てのレコードを削除する。
   */
  protected void deleteAllRecordsFromIndex()
  {
    rootMap_.clear();
  }


  /* -- inner class -- */

  /**
   * インデックス・ツリーを構成するマップ・クラス。
   */
  protected class IndexNodeMap extends HashMap<V,Object>
  {
    /** シリアル・バージョン番号。 */
    static final long serialVersionUID = 8037487212928327L;
  }

  /**
   * レコードを格納するセット・クラス。
   * <br>
   * インデックス・ツリーの末端に配置され、インデックス・キーの値が同じレコード
   * の集合を格納する。
   * <br>
   * このクラスは、内部に{@link ts.util.IdentityHashSet IdentityHashSet}を
   * 持っており、これにレコードが格納される。
   * すなわち、レコードの同一性は <code>record1.equals(record2)</code> ではなく
   * <code>record1 == record2</code> により判定される。
   * そのため、{@link #add(java.lang.Object)}メソッドを
   * 実行した際に別オブジェクトでカラムとキーの組み合わせが同じレコードが上書き
   * されたりすることもなく、また、{@link #remove(java.lang.Object)}を実行した
   * 際に、カラムとキーの組み合わせが等しい別のレコードが削除されたりすること
   * はない。
   */
  protected class RecordSet extends IdentityHashSet<Record<C,V>>
  {
    /** シリアル・バージョン番号。 */
    static final long serialVersionUID = 5528842630870790522L;
  }
}

