/*
 * [ShellSort.java]
 *
 * Summary: ShellSort to sort an array of Objects.
 *
 * Copyright: (c) 1998-2017 Roedy Green, Canadian Mind Products, http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.8+
 *
 * Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.0 1998-01-01 initial release.
 *  1.1 1998-12-28 JDK1.2 style Comparator interface
 *  1.2 2002-02-19 use java.util.Comparator by default.
 *  1.3 2002-03-30 tidy code a bit.
 *  1.4 2008-01-01 add generics
 */
package com.mindprod.shellsort;

import java.util.Comparator;

import static java.lang.System.*;

/**
 * ShellSort to sort an array of Objects.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.4 2008-01-01 add generics
 * @since 1998-01-01
 */
public class ShellSort<T>
    {
    private static final boolean DEBUGGING = false;

    private static final int FIRST_COPYRIGHT_YEAR = 1998;

    private static final String EmbeddedCopyright =
            "Copyright: (c) 1998-2017 Roedy Green, Canadian Mind Products, http://mindprod.com";

    /**
     * when package released.
     *
     * @noinspection UnusedDeclaration
     */
    private static final String RELEASE_DATE = "2008-01-01";

    /**
     * embedded version string.
     */
    @SuppressWarnings( { "UnusedDeclaration" } )
    private static final String VERSION_STRING = "1.4";

    // callback object we are passed that has
    // a Comparator( <? super T> a, <? super T> b ) method.
    private Comparator<? super T> comparator;

    // pointer to the array of user's objects we are sorting
    private T[] userArray;

    // check if user's array is already sorted
    private boolean isAlreadySorted()
        {
        for ( int i = 1; i < userArray.length; i++ )
            {
            if ( comparator.compare( userArray[ i ], userArray[ i - 1 ] ) < 0 )
                {
                return false;
                }
            }
        return true;
        } // end isAlreadySorted

    // Sort the user's array
    public static <T> void sort( T[] userArray, Comparator<? super T> comparator )
        {
        ShellSort<T> s = new ShellSort<>();
        s.userArray = userArray;
        s.comparator = comparator;
        if ( s.isAlreadySorted() )
            {
            return;
            }
        // ShellSort proper
        // h is the separation between items we compare.
        int h = 1;
        while ( h < userArray.length )
            {
            h = 3 * h + 1;
            }
        while ( h > 0 )
            {
            h = ( h - 1 ) / 3;
            for ( int i = h; i < userArray.length; ++i )
                {
                T item = userArray[ i ];
                int j;
                for ( j = i - h;
                      j >= 0 && comparator.compare( item, userArray[ j ] ) < 0;
                      j -= h )
                    {
                    userArray[ j + h ] = userArray[ j ];
                    } // end inner for
                userArray[ j + h ] = item;
                } // end outer for
            } // end while
        if ( DEBUGGING )
            {
            if ( !s.isAlreadySorted() )
                {
                out.println( "Sort failed" );
                }
            }
        } // end sort
    } // end class ShellSort