/*==$Workfile: Order.java $=============================================
Order class implements MergeSort (from Collections), HeapSort and SmoothSort.
Version     : $Header: /Order/ch/enterag/utils/order/Order.java 4     3.06.05 18:33 Hartwig $
              $NoKeywords: $
Application : Utilities
Description : Order class implements MergeSort (from Collections), HeapSort and SmoothSort
              for Lists
Version    : This code makes use of assertions and thus presupposes the
             version 1.4 of Java (with the source switch set to 1.4)
             as well as enabled assertions on execution and debugging.
------------------------------------------------------------------------
Copyright  : Enter AG, Zurich, 2005
Created    : May 2005, Hartwig Thomas
======================================================================*/
package ch.enterag.utils.order;

import java.util.*;
import java.lang.*;

/*======================================================================
/** Order is a non-instantiable class like Collections which implements
 various sorting algorithms.
 @author  Hartwig Thomas
*/
public class Order
{
  /*====================================================================
  class ComparableComparator permits treating Comparable
  implementations like Comparator implementations.
  ====================================================================*/
  private static class ComparableComparator
    implements Comparator
  {
    public int compare(Object o1, Object o2)
    {
      Comparable c1 = (Comparable) o1;
      Comparable c2 = (Comparable) o2;
      return c1.compareTo(c2);
    } /* compare */
  } /* class ComparableComparator */
  
  /*====================================================================
  class data and "properties"
  ====================================================================*/
  private static int m_iSwaps = 0;
  public static int getSwaps()
  {
    return m_iSwaps;
  } /* getSwaps */
  public static void setSwaps(int iSwaps)
  {
    m_iSwaps = iSwaps;
  } /* setSwaps */
  
  /*====================================================================
  list utilities
  ====================================================================*/
  /*------------------------------------------------------------------*/
  /** le returns true, if element i1 of list ls is less or equal element i1 */
  private static boolean le(List ls, Comparator c, int i1, int i2)
  {
    return (c.compare(ls.get(i1),ls.get(i2)) <= 0);
  } /* le */
  
  /*------------------------------------------------------------------*/
  /** swap exchanges elements i1 and i2 in list */
  private static void swap(List ls, int i1, int i2)
  {
    m_iSwaps++;
    Object oTemp = ls.get(i1);
    ls.set(i1,ls.get(i2));
    ls.set(i2,oTemp);
  } /* swap */
  
  /*====================================================================
  sortMerge (is also implemented by Collections)
  sorts the left and the right half of the list and then merges them.
  ====================================================================*/
  /*------------------------------------------------------------------*/
  /** leRange returns true, if left element is less than iFrom,
   le, if left element is greater or equal iFrom and less than iTo,
   false, if left element is greater or equal to iTo.
   This method is just used for the assertion in search.
  */
  private static boolean leRange(List ls, Comparator c, int i1, int iFrom, int iTo, int i2)
  {
    boolean bReturn = false;
    if (i1 >= iFrom)
    {
      if (i1 < iTo)
        bReturn = le(ls,c,i1,i2);
    }
    else
      bReturn = true;
    return bReturn;
  } /* leRange */

  /*------------------------------------------------------------------*/
  /** search returns index of first element in (iFrom, iTo) greater than Element iIndex */
  public static int search(List ls, Comparator c, int iFrom, int iTo, int iIndex)
  {
    int iLow = iFrom - 1;
    int iHigh = iTo;
    int iTemp;
    while (iHigh - iLow > 1)
    {
      /* iIndex is in interval between iLow and iHigh */
      assert leRange(ls,c,iLow,iFrom,iTo,iIndex) && !leRange(ls,c,iHigh,iFrom,iTo,iIndex): "Binary search assertion failed!";
      iTemp = (iLow + iHigh) / 2;
      if (le(ls,c,iTemp,iIndex))
        iLow = iTemp;
      else
        iHigh = iTemp;
    }
    return iHigh;
  } /* search */
  
