C# Binary Search Tree

Hi Folks,

I thought I would post source code for a Binary Search Tree Algorithm that I recently worked on.

https://github.com/Romiko/Dev2

In a future post, I will post source code for a Balanced Binary Search Tree (Red Black Tree RBTree).

Remember with an unbalanced Binary Search Tree, if you insert data in order, it will actually resemble a linked list and not a binary tree, hence why it is important to use a Balanced Binary Search Tree.

Of course, you can use built in .NET framework types like SortedSet and SortedDictionary, but for those of you that want to write your own implementation, then this can be a good starting point.

Remember, the rules for a Binary Search Tree, which will also return data in a sorted order, using your IComparer implementation.

I also wrote a method to delete nodes from a Binary Search Tree, which will treats leaf nodes, nodes with one child and nodes with two children differently.

There is allot of articles out there on BST’s, but it is important, that if you want to understand them, that you must understand the rules governing the Insertion, Deletion and Retrieval algorithms.

You can find the source code, at my repository here:
https://github.com/Romiko/Dev2

You will notice that there is also numerous unit tests for the solution as well.

You will notice that the way I delete nodes, uses a Random dice, so not to Degenerate the Binary Tree, if it was balanced, this would not be necessary.

One more thing, I have avoided recursive functions, why? Well, with large binary trees, if you use recursive functions, the stack is going to run out of memory, so avoid them all together.

Here is some code snippets of important algorithms, if you have any questions, or want to contribute to the code, you are welcome to do so.


public void Add(TKey key, TValue value)
        {
            var newNode = new BinaryTreeNode { KeyValue = new KeyValuePair(key, value) };

            if (Root == null)
                Root = newNode;
            else
            {
                var current = Root;
                while (true)
                {
                    var compareResult = Comparer.Compare(key, current.KeyValue.Key);
                    if (compareResult == 0)
                        throw new ArgumentException("Duplicate key found.");

                    if (compareResult  0)
                        if (current.Right != null)
                            current = current.Right;
                        else
                        {
                            current.Right = newNode;
                            newNode.Parent = current;
                            break;
                        }
                }
            }
        }

private void Delete(BinaryTreeNode node)
        {
            var nodeType = GetNodeType(node);

            if (nodeType == NodeType.LeafeNode)
            {
                DeleteLeafNode(node);
                return;
            }
            if (nodeType == NodeType.HasOneChild)
            {
                DeleteNodeWithOneChild(node);
                return;
            }
            DeleteNodeWithTwoChildren(node);
        }

        private void DeleteNodeWithTwoChildren(BinaryTreeNode node)
        {
            // Use random delete method, to avoid degenerate tree structure.
            var replaceInOrderType = RollDiceForSuccessorOrPredecessor();

            if (replaceInOrderType == InOrderNode.Successor)
                UseSuccessor(node);
            else
                UsePredecessor(node);
        }

        private static void DeleteNodeWithOneChild(BinaryTreeNode node)
        {
            var theChild = node.Left ?? node.Right;
            theChild.Parent = node.Parent;
            switch (NodeLinkedToParentAs(node))
            {
                case NodeLinkToParentAs.Right:
                    node.Parent.Right = theChild;
                    break;
                case NodeLinkToParentAs.Left:
                    node.Parent.Left = theChild;
                    break;
                case NodeLinkToParentAs.Root:
                    node.Parent = null;
                    break;
            }
        }

        private static void DeleteLeafNode(BinaryTreeNode node)
        {
            if (NodeLinkedToParentAs(node) == NodeLinkToParentAs.Right)
                node.Parent.Right = null;
            else
                node.Parent.Left = null;
        }

        private void UsePredecessor(BinaryTreeNode node)
        {
            var replaceWith = ReadLastRightNode(node.Left);
            node.KeyValue = replaceWith.KeyValue;
            Delete(replaceWith);
        }

        private void UseSuccessor(BinaryTreeNode node)
        {
            var replaceWith = ReadLastLeftNode(node.Right);
            node.KeyValue = replaceWith.KeyValue;
            Delete(replaceWith);
        }

        private InOrderNode RollDiceForSuccessorOrPredecessor()
        {
            if (ForceDeleteType.HasValue)
                return ForceDeleteType.Value;

            var random = new Random();
            var choice = random.Next(0, 2);
            return choice == 0 ? InOrderNode.Predecessor : InOrderNode.Successor;
        }

https://github.com/Romiko/Dev2

Learning Field Guiding in Southern Africa

Hi!

I have been spending the last 2 and half months living in the bush between Selati and Karongwe game reserve in Southern Africa, within the Limpopo province.

I am currently studying my FGASA level 1 with Ecotraining

We have been working on Tracking, Navigation, Survival, 4×4 Drives and learning loads about Mammals, Big 5, Insects, Trees and much more!

I was very privileged to encounter a Cheetah on foot, and here are some pictures that I would love to share with you.

Ecotraining is an awesome training provider, and the quality of training is superb, everyday, we go on drives and walks. This week, we have ben walking in the bush with a rifle for 4 hours in the morning and 4 hours in the afternoon, carrying a rifle as well, to learn rifle handling techniques and safety.

Typical day is:

  • Wake up at 4am
  • Coffee and a rusk
  • 5am Walk
  • 10:30am Breakfast
  • Theory
  • Exercise (Gay Time Gym)
  • Lunch
  • Afternoon walk/drive
  • Campfire and chilling
  • Get lucky with elephants next to your tent at night!

It can be very easy to over eat in the bush and exercise is a must. I started a gym group called Gay Time gym, where we do Yoga, sit-ups, pushups and many other core exercises. We also play ultimate Frisbee to keep fit as a fiddle!

It is awesome taking time out to live a simple and rewarding life style out in the bush.

I have produced a Game called Ranger Rom. You can download it for Tablet and Phone on both Android and Apple. Please download and have a play, it will teach you about wildlife.

Google Play

Apple Store

I will be off to Botswana for December, and hope to get some awesome experiences out there. Until then, Succulent Karoo!

selati

MG 7068

MG 7100

MG 7156

MG 7289

MG 7317

MG 7467

MG 7490

MG 7854

MG 7821

MG 7819

MG 7781

MG 7648

IMG 8262

IMG 8502

IMG 8571

IMG 8609

Off to Africa – a life long dream

Hi Everyone!

It has been a while since I last posted any cool technical articles and so on. Well I am off to Africa!

I was surfing in Indonesia in April this year and that is when the penny dropped for me.

Romiko surfing indonesia

I realised that:

We make a Living
by what we Get
We make a Life
by what we Give

This was my answer. I realised that, I need to follow my passions, and it is possible to work and live life, in harmony!

This is where Ranger Rom was born.

Romiko thinking about Ranger Rom

I love technology. I take pride in the work that I believe in. Ranger Rom is proof of this. It uses state of the art technology from Amazon EC2, S3, CloudFront, Ruby On Rails, ImageMagick, Jekyll and all sort of cool stuff that could take 10 blogs to write on, seriously! Since working on Ranger Rom, I enjoy developing products, because it enriches peoples lives, but most of all, it’s fun.

I realised that I had a choice in life, and now is the time for change. Now is the time to step out from the sheep, pull the wool over the eyes of the wolf; and make a stab at something new and creative.

I might fail, I might fall hard, but at least I will have no regrets when I am 113 years of age, sitting on my bed, going – I wish I did that when I was young.

I encourage you all to live simple, keep the luxuries in life low. A lower carbon footprint and more money to go travel. You do not need to work 9 to 5, year in and year out. You can make a CHANGE and still WORK. You can do the same job but only for half the year, instead of the entire year. There is a will, there is a way!

But this has now changed, and I encourage you all to follow my New Adventures, but more important to follow your dreams and your heart. Today I have posted the first chapter, and yes, it is based on a true story. I am going to the bush for a long time. In between breaks, I will be doing crazy things to, like Paragliding from Mozambique to Madagascar and surfing enormous waves. However, my primary goal is to give back to nature. There will be breaks in between, to earn an income, but ultimately my goals is a balance between my career and what I do outside of it. I believe I can do both a 50/50 split.

Below is Ranger Rom’s first news report to read, so please feel free to join the world of Ranger Rom!

