## Need help please

### Need help please

Hello to everybody,

i have to understand the way this programm works... Having only basic
knowledge of java i would very much appreciate if somebody would help
me by commenting this programm... Lots of thanks!

Stephane

import java.applet.*;
import java.awt.*;
import java.lang.*;
import java.util.*;

// the sort classes: feel free to add your own classes...

// this naive approach is unfortunately frequently used, because
// it works well in some frequently occuring cases: the list
// is almost sorted, and unsorted items are 'below' their final
position.
// (this happens for instance when sorting an array of invoices
// by invoice number, when some invoices have been inserted in 'holes'
// in the initial array.
// use insertion sort instead if you want to be naive, or at least
shaker sort.

class BubbleSort extends AlgoTri {
BubbleSort (int t, VueTris v) { super("Bubble Sort", t, v); }
public void sort () {
boolean dep=false;
int curndx=size;
do {
dep=false;
for (int i=1; i < curndx; i++) {
if (compare(i, i-1)<0) {
exchange(i, i-1);
dep=true;
}
} curndx--;
} while (dep);
}

};

// shaker sort is an optimization of bubble sort

class ShakerSort extends AlgoTri {
ShakerSort (int t, VueTris v) { super("Shaker Sort", t, v); }

public void sort () {
boolean dep=false;
int curmax=size, curmin=1;
do {
dep=false;
for (int i=curmin; i < curmax; i++)
if (compare(i, i-1)<0) {
exchange(i, i-1);
dep=true;
}
curmax--;
if (!dep) break;
for (int i=curmax-1; i >= curmin; i--)
if (compare(i, i-1)<0) {
exchange(i, i-1);
dep=true;
} curmin++;
} while (dep);
}

};

// select sort is optimal in terms of moves, but catastrophic
// in comparisons: n(n+1)/2 comparisons in all cases...
// Yet, it is the most straightforward algorithm of all.
// Use when when you want to make your users wait...

class SelectSort extends AlgoTri {
SelectSort (int t, VueTris v) { super("Selection Sort", t, v); }

public void sort () {
for (int i = 0; i < size; i++) {
int curmin = i;
for (int j = i+1; j < size; j++) {
if (compare(j, curmin)<0)
curmin=j;
}
if (curmin != i)
exchange(curmin, i);
}
}

};

// insertion sort is the best of the 3 "naive" approaches
// however, it is very bad in terms of moves.

class InsertSort extends AlgoTri {
InsertSort (int t, VueTris v) { super("Insertion Sort", t, v); }

public void sort () {
for (int i = 1; i < size; i++) {
for (int j = i; j > 0; j--) {
if (compare(j, j-1)<0)
exchange(j, j-1);
else break;
}
}
}

};

// dichotomic insertion is a simple optimsation of insertion sort
// it is optimal in terms of comparisons, and does not require
// an additional stack. It does at most sum(i=1 to n)(log2 i)
comparisons.
// however, because of its high moves complexity (n*n), it is still
// less efficient than 'smart' sorts.
// However, it makes an excellent intrdocutino to the notion of
optimizing
// algorithms, and a good intermediate step before introducing
// shell sort

class InsertDichoSort2 extends AlgoTri {
InsertDichoSort2 (int t, VueTris v) { super("Insert-Dicho2", t, v); }
public void sort () {
for (int i = 1; i < size; i++) {
// find by dichotomy before which item to insert the current
int binf=0, bsup=i-1;
int mid=(bsup+binf)/2;
do {
int res=compare(mid,i);
if (res < 0) binf=mid+1;
else if (res > 0) bsup=mid;
else binf=bsup=mid+1;
mid=(bsup+binf)/2;
} while (bsup > binf);
// now insert it before binf
if (mid < i-1) {
int val=item(i);
for (int k = i; k > mid; k--)
exchange(k, k-1);
assign(mid,val);
} else if (compare(i-1,i) > 0)  exchange(i,i-1);
}
}

};