  /*------------------------------------------------------------------*/
  /** merge the left and the right half of List l which are already ordered */
  private static void mergeScratch(List ls, List lsScratch, Comparator c, int iFrom, int iMiddle, int iTo)
  {
    /* merge from target to scratch array */
    int iLeft = iFrom;
    int iRight = iMiddle;
    int iIndex = iFrom;
    while ((iLeft < iMiddle) && (iRight < iTo))
    {
      if (le(ls,c,iLeft,iRight))
      {
        lsScratch.set(iIndex,ls.get(iLeft));
        iLeft++;
      }
      else
      {
        lsScratch.set(iIndex,ls.get(iRight));
        iRight++;
      }
      iIndex++;
    }
    while (iLeft < iMiddle)
    {
      lsScratch.set(iIndex,ls.get(iLeft));
      iLeft++;
      iIndex++;
    }
    while (iRight < iTo)
    {
      lsScratch.set(iIndex,ls.get(iRight));
      iRight++;
      iIndex++;
    }
    /* copy from scratch to target array */
    for (iIndex = iFrom; iIndex < iTo; iIndex++)
      ls.set(iIndex,lsScratch.get(iIndex));
  } /* merge */
  
  /*------------------------------------------------------------------*/
  /** merge sort of interval */
  private static void sortMerge(List ls, List lsScratch, Comparator c, int iFrom, int iTo)
  {
    if (iTo - iFrom > 1)
    {
      int iMiddle = (iFrom + iTo)/2;
      sortMerge(ls,lsScratch,c,iFrom,iMiddle);
      sortMerge(ls,lsScratch,c,iMiddle,iTo);
      if (!le(ls,c,iMiddle-1,iMiddle))
      {
        /*
        iTo = search(ls,c,iMiddle,iTo,iMiddle-1);
        iFrom = search(ls,c,iFrom,iMiddle,iMiddle);
        */
        mergeScratch(ls,lsScratch,c,iFrom,iMiddle,iTo);
      }
    }
  } /* sortMerge */

  /*------------------------------------------------------------------*/
  /** merge sort */
  public static void sortMerge(List ls, Comparator c)
  {
    List lsScratch = new ArrayList(ls);
    sortMerge(ls,lsScratch,c,0,ls.size());
  } /* sortMerge */

  /*------------------------------------------------------------------*/
  /** merge sort using Comparable interface */
  public static void sortMerge(List ls)
  {
    Comparator c = new ComparableComparator();
    sortMerge(ls,c);
  } /* sortMerge */
  
  /*====================================================================
  sortSwap
  merge sort variant of Siegfried Sielaff
  does the merging in place.
  ====================================================================*/
  /*------------------------------------------------------------------*/
  /** split the left and the right half. */
  private static int split(List ls, Comparator c, int iFrom, int iMiddle, int iTo)
  {
    int iLow = -1;
    int iHigh = Math.min(iMiddle-iFrom, iTo-iMiddle);
    while (iHigh - iLow > 1)
    {
      /* iSize is in interval between iLow and iHigh */
      int iSize = (iLow + iHigh) / 2;
      if (!le(ls,c,iMiddle-1-iSize,iMiddle+iSize))
        iLow = iSize;
      else
        iHigh = iSize;
    }
    return iHigh;
  } /* split */
  
  /*------------------------------------------------------------------*/
  /** merge in place recursively */
  private static void merge(List ls, Comparator c, int iFrom, int iMiddle, int iTo)
  {
    /* split */
    int iSize = split(ls,c,iFrom,iMiddle,iTo);
    if (iSize > 0)
    {
      /* swap last iSize elements of left half with first iSize elements of right half */
      for (int i = 0; i < iSize; i++)
        swap(ls,iMiddle-iSize+i,iMiddle+i);
      /* everything to the left is now less or equal to everything on the right */
      if (iMiddle - iSize > iFrom)
        merge(ls,c,iFrom, iMiddle-iSize, iMiddle);
      if (iTo > iMiddle + iSize)
        merge(ls,c,iMiddle, iMiddle+iSize, iTo);
    }
  } /* merge */
  
  /*------------------------------------------------------------------*/
  /** swap sort of interval using Comparable interface */
  private static void sortSwap(List ls, Comparator c, int iFrom, int iTo)
  {
    if (iTo - iFrom > 1)
    {
      int iMiddle = (iFrom + iTo) / 2;
      sortSwap(ls,c,iFrom,iMiddle);
      sortSwap(ls,c,iMiddle,iTo);
      if (!le(ls,c,iMiddle-1,iMiddle))
        merge(ls,c,iFrom,iMiddle,iTo);
    }
  } /* sortSwap */
  
  /*------------------------------------------------------------------*/
  /** swap sort using Comparable interface */
  public static void sortSwap(List ls, Comparator c)
  {
    sortSwap(ls,c,0,ls.size());
  } /* sortSwap */

