Wednesday, October 12, 2011

Enabling the PPTP for a Windows VPN behind OpenWrt router

Beside setting up the router by opening the required ports and creating the VPN server on my Windows machine i had to install the following packages to enable the pptp

Thursday, September 15, 2011

AVL - Binary balanced tree in C#

This is my implementation of a binary search tree with both recursive and iterative insert:
 
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace AVLTree
{
	public class AVLTree<ElementType>
		where ElementType : IComparable<ElementType>
	{
		public Node Root { get; set; }
		public Action<Node, ElementType> PerformActionOnInsertingNodesAllreadyInTheTree { get; set; }

		public void Insert(ElementType value)
		{
			Root = Insert(value, Root);
		}

		public IEnumerable<ElementType> GetContent()
		{
			foreach (var item in GetContent(Root))
				yield return item.Value;
		}

		public int GetHeight()
		{
			int max = int.MinValue;
			foreach (var item in GetContent(Root))
				max = Math.Max(max, item.Height);
			return max;
		}

		private IEnumerable<Node> GetContent(Node node)
		{
			if (null == node)
				yield break;

			foreach (var item in GetContent(node.Left))
				yield return item;
			yield return node;
			foreach (var item in GetContent(node.Right))
				yield return item;
		}

		private Node Insert(ElementType value, Node subtreeNode)
		{
			if (null == subtreeNode)
			{
				subtreeNode = new Node(value);
				return subtreeNode;
			}
			if (0 > value.CompareTo(subtreeNode.Value))
			{
				subtreeNode.Left = Insert(value, subtreeNode.Left);
				if (1 < subtreeNode.Left.Height - Node.HeightOf(subtreeNode.Right))
					if (0 > value.CompareTo(subtreeNode.Left.Value))
						subtreeNode = subtreeNode.RotateWithLeftChild();
					else
						subtreeNode = subtreeNode.DoubleRotateWithLeftChild();
			}
			else if (0 < value.CompareTo(subtreeNode.Value))
			{
				subtreeNode.Right = Insert(value, subtreeNode.Right);
				if (1 < subtreeNode.Right.Height - Node.HeightOf(subtreeNode.Left))
					if (0 < value.CompareTo(subtreeNode.Right.Value))
						subtreeNode = subtreeNode.RotateWithRightChild();
					else
						subtreeNode = subtreeNode.DoubleRotateWithRightChild();
			}
			else
			{
				if (null != PerformActionOnInsertingNodesAllreadyInTheTree)
					PerformActionOnInsertingNodesAllreadyInTheTree(subtreeNode, value);
			}

			subtreeNode.Height = Math.Max(Node.HeightOf(subtreeNode.Left), Node.HeightOf(subtreeNode.Right)) + 1;
			return subtreeNode;
		}

		public void InsertPlain(ElementType value)
		{
			Node current = Root;
			Stack<TreeNavigationStep> pathToCurrentNode = new Stack<TreeNavigationStep>();

			while (null != current)
			{
				if (0 > value.CompareTo(current.Value))
				{
					pathToCurrentNode.Push(new TreeNavigationStep(current, true, true));
					current = current.Left;
				}
				else if (0 < value.CompareTo(current.Value))
				{
					pathToCurrentNode.Push(new TreeNavigationStep(current, false, true));
					current = current.Right;
				}
				else
				{
					if (null != PerformActionOnInsertingNodesAllreadyInTheTree)
					{
						PerformActionOnInsertingNodesAllreadyInTheTree(current, value);
					}
					return;
				}
			}
			Node newNode = new Node(value);
			if (0 == pathToCurrentNode.Count)
			{
				Root = newNode;
				return;
			}

			TreeNavigationStep navigationStep = pathToCurrentNode.Peek();
			current = navigationStep.From;

			if (navigationStep.ToLeft)
			{
				current.Left = newNode;
			}
			else
			{
				current.Right = newNode;
			}

			while(pathToCurrentNode.Count >0)
			{
				var step = pathToCurrentNode.Pop();
				bool performedBalance = false;
				Node parent = step.From;
				Node nodeResultedByBalance = null;
				if (step.FreeToBalance)
				{
					if (step.ToLeft)
					{
						if (1 < parent.Left.Height - Node.HeightOf(parent.Right))
							if (0 > value.CompareTo(parent.Left.Value))
							{
								performedBalance = true;
								nodeResultedByBalance = parent.RotateWithLeftChild();
								if(0<pathToCurrentNode.Count)
								{
									var gradpa = pathToCurrentNode.Peek();
									if(gradpa.ToLeft)
										gradpa.From.Left = nodeResultedByBalance;
									else
										gradpa.From.Right = nodeResultedByBalance;
								}
								pathToCurrentNode.Push(new TreeNavigationStep(nodeResultedByBalance, false, false));
							}
							else
							{
								performedBalance = true;
								nodeResultedByBalance = parent.DoubleRotateWithLeftChild();
								if(0<pathToCurrentNode.Count)
								{
									var gradpa = pathToCurrentNode.Peek();
									if(gradpa.ToLeft)
										gradpa.From.Left = nodeResultedByBalance;
									else
										gradpa.From.Right = nodeResultedByBalance;
								}
								pathToCurrentNode.Push(new TreeNavigationStep(nodeResultedByBalance.Left, false, false));
								pathToCurrentNode.Push(new TreeNavigationStep(nodeResultedByBalance, false, false));
							}
					}
					else
					{
						if (1 < parent.Right.Height - Node.HeightOf(parent.Left))
							if (0 < value.CompareTo(parent.Right.Value))
							{
								performedBalance = true;
								nodeResultedByBalance = parent.RotateWithRightChild();
								if(0<pathToCurrentNode.Count)
								{
									var gradpa = pathToCurrentNode.Peek();
									if(gradpa.ToLeft)
										gradpa.From.Left = nodeResultedByBalance;
									else
										gradpa.From.Right = nodeResultedByBalance;
								}
								pathToCurrentNode.Push(new TreeNavigationStep(nodeResultedByBalance, false, false));
							}
							else
							{
								performedBalance = true;
								nodeResultedByBalance = parent.DoubleRotateWithRightChild();
								if(0<pathToCurrentNode.Count)
								{
									var gradpa = pathToCurrentNode.Peek();
									if(gradpa.ToLeft)
										gradpa.From.Left = nodeResultedByBalance;
									else
										gradpa.From.Right = nodeResultedByBalance;
								}
								pathToCurrentNode.Push(new TreeNavigationStep(nodeResultedByBalance.Right, false, false));
								pathToCurrentNode.Push(new TreeNavigationStep(nodeResultedByBalance, false, false));
							}
					}
					if (performedBalance)
						Root = nodeResultedByBalance;
					else
						Root = parent;
				}
				
				parent.Height = Math.Max(Node.HeightOf(parent.Left), Node.HeightOf(parent.Right)) + 1;
			}
		}

		public class TreeNavigationStep
		{
			public TreeNavigationStep(Node from, bool toLeftChild, bool freeToBalance)
			{
				From = from;
				ToLeft = toLeftChild;
				FreeToBalance = freeToBalance;
			}
			public Node From { get; set; }
			public bool ToLeft { get; set; }
			public bool FreeToBalance { get; set; }
		}

		[DebuggerDisplay("{Value}")]
		public class Node
		{
			public Node(ElementType value)
			{
				Value = value;
			}

			public Node Left { get; set; }
			public Node Right { get; set; }
			public ElementType Value { get; set; }
			public int Height { get; set; }

			public Node RotateWithLeftChild()
			{
				Debug.Assert(null != this.Left);

				Node left = this.Left;
				this.Left = left.Right;
				left.Right = this;

				this.Height = Math.Max(HeightOf(this.Left), HeightOf(this.Right)) + 1;
				left.Height = Math.Max(HeightOf(left.Left), this.Height) + 1;
				return left;
			}

			public Node RotateWithRightChild()
			{
				Debug.Assert(null != this.Right);

				Node right = this.Right;
				this.Right = right.Left;
				right.Left = this;

				this.Height = Math.Max(HeightOf(this.Left), HeightOf(this.Right)) + 1;
				right.Height = Math.Max(HeightOf(right.Right), this.Height) + 1;
				return right;
			}

			public Node DoubleRotateWithLeftChild()
			{
				Debug.Assert(null != this.Left && null != this.Left.Right);

				this.Left = this.Left.RotateWithRightChild();
				return this.RotateWithLeftChild();
			}

			public Node DoubleRotateWithRightChild()
			{
				Debug.Assert(null != this.Right && null != this.Right.Left);

				this.Right = this.Right.RotateWithLeftChild();
				return this.RotateWithRightChild();
			}

			public static int HeightOf(Node node)
			{
				if (null == node)
					return -1;
				return node.Height;
			}
		}
	}
}

