Skip to content

Instantly share code, notes, and snippets.

@archer884
Created February 16, 2018 17:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save archer884/12deb1dcff9c804263c653d5ff007554 to your computer and use it in GitHub Desktop.
Save archer884/12deb1dcff9c804263c653d5ff007554 to your computer and use it in GitHub Desktop.
Internal iteration in C#
using System;
using System.Collections;
using System.Collections.Generic;
namespace Scratch
{
class Program
{
class Node<T>
where T : IComparable<T>
{
public T Item { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public Node(T item)
{
Item = item;
}
public void Append(T item)
{
if (item.CompareTo(Item) < 0)
{
if (Left == null)
{
Left = new Node<T>(item);
}
else
{
Left.Append(item);
}
}
else
{
if (Right == null)
{
Right = new Node<T>(item);
}
else
{
Right.Append(item);
}
}
}
}
public class Tree<T> : IEnumerable<T>
where T : IComparable<T>
{
Node<T> _root;
public void Add(T item)
{
if (_root == null)
{
_root = new Node<T>(item);
}
else
{
_root.Append(item);
}
}
public IEnumerator<T> GetEnumerator()
{
foreach (var item in YieldNode(_root))
yield return item;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
private IEnumerable<T> YieldNode(Node<T> node)
{
if (node == null)
yield break;
foreach (var item in YieldNode(node.Left))
yield return item;
yield return node.Item;
foreach (var item in YieldNode(node.Right))
yield return item;
}
public void ForEach(Action<T> action)
{
ApplyToNode(_root, action);
}
private void ApplyToNode(Node<T> node, Action<T> action)
{
if (node == null)
return;
ApplyToNode(node.Left, action);
action(node.Item);
ApplyToNode(node.Right, action);
}
public void ForEach(Func<T, bool> f)
{
ApplyToNode(_root, f);
}
private void ApplyToNode(Node<T> node, Func<T, bool> f)
{
if (node == null)
return;
ApplyToNode(node.Left, f);
if (!f(node.Item))
return;
ApplyToNode(node.Right, f);
}
}
static void Main()
{
var rng = new Random(13);
var tree = new Tree<int>();
Console.WriteLine("Insert at random:");
for (var i = 0; i < 10; i++)
{
var item = rng.Next(20);
Console.WriteLine(item);
tree.Add(item);
}
Console.WriteLine("Print in order:");
tree.ForEach(item => Console.WriteLine(item));
Console.WriteLine("Early return:");
tree.ForEach(item =>
{
if (item > 5)
{
return false;
}
Console.WriteLine(item);
return true;
});
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment