Reservoir Sampling

Reservoir sampling is a great random sampling algorithm every data engineer should know. It’s an algorithm for extracting a random sample of a specified size, over a large unbounded dataset. The data is such that you cannot pull it all in memory at once, and you don’t know how large it will be when taking the sample.

Over on wikipedia you can check out a nice explanation of the idea behind reservoir sampling. It presents the most simple algorithm of reservoir sampling. Let me regurgitate it in C#:

public static T[] TakeSample<T>(IEnumerable<T> input, int sampleCount) {
	if (sampleCount <= 0)
		throw new ArgumentOutOfRangeException ("sampleCount");

	Random rand = new Random ();
	var samples = new T[sampleCount];
	int i = 0;
	foreach (T item in input) {
		if (i < sampleCount) {
			samples [i] = item;
		} else {
			int j = rand.Next () % i;
			if (j < sampleCount)
				samples [j] = item;
		}
		i++;
	}

	if (i < sampleCount)
		throw new InvalidOperationException ("Input data does not have enough items to sample");

	return samples;
}

To some this algorithm may seem botched, as the last items have the least likelihood of being selected. However the overall likelihood of being selected is roughly distributed evenly across the entire dataset. This is because the items with more likelihood of being selected earlier on (or absolute certainty for the first k samples, where k = sample count) will have more likelihood of being replaced by a successor sample.

Jeffrey Scott Vitter has published some alternative implementations that optimise the performance of the sampling.

Distributed Reservoir Sampling

When you are dealing with BIG data where you have a distribute infrastructure at your disposal, your not going to stream the entire data set into a single sequence. Here is a crafty map-reduce approach to the sampling problem on stack overflow: http://stackoverflow.com/questions/2514061/how-to-pick-random-small-data-samples-using-map-reduce. I really like this approach as it draws on fundamental computer science algorithm know-how with big-data technology to get the job done!

 

 

Helpful Tips for your Raspberry Pi Media Centre. Part 1: Hardware

It was about time I geeked it up and setup a DIY media centre for my home. I decided to go for the cheap and cheerful hardware option to power my media centre: Raspberry Pi. Only £25 (for the actual computer)! This post shares part 1 of my journey of setting up a choice raspberry pi media centre: from the research to the implementation and retrospection. I’m very happy with the results.

Note: I bought the revision 2/model B (512 Mb RAM) version of Raspberry Pi.

Choosing the SD Card

After countless hours researching on the internet for which SD cards are the best with Raspberry Pi, I finally reached a decision: “SanDisk 16GB 45MB/s Extreme SDHC Card (SDSDX-016G-X46)”. Most forums and guides will say you should spend the extra cash on the class 10 speed cards over lower class cards, this will give you a nice (and much needed) performance boost all round. But choosing the highest read/write speed cards doesn’t necessarily mean they will out perform lower speed cards during the typical workload of a Raspberry Pi session. Some key points to keep in mind when deciding on an SD card are:

  • Read/write speed ratings on SD Cards refer to sequential read throughput. This is great if you think you will be running applications that load/save large chunks of data on the SD card (e.g reading videos from the SD card).
    • My media centre doesn’t have a requirement to perform these types of operations on the SD cards: like most people  videos for my media centre will reside on an external storage (SD cards have limited storage).
    • Typically computers will randomly access the storage device hosting the OS and personal document space (especially when reading/writing to the swap space). So what we really want to look for is throughput based on random access tests.
    • Raspberry Pi’s SD interface limits the sequential read/write speeds anyway. I’ve only found (from my personal research) that the max read/write throughput is about 2oMB/s on the Pi.
    • Checkout this (outdated) article to give you an idea of all the different metrics to evaluate SD card performance: http://www.tomshardware.com/reviews/sdxc-sdhc-uhs-i,2940-9.html. Take note of the speed classes and how they perform differently for different read/write tasks.
  • Make sure your chosen SD card is compatible with Raspberry Pi, and the particular OS(s) you are planning to install. Refer to this site: http://elinux.org/RPi_SD_cards
  • Go for UHS cards, a recent development in SD technology that is kicks ass:  http://www.transcend-info.com/Press/DrT.asp?axn=Detail&PrsNo=115&NewsKeyWd=&Func1No=3&Func2No=211
  • Cheaply manufactured SD cards aren’t built for continuos random read/writes, and so they tend to break (there are some tricks to increase the lifetime of your SD card by configuring the OS, covered in part 2 of this series).

My personal choice was the “SanDisk 16GB 45MB/s Extreme SDHC Card (SDSDX-016G-X46)“, because it ticked all the boxes: UHS-1, 10-Class; 16GB will be more than enough space; and Compatibility (tested ok with both Raspbian and openELEC). Plus I stumbled on this (recent enough) great benchmark review with android: http://www.androidcentral.com/sd-card-showdown-testing-sandisk-extreme

Peripherals

I outlawed buying a conventional PC keyboard and mouse for the raspberry pi because A) it would detract away from its home-media-centre feel, B) it would look lame, and C) it would be just too inconvenient to handle a keyboard and mouse on a couch. I turned to all-in one wireless keyboard and tracker devices.

The long short of my search led me to two competing devices: the “Rii 2.4GHz Wireless Mini PC Keyboard Touchpad“, and the “Logitech K400 Wireless Touch Keyboard“. The winner: Logitech K400.