Thursday, August 4, 2011

Changed the free DNS Hosting

Just moved from http://free.editdns.net to http://freedns.afraid.org . Tomorrow I will see if the transition was frictionless.

Thursday, March 17, 2011

Publish C# formatted code in blogspot

To show formatted C# code in my blog from now on i will use the SyntaxHighlighter by Alex Gorbatchev

The quick setup is paste the following text in the blog template before the </head> tag.

<link href='http://alexgorbatchev.com/pub/sh/current/styles/shCore.css' rel='stylesheet' type='text/css'/>
<link href='http://alexgorbatchev.com/pub/sh/current/styles/shThemeRDark.css' rel='stylesheet' type='text/css'/>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCpp.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCSharp.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCss.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJava.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJScript.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPhp.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPython.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushRuby.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushSql.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushVb.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushXml.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPerl.js' type='text/javascript'></script>
<script language='javascript'>
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/current/scripts/clipboard.swf';
SyntaxHighlighter.all();
</script>


On posting you should enclose the Html encoded version of your code with <pre class="brush: csharp"> </pre> tags. For encoding in a friendly html format you can use the html encoder

Sanitize input strings against SQL injection using Regex

If SqlParameters cannot be used this is an anti-pattern that will do the job ( C# ):
        public static string Sanitize(this string stringValue)
        {
            if (null == stringValue)
                return stringValue;
            return stringValue
                        .RegexReplace("-{2,}", "-")                 // transforms multiple --- in - use to comment in sql scripts
                        .RegexReplace(@"[*/]+", string.Empty)      // removes / and * used also to comment in sql scripts
                        .RegexReplace(@"(;|\s)(exec|execute|select|insert|update|delete|create|alter|drop|rename|truncate|backup|restore)\s", string.Empty, RegexOptions.IgnoreCase);
        }


        private static string RegexReplace(this string stringValue, string matchPattern, string toReplaceWith)
        {
            return Regex.Replace(stringValue, matchPattern, toReplaceWith);
        }

        private static string RegexReplace(this string stringValue, string matchPattern, string toReplaceWith, RegexOptions regexOptions)
        {
            return Regex.Replace(stringValue, matchPattern, toReplaceWith, regexOptions);
        }

And some tests for input strings ( C# ) ...
        [TestMethod]
        public void OnNullShouldReturnNull()
        {
            Assert.IsNull(RegexExtensions.Sanitize(null));
        }

        [TestMethod]
        public void OnValidStringShouldReturnTheSameString()
        {
            Assert.AreEqual("a", "a".Sanitize());
            Assert.AreEqual("aa", "aa".Sanitize());
            Assert.AreEqual("-", "-".Sanitize());
            Assert.AreEqual("a-", "a-".Sanitize());
            Assert.AreEqual("-a", "-a".Sanitize());
            Assert.AreEqual("-a-", "-a-".Sanitize());
        }

        [TestMethod]
        public void OnMultipleDahsedShouldReturnJustADash()
        {
            Assert.AreEqual("-", "--".Sanitize());
            Assert.AreEqual("a-", "a--".Sanitize());
            Assert.AreEqual("-a", "--a".Sanitize());
            Assert.AreEqual("-", "---".Sanitize());
            Assert.AreEqual("-a-", "----a----".Sanitize());
        }

        [TestMethod]
        public void ShouldRemoveGroupCommentsSymbols()
        {
            Assert.AreEqual(string.Empty, "/".Sanitize());
            Assert.AreEqual(string.Empty, "*".Sanitize());
            Assert.AreEqual(string.Empty, "/**//*/*/".Sanitize());
            Assert.AreEqual("a", "/*a*/".Sanitize()); 
        }

        [TestMethod]
        public void ShouldRemoveSQLKeyWords()
        {
            Assert.AreEqual("eXec", "eXec".Sanitize());
            Assert.AreEqual(string.Empty, ";eXec ".Sanitize());
            Assert.AreEqual(string.Empty, " eXec ".Sanitize());
            Assert.AreEqual("  ", "  eXec  ".Sanitize());
        }

Thursday, February 17, 2011

CustomTypeDescriptors

Mebyon Kernow had a very nice simplification to commands in wpf using custom type descriptors: http://blogs.msdn.com/b/morgan/archive/2010/06/24/simplifying-commands-in-mvvm-and-wpf.aspx

I pasted some code for future reference:

namespace PersistingWorkflows
{
/// <summary>
/// A map that exposes commands in a WPF binding friendly manner
/// </summary>
[TypeDescriptionProvider(typeof(CommandMapDescriptionProvider))]
public class CommandMap
{
/// <summary>
/// Add a named command to the command map
/// </summary>
/// <param name="commandName">The name of the command</param>
/// <param name="executeMethod">The method to execute</param>
public void AddCommand(string commandName, Action<object> executeMethod)
{
Commands[commandName] = new DelegateCommand(executeMethod);
}

/// <summary>
/// Add a named command to the command map
/// </summary>
/// <param name="commandName">The name of the command</param>
/// <param name="executeMethod">The method to execute</param>
/// <param name="canExecuteMethod">The method to execute to check if the command can be executed</param>
public void AddCommand(string commandName, Action<object> executeMethod, Predicate<object> canExecuteMethod)
{
Commands[commandName] = new DelegateCommand(executeMethod, canExecuteMethod);
}

/// <summary>
/// Remove a command from the command map
/// </summary>
/// <param name="commandName">The name of the command</param>
public void RemoveCommand(string commandName)
{
Commands.Remove(commandName);
}

/// <summary>
/// Expose the dictionary of commands
/// </summary>
protected Dictionary<string, ICommand> Commands
{
get
{
if (null == _commands)
_commands = new Dictionary<string, ICommand>();

return _commands;
}
}

/// <summary>
/// Store the commands
/// </summary>
private Dictionary<string, ICommand> _commands;

/// <summary>
/// Implements ICommand in a delegate friendly way
/// </summary>
private class DelegateCommand : ICommand
{
/// <summary>
/// Create a command that can always be executed
/// </summary>
/// <param name="executeMethod">The method to execute when the command is called</param>
public DelegateCommand(Action<object> executeMethod) : this(executeMethod, null) { }

/// <summary>
/// Create a delegate command which executes the canExecuteMethod before executing the executeMethod
/// </summary>
/// <param name="executeMethod"></param>
/// <param name="canExecuteMethod"></param>
public DelegateCommand(Action<object> executeMethod, Predicate<object> canExecuteMethod)
{
if (null == executeMethod)
throw new ArgumentNullException("executeMethod");

this._executeMethod = executeMethod;
this._canExecuteMethod = canExecuteMethod;
}

public bool CanExecute(object parameter)
{
return (null == _canExecuteMethod) ? true : _canExecuteMethod(parameter);
}

public event EventHandler CanExecuteChanged
{
add { CommandManager.RequerySuggested += value; }
remove { CommandManager.RequerySuggested -= value; }
}

public void Execute(object parameter)
{
_executeMethod(parameter);
}

private Predicate<object> _canExecuteMethod;
private Action<object> _executeMethod;
}


/// <summary>
/// Expose the dictionary entries of a CommandMap as properties
/// </summary>
private class CommandMapDescriptionProvider : TypeDescriptionProvider
{
/// <summary>
/// Standard constructor
/// </summary>
public CommandMapDescriptionProvider()
: this(TypeDescriptor.GetProvider(typeof(CommandMap)))
{
}

/// <summary>
/// Construct the provider based on a parent provider
/// </summary>
/// <param name="parent"></param>
public CommandMapDescriptionProvider(TypeDescriptionProvider parent)
: base(parent)
{
}

/// <summary>
/// Get the type descriptor for a given object instance
/// </summary>
/// <param name="objectType">The type of object for which a type descriptor is requested</param>
/// <param name="instance">The instance of the object</param>
/// <returns>A custom type descriptor</returns>
public override ICustomTypeDescriptor GetTypeDescriptor(Type objectType, object instance)
{
return new CommandMapDescriptor(base.GetTypeDescriptor(objectType, instance), instance as CommandMap);
}
}

/// <summary>
/// This class is responsible for providing custom properties to WPF - in this instance
/// allowing you to bind to commands by name
/// </summary>
private class CommandMapDescriptor : CustomTypeDescriptor
{
/// <summary>
/// Store the command map for later
/// </summary>
/// <param name="descriptor"></param>
/// <param name="map"></param>
public CommandMapDescriptor(ICustomTypeDescriptor descriptor, CommandMap map)
: base(descriptor)
{
_map = map;
}

/// <summary>
/// Get the properties for this command map
/// </summary>
/// <returns>A collection of synthesized property descriptors</returns>
public override PropertyDescriptorCollection GetProperties()
{
//TODO: See about caching these properties (need the _map to be observable so can respond to add/remove)
PropertyDescriptor[] props = new PropertyDescriptor[_map.Commands.Count];

int pos = 0;

foreach (KeyValuePair<string, ICommand> command in _map.Commands)
props[pos++] = new CommandPropertyDescriptor(command);

return new PropertyDescriptorCollection(props);
}

private CommandMap _map;
}

/// <summary>
/// A property descriptor which exposes an ICommand instance
/// </summary>
private class CommandPropertyDescriptor : PropertyDescriptor
{
/// <summary>
/// Construct the descriptor
/// </summary>
/// <param name="command"></param>
public CommandPropertyDescriptor(KeyValuePair<string, ICommand> command)
: base(command.Key, null)
{
_command = command.Value;
}

/// <summary>
/// Always read only in this case
/// </summary>
public override bool IsReadOnly
{
get { return true; }
}

/// <summary>
/// Nope, it's read only
/// </summary>
/// <param name="component"></param>
/// <returns></returns>
public override bool CanResetValue(object component)
{
return false;
}

/// <summary>
/// Not needed
/// </summary>
public override Type ComponentType
{
get { throw new NotImplementedException(); }
}

/// <summary>
/// Get the ICommand from the parent command map
/// </summary>
/// <param name="component"></param>
/// <returns></returns>
public override object GetValue(object component)
{
CommandMap map = component as CommandMap;

if (null == map)
throw new ArgumentException("component is not a CommandMap instance", "component");

return map.Commands[this.Name];
}

/// <summary>
/// Get the type of the property
/// </summary>
public override Type PropertyType
{
get { return typeof(ICommand); }
}

/// <summary>
/// Not needed
/// </summary>
/// <param name="component"></param>
public override void ResetValue(object component)
{
throw new NotImplementedException();
}

/// <summary>
/// Not needed
/// </summary>
/// <param name="component"></param>
/// <param name="value"></param>
public override void SetValue(object component, object value)
{
throw new NotImplementedException();
}

/// <summary>
/// Not needed
/// </summary>
/// <param name="component"></param>
/// <returns></returns>
public override bool ShouldSerializeValue(object component)
{
return false;
}

/// <summary>
/// Store the command which will be executed
/// </summary>
private ICommand _command;
}
}
}