  /*------------------------------------------------------------------*/
  /** swap sort using Comparable interface */
  public static void sortSwap(List ls)
  {
    Comparator c = new ComparableComparator();
    sortSwap(ls,c);
  } /* sortSwap */
  
  /*====================================================================
  sortHeap
  sort using the heap property:
  a heap is an at most binary tree where the root is not less than
  any of the sons and all subtrees are heaps too.
  ====================================================================*/
  /*------------------------------------------------------------------*/
  /** isTrusty checks the heap condition of the sub tree at iRoot       */
  private static boolean isTrusty(List ls, Comparator c, int iRoot, int iSize)
  {
    boolean bTrusty = isDubious(ls,c,iRoot,iSize);
    int iLeft = 2*iRoot + 1;
    if (iLeft < iSize) // do we have a left son?
    {
      if (le(ls,c,iLeft,iRoot)) // is left son less or equal to root?
      {
        int iRight = 2*iRoot + 2;
        if (iRight < iSize) // do we have a right son?
        {
          if(!le(ls,c,iRight,iRoot)) // is right son less or equal to root?
            bTrusty = false;
        }
      }
      else
        bTrusty = false;
    }
    return bTrusty;
  } /* isTrusty */

  /*------------------------------------------------------------------*/
  /** isDubious checks the heap condition of the children of the 
      sub tree at iRoot       */
  private static boolean isDubious(List ls, Comparator c, int iRoot, int iSize)
  {
    boolean bDubious = true;
    int iLeft = 2*iRoot + 1;
    if (iLeft < iSize) // do we have a left son?
    {
      if (isTrusty(ls,c,iLeft,iRoot)) // is sub tree with root iLeft trusty?
      {
        int iRight = 2*iRoot + 2;
        if (iRight < iSize) // do we have a right son?
        {
          if (!isTrusty(ls,c,iRight,iRoot)) // is sub tree with root iRight trusty?
            bDubious = false;
        }
      }
      else
        bDubious = false;
    }
    return bDubious;
  } /* isDubious */
  
  /*------------------------------------------------------------------*/
  /** sift turns the heap with doubtful root iRoot into a trusty one. */
  private static void sift(List ls, Comparator c, int iRoot, int iSize)
  {
    assert isDubious(ls,c,iRoot,iSize): "precondition of sift not fulfilled!";
    int iLeft = 2*iRoot + 1;
    if (iLeft < iSize)
    {
      int iRight = iLeft + 1;
      if (iRight < iSize)
      {
        if (!le(ls,c,iRight,iLeft))
          iLeft = iRight;
      }
      /* iLeft is now maximum (or only) son */
      if (!le(ls,c,iLeft,iRoot))
      {
        swap(ls,iLeft,iRoot);
        /* tail recursion */
        sift(ls,c,iLeft,iSize);
      }
    }
    assert isTrusty(ls,c,iRoot,iSize): "postcondition of sift not fulfilled!";
  } /* sift */

  /*------------------------------------------------------------------*/
  /** isSortedHigh returns true, if partial list from i1 to i2-1 is 
  totally ordered and all elements from 0 to i1-1 are less or equal
  to element i1.
  */
  private static boolean isSortedHigh(List ls, Comparator c, int iRoot, int iSize)
  {
    boolean bSorted = true;
    for (int i = iRoot+1; bSorted && (i < iSize); i++)
    {
      if (!le(ls,c,i-1,i))
        bSorted = false;
    }
    if (iRoot < iSize)
    {
      for (int i = 0; bSorted && (i < iRoot); i++)
      {
        if (!le(ls,c,i,iRoot))
          bSorted = false;
      }
    }
    return bSorted;
  } /* isSortedHigh */
  
  /*------------------------------------------------------------------*/
  /** sortHeap first turns the list into a heap and then dismantles the heap */
  public static void sortHeap(List ls, Comparator c)
  {
    int iSize = ls.size();
    /* build heap */
    for (int iRoot = iSize/2; iRoot > 0; )
    {
      iRoot--;
      sift(ls,c,iRoot,iSize);
    }
    /* dismantle heap */
    for (int iRoot = iSize; iRoot > 1; )
    {
      assert isSortedHigh(ls,c,iRoot,iSize): "dismantle invariant in sortHeap not fulfilled!";
      iRoot--;
      swap(ls,iRoot,0);
      sift(ls,c,0,iRoot);
    } /* sortHeap */
  } /* sortHeap */