Ranger Rom – Off to Africa

Romiko and Ranger Rom in nature

Ranger Rom is all about promoting wildlife awareness by creating cool games for kids and adults to play. Scheduled for release on the IPhone and Android at the end of this month! IPad and Tablets will soon follow over the next couple of months.

Short Film, Roger”

It has been two weeks since we filmed “Roger”. This has been a truly inspiring experience and the professionalism demonstrated by everyone at The Central Coast Screen Co-op, check their website Central Coast Screen Co-Op

It was the first time I have done a film and found it challenging especially when playing the lead role. The first day went really well and I was impressed by the commitment and professional of the entire crew.

The first day of filming was at the house where Roger’s mother lived, Roger is picking up his childhood pet Parrot and exchanging some banter with his girlfriend Mandy. We also then shot the end of the film which involved driving a car and swerving off the side of the road. I was damn nervous not to swerve to much and slam the breaks to late and then plough into 20 crew members! So thanks guys for trusting me not to mow you all down!

The second day was all done within the car in front of a green screen. It was very exciting and a new experience as you really had to visualise and use your imagination whilst being cooped up inside a garage with 30 crew members trying their best to get the best shots. This I found the most challenging aspect for acting, here we had to create our own external stimuli.

The start of day 2 was a tad slow, until about lunch time when everything started to flow more nicely, however it was a challenge to keep emotions at bay, especially when you want to perform at your best and you know you can do better.

I have definitely learnt allot from the experience and had an amazing time with everyone from the crew. It felt like I had gone an a holiday and had a short term affair with someone special.

Here are some pictures from the day, and would like to thank all those involved on such a great weekend together.

 

Keep your eyes posted here and hopefully in coming months “Roger” will be ready to watch!

Of course, always good to have the crew list at the end Smile

Writer and Concept

John Blackhawk

Writer

Al Brooks

Producer

Robert Doyle

Director

Graeme Mitchell

DoP/Camera Op

Brendan Palmer

1st Assitant Director

Mark Ferris

1st Assistant Camera

Max Gersbach

2st Assistant Camera

Kate Cornish

Sound Recordist

Peter Henskens

Boom Operator

Terry Wunsch

Gaffer/Grip

Daniel Grey

Prod Designer

Ty Batterham

Standby Props

Daniel Mitchell

Make‐up

Samantha Thompson

Script Supervisor

Liesl Bamback

Data Wrangler

Katey Freyburg

Unit Manager

Nathan Dalton

Bird Wrangler

Kylie Cooke

Stills Photographer

Stefan Sroczynsk

Production Assistant

Christopher Kaye

Production Assistant

John Blackhawk

Production Assistant

Al Brooks

Catering Assistant

Ryan Montgomery

Catering Assistant

Kellie

Roger

Romiko Derbynew

Mandy

Cathy Burnside

Polly (V/O)

Cathy Burnside

Samantha (V/O)

Meg Macintosh

Patricia (V/O)

Gianna Pattison

Blue One (V/O)

John Blackhawk

Blue Three (V/O)

Al Brooks

Editor

Katey Freyburg

Assistant Editor

Christopher Kaye

Assistant Editor

Mark Ferris

CGI Effects Artist

Alex Burgess

Composer

Jenny Harkin

Creativity

The sight of all these people in uniforms does not prime creativity

(Kahneman, D. (2011). Thinking Fast and Slow, Allen Lane 2011 -  Noble Prize 2002 Economic Sciences).

Let’s rethink our culture so that our society can express themselves in a constructive manner and live a more fulfilling life during work hours. To promote conformity and to stifle expression is one of the intrinsic causes of our societies rebellious sub cultures.

So what do suites, ties and school uniforms do for us?  Another social “Etiquette” that hides the true intention of an individual, What are your thoughts?

First Cross Country milestone–Paragliding

It was Friday afternoon and Jamal and I checked out the charts for the weather and the conditions were looking good! We headed off to Manilla Paragliding in NSW at 4am on Saturday. I have been itching to fly after only being back at work for 3 days, all I can think of is to fly!