The Rii mini just seemed too small and a lot of reviews complained about its poor range (can stubble to get more than 1m in some cases). The K400 has a whopping 10m range with good reviews (working with raspberry pi). Also the K400 size is perfect: smaller than a conventional computer keyboard but not too small.

Power and USB

The Raspberry Pi requires at least 700mA of power to run. But once you start attaching other USB devices that don’t provide their own power source, you won’t have enough power to run your rig. What is the solution? Buy a USB hub powered using its own power source. Some key points to think about while you shop for your USB Hub:

  • Not all USB hubs work with Raspberry Pi. Refer to http://elinux.org/RPi_Powered_USB_Hubs for a verified compatibility list.
  • You can use the USB hub to power your Raspberry Pi so you only have a single power plug for the whole rig. This is a nice and tidy option. If you choose to power the Pi via the USB then consider:
    • Ensure the power adaptor provides enough amps for the pi + all additional devices.
  • Keep away from USB hubs that supply back-voltage. These hubs will back-power the Pi by supplying power through the connected USB port. This is dangerous because unlike the micro-USB power input on the Pi, the normal sized USB ports are not protected by a fuse. So if your USB hub has a upstream back-voltage then you need to ensure it will have some sort of fuse between the USB hub and the Pi, otherwise your Pi with Fry.

The PiHub is a great option because it’s supported by the Raspberry Pi Foundation (no worries about compatibility and quality), the proceeds go toward the foundations development, and it powers the Pi with all USB devices with a single powerful power adaptor.

I didn’t choose PiHub because its damn ugly. Too much of an eyesore for my lounge. In the end I went for the pluggable 7-port USB 2.0 hub – because of its ample power supply, copious amounts of positive reviews with Raspberry Pi, doesn’t look as ugly as PiHub,  and it doesn’t have back-voltage on upstream connection.

Also since I already owned a Pi power adaptor I kept using it for powering the Pi (so I have two power supplies for my rig). This probably a bit overkill but there is practically no risk of under supplying the Pi when adding extra devices to my USB hub.  All the coords from my Pi are hidden at the back of the TV: so the extra coord clutter is out of view.

Look out for my second part to this series!

Augmented Interval Tree in C#

Interval trees are an efficient ADT for storing and searching intervals. It is an ADT that probably doesn’t make the top 10 most commonly used collections in computer science. I often see code where a list/array like structure is used to store and searching interval data. Sometimes that is fine – even preferred for the sake of simplicity – but only in cases where the code is rarely run and is not having to handle large volumes of data.

My C# implementation of the IntervalTree uses generics and has the following features:

  • It uses generics.
  • It is mutable.
  • It is backed by a self balancing BST (AVL).
  • It is xml and binary serializable.
  • It supports duplicate intervals.

Originally I wrote the tree so that the end point selector was simply a lamba. However lamba’s are not serializable, so I changed the selector to become an interface (and implemented my own Xml serialization methods to handle the interface).

If your interval collections can afford to be immutable, then a better performing solution is to use a centered interval tree instead. Although the centered interval tree accomplishes the same average complexity has the augmented BST, the tree construction is generally faster.

Here is the code:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Runtime.Serialization;
using System.Xml;
using System.Xml.Schema;
using System.Xml.Serialization;

