|
On-screen rulers are becoming standard elements in word-processing, drawing, and related software. Tom presents a function for displaying a Windows ruler that's based on recursion-removal techniques.
June 01, 1994
URL:http://www.drdobbs.com/tools/algorithm-alley/184409261
Copyright © 1994, Dr. Dobb's Journal
Copyright © 1994, Dr. Dobb's Journal
Copyright © 1994, Dr. Dobb's Journal
With the growing popularity of GUIs, on-screen rulers are becoming standard elements in word processing, drawing, and other software. But displaying a true-to-life image of a ruler on a graphics screen (see Figure 1) is not as simple as it may seem. The key to discovering an efficient algorithm is to realize that a ruler's markings are a kind of fractal--they exhibit the self-similar characteristics of fractal geometry in which any section of an image looks like any other regardless of magnification. A ruler's markings are literally scale-symmetric, and drawing them on a computer screen naturally leads to a recursive algorithm with many practical applications.
A couple of years ago, I wrote a function to display a ruler in a Windows program for Borland's ObjectWindows (OWL) C++ and Pascal videos. I wasn't entirely happy with that code, so, when revising the program for OWL 2.0, I decided to upgrade the ruler-display procedure. I began with a recursive implementation similar to one in Robert Sedgewick's Algorithms in C++. I improved that code, then, using recursion-removal techniques, I wrote several new versions, finally arriving at a nonrecursive method that can easily be adapted to any programming language. The set of functions also demonstrates valuable techniques for removing recursion, which you might need, for example, when implementing recursive algorithms in a nonrecursive programming language such as assembly.
Example 1 is my improved recursive algorithm in Pascal for drawing a ruler's markings. The method differs from Sedgewick's in two ways. First, I use a Level parameter, which when equal to 0, ends the procedure's recursions. (The original algorithm stops calling itself when the marker height equals 0, making it difficult to develop a program that can display different levels of markings of the same relative sizes.) Second, I throw an exception if the marker height H becomes 0 or less before the procedure reaches its deepest recursion. In place of Throw, you could instead halt the program or call an Error function. To use the procedure, you need to define several global values--a constant smallMarkerSize equal to the largest size of a ruler's submarkings, another constant smallMarkerIncr equal to the difference in size between submarkers, a variable Top for the ruler's top-border coordinate, and a Line (X1, Y1, X2, Y2) function. The method works by repeatedly finding the midpoint between L and R, drawing a line at that point, then calling itself recursively one time each for the left- and right-hand subdivisions--an approach that closely resembles recursive divide-and-conquer algorithms for tree traversal, sorting, and other well-known programming techniques.
Although recursion usually makes algorithms easier to understand, it isn't always desirable. A procedure that calls itself wastes stack space and can slow performance by reexecuting entry and exit code added by the compiler. Removing recursion, however, is a painstaking chore that requires the utmost care. To master the process, it helps to follow the step-by-step stages of an algorithm such as Ruler in its transformation from a recursive procedure to a nonrecursive metamorphosis.
Example 2 shows the first such stage, which makes only one recursive call. I removed the second recursive statement from Example 1 by using a technique called "end-recursion removal." In general, when a recursive procedure's last statement calls that procedure, you can replace the statement by performing two simple operations: assigning the recursive statement's argument values to the procedure's parameters and using a Goto to restart the procedure from the top. In fact, a smart optimizing compiler should be able to remove end recursions automatically. After all, the compiler already generates code that pushes parameters onto the stack and calls the subroutine--it could just as easily reassign those values and jump to the subroutine's beginning. I don't know why more compilers don't perform end-recursion removal, but every compiler should offer this optimization.
Goto statements make me uneasy, but they are easily replaced with structured loops. As in Example 2, the Goto-less procedure in Example 3 removes the original's end recursion but uses a While loop in place of Goto. If you can derive the structured code directly from the original, go ahead, but I find it easier to waddle through the intermediate step. Removing recursions is one of the few practical uses I've found for the notorious Goto.
Removing a recursive call from the middle of a procedure is much more difficult than removing an end recursion. The trick is to think like a compiler, which generates code to push variables onto the stack before recursively calling the subroutine. In this case, however, you can't simply assign a few values and execute a Goto. You also have to add code to handle the processes that would occur after the original procedure's recursions unwind. Usually, the best way to write that code is to push parameters and local variables onto a stack variable. (You can implement the stack however you wish--as an array, for example, or a list.) Upon reaching the innermost loop--analogous to reaching the final recursion--pop the saved parameters and variables from the stack and restart the function. That description may seem simple enough, but writing the code to remove an inner recursion can be exceedingly difficult.
Again, I find it easier to accomplish the task by using unstructured code. Starting with Example 2, for instance, I derived Example 4, in which Gotos replace all recursive function calls. The code may seem highly obscure at this stage. I added a third Goto label, RulerRestart, which marks the processes that the original version executes after each recursion unwinds. If the stack is not empty at the end of the procedure, a Goto statement jumps to RulerRestart, which pops the stack and restarts the procedure from its beginning--exactly what the compiler-generated code does in the original recursive design. For illustration, I also inserted obviously unnecessary statements such as the assignment of L to L, simulating the code a compiler generates for pushing variables onto the stack.
All Gotos and no Whiles is about as much fun as all work and no play, so let's get rid of all those ugly labels and jumps. Example 5 replaces the Gotos in Example 4 with structured While and If statements for a fully nonrecursive version of the original procedure. Here again, I left in various inefficiencies, simulating the code a compiler might generate. As a general rule, when removing recursion, it's best to postpone optimizations for the final result. Inefficiencies don't matter at this stage. The new procedure in Example 5 tests whether the stack is empty at the procedure's beginning, so the first statement pushes parameters onto the stack before the While loop begins. Because local variable M isn't initialized at this point, the statement pushes a literal 0 in its place.
The nonrecursive, Goto-less code is nearing its final stage, and at this point, a useful trick for optimizing the procedure is to examine Push and Pop statements in the hope of weeding out null operations. For instance, Example 5 pushes L onto the stack, then later pops L, but immediately assigns it the value of M. Obviously, an improved procedure can simply push M and delete the assignment. Similarly, the procedure pushes and pops Level, but decreases it by one after each such operation. Instead, the code may as well first decrease Level, push that value, and delete the second subtraction. Parameter H is also reduced in two places by smallMarkerIncr, and the value can therefore be reduced before it is pushed. By making these optimizations, you can delete the three assignments in the If statement, leaving a Pop statement followed by a Push of the same values--another obvious null operation that you also can remove. In fact, the entire If statement isn't needed at all! Deleting other unnecessary statements such as the assignment of L to L leads to the final nonrecursive, optimized Ruler procedure in Example 6.
The final procedure lacks the intuitive simplicity of the original in Example 1, but the on-screen results are the same. I didn't profile any of the code listed here, so I can't say whether the nonrecursive version runs faster, but removing recursion usually produces a speed boost. If anyone cares to analyze the procedures, I'll list the results in a future "Algorithm Alley."
Listings One through Four (page 148) implement Examples 1 through 6 in C++ for Windows 3.1 or Windows NT. The final program displays the window in Figure 1, and it also shows miscellaneous steps for drawing the ruler's outline, labeling inch markings, and so on. I included each intermediate stage of the Ruler algorithm as comments so you can compare them. The program requires Borland C++ 4.0 with ObjectWindows 2.0. If you have the files on disk, open the .IDE project file and compile. You might have to adjust directory pathnames. If you are typing the listings, create a 16- or 32-bit Windows project for RULER.CPP, RULER.RC, and RULER.DEF.
When you run the program, you'll notice that the ruler is not drawn to scale. I ignored that problem to keep the algorithms as general as possible, but you can easily produce a real-size ruler by passing MM_LOENGLISH to the Windows SetMapMode function in reference to a display context. If you make that change, you also have to negate y coordinates because, with a mapping mode in effect, coordinate 0,0 is located at lower left rather than its normal pixel-based position at upper left. The printed ruler should be close to real size, but because Windows expands displayed graphics to keep text readable, the on-screen image still appears larger than life. If you need a foot-long ruler that actually measures 12 inches, you'll have to perform your own display mapping--but that's a subject for another time.
Next month, more algorithms and techniques in Pascal and C++. Meanwhile, send your favorite algorithms, tools, and comments to me in care of DDJ.
procedure Ruler(L, R, H, Level: Integer);
var
M: Integer;
begin
if H <= 0 then
Throw('Levels incomplete');
if Level > 0 then
begin
M := (L + R) DIV 2;
Line(M, Top, M, Top + H);
Ruler(L, M, H - smallMarkerIncr, Level - 1);
Ruler(M, R, H - smallMarkerIncr, Level - 1);
end;
end;
procedure Ruler(L, R, H, Level: Integer);
label
RulerStart, RulerEnd;
var
M: Integer;
begin
RulerStart:
if H <= 0 then
Throw('Levels incomplete');
if Level <= 0 then
goto RulerEnd;
M := (L + R) DIV 2;
Line(M, Top, M, Top + H);
Ruler(L, M, H - smallMarkerIncr, Level - 1);
L := M;
H := H - smallMarkerIncr;
Level := Level - 1;
goto RulerStart;
RulerEnd:
end;
procedure Ruler(L, R, H, Level: Integer);
var
M: Integer;
begin
while level > 0 do
begin
if H <= 0 then
Throw('Levels incomplete');
M := (L + R) DIV 2;
Line(M, Top, M, Top + H);
Ruler(L, M, H - smallMarkerIncr, Level - 1);
L := M;
Level := Level - 1;
H := H - smallMarkerIncr;
end;
end;
procedure Ruler(L, R, H, Level: Integer);
label
RulerStart, RulerRestart, RulerEnd;
var
M: Integer;
begin
RulerStart:
if Level = 0 then
goto RulerEnd;
if H <= 0 then
Throw('Levels incomplete');
M := (L + R) DIV 2;
Line(M, Top, M, Top + H);
Push(L, R, M, H, Level);
L := L;
R := M;
H := H - smallMarkerIncr;
Level := Level - 1;
goto RulerStart;
RulerRestart:
Pop(L, R, M, H, Level);
L := M;
Level := Level - 1;
H := H - smallMarkerIncr;
goto RulerStart;
RulerEnd:
if not StackEmpty then
goto RulerRestart;
end;
procedure Ruler(L, R, H, Level: Integer);
var
M: Integer;
begin
Push(L, R, 0, H, Level);
while not StackEmpty do
begin
Pop(L, R, M, H, Level);
while Level > 0 do
begin
if H <= 0 then
Throw('Levels incomplete');
M := (L + R) DIV 2;
Line(M, Top, M, Top + H);
Push(L, R, M, H, Level);
L := L;
R := M;
H := H - smallMarkerIncr;
Level := Level - 1;
end;
if not StackEmpty then
begin
Pop(L, R, M, H, Level);
L := M;
Level := Level - 1;
H := H - smallMarkerIncr;
Push(L, R, M, H, Level);
end;
end;
end;
procedure Ruler(L, R, H, Level: Integer);
var
M: Integer;
begin
Push(L, R, 0, H, Level);
while not StackEmpty do
begin
Pop(L, R, M, H, Level);
while Level > 0 do
begin
if H <= 0 then
Throw('Levels incomplete');
M := (L + R) DIV 2;
Line(M, Top, M, Top + H);
H := H - smallMarkerIncr;
Level := Level - 1;
Push(M, R, M, H, Level);
R := M;
end;
end;
end;
EXETYPE WINDOWS CODE PRELOAD MOVEABLE DISCARDABLE DATA PRELOAD MOVEABLE MULTIPLE HEAPSIZE 4096 STACKSIZE 5120
// ruler.rh -- Resource header file #define ID_MENU 100
#include <owl\window.rh>
#include "ruler.rh"
ID_MENU MENU
BEGIN
POPUP "&Demo"
BEGIN
MENUITEM "E&xit", CM_EXIT
END
END
/* =========================================================== *\
** ruler.cpp -- Ruler algorithms implemented for Windows 3.1 **
** Requires Borland C++ 4.0 and ObjectWindows 2.0 **
** Copyright (c) 1994 by Tom Swan. All rights reserved. **
\* =========================================================== */
#include <owl\applicat.h>
#include <owl\framewin.h>
#include <owl\scroller.h>
#include <owl\dc.h>
#include <classlib\stacks.h>
#include <string.h>
#include <cstring.h>
#include <stdio.h>
#pragma hdrstop
#include "ruler.rh"
// === The application's main window ===
class TRulerWin: public TFrameWindow {
public:
TRulerWin(TWindow* parent, const char far* title);
protected:
BOOL StackEmpty()
{ return stack.IsEmpty(); }
void Line(int x1, int y1, int x2, int y2)
{ dc->MoveTo(x1, y1); dc->LineTo(x2, y2); }
void Rectangle(int left, int top, int right, int bottom)
{ dc->Rectangle(left, top, right, bottom); }
void TextAt(int x, int y, const char *s)
{ dc->TextOut(x, y, s, strlen(s)); }
void InchRuler(int xOutline, int yOutline, int numInches);
void Paint(TDC& paintDC, BOOL erase, TRect& rect);
void Ruler(int l, int r, int h, int level);
void Push(int l, int r, int m, int h, int level);
void Pop(int& l, int& r, int& m, int& h, int& level);
private:
TDC* dc; // Device context for member functions
int unitsPerInch; // Display scale
int numDivisions; // Number of ruler marker divisions
int largeMarkerSize; // Size of main markers at labels
int smallMarkerIncr; // Size of sub marker increments
int smallMarkerSize; // Size of largest sub marker
int left, top, right, bottom; // Ruler outline coordinates
TStackAsVector<int> stack; // Push-down stack
};
TRulerWin::TRulerWin(TWindow* parent, const char far* title)
: TFrameWindow(parent, title),
TWindow(parent, title)
{
AssignMenu(ID_MENU);
Attr.Style |= WS_VSCROLL | WS_HSCROLL;
Scroller = new TScroller(this, 1, 1, 2000, 2000);
dc = 0; // Set pointer to null
unitsPerInch = 100; // 1 pixel == 1/100 inch
numDivisions = 4; // Recursion level (i.e. to 1/16-inch)
smallMarkerIncr = 4; // In units per inch (i.e. 0.04 inch)
left = top = right = bottom = 0; // Ruler coordinates
smallMarkerSize = // Size of largest sub marker
smallMarkerIncr + (smallMarkerIncr * numDivisions);
largeMarkerSize = // Size of markers at digit labels
smallMarkerSize + (smallMarkerIncr * 2);
}
// Display ruler
void
TRulerWin::InchRuler(int xOutline, int yOutline, int numInches)
{
int i; // For-loop control variable
int x, y; // Working coordinate variables
char s[4]; // Holds ruler digits in text form
// Initialize and draw ruler outline
left = xOutline;
top = yOutline;
right = left + (numInches * unitsPerInch);
bottom = top + (largeMarkerSize * 3);
Rectangle(left, top, right, bottom);
// Label main ruler markers at every inch
y = top + largeMarkerSize;
x = left;
for (i = 1; i < numInches; i++) {
x += unitsPerInch;
Line(x, top, x, y);
sprintf(s, "%d", i);
TextAt(x, y, s);
}
// Call Ruler() function to display ruler markings
x = left;
for (i = 0; i < numInches; i++) {
try {
Ruler(x, x + unitsPerInch, smallMarkerSize, numDivisions);
}
catch (const char *msg) {
throw TXOwl(msg);
}
x += unitsPerInch;
}
}
/* // Ruler implementation #1 (recursive version)
void
TRulerWin::Ruler(int l, int r, int h, int level)
{
int m;
if (h <= 0)
throw "Levels incomplete";
if (level > 0) {
m = (l + r) / 2;
Line(m, top, m, top + h);
Ruler(l, m, h - smallMarkerIncr, level - 1);
Ruler(m, r, h - smallMarkerIncr, level - 1);
}
}*/
/* // Ruler implementation #2 (end-recursion removed using goto)
void
TRulerWin::Ruler(int l, int r, int h, int level)
{
int m;
RulerStart:
if (h <= 0)
throw "Levels incomplete";
if (level <= 0)
goto RulerEnd;
m = (l + r) / 2;
Line(m, top, m, top + h);
Ruler(l, m, h - smallMarkerIncr, level - 1);
l = m;
level--;
h -= smallMarkerIncr;
goto RulerStart;
RulerEnd:
}*/
/* // Ruler implementation #3 (end-recursion removed using while)
void
TRulerWin::Ruler(int l, int r, int h, int level)
{
int m;
while (level > 0) {
if (h <= 0)
throw "Levels incomplete";
m = (l + r) / 2;
Line(m, top, m, top + h);
Ruler(l, m, h - smallMarkerIncr, level - 1);
l = m;
level--;
h -= smallMarkerIncr;
}
}*/
/* // Ruler implementation #4a (all-recursion removed using goto)
// Derived from implementation #2
void
TRulerWin::Ruler(int l, int r, int h, int level)
{
int m;
RulerStart:
if (level == 0)
goto RulerEnd;
if (h <= 0)
throw "Levels incomplete";
m = (l + r) / 2;
Line(m, top, m, top + h);
Push(l, r, m, h, level);
l = l;
r = m;
h -= smallMarkerIncr;
level--;
goto RulerStart;
RulerRestart:
Pop(l, r, m, h, level);
l = m;
level--;
h -= smallMarkerIncr;
goto RulerStart;
RulerEnd:
if (!StackEmpty())
goto RulerRestart;
}*/
/* // Ruler implementation #4b (all recursion removed using while and goto)
// Because this intermediate version jumps into a while loop, it may not be
// allowed in all languages. Derived from implementation #3
void
TRulerWin::Ruler(int l, int r, int h, int level)
{
int m;
RulerStart:
while (level > 0) {
if (h <= 0)
throw "Levels incomplete";
m = (l + r) / 2;
Line(m, top, m, top + h);
Push(l, r, m, h, level);
l = l;
r = m;
h -= smallMarkerIncr;
level--;
goto RulerStart;
RulerRestart:
Pop(l, r, m, h, level);
l = m;
level--;
h -= smallMarkerIncr;
}
if (!StackEmpty())
goto RulerRestart;
}*/
/* // Ruler implementation #5 (structured all-recursion removed)
// Non-optimized version
void
TRulerWin::Ruler(int l, int r, int h, int level)
{
int m;
Push(l, r, 0, h, level); // 0 == m, which is uninitialized
while (!StackEmpty()) {
Pop(l, r, m, h, level);
while (level > 0) {
if (h <= 0)
throw "Levels incomplete";
m = (l + r) / 2;
Line(m, top, m, top + h);
Push(l, r, m, h, level);
l = l;
r = m;
h -= smallMarkerIncr;
level--;
}
if (!StackEmpty()) {
Pop(l, r, m, h, level);
l = m;
level--;
h -= smallMarkerIncr;
Push(l, r, m, h, level);
}
}
}*/
// Ruler implementation #6 (structured all-recursion removed)
// Final optimized version
void
TRulerWin::Ruler(int l, int r, int h, int level)
{
int m;
Push(l, r, 0, h, level); // 0 == m, which is uninitialized
while (!StackEmpty()) {
Pop(l, r, m, h, level);
while (level > 0) {
if (h <= 0)
throw "Levels incomplete";
m = (l + r) / 2;
Line(m, top, m, top + h);
h -= smallMarkerIncr;
level--;
Push(m, r, m, h, level);
r = m;
}
}
}
// Push integer arguments onto stack
void
TRulerWin::Push(int l, int r, int m, int h, int level)
{
stack.Push(l);
stack.Push(r);
stack.Push(m);
stack.Push(h);
stack.Push(level);
}
// Pop integer arguments from stack
void
TRulerWin::Pop(int& l, int& r, int& m, int& h, int& level)
{
level = stack.Pop();
h = stack.Pop();
m = stack.Pop();
r = stack.Pop();
l = stack.Pop();
}
// Respond to WM_PAINT messages
void
TRulerWin::Paint(TDC& paintDC, BOOL /*erase*/, TRect& /*rect*/)
{
dc = &paintDC; // Address paintDC with object's private dc
InchRuler(3, 3, 12); // x == 3, y == 3, length = 12 inches
}
// === The application class ===
class TRulerApp: public TApplication {
public:
TRulerApp(const char far* name)
: TApplication(name) {}
void InitMainWindow();
};
// Initialize the program's main window
void
TRulerApp::InitMainWindow()
{
EnableCtl3d(); // Use Windows 3D controls and dialogs
EnableBWCC(); // Use Borland Custom Controls
MainWindow = new TRulerWin(0, "Ruler");
}
#pragma argsused
// Main program
int
OwlMain(int argc, char* argv[])
{
TRulerApp app("RulerApp");
return app.Run();
}
Copyright © 1994, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.