I took off form Mount Borah West and the wind was strong, whilst soaring the ridge I got parked and felt very uncomfortable, used a little speed bar to get out ahead and then did some figure of eights to gain height and turn and burn over the mountain to avoid rotor winds and turbulence on the lee side of the mountain.

Once I got over the mountain, it was all about looking at the ground for some trigger points where thermals would be released.

When I finally could see Barraba, it dawned on me that I have made my first real cross country flight and the feeling I had inside was fantastic, it is hard to describe, perhaps some form of euphoria!

I met some awesome pilots and some crazy pilots whilst away on the Christmas season, and learnt as much as I can about the art of flying, there is so much to learn and I am looking forward to learning as much as I can.

Paragliding has opened up a new avenue where you can be at the mercy of natures wrath and meet amazing people who are just as crazy!

Here is the flight path and data, just like life, it has it’s up’s and downs! Sunday, was not as great, but still a lovely flight, the conditions were very thermic on Sunday and stable, bombed out in the north west and had a long walk back for 4 hours in 45 degree heat, lesson learned? Carry lots of water and have a back up plan if you need a pick up!

Barogram

image

Data

image

Map

image

Well, that’s it, if you would like to try out something new and exciting and challenge yourself mentally, then Paragliding is definitely worth a try!

Manilla Paragliding

I would highly recommend going to Manilla Paragliding, cool people and an awesome teacher. Check out http://www.flymanilla.com/

Into the sun

Cheers

Tears Before Bedtime–Directed and Written by Malcolm Frawley

Just finished a play that we performed at Sydney Theatre School. It is written and directed by Malcolm Frawley. It went really well, and it is an excellent play with all sorts of characters from Grannies discussing sex when they were younger, two crazy writers trying write a play while having an affair and some hysterical comical characters discussing their future relationship after Blake fell in love with a tall, blonde and voluptuous women on a Ski Trip.

There are some sad and serious moments in the play to where most scenes are about revealing secrets, some shameful and shocking.

The play is interesting in that you are watching a play within a play, and you get a feeling that it is being done on the fly.

Photo Album contains:

  • Scene from a family gathering in the lounge, just before Christmas, a typical couple (MUM and DAD) having an argument, whilst a mischievous before is looking at the presence and wondering what is inside of them.
  • One of the old ladies Jennifer having a discussion with close friends (Beverly and Elizabeth) who is revealing, yet another secret.
  • Dennis discussing his sexual fantasies and stories of love.
  • A discussion about Trust between Paige and Claire
  • Meg reminiscing about here “Perfect” boyfriend Silas

Written and Directed by Malcolm Frawley
CAST: Dahna Cicco, Romiko Derbynew, Tom Dickson, Marcella Franco, Felicity Davey, Heidi Stewart, Camilla Turnbull, Brian Tyo, Matthew Vautin, Sophie Else, Malinda Hayward, Kate Rutherford, Emma Warner Collins

You can download the full play script here:

Performance royalties by negotiation – contact author via malfraw@hotmail.com

https://www.dropbox.com/s/31rdvyxz9ogv9qu/Tears%20Before%20Bedtime%20FINAL.docx?m

Summary

A very enjoyable play to perform and be part of, and received very good reviews from the Audience, moments of laughter, sadness and uncertainty. The scene with Lilly and Blake is absolutely comical and hilarious.

Windows Azure Cloud Drive–Dealing with large VHD’s and Blob Snapshot Restores

I ran into a scenario where I needed to transfer data from an Azure Cloud Drive VHD that was 250GB in Size from Production to Preproduction. So this means that I want to transfer the VHD from one azure account to another.

The thing with VHD’s and Cloud Drive, is that it is a Page Blob, and the VHD has to be a fixed size, so even though I might have 200MB of data in a 250GB VHD, you would need to download 250GB worth of data.

The Solution?

Remove desktop into the Azure Virtual Machine, Mount the VHD Manually, copy the data, zip it up and send it through other means, so in essence, I only send or download the data that is USED in the VHD i.e. 200MB and not 250GB.

This utility can use the concept of a blobsnapshot VHD backup to restore, and what it will do it mount it. This is ideal when you using blob snapshots as a backup mechanism and you need a way to restore the blob snapshot VHD data, as fast as possible to another Azure Account.