namespace BrookNovak.Collections
{
	/// <summary>
	/// An interval tree that supports duplicate entries.
	/// </summary>
	/// <typeparam name="TInterval">The interval type</typeparam>
	/// <typeparam name="TPoint">The interval's start and end type</typeparam>
	/// <remarks>
	/// This interval tree is implemented as a balanced augmented AVL tree.
	/// Modifications are O(log n) typical case.
	/// Searches are O(log n) typical case.
	/// </remarks>
	[Serializable]
	public class IntervalTree<TInterval, TPoint> : ICollection<TInterval>, ICollection, ISerializable, IXmlSerializable 
		where TPoint : IComparable<TPoint>
	{
		private readonly object syncRoot;
		private IntervalNode root;
		private ulong modifications;
		private IIntervalSelector<TInterval, TPoint> intervalSelector;

		/// <summary>
		/// Default ctor required for XML serialization support
		/// </summary>
		private IntervalTree()
		{
			syncRoot = new object();
		}

		public IntervalTree(IEnumerable<TInterval> intervals, IIntervalSelector<TInterval, TPoint> intervalSelector) :
			this(intervalSelector)
		{
			AddRange(intervals);
		}

		public IntervalTree(IIntervalSelector<TInterval, TPoint> intervalSelector)
			: this()
		{
			if (intervalSelector == null)
				throw new ArgumentNullException("intervalSelector");
			this.intervalSelector = intervalSelector;
		}

		/// <summary>
		/// Returns the maximum end point in the entire collection.
		/// </summary>
		public TPoint MaxEndPoint
		{
			get
			{
				if(root == null)
					throw new InvalidOperationException("Cannot determine max end point for emtpy interval tree");
				return root.MaxEndPoint;
			}
		}

		#region Binary Serialization

		public IntervalTree(SerializationInfo info, StreamingContext context)
			: this()
		{
			// Reset the property value using the GetValue method.
			var intervals = (TInterval[])info.GetValue("intervals", typeof(TInterval[]));
			intervalSelector = (IIntervalSelector<TInterval, TPoint>)info.GetValue("selector", typeof(IIntervalSelector<TInterval, TPoint>));
			AddRange(intervals);
		}

		public void GetObjectData(SerializationInfo info, StreamingContext context)
		{
			var intervals = new TInterval[Count];
			CopyTo(intervals, 0);
			info.AddValue("intervals", intervals, typeof(TInterval[]));
			info.AddValue("selector", intervalSelector, typeof(IIntervalSelector<TInterval, TPoint>));
		}

		#endregion

		#region IXmlSerializable

		public void WriteXml(XmlWriter writer)
		{
			writer.WriteStartElement("Intervals");
			writer.WriteAttributeString("Count", Count.ToString(CultureInfo.InvariantCulture));
			var itemSerializer = new XmlSerializer(typeof(TInterval));
			foreach (var item in this)
			{
				itemSerializer.Serialize(writer, item);
			}
			writer.WriteEndElement();

			writer.WriteStartElement("Selector");
			var typeName = intervalSelector.GetType().AssemblyQualifiedName ?? intervalSelector.GetType().FullName;
			writer.WriteAttributeString("Type", typeName);
			var selectorSerializer = new XmlSerializer(intervalSelector.GetType());
			selectorSerializer.Serialize(writer, intervalSelector);
			writer.WriteEndElement();
		}

		public void ReadXml(XmlReader reader)
		{
			reader.MoveToContent();
			reader.ReadStartElement();

			reader.MoveToAttribute("Count");
			int count = int.Parse(reader.Value);
			reader.MoveToElement();

			if (count > 0 && reader.IsEmptyElement)
				throw new FormatException("Missing tree items");
			if (count == 0 && !reader.IsEmptyElement)
				throw new FormatException("Unexpected content in tree item Xml (expected empty content)");

			reader.ReadStartElement("Intervals");

			var items = new TInterval[count];

			if (count > 0)
			{
				var itemSerializer = new XmlSerializer(typeof(TInterval));

				for (int i = 0; i < count; i++)
				{
					items[i] = (TInterval)itemSerializer.Deserialize(reader);

				}
				reader.ReadEndElement(); // </intervals>
			}

			reader.MoveToAttribute("Type");
			string selectorTypeFullName = reader.Value;
			if (string.IsNullOrEmpty(selectorTypeFullName))
				throw new FormatException("Selector type name missing");
			reader.MoveToElement();

			reader.ReadStartElement("Selector");

			var selectorType = Type.GetType(selectorTypeFullName);
			if(selectorType == null)
				throw new XmlException(string.Format("Selector type {0} missing from loaded assemblies", selectorTypeFullName));
			var selectorSerializer = new XmlSerializer(selectorType);
			intervalSelector = (IIntervalSelector<TInterval, TPoint>)selectorSerializer.Deserialize(reader);

			reader.ReadEndElement(); // </selector>

			AddRange(items);
		}

		public XmlSchema GetSchema()
		{
			return null;
		}

		#endregion

		#region IEnumerable, IEnumerable<T>

		IEnumerator IEnumerable.GetEnumerator()
		{
			return new IntervalTreeEnumerator(this);
		}

		public IEnumerator<TInterval> GetEnumerator()
		{
			return new IntervalTreeEnumerator(this);
		}

		#endregion

		#region ICollection

		public bool IsSynchronized { get { return false; } }

		public Object SyncRoot { get { return syncRoot; } }

		public void CopyTo(
			Array array,
			int arrayIndex)
		{
			if (array == null)
				throw new ArgumentNullException("array");
			PerformCopy(arrayIndex, array.Length, (i, v) => array.SetValue(v, i));
		}

		#endregion

		#region ICollection<T>

		public int Count { get; private set; }

		public bool IsReadOnly
		{
			get
			{
				return false;
			}
		}

		public void CopyTo(
			TInterval[] array,
			int arrayIndex)
		{
			if (array == null)
				throw new ArgumentNullException("array");
			PerformCopy(arrayIndex, array.Length, (i, v) => array[i] = v);
		}

		/// <summary>
		/// Tests if an item is contained in the tree.
		/// </summary>
		/// <param name="item">The item to check</param>
		/// <returns>
		/// True iff the item exists in the collection. 
		/// </returns>
		/// <remarks>
		/// This method uses the collection’s objects’ Equals and CompareTo methods on item to determine whether item exists.
		/// </remarks>
		public bool Contains(TInterval item)
		{
			if (ReferenceEquals(item, null))
				throw new ArgumentNullException("item");

			return FindMatchingNodes(item).Any();
		}

		public void Clear()
		{
			SetRoot(null);
			Count = 0;
			modifications++;
		}

		public void Add(TInterval item)
		{
			if (ReferenceEquals(item, null))
				throw new ArgumentNullException("item");

			var newNode = new IntervalNode(item, Start(item), End(item));

			if (root == null)
			{
				SetRoot(newNode);
				Count = 1;
				modifications++;
				return;
			}

			IntervalNode node = root;
			while (true)
			{
				var startCmp = newNode.Start.CompareTo(node.Start);
				if (startCmp <= 0)
				{
					if (startCmp == 0 && ReferenceEquals(node.Data, newNode.Data))
						throw new InvalidOperationException("Cannot add the same item twice (object reference already exists in db)");

					if (node.Left == null)
					{
						node.Left = newNode;
						break;
					}
					node = node.Left;
				}
				else
				{
					if (node.Right == null)
					{
						node.Right = newNode;
						break;
					}
					node = node.Right;
				}
			}

			modifications++;
			Count++;

			// Restructure tree to be balanced
			node = newNode;
			while (node != null)
			{
				node.UpdateHeight();
				node.UpdateMaxEndPoint();
				Rebalance(node);
				node = node.Parent;
			}
		}

		/// <summary>
		/// Removes an item.
		/// </summary>
		/// <param name="item">The item to remove</param>
		/// <returns>True if an item was removed</returns>
		/// <remarks>
		/// This method uses the collection’s objects’ Equals and CompareTo methods on item to retrieve the existing item.
		/// If there are duplicates of the item, then object reference is used to remove.
		/// If <see cref="TInterval"/> is not a reference type, then the first found equal interval will be removed.
		/// </remarks>
		public bool Remove(TInterval item)
		{
			if (ReferenceEquals(item, null))
				throw new ArgumentNullException("item");

			if (root == null)
				return false;

			var candidates = FindMatchingNodes(item).ToList();

			if (candidates.Count == 0)
				return false;

			IntervalNode toBeRemoved;
			if (candidates.Count == 1)
			{
				toBeRemoved = candidates[0];
			}
			else
			{
				toBeRemoved = candidates.SingleOrDefault(x => ReferenceEquals(x.Data, item)) ?? candidates[0];
			}

			var parent = toBeRemoved.Parent;
			var isLeftChild = toBeRemoved.IsLeftChild;

			if (toBeRemoved.Left == null && toBeRemoved.Right == null)
			{
				if (parent != null)
				{
					if (isLeftChild)
						parent.Left = null;
					else
						parent.Right = null;

					Rebalance(parent);
				}
				else
				{
					SetRoot(null);
				}
			}
			else if (toBeRemoved.Right == null)
			{
				if (parent != null)
				{
					if (isLeftChild)
						parent.Left = toBeRemoved.Left;
					else
						parent.Right = toBeRemoved.Left;

					Rebalance(parent);
				}
				else
				{
					SetRoot(toBeRemoved.Left);
				}
			}
			else if (toBeRemoved.Left == null)
			{
				if (parent != null)
				{
					if (isLeftChild)
						parent.Left = toBeRemoved.Right;
					else
						parent.Right = toBeRemoved.Right;

					Rebalance(parent);
				}
				else
				{
					SetRoot(toBeRemoved.Right);
				}
			}
			else
			{
				IntervalNode replacement, replacementParent, temp;

				if (toBeRemoved.Balance > 0)
				{
					if (toBeRemoved.Left.Right == null)
					{
						replacement = toBeRemoved.Left;
						replacement.Right = toBeRemoved.Right;
						temp = replacement;
					}
					else
					{
						replacement = toBeRemoved.Left.Right;
						while (replacement.Right != null)
						{
							replacement = replacement.Right;
						}
						replacementParent = replacement.Parent;
						replacementParent.Right = replacement.Left;

						temp = replacementParent;

						replacement.Left = toBeRemoved.Left;
						replacement.Right = toBeRemoved.Right;
					}
				}
				else
				{
					if (toBeRemoved.Right.Left == null)
					{
						replacement = toBeRemoved.Right;
						replacement.Left = toBeRemoved.Left;
						temp = replacement;
					}
					else
					{
						replacement = toBeRemoved.Right.Left;
						while (replacement.Left != null)
						{
							replacement = replacement.Left;
						}
						replacementParent = replacement.Parent;
						replacementParent.Left = replacement.Right;

						temp = replacementParent;

						replacement.Left = toBeRemoved.Left;
						replacement.Right = toBeRemoved.Right;
					}
				}

				if (parent != null)
				{
					if (isLeftChild)
						parent.Left = replacement;
					else
						parent.Right = replacement;
				}
				else
				{
					SetRoot(replacement);
				}

				Rebalance(temp);
			}

			toBeRemoved.Parent = null;
			Count--;
			modifications++;
			return true;
		}

		#endregion

		#region Public methods

		public void AddRange(IEnumerable<TInterval> intervals)
		{
			if (intervals == null)
				throw new ArgumentNullException("intervals");
			foreach (var interval in intervals)
			{
				Add(interval);
			}
		}
		
		public TInterval[] this[TPoint point]
		{
			get
			{
				return FindAt(point);
			}
		}

		public TInterval[] FindAt(TPoint point)
		{
			if (ReferenceEquals(point, null))
				throw new ArgumentNullException("point");

			var found = new List<IntervalNode>();
			PerformStabbingQuery(root, point, found);
			return found.Select(node => node.Data).ToArray();
		}

		public bool ContainsPoint(TPoint point)
		{
			return FindAt(point).Any();
		}

		public bool ContainsOverlappingInterval(TInterval item)
		{
			if (ReferenceEquals(item, null))
				throw new ArgumentNullException("item");

			return PerformStabbingQuery(root, item).Count > 0;
		}

		public TInterval[] FindOverlapping(TInterval item)
		{
			if (ReferenceEquals(item, null))
				throw new ArgumentNullException("item");

			return PerformStabbingQuery(root, item).Select(node => node.Data).ToArray();
		}

		#endregion

		#region Private methods

		private void PerformCopy(int arrayIndex, int arrayLength, Action<int, TInterval> setAtIndexDelegate)
		{
			if (arrayIndex < 0)
				throw new ArgumentOutOfRangeException("arrayIndex");
			int i = arrayIndex;
			IEnumerator<TInterval> enumerator = GetEnumerator();
			while (enumerator.MoveNext())
			{
				if (i >= arrayLength)
					throw new ArgumentOutOfRangeException("arrayIndex", "Not enough elements in array to copy content into");
				setAtIndexDelegate(i, enumerator.Current);
				i++;
			}
		}

		private IEnumerable<IntervalNode> FindMatchingNodes(TInterval interval)
		{
			return PerformStabbingQuery(root, interval).Where(node => node.Data.Equals(interval));
		}

		private void SetRoot(IntervalNode node)
		{
			root = node;
			if (root != null)
				root.Parent = null;
		}

		private TPoint Start(TInterval interval)
		{
			return intervalSelector.GetStart(interval);
		}

		private TPoint End(TInterval interval)
		{
			return intervalSelector.GetEnd(interval);
		}

		private bool DoesIntervalContain(TInterval interval, TPoint point)
		{
			return point.CompareTo(Start(interval)) >= 0
				&& point.CompareTo(End(interval)) <= 0;
		}

		private bool DoIntervalsOverlap(TInterval interval, TInterval other)
		{
			return Start(interval).CompareTo(End(other)) <= 0 &&
				End(interval).CompareTo(Start(other)) >= 0;
		}

		private void PerformStabbingQuery(IntervalNode node, TPoint point, List<IntervalNode> result)
		{
			if (node == null)
				return;

			if (point.CompareTo(node.MaxEndPoint) > 0)
				return;

			if (node.Left != null)
				PerformStabbingQuery(node.Left, point, result);

			if (DoesIntervalContain(node.Data, point))
				result.Add(node);

			if (point.CompareTo(node.Start) < 0)
				return;

			if (node.Right != null)
				PerformStabbingQuery(node.Right, point, result);
		}

		private List<IntervalNode> PerformStabbingQuery(IntervalNode node, TInterval interval)
		{
			var result = new List<IntervalNode>();
			PerformStabbingQuery(node, interval, result);
			return result;
		}

		private void PerformStabbingQuery(IntervalNode node, TInterval interval, List<IntervalNode> result)
		{
			if (node == null)
				return;

			if (Start(interval).CompareTo(node.MaxEndPoint) > 0)
				return;

			if (node.Left != null)
				PerformStabbingQuery(node.Left, interval, result);

			if (DoIntervalsOverlap(node.Data, interval))
				result.Add(node);

			if (End(interval).CompareTo(node.Start) < 0)
				return;

			if (node.Right != null)
				PerformStabbingQuery(node.Right, interval, result);
		}

		private void Rebalance(IntervalNode node)
		{
			if (node.Balance > 1)
			{
				if (node.Left.Balance < 0)
					RotateLeft(node.Left);
				RotateRight(node);
			}
			else if (node.Balance < -1)
			{
				if (node.Right.Balance > 0)
					RotateRight(node.Right);
				RotateLeft(node);
			}
		}

		private void RotateLeft(IntervalNode node)
		{
			var parent = node.Parent;
			var isNodeLeftChild = node.IsLeftChild;

			// Make node.Right the new root of this sub tree (instead of node)
			var pivotNode = node.Right;
			node.Right = pivotNode.Left;
			pivotNode.Left = node;

			if (parent != null)
			{
				if (isNodeLeftChild)
					parent.Left = pivotNode;
				else
					parent.Right = pivotNode;
			}
			else
			{
				SetRoot(pivotNode);
			}
		}

		private void RotateRight(IntervalNode node)
		{
			var parent = node.Parent;
			var isNodeLeftChild = node.IsLeftChild;

			// Make node.Left the new root of this sub tree (instead of node)
			var pivotNode = node.Left;
			node.Left = pivotNode.Right;
			pivotNode.Right = node;

			if (parent != null)
			{
				if (isNodeLeftChild)
					parent.Left = pivotNode;
				else
					parent.Right = pivotNode;
			}
			else
			{
				SetRoot(pivotNode);
			}
		}

		#endregion

		#region Inner classes

		[Serializable]
		private class IntervalNode
		{
			private IntervalNode left;
			private IntervalNode right;
			public IntervalNode Parent { get; set; }
			public TPoint Start { get; private set; }
			private TPoint End { get; set; }
			public TInterval Data { get; private set; }
			private int Height { get; set; }
			public TPoint MaxEndPoint { get; private set; }

			public IntervalNode(TInterval data, TPoint start, TPoint end)
			{
				if(start.CompareTo(end) > 0)
					throw new ArgumentOutOfRangeException("end", "The suplied interval has an invalid range, where start is greater than end");
				Data = data;
				Start = start;
				End = end;
				UpdateMaxEndPoint();
			}

			public IntervalNode Left
			{
				get
				{
					return left;
				}
				set
				{
					left = value;
					if (left != null)
						left.Parent = this;
					UpdateHeight();
					UpdateMaxEndPoint();
				}
			}

			public IntervalNode Right
			{
				get
				{
					return right;
				}
				set
				{
					right = value;
					if (right != null)
						right.Parent = this;
					UpdateHeight();
					UpdateMaxEndPoint();
				}
			}

			public int Balance
			{
				get
				{
					if (Left != null && Right != null)
						return Left.Height - Right.Height;
					if (Left != null)
						return Left.Height + 1;
					if (Right != null)
						return -(Right.Height + 1);
					return 0;
				}
			}

			public bool IsLeftChild
			{
				get
				{
					return Parent != null && Parent.Left == this;
				}
			}

			public void UpdateHeight()
			{
				if (Left != null && Right != null)
					Height = Math.Max(Left.Height, Right.Height) + 1;
				else if (Left != null)
					Height = Left.Height + 1;
				else if (Right != null)
					Height = Right.Height + 1;
				else
					Height = 0;
			}

			private static TPoint Max(TPoint comp1, TPoint comp2)
			{
				if (comp1.CompareTo(comp2) > 0)
					return comp1;
				return comp2;
			}

			public void UpdateMaxEndPoint()
			{
				TPoint max = End;
				if (Left != null)
					max = Max(max, Left.MaxEndPoint);
				if (Right != null)
					max = Max(max, Right.MaxEndPoint);
				MaxEndPoint = max;
			}

			public override string ToString()
			{
				return string.Format("[{0},{1}], maxEnd={2}", Start, End, MaxEndPoint);
			}
		}

		private class IntervalTreeEnumerator : IEnumerator<TInterval>
		{
			private readonly ulong modificationsAtCreation;
			private readonly IntervalTree<TInterval, TPoint> tree;
			private readonly IntervalNode startNode;
			private IntervalNode current;
			private bool hasVisitedCurrent;
			private bool hasVisitedRight;

			public IntervalTreeEnumerator(IntervalTree<TInterval, TPoint> tree)
			{
				this.tree = tree;
				modificationsAtCreation = tree.modifications;
				startNode = GetLeftMostDescendantOrSelf(tree.root);
				Reset();
			}

			public TInterval Current
			{
				get
				{
					if (current == null)
						throw new InvalidOperationException("Enumeration has finished.");

					if (ReferenceEquals(current, startNode) && !hasVisitedCurrent)
						throw new InvalidOperationException("Enumeration has not started.");

					return current.Data;
				}
			}

			object IEnumerator.Current
			{
				get
				{
					return Current;
				}
			}

			public void Reset()
			{
				if (modificationsAtCreation != tree.modifications)
					throw new InvalidOperationException("Collection was modified.");
				current = startNode;
				hasVisitedCurrent = false;
				hasVisitedRight = false;
			}

			public bool MoveNext()
			{
				if (modificationsAtCreation != tree.modifications)
					throw new InvalidOperationException("Collection was modified.");

				if (tree.root == null)
					return false;

				// Visit this node
				if (!hasVisitedCurrent)
				{
					hasVisitedCurrent = true;
					return true;
				}

				// Go right, visit the right's left most descendant (or the right node itself)
				if (!hasVisitedRight && current.Right != null)
				{
					current = current.Right;
					MoveToLeftMostDescendant();
					hasVisitedCurrent = true;
					hasVisitedRight = false;
					return true;
				}

				// Move upward
				do
				{
					var wasVisitingFromLeft = current.IsLeftChild;
					current = current.Parent;
					if (wasVisitingFromLeft)
					{
						hasVisitedCurrent = false;
						hasVisitedRight = false;
						return MoveNext();
					}
				} while (current != null);

				return false;
			}

			private void MoveToLeftMostDescendant()
			{
				current = GetLeftMostDescendantOrSelf(current);
			}

			private IntervalNode GetLeftMostDescendantOrSelf(IntervalNode node)
			{
				if (node == null)
					return null;
				while (node.Left != null)
				{
					node = node.Left;
				}
				return node;
			}

			public void Dispose()
			{
			}
		}

		#endregion
	}

