Wednesday, November 7, 2007

Core Erlang + "GS" = GUI version of the "Insertion Sort"

In this article, i got another popular sorting algorithm commonly known as the "Insertion Sort". Basically, this sort an example of (a) in-place , (b) comparison-sort .You may wish to consult your favourite algorithm texts or visit the Wikipedia (I've heard its rather unreliable but i'm not so sure why). Again like all my previous articles, there are two parts to this: (a) Non-graphical, (b) Graphical version.

Here's the codes:

Filename: "isort.erl"
-module(isort).
-export([start/1]).
-copyright('Copyright (c) 2007 Raymond Tay').
-vsn('$Revision: 1').
%
%
% The insertion sort is a good middle-of-the-road choice for sorting lists of
% a few thousand items or less. The algorithm is significantly simpler than
% the shell sort, with only a small trade off in efficiency. At the same time
% the insertion sort is over twice as fast as the bubble sort and almost 40%
% faster than the selection sort. The insertion sort shouldn't be used for
% sorting lists larger than a couple thousands items or repetitive sorting
%of lists larger than a couple hundred items
%
% insertionSort(array A)
% for i = 1 to length[A]-1 do
% value = A[i]
% j = i-1
% while j >= 0 and A[j] > value do
% A[j + 1] = A[j]
% j = j-1
% A[j+1] = value
%

genNum(N,N,L,F,Num) -> [F(Num),L];
genNum(I,N,L,F,Num) -> Val = F(Num), genNum(I+1,N,[Val,L],F,Num).

for(N,N,F,L) -> Val = lists:nth(N,L), J = N - 1,T = lists:nth(J,L), F(J,L,Val,T);
for(I,N,F,L) -> Val = lists:nth(I,L), J = I - 1,T = lists:nth(J,L), L2 = F(J,L,Val,T), for(I+1,N,F,L2).

checkNInsert(Index,L,Value,T) when Index >= 1 andalso T > Value ->
{L1,L2} = lists:split(Index,L),
[_H|T1] = L2,
Temp1 = lists:flatten(lists:append([L1],[T])),
Temp2 = lists:append(Temp1, T1),
if
Index - 1 /= 0 ->
NewVal = lists:nth(Index - 1, Temp2),
checkNInsert(Index - 1, Temp2, Value, NewVal);
Index - 1 =:= 0 ->
checkNInsert(Index - 1, Temp2, Value, Value)
end;
checkNInsert(Index,L,Value,T) when Index =< 1 orelse T =< Value ->
{L1,L2} = lists:split(Index,L),
[_H|T1] = L2,
lists:append(lists:append(L1,[Value]),T1).

start(N) ->
L = lists:flatten(genNum(1,N,[],fun random:uniform/1, N)),
for(2, length(L), fun checkNInsert/4, L).

And next is for the graphical version

Filename: "isortgui.erl"
-module(isortgui).
-export([start/0]).
-copyright('Copyright (c) 2007 Raymond Tay').
-vsn('$Revision: 1').
%
% The insertion sort is a good middle-of-the-road choice for sorting lists of
% a few thousand items or less. The algorithm is significantly simpler than
% the shell sort, with only a small trade off in efficiency. At the same time
% the insertion sort is over twice as fast as the bubble sort and almost 40%
% faster than the selection sort. The insertion sort shouldn't be used for
% sorting lists larger than a couple thousands items or repetitive sorting
% of lists larger than a couple hundred items
%
% insertionSort(array A)
% for i = 1 to length[A]-1 do
% value = A[i]
% j = i-1
% while j >= 0 and A[j] > value do
% A[j + 1] = A[j]
% j = j-1
% A[j+1] = value
%
forL(N,N,{stretch,_N,_X}) -> [{stretch,_N,_X}];
forL(I,N,{stretch,_N,_X}) -> [{stretch,_N,_X}|forL(I+1,N,{stretch,_N,_X})].

for(N,N,F,L) -> {_,Val} = gs:read(dict:fetch({1,N},L),label), J = N - 1, {_,T} = gs:read(dict:fetch({1,J},L),label), {Val1,_} = string:to_integer(Val), {T1,_} = string:to_integer(T),F(J,L,Val1,T1);
for(I,N,F,L) -> {_,Val} = gs:read(dict:fetch({1,I},L),label), J = I - 1, {_,T} = gs:read(dict:fetch({1,J},L),label), {Val1,_} = string:to_integer(Val), {T1,_} = string:to_integer(T), D2 = F(J,L,Val1,T1), for(I+1,N,F,D2).

checkNInsert(Index,L,Value,T) when Index >= 1 andalso T > Value ->
ButId = dict:fetch({1,Index+1},L),
gs:config(ButId, [{label, {text, T}}]),
gs:config(ButId, [flash]),
sleep(50),
if
Index - 1 =:= 0 -> checkNInsert(0,L,Value,Value);
Index - 1 /= 0 ->
{_,Val} = gs:read(dict:fetch({1,Index -1},L),label),
{Val1,_} = string:to_integer(Val),
if
Val1 =< Value -> checkNInsert(Index - 1, L, Value, Value);
Val1 > Value -> checkNInsert(Index - 1, L, Value, Val1)
end
end;
checkNInsert(Index,L,Value,T) when Index =:= 0 orelse T =< Value ->
ButId = dict:fetch({1,Index+1},L),
gs:config(ButId, [{label, {text, Value}}]),
gs:config(ButId, [flash]),
L.

