/******************************************************************************
Insert Sort
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.searchAndSort;

import FlexOr.container.*;

/** Sort an array of objects using insert sort.

<P>
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/

public class InsertSort implements ArraySort {

/**
@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public void sort(final Object[] array, final BinaryPredicate bp) {
       execute(array, bp);
   }

/** The insert sort method.

@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public static void execute(final Object[] array, final BinaryPredicate bp) {
       Object tmp;

    // Loop invariant: for i : 0..array.length :: ( sorted(array[0..i-1])
       
       for (int i = 1 ; i < array.length ; i++) {
           
           // Loop invariant: array[j] bp array[j+1..i]
       
           for (int j = i ; j > 0 && bp.execute(array[j], array[j-1]) ; j--) {
               tmp = array[j]; array[j] = array[j-1]; array[j-1] = tmp;
           }
       }
   }
}