	/// <summary>
	/// Selects interval start and end points for an object of type <see cref="TInterval"/>.
	/// </summary>
	/// <typeparam name="TInterval">The type containing interval data</typeparam>
	/// <typeparam name="TPoint">The type of the interval start and end points</typeparam>
	/// <remarks>
	/// In order for the collection using these selectors to be XML serializable, your implementations of this interface must also be
	/// XML serializable (e.g. dont use delegates, and provide a default constructor).
	/// </remarks>
	public interface IIntervalSelector<in TInterval, out TPoint> where TPoint : IComparable<TPoint>
	{
		TPoint GetStart(TInterval item);
		TPoint GetEnd(TInterval item);
	}
}

Here is an example unit test:

[TestFixture]
public class ExampleTestFixture {
	
	[Test]
	public void FindAt_Overlapping ()
	{
		// ARRANGE
		var int1 = new TestInterval (20, 60);
		var int2 = new TestInterval (10, 50);
		var int3 = new TestInterval (40, 70);

		var intervalColl = new[] { 
			int1, int2, int3
		};
		var tree = new IntervalTree<TestInterval, int>(intervalColl, new TestIntervalSelector());

		// ACT
		var res1 = tree.FindAt (0);
		var res2 = tree.FindAt (10);
		var res3 = tree.FindAt (15);
		var res4 = tree.FindAt (20);
		var res5 = tree.FindAt (30);
		var res6 = tree.FindAt (40);
		var res7 = tree.FindAt (45);
		var res8 = tree.FindAt (50);
		var res9 = tree.FindAt (55);
		var res10 = tree.FindAt (60);
		var res11 = tree.FindAt (65);
		var res12 = tree.FindAt (70);
		var res13 = tree.FindAt (75);

		// ASSERT
		Assert.That (res1, Is.Empty);
		Assert.That (res2, Is.EquivalentTo(new[] { int2 }));
		Assert.That (res3, Is.EquivalentTo(new[] { int2 }));
		Assert.That (res4, Is.EquivalentTo(new[] { int1, int2 }));
		Assert.That (res5, Is.EquivalentTo(new[] { int1, int2 }));
		Assert.That (res6, Is.EquivalentTo(new[] { int1, int2, int3 }));
		Assert.That (res7, Is.EquivalentTo(new[] { int1, int2, int3 }));
		Assert.That (res8, Is.EquivalentTo(new[] { int1, int2, int3 }));
		Assert.That (res9, Is.EquivalentTo(new[] { int1, int3 }));
		Assert.That (res10, Is.EquivalentTo(new[] { int1, int3 }));
		Assert.That (res11, Is.EquivalentTo(new[] { int3 }));
		Assert.That (res12, Is.EquivalentTo(new[] { int3 }));
		Assert.That (res13, Is.Empty);
	}
}