  /*------------------------------------------------------------------*/
  /** heapSort using Comparable interface */
  public static void sortHeap(List ls)
  {
    Comparator c = new ComparableComparator();
    sortHeap(ls, c);
  } /* sortHeap */
  
  /*====================================================================
  sortSmooth
  sort using a sequence of completely balanced heaps (sizes 1, 3, 7, 15, ...)
  (with roots to the right of the children)
  arranged in decreasing heap size and increasing heap root
  as described in E. W. Dijkstra's article.
  ====================================================================*/
  /*------------------------------------------------------------------*/
  /** Class Leonardo implements basic manipulation of Leonardo numbers */
  private static class Leonardo
  {
    /* data members */
    private int m_iSize;
    private int m_iPrevious;
    /* access */
    public int getSize() { return m_iSize; }
    private void setSize(int iSize) { m_iSize = iSize; }
    private int getPrevious() { return m_iPrevious; }
    private void setPrevious(int iPrevious) { m_iPrevious = iPrevious; }
    /* default constructor */
    public Leonardo()
    {
      setSize(1);
      setPrevious(1);
    }
    /* copy constructor */
    public Leonardo(Leonardo lSize)
    {
      setSize(lSize.getSize());
      setPrevious(lSize.getPrevious());
    } /* copy constructor */
    /* recursion */
    public void up()
    {
      int iTemp = m_iSize;
      setSize(m_iPrevious + m_iSize + 1);
      setPrevious(iTemp);
    }
    public void down()
    {
      int iTemp = m_iPrevious;
      setPrevious(m_iSize - m_iPrevious - 1);
      setSize(iTemp);
    }
  } /* class Leonardo */
  
  /*------------------------------------------------------------------*/
  /** Class Sequence implements basic manipulation of concatenation sequence sizes.
  The current size is not stored in the bitmap but is assumed to be occupied.
  if current size = L(n) and bit i is set in bitmap then L(n+i) is in
  concatenation sequence. Thus having bit 0 set means, that current size
  appears twice (can only occur for size 1).
  */
  private static class Sequence
  {
    /* data members */
    private Leonardo m_lSize;
    private int m_iStretches;
    /* access */
    public Leonardo getSize() { return m_lSize; }
    private void setSize(Leonardo lSize ) { m_lSize = lSize; }
    private int getStretches() { return m_iStretches; }
    private void setStretches(int iStretches) { m_iStretches = iStretches; }
    /** default constructor */
    public Sequence() 
    {
      setSize(new Leonardo()); 
      setStretches(0);
    }
    /** copy constructor */
    public Sequence(Sequence sSize) 
    {
      setSize(new Leonardo(sSize.getSize())); 
      setStretches(sSize.getStretches()); 
    }
    /** returns underlying current size of binary heap */
    public int size()
    {
      return m_lSize.getSize();
    } /* size */
    /** empty returns true, if there are no stretches to the left */
    private boolean empty()
    {
      return m_iStretches == 0;
    } /* empty */
    /** length returns total size of ternary heap */
    public int length()
    {
      int iLength = size();
      Sequence s = new Sequence(this);
      while (!s.empty())
      {
        s.upToPrevious();
        iLength = iLength + s.size();
      }
      return iLength;
    } /* length */
    /** mergeable is given, if bit 1 is set */
    public boolean mergeable()
    {
      return (m_iStretches & 2) != 0;
    } /* mergeable */
    /** permanent returns true, if ternary tree at root is permanent */
    public boolean permanent(int iRoot, int iTotalSize)
    {
      boolean bPermanent = true;
      int iSize = m_lSize.getPrevious();
      if (iSize < 0)
        iSize = 0;
      if ((iRoot + 1) + iSize + 1 <= iTotalSize)
        bPermanent = false;
      return bPermanent;
    } /* permanent */
    /** up goes to next size */
    public void up()
    {
      m_lSize.up(); /* size of left stretch */
      setStretches(m_iStretches >> 1);
    } /* up */
    /** down goes to previous size */
    public void down()
    {
      m_lSize.down();
      setStretches(m_iStretches << 1);
    } /* down */
    /** upToPrevious finds next stretch size in sequence */
    public void upToPrevious()
    {
      /* find next occupied stretch */
      while (!empty() && !mergeable())
        up();
      up();
      clear();
    } /* upToPrevious */
    /** downToOne reduces current size to one */
    public void downToOne()
    {
      set();
      /* go down to one */
      down();
      while (size() > 1)
        down();
    } /* downToOne */
    /** set adds current size to left sequence */
    public void set()
    {
      m_iStretches = m_iStretches | 1;
    } /* set */
    /** clear removes current size from left sequence */
    public void clear()
    {
      m_iStretches = m_iStretches & ~1;
    } /* clear */
  } /* class Sequence */
  