class InsertDichoSort extends AlgoTri {
InsertDichoSort (int t, VueTris v) { super("Insert-Dicho", t, v); }
public void sort () {
for (int i = 1; i < size; i++) {
// find by dichotomy before which item to insert the current
if (compare(i-1,i) <= 0) continue;
int binf=0, bsup=i-1;
do {
int mid=(bsup+binf)/2;
int res=compare(mid,i);
if (res < 0) binf=mid+1;
else if (res > 0) bsup=mid;
else binf=bsup=mid+1;
} while (bsup > binf);

// now insert it before binf
int val=item(i);
for (int k = i; k > binf; k--)
exchange(k, k-1);
assign(binf,val);
}
}

};

// the most used sort algorithm. ONce undesrtood it is simple
// to understand. My take is that its efficiency is not so much
// due to redcuing the number of comparisons, but rather that it
// is also very efficient in number of moves.
// worst case is still O(n2), but on quasi sorted strings.
// often seen as a generalization of bubblesort.
// it can also be very demanding in stack use. unfortunatley,
// our visualizer does not show that.

class QuickSort extends AlgoTri {
QuickSort (int t, VueTris v) { super("QuickSort", t, v); }
void sort(int from, int to) {
delay (ext); // emulates recursion's & stack cost
int pivot=item((from+to)/2);
int ma=to; int mi=from;
do {
while(compare_val(pivot, ma)<0) ma--;
while(compare_val(pivot, mi)>0) mi++;
if(mi <= ma) {
if (mi != ma)
exchange(ma, mi);
ma--; mi++;
}
} while (ma>=mi);
if (from < ma) sort(from, ma);
if (to > mi) sort(mi, to);
}
public void sort () {
sort(0,size-1);
}

};

// some local often used improvements over quicksort:
// use the median of 3 values to improve chances of partitioning
// right, and use insertino sort on small lists instead of
// recursion, to minimize stack use and because partitioning
// is not efficient on small quasi ordered lists.
// Note that the 'quasi-ordered' conditions, as we implemented it,
// is one of the cases where these optimizations do not work well.

class QuickerSort extends AlgoTri {
QuickerSort (int t, VueTris v) { super("QuickerSort", t, v); }

void insert_sort (int from, int to) {
delay (ext); // emulates recursion's & stack cost
if (to > from) {
for (int i = from+1; i <= to; i++) {
for (int j = i; j > from; j--) {
if (compare(j, j-1)<0)
exchange(j, j-1);
else break;
}
}
}
}

void sort(int from, int to) {
delay (ext); // emulates recursion's & stack cost
int pivot;
// choose the median of three of the values as a pivot
if (compare(to, from) > 0) {
if (compare((from+to)/2, to) > 0) pivot=item(to);
else {
if (compare((from+to)/2, from) > 0)
pivot=item((from+to)/2);
else pivot=item(from);
}
} else {
if (compare((from+to)/2, from)>0) pivot=item(from);
else {
if (compare((from+to)/2, to) > 0)
pivot=item((from+to)/2);
else pivot=item(to);
}
}

int ma=to; int mi=from;
do {
while(compare_val(pivot, ma)<0) ma--;
while(compare_val(pivot, mi)>0) mi++;
if(mi <= ma) {
if (mi != ma)
exchange(ma, mi);
ma--; mi++;
}
} while (ma>=mi);

// if array is small, do insertion instead of recursion
if (Math.abs(ma - from) > 10) sort(from, ma);
else insert_sort(from, ma);
if (Math.abs(to - mi) > 10) sort(mi, to);
else insert_sort(mi, to);
}

public void sort () {
sort(0,size-1);
}

};

// theoretically a very efficient sort: bounded in nlogn
// a generalization of selection sort.