[Serializable]
public class TestInterval 
{
	private TestInterval() {}

	public TestInterval(int low, int hi) 
	{
		if(low > hi)
			throw new ArgumentOutOfRangeException("lo higher the hi");
		Low = low;
		Hi = hi;
	}

	public int Low { get; private set; }
	public int Hi { get; private set; }
	public string MutableData { get; set; }

	public override string ToString ()
	{
		return string.Format ("[Low={0}, Hi={1}, Data={2}]", Low, Hi, MutableData);
	}
}

[Serializable]
public class TestIntervalSelector : IIntervalSelector<TestInterval, int>
{
	public int GetStart (TestInterval item) 
	{
		return item.Low;
	}

	public int GetEnd (TestInterval item) 
	{
		return item.Hi;
	}
}

Note: I have rigorously unit tested this.

PS: Sorry but I should have probably uploaded the code to a online source repo + tests (like github)… but I’m too lazy.

XML Serialization for interfaces in .NET

In your quest to find out how you can support XML serialization for types that contain interfaces, you may often find yourself coming to the same answer: you cannot serialize interfaces. That is true, but you can work around it, and I will present two methods.

Write you own Xml serialization code

Refer to : http://social.msdn.microsoft.com/Forums/en-US/bac96f79-82cd-4fef-a748-2a85370a8510/xmlserialization-with-interfaces?forum=asmxandxml

