/*
 * Created on 2005-5-14
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package treeNode;

/**
 * @author ade
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
import java.io.Serializable;
/**
 * <p>Title: class My23Tree</p>
 * <p>Description: 實現一個3階B-樹(2-3樹).</p>
 * <p>Copyright: Copyright (c) 2004</p>
 * @author WLD
 * @version 1.0
 */

public class My23Tree implements Serializable
{
  private My23TreeNode root;   // 根結點

  // public methods
  // 默認構造方法. 構造一個空的B-樹
  public My23Tree() {
    root = null;
  }

  // 插入關鍵字。若成功則返回true，存在相同關鍵字則返回false
  public boolean insertKey( AbstractKey key, Object record )
  {
    if( root == null )  // 如果樹為空，建立新結點
    {
      root = new My23TreeNode(key, record, null);
    }
    else  // 樹非空
    {
      SearchResult result = search( key ); // 先進行查找以確定插入位置
      if( result.isFound() )               // 存在相同結點，插入失敗
        return false;
      else   // 不存在相同結點，且確定插入位置
      {
        My23TreeNode p = result.getNode();  // 插入位置
        My23TreeNode q = null;              // 分裂時新建立的結點
        int index = result.getIndex();
        while( p.insertKeyAt(key, record, index) == false ) // 需進行結點分裂
        {
          if( q != null )
          {
            p.children[index + 1] = q;      // 更新children引用
          }
          q = new My23TreeNode(p.keys[3], p.records[3], p.parent); // 建立新結點
          q.children[0] = p.children[2];    // 更新children引用
          q.children[1] = p.children[3];
          if( q.children[0] != null ) q.children[0].parent = q; // 更新parent的children指針
          if( q.children[1] != null ) q.children[1].parent = q;
          key = p.keys[2];
          record = p.records[2];
          p.keyNum = 1;          // 修改原結點
          p.keys[2] = p.keys[3] = null;
          p.records[2] = p.records[3] = null;
          p.children[2] = p.children[3] = null;
          if( p.parent == null ) // 若p為根結點，則建立新的根結點
          {
            p.parent = new My23TreeNode( key, record, null );
            p.parent.children[0] = p;
            p.parent.children[1] = q;
            root = p.parent;
            q.parent = p.parent;
            q = null;
            break;
          }
          for( index = 0; p.parent.children[index] != p && index < 2; index++ );
          p = p.parent;          // 更新p和index用于繼續向parent插入關鍵字
        }
        if( q != null )
        {
          p.children[index + 1] = q;  // 如有必要，更新children引用
        }
      }
    }
    return true;
  }

  // 刪除關鍵字
  public Object deleteKey( AbstractKey key )
  {
    SearchResult result = search( key ); // 先進行查找以確定插入位置
    if( !result.isFound() )   // 未找到關鍵字，刪除失敗
      return null;
    else    // 找到了關鍵字
    {
      My23TreeNode p = result.getNode();
      int index = result.getIndex();
      deleteKey( p, index );   // 調用私有方法刪除結點p上的第index個關鍵字
      return result.getRecord();
    }
  }

  // 查找關鍵字。找到則返回指向記錄的引用，否則返回null
  public Object searchByKey( AbstractKey key )
  {
    return search(key).getRecord();
  }

  // 以字符串形式輸出樹的信息
  public String toString()
  {
    return root == null? "" : toString(root, "", false);
  }

