_ALGORITHM ALLEY_
by Tom Swan

Listing One

EXETYPE WINDOWS
CODE PRELOAD MOVEABLE DISCARDABLE
DATA PRELOAD MOVEABLE MULTIPLE
HEAPSIZE 4096
STACKSIZE 5120


Listing Two


// ruler.rh -- Resource header file
#define ID_MENU 100


Listing Thre

#include <owl\window.rh>
#include "ruler.rh"

ID_MENU MENU
BEGIN
  POPUP "&Demo"
  BEGIN
    MENUITEM "E&xit", CM_EXIT
  END
END


Listing Four

/* =========================================================== *\
**  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
};
// Constructor
TRulerWin::TRulerWin(TWindow* parent, const char far* title)
  : TFrameWindow(parent, title),
    TWindow(parent, title)
{
// Window initializations
  AssignMenu(ID_MENU);
  Attr.Style |= WS_VSCROLL | WS_HSCROLL;
  Scroller = new TScroller(this, 1, 1, 2000, 2000);
// Constant initializations
  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
// Position dependent initializations
  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();
}


Example 1. Pascal code for Algorithm #20: Ruler (recursive 
version)

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;


Example 2. Pascal code for Algorithm #20: Ruler (end-recursion 
removed using Goto)
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;

Example 3. Pascal code for Algorithm #20: Ruler (end-recursion removed 
using While) 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;


Example 4. Pascal code for Algorithm #20: Ruler (all recursion removed using Goto)
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;


Example 5. Pascal code for Algorithm #20: Ruler (all recursion removed 
using While and If) 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;



Example 6. Pascal code for Algorithm #20: Ruler (final optimized version)
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;