This post provides a nice answer to your woes. But you should watch out for a gotcha: 

strType = m_Child.GetType().FullName;

Instead you may want to use this in case your dependant interface implementations could come from an external assembly:

string strType = m_Child.GetType().AssemblyQualifiedName 
	?? m_Child.GetType().FullName;

Use generics with constraints

You can get away with not having to write your own serialization code by using generics. This isn’t a silver bullet as it will effect your class design, and may not make sense. Take this example:

public class MyClass 
{
	public IMyInterface MyProperty { get; set; }
}

You could rewrite this to become:

public class MyClass <T> where T : IMyInterface
{
	public T MyProperty { get; set; }
}

Of course this has several implications. For example, instantiating these types become more complicated and could lead to tricker wiring/construction problems.  Another point to make is the class itself doesn’t guarantee it is XML serializable: if the class is declared with type (T) of an interface (or a non-serializable class) then it won’t be XML serializable. But this should nothing to be surprized about, the .Net frameworks  XML serializable generic types also behave like this (e.g. List<T>).

Here is another example:

public class MyCollection
{
	public IList<IMyInterface> MyProperty { get; set; }
}

Generic XML serializable version (provided T is XML serializable):

public class MyCollection <T> where T : IMyInterface
{
	public IList<T> MyProperty { get; set; }
}