Below is the code for the helper and you can download the source code for the project here:

NOTE: This application must be run in a Windows Azure Virtual Machine, it will NOT WORK on a development machine/emulator.

hg clone ssh://hg@bitbucket.org/romiko/mountclouddrive
hg clone https://romiko@bitbucket.org/romiko/mountclouddrive

using System;
using Microsoft.WindowsAzure;
using Microsoft.WindowsAzure.StorageClient;
using MountCloudDrive.Properties;

namespace MountCloudDrive
{
    public class CloudDriveHotAssistant
    {
        private string restoreVHDName;
        private readonly StorageCredentialsAccountAndKey storageCredentials;
        private readonly CloudStorageAccount cloudStorageAccount;
        private CloudBlobClient blobClient;

        public CloudDriveHotAssistant(string accountName, string accountKey)
        {
            restoreVHDName = Settings.Default.DefaultRestoreDestination;
            storageCredentials = new StorageCredentialsAccountAndKey(accountName, accountKey);
            cloudStorageAccount = new CloudStorageAccount(storageCredentials, false);
            blobClient = new CloudBlobClient(cloudStorageAccount.BlobEndpoint, storageCredentials);
        }

        public CloudPageBlob GetBlobToRestore(string blobContainer, string blobFileName)
        {
            DateTime snapShotTime;
            var converted = DateTime.TryParse(Settings.Default.BlobSnapShotTime, out snapShotTime);

            CloudPageBlob pageBlob;

            if (converted)
                pageBlob = blobClient.GetPageBlobReference(string.Format(@"{0}\{1}", blobContainer, blobFileName), snapShotTime);
            else
                pageBlob = blobClient.GetPageBlobReference(string.Format(@"{0}\{1}", blobContainer, blobFileName));

            try
            {
                pageBlob.FetchAttributes();
            }
            catch (Exception ex)
            {
                Console.WriteLine("\r\nBlob Does Not Exist!");
                Console.WriteLine(ex);
                return null;
            }
            return pageBlob;
        }

        public void UnMountCurrentDrives()
        {
            foreach (var driveName in CloudDrive.GetMountedDrives())
            {
                var drive = new CloudDrive(driveName.Value, storageCredentials);
                Console.WriteLine(string.Format("\r\nUnmounting {0}", driveName.Key));
                Console.WriteLine("\r\nAre you sure Y/N");
                var key = Console.ReadKey();
                var decision = key.Key == ConsoleKey.Y;

                if (!decision)
                    continue;

                try
                {
                    drive.Unmount();
                }
                catch (Exception ex)
                {
                    Console.WriteLine(string.Format("\r\nUnmounting {0} FAILED.\r\n {1}", driveName.Key, ex));
                }
            }
        }

        public CloudPageBlob GetBlobReferenceToRestoreTo(string blobContainer)
        {
            return blobClient.GetPageBlobReference(string.Format(@"{0}\{1}", blobContainer, restoreVHDName));
        }

        public void MountCloudDrive(CloudPageBlob pageBlobSource, CloudPageBlob pageBlobDestination, string blobContainer)
        {
            pageBlobDestination.CopyFromBlob(pageBlobSource);
            Console.WriteLine(string.Format("\r\nAttempting to mount {0}", pageBlobDestination.Uri.AbsoluteUri));
            var myDrive = cloudStorageAccount.CreateCloudDrive(pageBlobDestination.Uri.AbsoluteUri);
            var drivePath = myDrive.Mount(0, DriveMountOptions.None);
            Console.WriteLine(string.Format("\r\nVHD mounted at {0}", drivePath));
        }
    }
}

Automate #WindowsAzure snapshot restores

Hi,
This is the last series in blog posts regarding the automation of backups, purging and restoring azure blobs.

Below is a PowerShell script that can take a file containing the contents of snapshot urls, it also supports the log file output from the backup restore script and just pasting that output in the event you want to restore a complete backup set.

Remember, when using the backup script, ALWAYS save the output of the script to use as a reference so that you have the URL’s of the snapshots you want to restore.