  // private methods
  // 私有方法deleteKey刪除給定結點p上的第index個關鍵字
  private void deleteKey( My23TreeNode p, int index )
  {
    if( p.children[0] == null )  // p為最下層結點
    {
      if( p.keyNum > 1 ) // 關鍵字大于1或為根結點，直接刪除即可
      {
        p.deleteKeyAt(index);
        p.keys[p.keyNum+1] = null;
        p.records[p.keyNum+1] = null;
        p.children[p.keyNum+1] = null;
      }
      else               // 否則就麻煩些
      {
        if( p == root )  // 整棵樹就一個根結點且就包含一個關鍵字，刪除后即為空樹一棵
        {
          root = null;
          return;
        }
        int indexInParent = 0;
        if( p.parent.children[1] == p ) indexInParent = 1;
        else if( p.parent.children[2] == p ) indexInParent = 2;  // 確定p在其parent中的位置
        // 右邊的兄弟有足夠的關鍵字，就借一個給parent，并把parent中的拿來給自己
        if( indexInParent < p.parent.keyNum && p.parent.children[indexInParent+1].keyNum > 1 )
        {
          p.keys[index] = p.parent.keys[indexInParent + 1];
          p.records[index] = p.parent.records[indexInParent + 1];

          p.parent.keys[indexInParent + 1] =
              p.parent.children[indexInParent + 1].keys[1];
          p.parent.records[indexInParent + 1] =
              p.parent.children[indexInParent + 1].records[1];

          p.parent.children[indexInParent + 1].keys[1] =
              p.parent.children[indexInParent + 1].keys[2];
          p.parent.children[indexInParent + 1].records[1] =
              p.parent.children[indexInParent + 1].records[2];

          p.parent.children[indexInParent + 1].keys[2] = null;
          p.parent.children[indexInParent + 1].records[2] = null;
          p.parent.children[indexInParent + 1].keyNum = 1;
          return;
        }
        // 左邊的兄弟有足夠的關鍵字
        if( indexInParent > 0 && p.parent.children[indexInParent-1].keyNum > 1 )
        {
          p.keys[index] = p.parent.keys[indexInParent];
          p.records[index] = p.parent.records[indexInParent];

          p.parent.keys[indexInParent] =
              p.parent.children[indexInParent - 1].keys[2];
          p.parent.records[indexInParent] =
              p.parent.children[indexInParent - 1].records[2];

          p.parent.children[indexInParent - 1].keys[2] = null;
          p.parent.children[indexInParent - 1].records[2] = null;
          p.parent.children[indexInParent - 1].keyNum = 1;
          return;
        }
        // 所有相鄰兄弟的關鍵字數目均為1...
        if (indexInParent < p.parent.keyNum) { // 右面有兄弟，向右合并
          p.parent.children[indexInParent] = null;
          p.parent.children[indexInParent + 1].insertKeyAt(
              p.parent.keys[indexInParent + 1],
              p.parent.records[indexInParent + 1], 0);
          p.parent.deleteKeyAt(indexInParent + 1);
          p = p.parent.children[indexInParent + 1];
        }
        else { // 右面沒兄弟左面一定有（B-Tree性質，且p不為根結點），向左合并
          p.parent.children[indexInParent] = null;
          p.parent.children[indexInParent - 1].insertKeyAt(
              p.parent.keys[indexInParent],
              p.parent.records[indexInParent], 1);
          p.parent.keys[indexInParent] = null;
          p.parent.records[indexInParent] = null;
          p.parent.keyNum--;
          p = p.parent.children[indexInParent - 1];
        }
        if (p.parent.keyNum > 0)     // parent中還有足夠結點
          return;               // 刪除完成。無需向上合并
        else { // parent已沒有足夠關鍵字，需要向上重復合并
          p.parent.keys[1] = p.keys[1];
          p.parent.keys[2] = p.keys[2];
          p.parent.records[1] = p.records[1];
          p.parent.records[2] = p.records[2];

          p.parent.children[0] = p.parent.children[1] =
              p.parent.children[2] = null;
          p.parent.keyNum = 2;
          p = p.parent;
          merge(p);
        }
      }
    } // if( p.children[0] == null )  // p為最下層結點
    else  // p非最下層結點
    {
      My23TreeNode q = p.children[index];
      while( q.children[0] != null )
        q = q.children[0];           // 找到對應子樹中包含最小關鍵字的結點
      p.keys[index] = q.keys[1];     // 用對應子樹中的最小關鍵字代替
      p.records[index] = q.records[1];
      deleteKey( q, 1 );             // 刪除多余的最小關鍵字
    }
  }

  // 用于刪除結點時“合并”的方法。將srcNode和其parent中的對應關鍵字一起合并到相鄰兄弟結點
  // 此方法中并未刪除任何關鍵字，只是對在deleteKey方法中刪除掉關鍵字的樹進行整理合并
  private void merge( My23TreeNode node )
  {
    if( node == root ) return;

    int indexInParent = 0;
    if (node.parent.children[1] == node) indexInParent = 1;
    else if (node.parent.children[2] == node) indexInParent = 2; // 確定node在其parent中的位置

    while( true )
    {
      if (indexInParent < node.parent.keyNum) { // node右面有兄弟，向右合并