Programming Praxies – Finding Digit Strings In Powers Of Two

Today’s boredom lead me to solving another programming praxies problem:

Search every power of two below 210000 and return the index of the first power of two in which a target string appears. For instance, if the target is 42, the correct answer is 19 because 219 = 524288, in which the target 42 appears as the third and fourth digits, and no smaller power of two contains the string 42.

The naive solution is simple: keep doubling a number (starting at 1) until you find a sequence that matches the target. Of course once you get 2^64 storing the number as a primitive type will not suffice, where you would need to come up with a solution to store larger numbers.

I  improved on the naive approach by caching the number sequences for each exponent. For the cache I used a type of suffix tree:

private class SuffixTreeNode {
	public short MinExponent;
	public SuffixTreeNode[] Children;
}

Unlike your traditional suffix tree, this one does not compress string sequences. It’s really just a trie, where the number in each sequence is stored implicitly as the index in Children (i.e. these arrays are of length 10). However the data structure is populated and access like a suffix tree: where each suffix of a number sequence is inserted into the tree. Each node in the tree is annotated with the smallest exponent that the sequence can be found in.

Here is the full code:

public static class DigitStringPowerTwoSearch
{
	private static SuffixTreeNode suffixRoot;
	private static short currentExponent;
	private static List<int> currentDigits;

	static DigitStringPowerTwoSearch () {
		FlushCache ();
	}

	internal static void FlushCache() {
		// Exposed as internal really for unit tests only
		currentExponent = 0;
		currentDigits = new List<int> { 1 };
		suffixRoot = new SuffixTreeNode ();
		AddDigitsToTree (currentDigits, 0, 0);
	}

	public static int FindMinBaseTwoExponent(ulong target) {
		var targetDigits = ToDigitArray(target);
		while (currentExponent <= 10000) {
			short exponent = FindMinExponentInTree(targetDigits);
			if (exponent >= 0)
				return exponent;
			AddNextExponentToTree();
		}
		throw new ArgumentOutOfRangeException ("target", 
		                                       "target's digits do not exist in a base two number with exponent " +
		                                       "less or equal to 10,000");
	}

