/**
 * The MIT License
 * Copyright © 2020 Luis Andrés Lange <http://javacomm.net>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package org.nexuswob.util;

import java.util.Vector;

/*****************************************************************************/
/*                                                                           */
/*                              Class Quicksort                              */
/*                                                                           */
/*****************************************************************************/



public class Quicksort {

  private Object a [];
  private int left, right, count;
  private Integer integer [];
  private Vector<?> vector [];


  /* f�r alphanumerische Typen */
  public Quicksort (Object [] obj)  {
    this.a = obj;
    count = obj.length;
    left = 0;
    right = count-1;
    if (left>=right) return;
    quicksortAlpha (left, right);
  }


  /* f�r Record Typen */
  public Quicksort (Vector<?> [] vector, SelectNodeIndex select)  {
    this.vector = vector;
    count = vector.length;
    left = 0;
    right = count-1;
    if (left>=right) return;


    switch (select.getType ())  {

      case SelectNodeIndex.NUMERIC :
        quicksortVectorNumeric (left, right, select.getKeyIndex ());
        break;
      case SelectNodeIndex.ALPHA_NUMERIC :
        quicksortVectorAlpha (left, right, select.getKeyIndex ());
        break;
      default : break;
    }
  }




  /* f�r numerische Typen */
  public Quicksort (Integer [] integer)  {
    this.integer = integer;
    count = integer.length;
    left = 0;
    right = count-1;
    if (left>=right) return;
    quicksort (left, right);
  }





  private void quicksortVectorNumeric (int left, int right, int keyIndex)  {
    int i, j;
    Vector<?> v, t;

    if (right<=left) return;
    v = vector [right];
    i = left-1;
    j = right;


    do {
      while (((Integer) (vector [++i].elementAt (keyIndex))).intValue ()< ((Integer) (v.elementAt (keyIndex))).intValue ())  {}
      try  {
        while (((Integer) (vector [--j].elementAt (keyIndex))).intValue ()>((Integer) (v.elementAt (keyIndex))).intValue ())  {}
      }
      catch (ArrayIndexOutOfBoundsException e)  {
        j++;
      }

      t = vector [i];
      vector [i] = vector [j];
      vector [j] = t;

    } while (j>i);


    vector [j] = vector [i];
    vector [i] = vector [right];
    vector [right] = t;

    quicksortVectorNumeric (left, i-1, keyIndex);
    quicksortVectorNumeric (i+1, right, keyIndex);



  }





  private void quicksortVectorAlpha (int left, int right, int keyIndex)  {

    int i, j; // Indices
    Vector<?> v, t; // Hilfsvariable

    if (right<=left) return;

    v = vector [right];
    i = left-1;
    j = right;

    do {
      while (vector [++i].elementAt (keyIndex).toString ().compareTo (v.elementAt (keyIndex).toString ())<0)  {}
      try  {
        while (vector [--j].elementAt (keyIndex).toString ().compareTo (v.elementAt (keyIndex).toString ())>0)  {}
      }
      catch (ArrayIndexOutOfBoundsException e)  {
        j++;
      }

      t = vector [i];
      vector [i] = vector [j];
      vector [j] = t;

    } while (j>i);

    vector [j] = vector [i];
    vector [i] = vector [right];
    vector [right] = t;

    quicksortVectorAlpha (left, i-1, keyIndex);
    quicksortVectorAlpha (i+1, right, keyIndex);

  }




  private void quicksort (int left, int right)  {

    int i, j; // Indices
    int v, t; // Hilfsvariable

    if (right<=left) return;

    v = integer [right].intValue ();
    i = left-1;
    j = right;

    do {
      while (integer [++i].intValue ()<v)  {}

      try  {
        while (integer [--j].intValue ()>v)  {}
      }
      catch (ArrayIndexOutOfBoundsException e)  {
        j++;
      }

      t = integer [i].intValue ();
      integer [i] = integer [j];
      integer [j] = t;

    } while (j>i);

    integer [j] = integer [i];
    integer [i] = integer [right];
    integer [right] = t;


    quicksort (left, i-1);
    quicksort (i+1, right);

  }








  private void quicksortAlpha (int left, int right)  {

    int i, j; // Indices
    Object v, t; // Hilfsvariable

    if (right<=left) return;

    v = a [right];
    i = left-1;
    j = right;

    do {
      while (a [++i].toString ().compareTo (v.toString ())<0)  {}
      try  {
        while (a [--j].toString ().compareTo (v.toString ())>0)  {}
      }
      catch (ArrayIndexOutOfBoundsException e)  {
        j++;
      }

      t = a [i];
      a [i] = a [j];
      a [j] = t;

    } while (j>i);

    a [j] = a [i];
    a [i] = a [right];
    a [right] = t;

    quicksortAlpha (left, i-1);
    quicksortAlpha (i+1, right);

  }




}