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.
- Window should be border-less, style-less
- We can drag the window with the help of the mouse.
- Draw the ruler in either direction, i.e. Left, Top, Right and Bottom.
- With double click you can change its direction from Horizontal to Vertical positioning.
Here is how it looks like pictorially :-
( 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:-
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 :)
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!