	private static void AddNextExponentToTree() {
		DoubleDigits (currentDigits);
		currentExponent++;

		for (int i = 0; i < currentDigits.Count; i++) {
			AddDigitsToTree (currentDigits, i, currentExponent);
		}
	}

	private static void AddDigitsToTree(IList<int> digits, int startIndex, short exponent) {
		SuffixTreeNode current = suffixRoot;
		for (int i = startIndex; i < digits.Count; i++) {
			int digit = digits [i];
			if (current.Children == null) {
				current.Children = new SuffixTreeNode[10];
			}
			if (current.Children [digit] == null) {
				var newNode = new SuffixTreeNode { MinExponent = exponent };
				current.Children [digit] = newNode;
				current = newNode;
			} else {
				current = current.Children [digit];
				// Here we assume exponent is always the largest exponent,
				// so no need to check/update current.MinExponent
			}
		}
	}

	private static short FindMinExponentInTree(int[] targetDigits) {
		SuffixTreeNode current = suffixRoot;
		foreach(var digit in targetDigits) {
			if (current == null || current.Children == null)
				return -1;
			current = current.Children[digit];
		}
		if (current == null)
			return -1;
		return current.MinExponent;
	}

	private static int[] ToDigitArray(ulong n) {
		if (n == 0) 
			return new int[] { 0 };

		var digits = new List<int>();

		for (; n != 0; n /= 10)
			digits.Add((int)(n % 10));

		var arr = digits.ToArray();
		Array.Reverse(arr);
		return arr;
	}

	private static void DoubleDigits(List<int> digits) {
		bool carry = false;
		for (int i = digits.Count - 1; i >= 0; i--) {
			int d = digits [i] * 2;
			if (carry)
				d++;
			if (d >= 10) {
				d -= 10;
				carry = true;
			} else {
				carry = false;
			}
			digits [i] = d;
		}
		if (carry)
			digits.Insert (0, 1);
	}

	private class SuffixTreeNode {
		public short MinExponent;
		public SuffixTreeNode[] Children;
	}
}

When the function is invoked, if a sequence of numbers have been seen before, then we get O(N) performance (where N = amount of digits in target). Effectively the cache becomes a hash-trie.

A reflection on code reflection: where it helps, and where it hinders.

Today at work I broke some of my team project’s unit tests from a seemingly harmless code change (C#). I simply changed a protected member into an auto-property. Unfortunately the code change was bundled with other changes, for which any other innocent coder would have thought be the changes to blame. But it was the small, innocent (almost code-cosmetic), change that was carried out using a click of the button with Resharper. The test blew up because there was an important piece of code (somewhere) that used reflection to search the class for non-public instance (visible to the class type) member variables and collate members that inherited a specific interface. What is this!? Some silent protocol?? How fragile!

Image

Reflection is a powerful tool that has blessed us with many awesome easy to use API’s. But clearly, it is not suitable to solve all problems. So when should we use reflection? And when should we avoid it? Here are a few common pros and cons that tend to crop up around the topic of reflection (this is not by all means a comprehensive list!):

Good reflection:)

  • Dependency injection frameworks.
    Reflection has given us killer IoC tools like Windsor and Unity to solve our dependency problems.
    Clearly refection is a key enabler in the technology, as dependencies and instaintiation is all achievable via binary metadata analysis.

  • Plugin frameworks.
    Plugins frameworks commonly use reflection to dynamically load 3rd party plugins, which it could not do so easily without dynamically loading the additional libraries via reflection.

Bad reflection😦

  • Refactoring tools and code analysis tools are incompatible.
    The opening example of this post shows that refactoring tools cannot cover what reflection can do: it can make your code brittle. It’s much better to be explicit with your code design; avoid establishing implicit protocols in your code base which your reflection code requires in order to work correctly. Note that static code analysis tools such as refactoring tools, or features like discovering method usage (e.g. with the reshaper tool) are rendered useless with code that uses reflection. This is a dangerous place to be.

  • Adds a super-generic layer of indirection.
    Indirection is a double edged sword: it can improve the design (and yield a number of benefits), but with the cost of adding complexity. The problem with reflection is that it adds a higher degree of indirection than non-reflective code, because it hides static detail such as class names, method names, and property names.  So heavy use of reflection makes the program near impossible to run through static code walk throughs. It also can be very difficult to debug. 
  • Run-time errors instead of compile-time errors.
    This argument can be used for all sorts of mechanisms (such as dynamic type-checking features), but it is a good point to make.  If you have the option of a design that doesn’t require reflection, at least you have a chance your compiler will complain if code changes have broken something. A design using reflection is subject to runtime errors, which in the worst case may not be detected until a release cycle (or in production!).
  • Invocation via reflection is much slower.
    Generally the performance hit from reflection is neglectable, but in sections of code where reflection is used heavily performance will degrade. Performance is much slower in reflection because during invocation the binaries metadata must be inspected at runtime (rather than being precompiled at compile time).

Conclusion

Avoid reflection.

If you think you need to solve a problem by reflection, rework the design (don’t be lazy!). Also don’t use reflection to get at protected data (e.g. non-public members), violating standard language conventions will get you into all sorts of trouble further down the line. Only use reflection where it is absolutely the only way to meet your needs. An acceptable place to use reflection is where there would be no way – at least without enforcing a difficult/cumbersome protocol to adhere to – to implement a solution. So be wary of the drawbacks of reflection before you get crazy with it, and always strive for a solid design!