sorters.java

实现数据库的storage manager 功能

/*
 * Copyright (c) 2000-2004, Rickard C鰏ter, Martin Svensson
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 * Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer. 
 * Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution. 
 * Neither the name of SICS nor the names of its contributors 
 * may be used to endorse or promote products derived from this software 
 * without specific prior written permission. 
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 *
 *
 */

package com.mellowtech.disc.sort;

import java.nio.*;
import java.util.*;
import com.mellowtech.disc.ByteComparable;

/**
 * A number of static methods for sorting data
 *
 * @author Martin Svensson
 * @version 1.0
 */
public class Sorters{

  /**
   * Sort objects that are stored in a byte buffer using heap sort.
   * @param n[] start offsets in the buffer
   * @param bc a comparator for byte level comparisons
   * @param buffer has to be either a byte[] or java.nio.ByteBuffer
   */
  public static void heapSort(int n[], ByteComparable bc, Object buffer){
    if(buffer instanceof ByteBuffer)
      ByteBufferHeap.heapSort(n, (ByteBuffer) buffer, bc);
    else if(buffer instanceof byte[])
      ByteHeap.heapSort(n, (byte[]) buffer, bc);
  }

  /**
   * Sort using heap sort.
   * @param n[] objects to sort
   */
  public static void heapSort(Comparable n[]){
    Heap.heapSort(n);
  }
  
  /**
   * Sort objects that are stored in a byte buffer using quickSort.
   * @param n[] start offsets in the buffer
   * @param bc a comparator for byte level comparisons
   * @param buffer has to be either a byte[] or java.nio.ByteBuffer
   * @param endPos only sort up to endPos offsets in the array.
   */
  public static final void quickSort(int n[], ByteComparable bc, Object buffer, int endPos){
    if(buffer instanceof ByteBuffer){
      quickSort(n, 0, endPos-1, (ByteBuffer) buffer, bc);
      insertionSort(n, 0, endPos-1, (ByteBuffer) buffer, bc);
    }
    else if(buffer instanceof byte[]){
      quickSort(n, 0, endPos-1, (byte[]) buffer, bc);
      insertionSort(n, 0, endPos-1, (byte[]) buffer, bc);
    }
  }

  /**
   * Sort objects that are stored in a byte buffer using quickSort.
   * @param n[] offsets in a byte buffer
   * @param bc a comparator for byte level comparisons
   * @param buffer has to be either a byte[] or java.nio.ByteBuffer
   * @see java.nio.ByteBuffer
   */
  public static final void quickSort(int n[], ByteComparable bc, Object buffer){
    quickSort(n, bc, buffer, n.length);
  }

  /**
   * Sort objects using non-recursive quickSort.
   * @param n[] objects to sort
   */
  public static final void quickSortStack(Comparable n[]){
    LinkedList al = new LinkedList();
    al.addFirst(new LeftRight(0, n.length-1));
    quickSortStack(n, al);
    insertionSort(n, 0, n.length-1);
  }

  /**
   * Sort objects using non-recursive quickSort.
   * @param n[] objects to sort
   * @param endPos only sort endPos number of objects
   */
  public static final void quickSortStack(Comparable n[], int endPos){
    LinkedList al = new LinkedList();
    al.addFirst(new LeftRight(0, endPos-1));
    quickSortStack(n, al);
    insertionSort(n, 0, endPos-1);
  }

  /**
   * Sort objects using quickSort.
   * @param n[] objects to sort
   */
  public static final void quickSort(Comparable n[]){
    quickSort(n, 0, n.length-1);
    insertionSort(n, 0, n.length-1);
  }

  /**
   * Sort objects using quickSort.
   * @param n[] objects to sort
   * @param endPos only sort endPos number of objects
   */
  public static final void quickSort(Comparable n[], int endPos){
    quickSort(n, 0, endPos-1);
    insertionSort(n, 0, endPos-1);
  }

  private static final void quickSort(int n[], int left, int right, 
				ByteBuffer bb, ByteComparable bc){
    int min = 4;
    int middle, j;
    int tmp;
    
    if((right-left) > min){
    
      //Tri-median:
      middle = (right+left) / 2;
      if(bc.byteCompare(n[left], n[middle], bb) > 0) swap(n, left, middle);
      if(bc.byteCompare(n[left], n[right], bb) > 0) swap(n, left, right);
      if(bc.byteCompare(n[middle], n[right], bb) > 0) swap(n, middle, right);
      
      j = right - 1;
      swap(n, middle, j);
      middle = left;
      tmp = n[j];
      for(;;){
	while(bc.byteCompare(n[++middle], tmp, bb) < 0);
	while(bc.byteCompare(n[--j], tmp, bb) > 0);
	if(j < middle)
	  break;
	swap(n, middle, j);
      }
      swap(n, middle, right-1);
      
      quickSort(n,left,j, bb, bc);
      quickSort(n,middle+1,right, bb, bc);
    }
  }