isort(Dict) ->
for(2, 50, fun checkNInsert/4, Dict). % Sort it for 2-to-<number of columns in GUI>

start() ->
D = dict:new(),
WH = [{width, 1000}, {height, 50}],
Win = gs:window(gs:start(), [{map, true}, {configure, true}, {title, "Insertion-Sort Algorithm"} |WH]),
XOpts = forL(1,50,{stretch,1,20}),
YOpts = [{stretch,1,20}],
gs:frame(packer, Win, [{packer_x, XOpts}, {packer_y, YOpts}]),
NewD = genBut(1,1,D),
gs:config(packer,WH),
dumpDict(NewD),
isort(NewD),
dumpDict(NewD),
io:format("algo done~n",[]),
loop().
%
%
% Generate the "button" GUI objects
%
genBut(Row,Col,Dict) when Col =< 50 ->
ButId = gs:button(packer, [{label, {text, random:uniform(50)}}, {pack_xy, {Col,Row}}]),
NewDict = dict:store({Row,Col}, ButId, Dict), % used later for GUI manipulation
genBut(Row,Col+1,NewDict);
genBut(Row,Col,Dict) when Col > 50 -> Dict.

%
% Pretty standard GUI-event loop
%
loop() ->
receive
{gs,_Id,destroy,_Data,_Arg} -> bye;
{gs,_Id,configure,_Data,[W,H|_]} ->
gs:config(packer, [{width,W}, {height,H}]), %refresh to initial size
loop();
_Other -> loop()
end.
%
% Pretty standard "sleep" function
%
sleep(T) ->
receive
after T -> ok
end.

%
% Dump the dictionary
%
dumpDict(D) ->
Keys = lists:sort(dict:fetch_keys(D)),
lists:foreach( fun({R,C}) -> Val = gs:read(dict:fetch({R,C},D),label), io:format("{~p,~p}->~p~n", [R,C,Val]) end, Keys).
While the algorithm is executing, you will notice that the buttons will flash every time it detects a re-positioning is required. Here is a screen shot and do let me know if you have any comments, it would be much appreciated; that applies to ideas as well :-)


Saturday, November 3, 2007

Core Erlang + "GS" = GUI version of the "BubbleSort"

Everyone who has studied Computer Science would know about the Bubble Sort algorithm. This is a simple sorting algorithm which runs at O(n^2). You may wish to consult your standard data structure text or the above hyperlink for further information.

Since this particular blog of mine is about Erlang and also i'm quite "hooked" to it, so again this article is about illustrating this algorithm implemented using Erlang. It's a fun exercise.

I have included source codes for running 2 versions: (a) Non-graphical and (b) Graphical.

%
% This is an attempt to create a GUI version of the "Bubble Sort"
%
% procedure bubblesort(A:list of unsorted items) defined as:
% do
% swapped := false
% for each i in 0 to length(A) -2 do
% if A[i] > A[i+1] then
% swap(A[i], A[i+1])
% swapped := true
% end if
% end for
% while swapped
% end procedure

-module(bsort).
-export([start/1, init/1]).
-copyright('Copyright (c) 2007 Raymond Tay').
-vsn('$Revision: 1').

start(N) -> spawn(bsort, init, [N]).

%
% Standard "for"-loop concept
%
for(N,N,Dict,F,Num) -> Val = F(Num), NewDict = dict:store(N,Val,Dict), NewDict;
for(I,N,Dict,F,Num) -> Val = F(Num), NewDict = dict:store(I,Val,Dict), for(I+1,N,NewDict,F,Num).

% Swaps the value but not the position of the record
%
swap({Pos1,Value1},{Pos2,Value2},Dict) ->
NewDict1 = dict:store(Pos1,Value2,Dict),
NewDict2 = dict:store(Pos2,Value1,NewDict1),
NewDict2.

%
% BubbleSort implementation
%
bsort(D,Swapped) when Swapped =:= false -> D;
bsort(D,Swapped) when Swapped =:= true ->
Len = erlang:length(dict:fetch_keys(D)),
{Again, NewDict} = checkNSwap(D,1,Len, false),
bsort(NewDict,Again).

%
% Check-N-Swap
%
checkNSwap(Dict,N,N,Again) -> {Again,Dict};
checkNSwap(Dict,I,N,Again) ->
Ele1 = dict:fetch(I,Dict),
Ele2 = dict:fetch(I+1,Dict),
if
Ele1 > Ele2 -> NewDict = swap({I,Ele1},{I+1,Ele2},Dict), checkNSwap(NewDict, I+1,N,true);
Ele1 =< Ele2 -> checkNSwap(Dict,I+1,N,Again)
end.

