Rules || “Rulers” in WPF – Power of Recursion

Recursion always been a power full tool of solving the most complicated problems in a very elegant manner, but at the price of space (as it is based on stack). The problems we solve with recursion are usually involve divide and conquer, trees traversal / graphs traversal etc. Today we’ll discuss about binary divide and conquer and you’ll see how trivial it is to draw a “Ruler” in WPF with the help of recursion technique.

Now the question is, what exactly is the “Recursion”? Here is one definition for it :–

Recursion: 
        If you still don't get it, see – "Recursion:"  
(It seems non terminating, actually it does terminate, when the reader “gets it”

In Recursion, we look for patterns, and if we find one, we subdivide it to find similar sub-patterns and so on and that is very much analogous to “Divide and Conquer”. In our case, we will be using “Binary Divide and Conquer (BCD)”, where we divide the problem domain in two halves, each half further is divided into two halves and so on. This technique is used in many problem domains like, binary trees algorithms, like binary search or binary tree traversals, etc, etc.

As an example We’ll be building a Ruler application, xpRuler, in WPF and here are some simple requirements for it.

  1. Window should be border-less, style-less
  2. We can drag the window with the help of the mouse.
  3. Draw the ruler in either direction, i.e. Left, Top, Right and Bottom.
  4. With double click you can change its direction from Horizontal to Vertical positioning.

Here is how it looks like pictorially :-

ruler( Figure – 1 )

This shows both horizontal and vertical positions when you double click them, the positions changes to horizontal or vice versa.

First two requirements can be achieved very easily using XAML and some code behind:-

image

If you look at the above highlighted area, we need to setup three properties, AllowsTransparency should be True, WindowStyle should be none and Background should be transparent.

One more thing and that we’ll do under the MouseLeftButtonDown event handler:

        private void Window_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
        {
            //
            // Allows a window to be dragged by a mouse with its left button down over an
            // exposed area of the window's client area. Needed for auto dragging of the window.
            //
            this.DragMove();
        }

That’s all for making the window’s look and feel, border-less and you can drag the window by clicking in any where in the client-area and move it around. All said, now lets move on to the Recursion algorithm for the drawing of the rulers and here is the code for it.

   1:  using System;
   2:  using System.Collections.Generic;
   3:  using System.Linq;
   4:  using System.Text;
   5:  using System.Windows;
   6:  using System.Windows.Controls;
   7:  using System.Windows.Data;
   8:  using System.Windows.Documents;
   9:  using System.Windows.Input;
  10:  using System.Windows.Media;
  11:  using System.Windows.Media.Imaging;
  12:  using System.Windows.Navigation;
  13:  using System.Windows.Shapes;
  14:  using System.Threading;
  15:   
  16:  namespace Shams.Wpf.Ruler
  17:  {
  18:      /// <summary>
  19:      /// Interaction logic for MainWindow.xaml
  20:      /// </summary>
  21:      public partial class MainWindow : Window
  22:      {
  23:          public MainWindow()
  24:          {
  25:              InitializeComponent();
  26:          }
  27:   
  28:          bool IsHorizontal = true; // initially shall be drawn in horizontal position
  29:          private void TicksCanvas_Loaded(object sender, RoutedEventArgs e)
  30:          {
  31:              // draw the ruler level 8 => (2^level - 1) = 255 <= are the total elements of the balanced tree.
  32:              // (both sides of the ruler multiply by 2 =>(2)*(2^level - 1) == 2 * 255 = 510 elements.
  33:              DrawRuler(sender as Canvas, 8);
  34:   
  35:              // negate the current horizontal state
  36:              IsHorizontal = !IsHorizontal;
  37:          }
  38:   
  39:          private void Window_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
  40:          {
  41:              //
  42:              // Allows a window to be dragged by a mouse with its left button down over an
  43:              // exposed area of the window's client area. Needed for auto dragging of the window.
  44:              //
  45:              this.DragMove();
  46:   
  47:              // If double clicked.
  48:              if (e.ClickCount > 1)
  49:              {
  50:                  // get the actual width and height
  51:                  double width = this.Width;
  52:                  double height = this.Height;
  53:   
  54:                  // reverse them
  55:                  this.Height = width;
  56:                  this.Width = height;
  57:   
  58:                  // Refresh the canvas
  59:                  this.TicksCanvas.Children.Clear();
  60:   
  61:                  // draw the ruler
  62:                  DrawRuler(this.TicksCanvas, 8);
  63:   
  64:                  // negate the current horizontal state
  65:                  IsHorizontal = !IsHorizontal;
  66:              }
  67:          }
  68:   
  69:          void DrawRuler(Canvas canvas, int level)
  70:          {
  71:              if (IsHorizontal)
  72:              {
  73:                  // draw the top one.
  74:                  DrawRuler(this.TicksCanvas,
  75:                      0,
  76:                      0,
  77:                      this.TicksCanvas.ActualWidth,
  78:                      level,
  79:                      true,
  80:                      true,
  81:                      0);
  82:                  
  83:                   // draw the bottom one.
  84:                  DrawRuler(this.TicksCanvas,
  85:                      this.TicksCanvas.ActualHeight,
  86:                      0,
  87:                      this.TicksCanvas.ActualWidth,
  88:                      level,
  89:                      true,
  90:                      false,
  91:                      0);
  92:              }
  93:              else // Vertical
  94:              {
  95:                  // draw the left one.
  96:                  DrawRuler(this.TicksCanvas, 
  97:                      0, 
  98:                      0, 
  99:                      this.TicksCanvas.ActualHeight, 
 100:                      level, 
 101:                      false, 
 102:                      false,
 103:                      0);
 104:   
 105:                  // draw the right one.
 106:                  DrawRuler(this.TicksCanvas, 
 107:                      this.TicksCanvas.ActualWidth, 
 108:                      0, 
 109:                      this.TicksCanvas.ActualHeight, 
 110:                      level, 
 111:                      false, 
 112:                      true,
 113:                      0);
 114:              }
 115:          }
 116:   
 117:          /// <summary>
 118:          /// The main recursive algorithm, divide-n-conquer
 119:          /// </summary>
 120:          /// <param name="canvas"></param>
 121:          /// <param name="start"></param>
 122:          /// <param name="left"></param>
 123:          /// <param name="right"></param>
 124:          /// <param name="level"></param>
 125:          /// <param name="isHorizontal"></param>
 126:          /// <param name="isInvert"></param>
 127:          /// <param name="label"></param>
 128:          void DrawRuler(Canvas canvas,
 129:              double start,
 130:              double left,
 131:              double right,
 132:              int level,
 133:              bool isHorizontal,
 134:              bool isInvert,
 135:              double label)
 136:          {
 137:              // when level reaches 0, stack unwinding starts...
 138:              if (level > 0)
 139:              {
 140:                  double mid = ((left + right) / 2);
 141:   
 142:                  // recursive - devide and conquer algorithm                
 143:                  // draw left to the ruler
 144:                  DrawRuler(canvas,
 145:                      start,
 146:                      left,
 147:                      mid,
 148:                      level - 1,
 149:                      isHorizontal,
 150:                      isInvert,
 151:                      label+1);
 152:   
 153:                  // draw right to the ruler
 154:                  DrawRuler(canvas,
 155:                      start,
 156:                      mid,
 157:                      right,
 158:                      level - 1,
 159:                      isHorizontal,
 160:                      isInvert,
 161:                      label+1);
 162:   
 163:                  #region Drawing functionality
 164:   
 165:                  Line gridline = new Line();
 166:                  gridline.Stroke = Brushes.Black;
 167:                  gridline.StrokeThickness = 1.0;
 168:   
 169:                  int ifactor = isInvert ? -1 : +1;
 170:                  if (isHorizontal)
 171:                  {
 172:                      gridline.X1 = mid;
 173:                      gridline.Y1 = start;
 174:                      gridline.X2 = mid;
 175:   
 176:                      gridline.Y2 = (start - ifactor * (level * 5));
 177:                  }
 178:                  else // vertical
 179:                  {
 180:                      gridline.X1 = start;
 181:                      gridline.Y1 = mid;
 182:                      gridline.X2 = (start + ifactor * (level * 5));
 183:                      gridline.Y2 = mid;
 184:                  }
 185:                  //System.Diagnostics.Debug.Write(level + " ");
 186:                  
 187:                  // finally add to the canvas
 188:                  canvas.Children.Add(gridline);
 189:   
 190:                  #endregion
 191:   
 192:              }
 193:          }
 194:   
 195:          private double GetLabel(double level)
 196:          {
 197:              return Math.Pow(2,level) - 1;
 198:          }
 199:   
 200:          private void MenuItemExit_Click(object sender, RoutedEventArgs e)
 201:          {
 202:              this.Close();
 203:          }
 204:   
 205:          private void MenuItemAbout_Click(object sender, RoutedEventArgs e)
 206:          {
 207:              MessageWindow messageWindow = new MessageWindow();
 208:              messageWindow.Title = "About xpRuler Ver.1.1a";
 209:              messageWindow.Message = "Developed by shams mukhtar (shams@xpersoft.com)";
 210:              messageWindow.ShowDialog();
 211:          }
 212:      }
 213:  }

All the magic is done in the method @ lines 128-193

void DrawRuler(Canvas canvas,
            double start,
            double left,
            double right,
            int level,
            bool isHorizontal,
            bool isInvert,
            double label);

The algorithm is analogous to Postorder binary tree traversal, where we visit the left and right sub-trees first and then visit the node itself. In the Method above, left and right indicates the width of the ruler, that's what we divide in each recursive call while the start param. is the start for vertical or start of horizontal location and level indicates the depth for each half. IsHorizontal is an indicator for horizontal/vertical positions and isInvert is used to mirror the start location of the ticks and label is not used (TBD).

Exercise: To the scale (inches / centimeters) plotting of the ruler, along with the proper labeling.
(Hint: Use label argument in the DrawRuler method and (2^level - 1) formula)


So, that's all for now folks. I’ll be looking forward to your feedbacks/comments, enjoy :)

Download File - Ruler Project

If you enjoyed reading this blog, leave your valuable feedback and consider subscribing to the RSS feed. You can also subscribe to it by email. Also, you can follow me on Twitter. Thank you!
Comments are closed