  private static void quickSort(int n[], int left, int right, 
				byte[] bb, ByteComparable bc){
    int min = 4;
    int middle, j;
    int tmp;
    
    if((right-left) > min){
    
      //Tri-median:
      middle = (right+left) / 2;
      if(bc.byteCompare(n[left], n[middle], bb) > 0) swap(n, left, middle);
      if(bc.byteCompare(n[left], n[right], bb) > 0) swap(n, left, right);
      if(bc.byteCompare(n[middle], n[right], bb) > 0) swap(n, middle, right);
      
      j = right - 1;
      swap(n, middle, j);
      middle = left;
      tmp = n[j];
      for(;;){
	while(bc.byteCompare(n[++middle], tmp, bb) < 0);
	while(bc.byteCompare(n[--j], tmp, bb) > 0);
	if(j < middle)
	  break;
	swap(n, middle, j);
      }
      swap(n, middle, right-1);
      
      quickSort(n,left,j, bb, bc);
      quickSort(n,middle+1,right, bb, bc);
    }
  }

  private static void quickSort(Comparable n[], int left, int right){
    int min = 4;
    int middle, j;
    Comparable tmp;
    
    if((right-left) > min){
    
      //Tri-median:
      middle = (right+left) / 2;
      if(n[left].compareTo(n[middle]) > 0) swap(n, left, middle);
      if(n[left].compareTo(n[right]) > 0) swap(n, left, right);
      if(n[middle].compareTo(n[right]) > 0) swap(n, middle, right);
      
      j = right - 1;
      swap(n, middle, j);
      middle = left;
      tmp = n[j];
      for(;;){
	while(n[++middle].compareTo(tmp) < 0);
	while(n[--j].compareTo(tmp) > 0);
	if(j < middle)
	  break;
	swap(n, middle, j);
      }
      swap(n, middle, right-1);
      
      quickSort(n,left,j);
      quickSort(n,middle+1,right);
    }
 }

  private static void quickSortStack(Comparable n[], LinkedList stack){
    int min = 4;
    int middle, j;
    Comparable tmp;
    int left, right;
    LeftRight lr;

    while(stack.size() > 0){
      
      lr = (LeftRight) stack.removeFirst();
      left = lr.left;
      right = lr.right;

      if((right - left) < min)
	continue;
    
      //Tri-median:
      middle = (right+left) / 2;
      if(n[left].compareTo(n[middle]) > 0) swap(n, left, middle);
      if(n[left].compareTo(n[right]) > 0) swap(n, left, right);
      if(n[middle].compareTo(n[right]) > 0) swap(n, middle, right);
    
      j = right - 1;
      swap(n, middle, j);
      middle = left;
      tmp = n[j];
      for(;;){
	while(n[++middle].compareTo(tmp) < 0);
	while(n[--j].compareTo(tmp) > 0);
	if(j < middle)
	  break;
	swap(n, middle, j);
      }
      swap(n, middle, right-1);
      lr.left = middle + 1;
      lr.right = right;
      //System.out.println("pushing to stack");
      stack.addFirst(lr);
      stack.addFirst(new LeftRight(left, j));
    }
  }

  private static final void swap(Object[] n, int i, int j){
    Object tmp;
    tmp = n[i];
    n[i] = n[j];
    n[j] = tmp;
  }

   private static final void swap(int[] n, int i, int j){
    int tmp;
    tmp = n[i];
    n[i] = n[j];
    n[j] = tmp;
  }

  private static final void insertionSort(Comparable a[], int lo0, int hi0){
    int i;
    int j;
    Comparable v;
    
    for (i=lo0+1;i<=hi0;i++){
      v = a[i];
      j=i;
      while ((j>lo0) && (a[j-1].compareTo(v)>0)){
	  a[j] = a[j-1];
	  j--;
      }
      a[j] = v;
    }
  }

  private static final void insertionSort(int a[], int lo0, int hi0,
					  ByteBuffer bb, ByteComparable bc){
    int i;
    int j;
    int v;
    
    for (i=lo0+1;i<=hi0;i++){
      v = a[i];
      j=i;
      while ((j>lo0) && (bc.byteCompare(a[j-1], v, bb)>0)){
	  a[j] = a[j-1];
	  j--;
      }
      a[j] = v;
    }
  }

  private static final void insertionSort(int a[], int lo0, int hi0,
					  byte[] bb, ByteComparable bc){
    int i;
    int j;
    int v;
    
    for (i=lo0+1;i<=hi0;i++){
      v = a[i];
      j=i;
      while ((j>lo0) && (bc.byteCompare(a[j-1],v, bb)>0)){
	  a[j] = a[j-1];
	  j--;
      }
      a[j] = v;
    }
  }
}

final class LeftRight{
  int left, right;
  public LeftRight(int l, int r){
    left = l; right = r;
  }
}