Imagine the following task – you have a stack with some numbers inside followed by a marker.
For example:
1
2
3
4
8
19
29
marker
3
4
… (etc.)We want to sort the numbers above the marker – descending.
Let’s first write down and plan how to resolve this problem. Let’s define our stack like that:
a
b
c
d
MARK
e
f (etc.)Let’s say that
c<b<d<a. How to sort them out?
We need to find a function sort.
/sort { } defNo matter what we are going to write in the block, we need to define on what condition the function will stop working (I mean such state in which we realize that the stack is sorted). In each step we are going to find the minimum element from the stack (above the marker), push it above the marker (with roll command) and finally restart the sort function with recursion. So the condition should be – “proceed until the marker is on top of the stack”. So we have:
/sort {
counttomark 0 gt { } if
} defSo far – so good. Now let’s create the source for the steps we highlighted above.
/sort {
counttomark 0 gt {
counttomark mark exch
1 add 1 roll
findmin
exch pop
counttomark
1 add 1 pop
sort
} if
} defNow, findmin will be the function that will find us the minimum element from the stack. We are going to define it later. It will find the minimum element with recursion and again roll on each step, so at the end we are going to receive this:
minimum element
MARKER
value
value
etc..So, let’s see what our source code will do when we plug in our stack:
a
b
c
d
MARK
e
f (etc.)countomark 0 gt {} if – In our case counttomark is equal to 4. So we push in the stack 4 and then 0.
0
4
a
b
c
d
MARK
e
f (etc.)Then the gt function applies. 4 is greater than 0, so the function-block will be triggered.
In the mean time gt function will destroy the top 2 elements 0 and 4, and push the binary value true. But the if statement will check that value and therefore it will be destroyed. So the function-blocked is triggered and we have again the same stack as the one – we started with.
a
b
c
d
MARK
ecounttomark mark exch – again we counttomark and push 4 as value in the stack. Then we push a marker. Then we proceed with function exch – it will exchange the top 2 elements from the stack. So we will have this stack:
4
MARK
a
b
c
d
MARK
e1 add – we push 1 in the stack. Then the function add will add the top 2 elements from the stack and push in the result. In our case: 4+1 = 5, so 5 will be pushed in back in the stack.
5
MARK
a
b
c
d
MARK
e1 roll – 1 will be pushed in the stack and the function roll will be launched. Roll will take the top 2 values from the stack (first will say how many elements to roll, the second will define in which direction and how many times to be rolled). In our case we will have 5 1 roll (you should see that the two values 5 and 1 will be destroyed/popped after the roll function). So we will have as a result:
a
b
c
d
MARK
MARK
eNow we call the findmin function (which we are going to code later) and the result will be:
c
MARK
d
a
b
MARKWe don’t need the second marker so we need to destroy it with the command – exch pop.
So we will have this stack as a result:
c
d
a
b
MARKcounttomark 1 add 1 roll – again we counttomark which is equal to 4. Then we are adding 1 to the count, because when we roll – we want to roll the marker too. So we will have at the end this stack:
d
a
b
MARK
cCan you see that below the marker we have the minimum element of the stack – c?
If we repeat this process again (by calling the sort function again) we will end up with this stack:
d
a
MARK
b
cJust to recall you that
c<b<d<aSo two more iterations and the stack will be sorted! I told you that PostScript is cryptic language. Now, I am sure you do agree
How to construct the findmin function?
/findmin {
counttomark 1 gt {
2 copy gt { exch } if
counttomark 1 add 1 roll
findmin } if
} defAgain we are using recursion. The idea here is almost the same as the main sort function. I am leaving the decoding to you. Just the third row – 2 copy gt { exch } if – it means that we are going to create the duplicate values of the top two elements on the stack. Then we compare them and we are going to exchange them if the first is greater than the second. We do that until the counttomark is greater than 1 (which means until above the marker to have only 1 element).
Let’s test now the source:
/findmin {
counttomark 1 gt {
2 copy gt { exch } if
counttomark 1 add 1 roll
findmin
} if
} def
/sort {
counttomark 0 gt {
counttomark mark exch
1 add 1 roll
findmin
exch pop
counttomark 1 add 1 roll
sort
} if
} def
mark 88 6 73 9 1 55
stack
sort
stackWhen you compile the source at the beginning we have this stack:
55
1
9
73
6
88
--nostringval--When we call the sort function and print the new stack - we have this:
--nostringval--
88
73
55
9
6
1In next chapter we are going to take a look in the loop operators and solve the same task with loop function.