init(N) -> Dict = dict:new(),
NewDict = for(1,N,Dict, fun random:uniform/1, N),
dumpDict(bsort(NewDict,true)).


dumpDict(Dict) ->
Keys = lists:sort(dict:fetch_keys(Dict)),
lists:foreach(fun(X) -> io:format("{~p,~p} ...", [X,dict:fetch(X,Dict)]) end, Keys).

The next is the source code for the graphical version of the "Bubble Sort" and some screen-shots of the algorithm in action. I used an 25 x 25 "grid" composed of buttons (Will explore using the canvas when i have more time) and i tried the 100 x 100 "grid" but it didn't work out on my laptop as i had some resolution problems, but i think as an exercise a 25 x 25 was good enough for me :-)

-module(bsortgui).
-export([start/0]).
%
% BubbleSort implementation
%
bsort(D,Swapped) when Swapped =:= false -> D;
bsort(D,Swapped) when Swapped =:= true ->
{Again, NewDict} = checkNSwap(D,1,25, false),
bsort(NewDict,Again).

%
% Swaps the value but not the position of the record
%
swap({Pos1,Value1,ButId1},{Pos2,Value2,ButId2},Dict) ->
gs:config(ButId1,[{label, {text, ""}}]),
gs:config(ButId2,[{label, {text, ""}}]),
NewButId1 = dict:fetch({Value1,Pos2},Dict),
NewButId2 = dict:fetch({Value2,Pos1},Dict),
gs:config(NewButId1,[{label, {text, Value1}}]),
gs:config(NewButId2,[{label, {text, Value2}}]),
NewDict1 = dict:store(Pos1,{Value2,NewButId2},Dict),
NewDict2 = dict:store(Pos2,{Value1,NewButId1},NewDict1), NewDict2.

sleep(T) ->
receive
after T -> ok end.
%
% Check-N-Swap
%
checkNSwap(Dict,N,N,Again) -> {Again,Dict};
checkNSwap(Dict,I,N,Again) ->
{Ele1,ButId1} = dict:fetch(I,Dict),
{Ele2,ButId2} = dict:fetch(I+1,Dict),
%io:format("Col:~p,Row:~p~n", [I,Ele1]),
%io:format("Col:~p,Row:~p~n", [I+1,Ele2]),
if
Ele1 > Ele2 -> NewDict = swap({I,Ele1,ButId1},{I+1,Ele2,ButId2},Dict), sleep(300), checkNSwap(NewDict, I+1,N,true);
Ele1 =< Ele2 -> checkNSwap(Dict,I+1,N,Again)
end.


forL(N,N,{stretch,_N,_X}) -> [{stretch,_N,_X}];
forL(I,N,{stretch,_N,_X}) -> [{stretch,_N,_X}|forL(I+1,N,{stretch,_N,_X})].

%for(N,N,[H|_], D, F) -> F(H,D);
%for(I,N,[H|T], D, F) -> NewD = F(H,D), for(I+1,N,T,NewD,F).

genBut(Row,Col,Dict) when Row*Col =< 625 ->
if
Col =< 25 ->
ButId = gs:button(packer, [{label, {text, ""}}, {pack_xy, {Col,Row}}]),
NewDict = dict:store({Row,Col}, ButId, Dict), % used later for GUI manipulation
%io:format("genBut(), Row:~p, Col:~p, Id:~p~n", [Row,Col,ButId]),
genBut(Row,Col+1,NewDict);
Col > 25 -> genBut(Row+1, 1, Dict)
end;
genBut(Row,Col,Dict) when Row*Col > 625 -> Dict.

%
% Fill each column with exactly 1 random number
%
fillRand(Col,Dict) when Col =< 25 ->
Ran = random:uniform(25),
if
Col =< 25 ->
ButId = dict:fetch({Ran,Col},Dict),
gs:config(ButId, [{label, {text, Ran}}]),
NewDict = dict:store(Col, {Ran,ButId}, Dict), % used later for GUI manipulation
%io:format("Row:~p,Col:~p,Val:~p~n", [Ran,Col,Ran]),
fillRand(Col+1,NewDict)
end;
fillRand(Col,Dict) when Col > 25 -> Dict.



start() ->
D = dict:new(),
WH = [{width, 800}, {height, 800}],
Win = gs:window(gs:start(), [{map, true}, {configure, true}, {title, "BubbleSort Algorithm"} |WH]),
XOpts = forL(1,25,{stretch,1,15}),
YOpts = forL(1,25,{stretch,1,15}),
gs:frame(packer, Win, [{packer_x, XOpts}, {packer_y, YOpts}]),
NewD = genBut(1,1,D),
NewD2 = fillRand(1,NewD),
gs:config(packer,WH),
bsort(NewD2,true),
io:format("Done~n",[]),
loop().
%
% A typical loop for receiving messages
%
loop() ->
receive
{gs,_Id,destroy,_Data,_Arg} -> bye;
{gs,_Id,configure,_Data,[W,H|_]} ->
gs:config(packer, [{width,W},{height,H}]), %refresh to initial size
loop();
_Other -> loop()
end.

Below are some screenshots.



Let me know your comments if you got any :-)