import java.awt.*;
public class LSort
 {
  private int DELAY = 15;
  private int temp = 0;
  LC lc;
  private boolean INNER = false;
  private boolean OUTER = true;
  int sa[];
  int s=0;
  static M parent;
  static Te te=M.te0;
  String name;
  public LSort(M p,String n,int N,LC lc)
   {
    parent=p;
    name=n;
    this.lc=lc;
    setsize(N);
    shuffle();
    tta("LSort:"+name+" is shuffled");
    render();
   }
  void ed() 
   {
    // tta1(name+".e "+te.Svo(e)); 
   }
  static void tta1(String s) { parent.tta1(s); }
  static void tta(String s) { parent.tta(s); }
  public void setInnerDelay()
   {
    INNER = true;
    OUTER = false;
   }
  public void setOuterDelay()
   {
    INNER = false;
    OUTER = true;
   }
  public void setNoDelay()
   {
    INNER = false;
    OUTER = false;
   }
  public void setsize(int N)
   {
    s=N;
    if(sa==null || N != sa.length) sa=new int[N];
   }
  public void shuffle()
   {
    int val,i;
    for(i=0;i<s;i++)
     {
      do
      val = (int)((double)s * Math.random());
      while(alreadyThere(sa, val, i));
      sa[i]=val;
     }
    i = 0;
    do
     {
      if(i >= s)
      break;
      if(sa[i] == s - 1)
       {
        sa[i] = sa[0];
        sa[0] = s - 1;
        break;
       }
      i++;
     }
    while(true);
   }
  private boolean alreadyThere(int sa[], int num, int bound)
   {
    for(int i = 0; i < bound; i++)
     {
      if(sa[i] == num) return true;
     }
    return false;
   }
  public  void dist(int sa[], int N, LC lc) throws InterruptedException
   {
    int n=N;
    int counter[] = new int[n];
    for(int i = 0; i < n; i++) counter[n - 1 - sa[i]] = sa[i];
    for(int i = 0; i < n; i++)
     {
      sa[i] = counter[i];
      if(INNER || OUTER)
       {
        Thread.sleep(15L);
        lc.repaint();
       }
     }
    lc.repaint();
   }
  public void selection()
   {
    int maxElem = 0;
    for(int i = 0; i < sa.length - 1; i++)
     {
      maxElem = i;
      for(int j = i + 1; j < sa.length; j++)
       {
        if(INNER)
         {
          sleep(15);
          render();
         }
        if(sa[j] > sa[maxElem])
        maxElem = j;
       }
      temp = sa[maxElem];
      sa[maxElem] = sa[i];
      sa[i] = temp;
      if(OUTER)
       {
        sleep(15);
        render();
       }
     }
    render();
   }
  public void sleep(double d) { te.schleep(d); }
  public void bubble()
   {
    for(int i = 0; i < sa.length; i++)
     {
      if(OUTER)
       {
        sleep(15);
        render();
       }
      for(int j = sa.length - 1; j > i; j--)
       {
        if(sa[j - 1] >= sa[j]) continue;
        temp = sa[j - 1];
        sa[j - 1] = sa[j];
        sa[j] = temp;
        if(INNER)
         {
          sleep(15);
          render();
         }
       }
     }
   }
  public void insertion()
   {
    int j = 0;
    for(int i = 1; i < sa.length; i++)
     {
      if(OUTER)
       {
        sleep(15);
        render();
       }
      int v = sa[i];
      j = i;
      do
       {
        if(j <= 0 || sa[j - 1] >= v)
        break;
        sa[j] = sa[j - 1];
        j--;
        if(INNER)
         {
          sleep(15);
          render();
         }
       }
      while(true);
      sa[j] = v;
     }
    render();
   }
  public void shell()
   {
    int n=sa.length;
    int j = 0;
    int h = 1;
    int v = 0;
    do
    h = 3 * h + 1;
    while(h <= n);
    do
     {
      h /= 3;
      for(int i = h; i < n; i++)
       {
        if(OUTER)
         {
          sleep(15);
          render();
         }
        v = sa[i];
        j = i;
        do
         {
          if(j < h || sa[j - h] >= v)
          break;
          sa[j] = sa[j - h];
          j -= h;
          if(j <= h)
          break;
          if(INNER)
           {
            sleep(15);
            render();
           }
         }
        while(true);
        sa[j] = v;
       }
     }
    while(h != 0);
    render();
   }
  public void qs()
   {
    try { quicksort(0,sa.length-1); }
    catch (Throwable e) {}
   }
  private void quicksort(int left, int right) throws InterruptedException
   {
    if(right > left)
     {
      int p=partition(left,right);
      quicksort(left,p-1);
      render();
      quicksort(p+1,right);
      render();
     }
   }
  private int partition(int start, int end) throws InterruptedException
   {
    int left = start - 1;
    int right = end;
    do
     {
      int p;
      for(p = sa[end]; p < sa[++left] && left != end;);
      while(p > sa[--right] && right != start) ;
      if(left >= right) break;
      temp = sa[left];
      sa[left] = sa[right];
      sa[right] = temp;
      //if(INNER || OUTER) { Thread.sleep(15L); render(start,end); }
     }
    while(true);
    temp = sa[left];
    sa[left] = sa[end];
    sa[end] = temp;
    return left;
   }
  public void radixExchange()
   {
    int n=sa.length;
    radixExchangeDo(0, n - 1, 9);
    render();
   }
  private void radixExchangeDo(int left, int right, int b)
   {
    if(right > left && b >= 0)
     {
      int i = left;
      int j;
      do
       {
        for(j = right; bits(sa[i], b, 1) == 1 && i < j; i++);
        for(; bits(sa[j], b, 1) == 0 && i < j; j--);
        temp = sa[i];
        sa[i] = sa[j];
        sa[j] = temp;
        if(INNER)
         {
          sleep(15);
          render();
         }
       }
      while(j != i);
      if(bits(sa[right], b, 1) == 1)
      j++;
      if(OUTER)
       {
        sleep(15);
        render();
       }
      radixExchangeDo(left, j - 1, b - 1);
      radixExchangeDo(j, right, b - 1);
     }
   }
  public  void radixStraight(int sa[], int N, LC lc) throws InterruptedException
   {
    int n=N;
    int sa2[] = new int[sa.length];
    System.arraycopy(sa, 0, sa2, 0, sa.length);
    int m = 5;
    int M = 32;
    int w = 20;
    int count[] = new int[n];
    int b[] = new int[n];
    for(int pass = 0; pass < w / m - 1; pass++)
     {
      for(int j = 0; j < M - 1; j++)
      count[j] = 0;
      for(int i = 0; i < n - 1; i++)
      count[bits(sa2[i], pass * m, m)] = count[bits(sa2[i], pass * m, m)] + 1;
      for(int j = 1; j < M; j++)
      count[j] = count[j - 1] + count[j];
      for(int i = n - 1; i >= 0; i--)
       {
        b[count[bits(sa2[i], pass * m, m)]] = sa2[i];
        count[bits(sa2[i], pass * m, m)] = count[bits(sa2[i], pass * m, m)] - 1;
        if(INNER)
         {
          Thread.sleep(15L);
          lc.repaint();
         }
       }
      for(int i = 0; i < n; i++)
      sa2[i] = b[i];
      for(int i = 0; i < sa.length; i++)
      sa[i] = n - sa2[i];
      if(OUTER)
       {
        Thread.sleep(15L);
        lc.repaint();
       }
     }
   }
  private final int bits(int i, int position, int howMany)
   {
    int mask = (1 << howMany) - 1;
    return i >> position & mask;
   }
  public void merge(int sa[], int N, LC lc) throws InterruptedException
   {
    int n=N;
    lc = lc;
    mergesort(sa, 0, n, n,lc);
    lc.repaint();
   }
  private void mergesort(int sa[], int left, int right, int total,LC lc)
  throws InterruptedException
   {
    if(right <= left)
    return;
    int middle = (right + left) / 2;
    mergesort(sa, left, middle, total,lc);
    mergesort(sa, middle + 1, right, total,lc);
    int atemp[] = new int[total];
    int i;
    for(i = middle; i > left; i--)
     {
      atemp[i] = sa[i];
      System.out.print(String.valueOf(String.valueOf(sa[i])).concat(", "));
     }
    int j;
    for(j = middle + 1; j < right; j++)
     {
      atemp[(right + middle + 1) - j] = sa[j];
      System.out.print(String.valueOf(String.valueOf(sa[j])).concat(", "));
     }
    System.out.println("\n---\n");
    if(OUTER)
     {
      Thread.sleep(15L);
      lc.repaint();
     }
    for(int k = left; k < right; k++)
     {
      if(atemp[i] < atemp[j])
       {
        sa[k] = atemp[i];
        i++;
       }
      else
       {
        sa[k] = atemp[j];
        j--;
       }
      if(INNER)
       {
        Thread.sleep(15L);
        lc.repaint();
       }
     }
   }
  void render()
   {
    int n=sa.length;
    double gwx=lc.width;
    double gwy=lc.height;
    double grscy=gwy/n;
    double offay=-gwy/2;
    double dx=gwx/n;
    double glx=-gwx/2;
    Rec rec;
    lc.clearoffscreen();
    for(int i = 0; i < n; i++) 
     {
      rec=new Rec(glx+(dx*i),offay,dx,grscy*sa[i]);
      lc.rRecoffs(rec,true);
     }
    lc.repaint();
   }
  void render(int l,int u)
   {
    tta("render l:"+l+" u:"+u);
    int n=sa.length;
    double gwx=lc.width;
    double gwy=lc.height;
    double grscy=gwy/n;
    double offay=-gwy/2;
    double dx=gwx/n;
    double glx=-gwx/2;
    Rec rec;
    K k=new K(255,255,255);
    lc.offsg.setColor(k.c);
    rec=new Rec(glx+(dx*l),offay,dx*(u-l),gwy);
    lc.rRecoffs(rec,true);
    lc.offsg.setColor(lc.pk.c);
    for(int i = l; i <=u ; i++)
     {
      rec=new Rec(glx+(dx*i),offay,dx,grscy*sa[i]);
      lc.rRecoffs(rec,true);
     }
    lc.repaint();
    te.schleep(1500);
   }
 }