  /*------------------------------------------------------------------*/
  /** isTrusty2 determines, whether the binary tree at iRoot fulfills
  the binary heap condition.
  */
  private static boolean isTrusty2(List ls, Comparator c, int iRoot, Leonardo lSize)
  {
    boolean bTrusty = isDubious2(ls,c,iRoot,lSize);
    int iSize = lSize.getSize();
    if (iSize > 1)
    {
      Leonardo l = new Leonardo(lSize);
      l.down();
      int iLeft = iRoot - iSize + l.getSize();
      bTrusty = bTrusty && le(ls,c,iLeft,iRoot);
      l.down();
      int iRight = iRoot - 1;
      bTrusty = bTrusty && le(ls,c,iRight,iRoot);
    }
    return bTrusty;
  } /* isTrusty2 */
  
  /*------------------------------------------------------------------*/
  /** isDubious2 determines, whether the binary tree at iRoot almost fulfills
  the binary heap condition.
  */
  private static boolean isDubious2(List ls, Comparator c, int iRoot, Leonardo lSize)
  {
    boolean bTrusty = true;
    int iSize = lSize.getSize();
    if (iSize > 1)
    {
      Leonardo l = new Leonardo(lSize);
      l.down();
      int iLeft = iRoot - iSize + l.getSize();
      bTrusty = bTrusty && isTrusty2(ls,c,iLeft,l);
      l.down();
      int iRight = iRoot - 1;
      bTrusty = bTrusty && isTrusty2(ls,c,iRight,l);
    }
    return bTrusty;
  } /* isDubious2 */

  /*------------------------------------------------------------------*/
  /** sift2
  converts a binary dubious tree into a trusty one.
  */
  private static void sift2(List ls, Comparator c, int iRoot, Leonardo lSize)
  {
    assert isDubious2(ls,c,iRoot,lSize):"precondition of sift2 not fulfilled!";
    int iSize = lSize.getSize();
    if (iSize > 1)
    {
      Leonardo l = new Leonardo(lSize);
      /* left sub tree */
      l.down();
      int iLeft = iRoot - iSize + l.getSize();
      int iRight = iRoot - 1;
      /* make iLeft maximum son of balanced tree */
      if (!le(ls,c,iRight,iLeft))
      {
        iLeft = iRight;
        l.down();
      }
      if (!le(ls,c,iLeft,iRoot))
      {
        swap(ls,iLeft,iRoot);
        /* tail recursion */
        sift2(ls,c,iLeft,l);
      }
    }
    assert isTrusty2(ls,c,iRoot,lSize):"postcondition of sift2 not fulfilled!";
  } /* sift2 */

  /*------------------------------------------------------------------*/
  /** isTrusty3 determines, whether the ternary tree at iRoot fulfills
  the ternary heap condition.
  */
  private static boolean isTrusty3(List ls, Comparator c, int iRoot, Sequence sSize)
  {
    boolean bTrusty = isDubious3(ls,c,iRoot,sSize);
    bTrusty = bTrusty && isTrusty2(ls,c,iRoot,sSize.getSize());
    int iSize = sSize.size();
    if (iSize > 1)
    {
      Leonardo l = new Leonardo(sSize.getSize());
      l.down();
      int iLeft = iRoot - iSize + l.getSize();
      bTrusty = bTrusty && le(ls,c,iLeft,iRoot);
      l.down();
      int iRight = iRoot - 1;
      bTrusty = bTrusty && le(ls,c,iRight,iRoot);
    }
    int iStep = iRoot - iSize;
    if (iStep >= 0)
      bTrusty = bTrusty && le(ls,c,iStep,iRoot);
    return bTrusty;
  } /* isTrusty3 */
  