class HeapSort extends AlgoTri {
HeapSort (int t, VueTris v) { super("HeapSort", t, v); }

boolean isLeaf(int t, int pos)  {return (pos >= t/2) && (pos < t) &&
t > 0;}
int leftchild(int pos) {return 2*pos+1;}
int rightchild(int pos)  {return 2*pos;}

void siftdown (int t, int pos) {
while (!isLeaf(t, pos)) {
int j = leftchild(pos);
int k = rightchild(pos);
int maxchildindex;
if (compare(k,j) < 0) maxchildindex=j;
else maxchildindex=k;
if (compare(pos, maxchildindex) >= 0) return;
exchange(pos, maxchildindex);
pos = maxchildindex;
}
}

public void sort () {
for (int i = size/2-1; i>=0; i--)
siftdown(size-1, i);

for (int i=size-1; i>1; i--) {
exchange(0,i);
siftdown (i-1, 0);
}
}

};

// the fastest sort before quicksort was invented in 1976
// a generalizatino of insertion sort.
// lots of research has gone in finding the optimum intervals
// of the sequence of separations...

class ShellSort extends AlgoTri {
ShellSort (int t, VueTris v) { super("Shell Sort", t, v); }

void insertionsort (int offset, int n, int incr) {
for (int i = incr; i < n; i+= incr)
for (int j = i; (j >= incr)
&& compare(j+offset, j+offset-incr)< 0; j-=incr)
exchange(j+offset, j+offset-incr);
}

public void sort () {
// here, we use the simplest increment suite.
for (int i = (size/2); i > 1; i /= 2)
for (int j = 0; j < i; j++)
insertionsort(j, size-j, i);
insertionsort(0, size, 1);
}

};

class ShellSort2 extends AlgoTri {
ShellSort2 (int t, VueTris v) { super("Shell Sort2", t, v); }

void insertionsort (int offset, int n, int incr) {
for (int i = incr; i < n; i+= incr)
for (int j = i; (j >= incr)
&& compare(j+offset, j+offset-incr)< 0; j-=incr)
exchange(j+offset, j+offset-incr);
}

public void sort () {
// here, we use a smarter increment suite:
int maxi=1;
while(maxi < size - 1)
maxi=3*maxi+1;
for (int i = maxi/3; i > 1; i /= 3)
for (int j = 0; j < i; j++)
insertionsort(j, size-j, i);
insertionsort(0, size, 1);
}

};

// fastest know in place stable sort.
// no risk of exploding a stack.
// cost: a relatively high number of moves. stack can still
// be expensive too.
// this is a merge sort with a smart in place merge that
// 'rotates' the sub arrays. to see the way it works, view it
// on inverted array

class InPlaceStableSort extends AlgoTri {
InPlaceStableSort (int t, VueTris v) { super("InPlaceStable", t, v);

}

int lower (int from, int to, int val) {
int len = to - from, half;
while (len > 0) {
half = len/2;
int mid= from + half;
if (compare (mid, val) < 0) {
from = mid+1;
len = len - half -1;
} else len = half;
} return from;
}
int upper (int from, int
...

### Need help please

Hi Stephane, there are bazillions of good books on the Java programming
language, and even more turorials on the web. Together, these should allow
you to find out what this program is doing.

You should be able to ask more specific Java questions in comp.lang.java
also.

Cheers,

4Space

[Biggest snip ever]

Hi,

I have trouble flushing WM_MOUSEMOVE events from queue. The code I have
looks like this:

CScrollview::OnMouseMove (...)
{
//flush all pending WM_MOUSEMOVE messages except for the last one
MSG msg;
while (PeekMessage (&msg, m_hWnd, WM_MOUSEMOVE, WM_MOUSEMOVE,
PM_REMOVE)
{
point = msg.lParam;
nflags = msg.mParam;
}

//call standart handler
...

//do custom drawing
...

I have fairly complex drawing routing that in some cases creates
annoying lag with respect to mouse movements (while all mouse move
events are dispatched). However PeekMessage never returns TRUE as if
these events are not buffered in the the message queue (maybe low level
mouse driver has another mouse event queue ?).

Am I doing something wrong here ?
Is there a reasonably simple way to flush low level mouse driver queue ?

BTW I am testing on win98 with VC 6.0.