e.g. Sample restore.txt file.
[05:01:08]: [Publishing internal artifacts] Sending build.start.properties.gz file
[05:01:05]: Step 1/2: Command Line (14s)
[05:01:05]: [Step 1/2] in directory: C:\TeamCity\buildAgent\work\d9375448b88c1b75\Maintenance
[05:01:08]: [Step 1/2] Starting snapshot uniqueids
[05:01:08]: [Step 1/2] Found blob container uniqueids
[05:01:09]: [Step 1/2] https://uatmystory.blob.core.windows.net/uniqueids/agencies?snapshot=2012-04-22
[05:01:09]: [Step 1/2] T19:01:10.6488549Z
[05:01:09]: [Step 1/2] https://uatmystory.blob.core.windows.net/uniqueids/agency1-centres?snapshot=201
[05:01:09]: [Step 1/2] 2-04-22T19:01:10.8818083Z
[05:01:09]: [Step 1/2] https://uatmystory.blob.core.windows.net/uniqueids/agency1-clients?snapshot=201
[05:01:09]: [Step 1/2] 2-04-22T19:01:11.0257795Z
[05:01:09]: [Step 1/2] https://uatmystory.blob.core.windows.net/uniqueids/agency1-referrals?snapshot=2
[05:01:09]: [Step 1/2] 012-04-22T19:01:11.1717503Z

So the script will parse any restore file and just find URI’s in it, and then restore them.

#requires -version 2.0
param (
	[parameter(Mandatory=$true)] [string]$AzureAccountName,
	[parameter(Mandatory=$true)] [string]$AzureAccountKey,
	[parameter(Mandatory=$true)] [string]$FileContainingSnapshotAddresses
)

$ErrorActionPreference = "Stop"

if ((Get-PSSnapin -Registered -Name AzureManagementCmdletsSnapIn -ErrorAction SilentlyContinue) -eq $null)
{
	throw "AzureManagementCmdletsSnapIn missing. Install them from Https://www.cerebrata.com/Products/AzureManagementCmdlets/Download.aspx"
}

Add-PSSnapin AzureManagementCmdletsSnapIn -ErrorAction SilentlyContinue
Add-Type -Path 'C:\Program Files\Windows Azure SDK\v1.6\ref\Microsoft.WindowsAzure.StorageClient.dll'

$cred = New-Object Microsoft.WindowsAzure.StorageCredentialsAccountAndKey($AzureAccountName,$AzureAccountKey)
$client = New-Object Microsoft.WindowsAzure.StorageClient
.CloudBlobClient("https://$AzureAccountName.blob.core.windows.net",$cred)

function RestoreSnapshot
{
	param ( $snapShotUri)
	Write-Host "Parsing snapshot restore for $SnapShotUri"

	$regex = new-object System.Text.RegularExpressions.Regex("http://.*?/(devstoreaccount1/)?(?<containerName>.*?)/.*")
	$match = $regex.Match($snapShotUri)
	$container = $match.Groups["containerName"].Value
	$parsedUri = $match
	
	if($match.Value -eq "")
	{
		return
	}
		
	if ($container -eq $null)
	{
		Write-Host  "Container $blobContainerName doesn't exist, skipping snapshot restore"
	}
	else
	{
		Write-Host  "Restoring $snapShotUri" 
		Copy-Blob -BlobUrl $parsedUri -AccountName $AzureAccountName -AccountKey $AzureAccountKey -TargetBlobContainerName $container
		Write-Host  "Restore snapshot complete for $parsedUri"
	}
}

$fileContent = Get-Content $FileContainingSnapshotAddresses

foreach($uri in $fileContent)
{
	RestoreSnapshot $uri
}


Cloning Disks and Partitions

I have been using CloneZilla to manage all my disk and partition backups, I find it very user friendly and support all my disks (USB, ESATA). I recommend TUXBOOT for making Clonezilla bootable USB drive and to keep it with you whenever you need to clone a disk, then just boot off the stick.

http://clonezilla.org/liveusb.php

Windows 7 bootable USB stick

On the subject, sometimes you need to get an OS on beforehand for Windows, I like using this tool to make a bootable windows 7 USB stick.

http://images2.store.microsoft.com/prod/clustera/framework/w7udt/1.0/en-us/Windows7-USB-DVD-tool.exe