  /*------------------------------------------------------------------*/
  /** isDubious3 determines, whether the ternary tree at iRoot almost fulfills
  the ternary heap condition.
  */
  private static boolean isDubious3(List ls, Comparator c, int iRoot, Sequence sSize)
  {
    boolean bDubious = isDubious2(ls,c,iRoot,sSize.getSize());
    int iSize = sSize.size();
    int iStep = iRoot - iSize;
    if (iStep >= 0)
    {
      Sequence s = new Sequence(sSize);
      s.upToPrevious();
      bDubious = bDubious && isTrusty3(ls,c,iStep,s);
    }
    return bDubious;
  } /* isDubious3 */

  /*------------------------------------------------------------------*/
  /** sift3
  converts a ternary dubious tree into a trusty one.
  */
  private static void sift3(List ls, Comparator c, int iRoot, Sequence sSize)
  {
    assert isDubious3(ls,c,iRoot,sSize): "precondition of sift3 not fulfilled!";
    int iSize = sSize.size();
    int iStep = iRoot - iSize;
    if (iStep >= 0)
    {
      if (iSize > 1)
      {
        Leonardo l = new Leonardo(sSize.getSize());
        /* left son of balanced tree */
        l.down();
        int iLeft = iRoot - iSize + l.getSize();
        /* right son of balanced tree */
        int iRight = iRoot - 1;
        /* make iLeft maximum son of balanced tree */
        if (!le(ls,c,iRight,iLeft))
        {
          iLeft = iRight;
          l.down();
        }
        if (le(ls,c,iStep,iLeft))
        {
          /* just like siftTwo */
          if (!le(ls,c,iLeft,iRoot))
          {
            swap(ls,iLeft,iRoot);
            sift2(ls,c,iLeft,l);
          }
          iStep = -1; // already sifted
        }
      }
      if (iStep >= 0)
      {
        /* step son is greater than either son in balanced tree */
        if (!le(ls,c,iStep,iRoot))
        {
          swap(ls,iStep,iRoot);
          /* tail recursion */
          Sequence s = new Sequence(sSize);
          s.upToPrevious();
          sift3(ls,c,iStep,s);
        }
      }
    }
    else
      sift2(ls,c,iRoot,sSize.getSize());
    assert isTrusty3(ls,c,iRoot,sSize): "postcondition of sift3 not fulfilled!";
  } /* sift3 */
  
  /*------------------------------------------------------------------*/
  /** isHalfDubious3 determines, whether the binary tree at iRoot fulfills
  the binary heap condition and the ternary tree at iRoot almost fulfills
  the ternary heap condition.
  */
  private static boolean isHalfDubious3(List ls, Comparator c, int iRoot, Sequence sSize)
  {
    boolean bDubious = isTrusty2(ls,c,iRoot,sSize.getSize());
    int iSize = sSize.getSize().getSize();
    int iStep = iRoot - iSize;
    if (iStep >= 0)
    {
      Sequence s = new Sequence(sSize);
      s.upToPrevious();
      bDubious = bDubious && isTrusty3(ls,c,iStep,s);
    }
    return bDubious;
  } /* isHalfDubious3 */

  /*------------------------------------------------------------------*/
  /** siftHalf3
  converts a ternary semidubious tree into a trusty one.
  */
  private static void siftHalf3(List ls, Comparator c, int iRoot, Sequence sSize)
  {
    assert isHalfDubious3(ls,c,iRoot,sSize): "precondition of siftHalf3 not fulfilled!";
    int iSize = sSize.getSize().getSize();
    int iStep = iRoot - iSize;
    if (iStep >= 0)
    {
      /* root is not less than left or right */
      /* step son (exists!) is root of next stretch to the left */
      if (!le(ls,c,iStep,iRoot))
      {
        swap(ls,iStep,iRoot);
        /* tail recursion */
        Sequence s = new Sequence(sSize);
        s.upToPrevious();
        sift3(ls,c,iStep,s);
      }
    }
    assert isTrusty3(ls,c,iRoot,sSize): "postcondition of siftHalf3 not fulfilled!";
  } /* siftHalf3 */
  
  /*------------------------------------------------------------------*/
  /** isPartiallyTrusty3 determines, whether all permanent stretches
  up to iRoot are trusty ternary trees and all remaining ones are
  trusty binary trees.
  */
  private static boolean isPartiallyTrusty3(
    List ls, Comparator c, int iRoot, Sequence sSize, int iTotalSize)
  {
    boolean bTrusty = true;
    /* if permanent then trusty3 else (trusty2 and stepson is partiallytrusty3) */
    if (sSize.permanent(iRoot,iTotalSize))
      bTrusty = isTrusty3(ls,c,iRoot,sSize);
    else
    {
      bTrusty = isTrusty2(ls,c,iRoot,sSize.getSize());
      int iSize = sSize.size();
      int iStep = iRoot - iSize;
      if (iStep >= 0)
      {
        Sequence s = new Sequence(sSize);
        s.upToPrevious();
        bTrusty = bTrusty && isPartiallyTrusty3(ls,c,iStep,s,iTotalSize);
      }
    }
    return bTrusty;
  } /* isPartiallyTrusty3 */
  
  /*------------------------------------------------------------------*/
  /** isPartiallyDubious3 determines, whether sequence at iRoot is
  partially trusty except maybe for iRoot.
  */
  private static boolean isPartiallyDubious3(
    List ls, Comparator c, int iRoot, Sequence sSize, int iTotalSize)
  {
    boolean bDubious = true;
    /* if permanent the dubious3 else (dubious2 and stepson is partiallytrusty3) */
    if (sSize.permanent(iRoot,iTotalSize))
      bDubious = isDubious3(ls,c,iRoot,sSize);
    else
    {
      bDubious = isDubious2(ls,c,iRoot,sSize.getSize());
      int iSize = sSize.size();
      int iStep = iRoot - iSize;
      if (iStep >= 0)
      {
        Sequence s = new Sequence(sSize);
        s.upToPrevious();
        bDubious = bDubious && isPartiallyTrusty3(ls,c,iStep,s,iTotalSize);
      }
    }
    return bDubious;
  } /* isPartiallyDubious3 */

  /*------------------------------------------------------------------*/
  /** siftPartially3
  converts a partially dubious ternary tree into a partially trusty one.
  */
  private static void siftPartially3(List ls, Comparator c, int iRoot, Sequence sSize, int iTotalSize)
  {
    assert isPartiallyDubious3(ls,c,iRoot,sSize, iTotalSize):
           "precondition of siftPartially3 not fulfilled!";
    if (sSize.permanent(iRoot,iTotalSize))
      sift3(ls,c,iRoot,sSize);
    else
      sift2(ls,c,iRoot,sSize.getSize());
    assert isPartiallyTrusty3(ls,c,iRoot,sSize,iTotalSize):
           "postcondition of siftPartially3 not fulfilled!";
  } /* siftPartially3 */
  
  /*------------------------------------------------------------------*/
  /** sortSmooth */
  public static void sortSmooth(List ls, Comparator c)
  {
    /* build ternary heap */
    Sequence sSize = new Sequence();
    int iRoot = 0;
    while (iRoot < ls.size()-1)
    {
      assert sSize.length() == iRoot + 1: "length of sequence on building incorrect!";
      assert isPartiallyTrusty3(ls,c,iRoot,sSize,ls.size()):
             "loop invariant in building sequence not fulfilled!";
      iRoot++;
      /* reestablish invariant for next iRoot */
      if (sSize.mergeable())
      {
        sSize.up();
        sSize.up();
      }
      else
        sSize.downToOne();
      siftPartially3(ls,c,iRoot,sSize,ls.size());
    }
    /* dismantle ternary heap */
    while (iRoot > 1)
    {
      assert sSize.length() == iRoot + 1: "length of sequence on dismantling incorrect!";
      assert isTrusty3(ls,c,iRoot,sSize): "loop invariant in dismantling sequence not fulfilled!";
      assert isSortedHigh(ls,c,iRoot,ls.size()): "right hand side is not ordered on dismantling!";
      /* reestablish invariant */
      if (sSize.size() > 1)
      {
        /* two sub heaps need to be integrated in ternary heap */
        int iSize = sSize.size();
        /* size of left stretch */
        sSize.down();
        int iLeft = iRoot - iSize + sSize.size();
        siftHalf3(ls,c,iLeft,sSize);
        /* add left sub tree to concatenation sequence */
        sSize.set();
        /* size of right stretch */
        sSize.down();
        int iRight = iRoot - 1;
        siftHalf3(ls,c,iRight,sSize);
      }
      else
        sSize.upToPrevious();
      iRoot--;
    }
  } /* sortSmooth */
  
  /** sortSmooth using Comparable interface */
  public static void sortSmooth(List ls)
  {
    Comparator c = new ComparableComparator();
    sortSmooth(ls,c);
  } /* sortSmooth */
  
} /* class Order */