Pattern Tree

Dimension.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Patterns
{
    /// <summary>
    /// Represents an array dimension.
    /// </summary>
    struct Dimension
    {
        /// <summary>
        /// Gets the width of the array dimension.
        /// </summary>
        /// <value>
        /// The width.
        /// </value>
        public int Width { get; private set; }
        /// <summary>
        /// Gets the height of the array dimension.
        /// </summary>
        /// <value>
        /// The height.
        /// </value>
        public int Height { get; private set; }

        /// <summary>
        /// Initializes a new instance of the <see cref="Dimension"/> struct.
        /// </summary>
        public Dimension(int width, int height)
            : this()
        {
#if CONTRACTS
            if (Width < 0)
                throw new ArgumentOutOfRangeException("width");
            if (Height < 0)
                throw new ArgumentOutOfRangeException("height");
#endif
            Width = width;
            Height = height;
        }

        /// <summary>
        /// Returns a <see cref="System.String"/> that represents this instance.
        /// </summary>
        /// <returns>
        /// A <see cref="System.String"/> that represents this instance.
        /// </returns>
        public override string ToString()
        {
            return string.Concat("{", Width, ", ", Height, "}");
        }
    }

    /// <summary>
    /// Represents an equality comparer for <see cref="Dimension"/> structures.
    /// </summary>
    sealed class DimensionEqualityComparer : IEqualityComparer<Dimension>
    {
        /// <summary>
        /// Gets the default comparer.
        /// </summary>
        public static readonly IEqualityComparer<Dimension> Default = new DimensionEqualityComparer();

        /// <summary>
        /// Prevents a default instance of the <see cref="DimensionEqualityComparer"/> class from being created.
        /// </summary>
        private DimensionEqualityComparer() { }

        /// <summary>
        /// Determines whether the specified objects are equal.
        /// </summary>
        /// <param name="x">The first object of type <paramref name="T"/> to compare.</param>
        /// <param name="y">The second object of type <paramref name="T"/> to compare.</param>
        /// <returns>
        /// true if the specified objects are equal; otherwise, false.
        /// </returns>
        public bool Equals(Dimension x, Dimension y)
        {
            return x.Width == y.Width && x.Height == y.Height;
        }

        /// <summary>
        /// Returns a hash code for this instance.
        /// </summary>
        /// <param name="obj">The obj.</param>
        /// <returns>
        /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table. 
        /// </returns>
        /// <exception cref="T:System.ArgumentNullException">The type of <paramref name="obj"/> is a reference type and <paramref name="obj"/> is null.</exception>
        public int GetHashCode(Dimension obj)
        {
            var hc = (uint)obj.Width;
            hc = hc << 3 | hc >> (29); // Rotate.
            hc ^= (uint)obj.Height;
            return (int)hc;
        }
    }
}

ItemType.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Patterns
{
    /// <summary>
    /// Represents the different item types.
    /// </summary>
    public enum ItemType
    {
        /// <summary>
        /// A blank cell.
        /// </summary>
        Nothing = 0,
        /// <summary>
        /// A wood item.
        /// </summary>
        Wood = 1,
        /// <summary>
        /// A flint item.
        /// </summary>
        Flint = 2,
        /// <summary>
        /// A torch item.
        /// </summary>
        Torch = 3,
        /// <summary>
        /// A wooden wall.
        /// </summary>
        WoodWall = 4,
        /// <summary>
        /// A torch fence.
        /// </summary>
        TorchFence = 5
    }

    // In case you decide to use a dictionary in PatternNode.
    /// <summary>
    /// Represents an equality comparer for <see cref="ItemType"/> enums.
    /// </summary>
    public sealed class ItemTypeComparer : IEqualityComparer<ItemType>
    {
        /// <summary>
        /// Gets the default comparer.
        /// </summary>
        public static readonly ItemTypeComparer Default = new ItemTypeComparer();

        /// <summary>
        /// Prevents a default instance of the <see cref="ItemTypeComparer"/> class from being created.
        /// </summary>
        private ItemTypeComparer() { }

        /// <summary>
        /// Determines whether the specified objects are equal.
        /// </summary>
        /// <param name="x">The first object of type <paramref name="T"/> to compare.</param>
        /// <param name="y">The second object of type <paramref name="T"/> to compare.</param>
        /// <returns>
        /// true if the specified objects are equal; otherwise, false.
        /// </returns>
        public bool Equals(ItemType x, ItemType y)
        {
            return x == y;
        }

        /// <summary>
        /// Returns a hash code for this instance.
        /// </summary>
        /// <param name="obj">The obj.</param>
        /// <returns>
        /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table. 
        /// </returns>
        /// <exception cref="T:System.ArgumentNullException">The type of <paramref name="obj"/> is a reference type and <paramref name="obj"/> is null.</exception>
        public int GetHashCode(ItemType obj)
        {
            return (int)obj;
        }
    }
}

PatternNode.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Patterns
{
    /// <summary>
    /// Represents a pattern node
    /// </summary>
    class PatternNode
    {
        private Dictionary<Dimension, ItemType> _terminators = new Dictionary<Dimension, ItemType>(DimensionEqualityComparer.Default);
        // You may want to flip this to a dictionary instead - depending on how many items you have.
        private PatternNode[] _nodes;
        private static readonly int _nodesCount;

        static PatternNode()
        {
            var max = 0;
            foreach (int val in Enum.GetValues(typeof(ItemType)))
            {
                max = Math.Max(max, val);
            }
            _nodesCount = max + 1;
        }

        /// <summary>
        /// Gets the <see cref="Patterns.PatternNode"/> with the specified item type.
        /// </summary>
        public PatternNode this[ItemType next]
        {
            get
            {
                if (_nodes == null)
                    return null;
                return _nodes[(int)next];
            }
        }

        /// <summary>
        /// Gets or sets the <see cref="Patterns.ItemType"/> with the specified dimension.
        /// </summary>
        public ItemType this[Dimension dimension]
        {
            get
            {
                ItemType result;
                if (!_terminators.TryGetValue(dimension, out result))
                    return ItemType.Nothing;
                return result;
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="PatternNode"/> class.
        /// </summary>
        public PatternNode()
        {
        }

        /// <summary>
        /// Adds the specified terminator.
        /// </summary>
        /// <param name="dimension">The dimension.</param>
        /// <param name="next">Type of the item.</param>
        public void Add(Dimension dimension, ItemType itemType)
        {
            _terminators.Add(dimension, itemType);
        }

        /// <summary>
        /// Creates or gets a node for the specified item type.
        /// </summary>
        /// <param name="next">The next item type.</param>
        public PatternNode Add(ItemType next)
        {
            // Definitely not thread safe.
            var nodes = _nodes ?? (_nodes = new PatternNode[_nodesCount]);
            return _nodes[(int)next] ?? (_nodes[(int)next] = new PatternNode());
        }
    }
}

PatternTree.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Patterns
{
    /// <summary>
    /// Represents a tree of patterns.
    /// </summary>
    public class PatternTree
    {
        private PatternNode _root;

        /// <summary>
        /// Gets the <see cref="Patterns.ItemType"/> with the specified pattern.
        /// </summary>
        public ItemType this[ItemType[,] pattern]
        {
            get
            {
                return Search(pattern);
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="PatternTree"/> class.
        /// </summary>
        public PatternTree()
        {
            _root = new PatternNode();
        }

        /// <summary>
        /// Adds the specified pattern to the tree.
        /// </summary>
        /// <param name="pattern">The pattern for the recipe.</param>
        /// <param name="result">The result of the recipe.</param>
        public void Add(ItemType[,] pattern, ItemType result)
        {
#if CONTRACTS
            if (pattern == null)
                throw new ArgumentNullException("pattern");
#endif
            var height = pattern.GetUpperBound(0) + 1;
            var width = pattern.GetUpperBound(1) + 1;
            var current = _root;
            for (var y = 0; y < height; y++)
            {
                for (var x = 0; x < width; x++)
                {
                    current = current.Add(pattern[y, x]);
                }
            }

            current.Add(new Dimension(width, height), result);
        }

        private ItemType Search(ItemType[,] pattern)
        {
#if CONTRACTS
            if (pattern == null)
                throw new ArgumentNullException("pattern");
#endif
            var width = pattern.GetUpperBound(0) + 1;
            var height = pattern.GetUpperBound(1) + 1;

            var right = 0;
            var bottom = 0;
            var top = width;
            var left = height;

            // Search for the first non-empty cells.
            for (var y = 0; y < width; y++)
            {
                for (var x = 0; x < height; x++)
                {
                    if (pattern[y, x] != ItemType.Nothing)
                    {
                        left = Math.Min(left, x);
                        top = Math.Min(top, y);
                        right = Math.Max(right, x);
                        bottom = Math.Max(bottom, y);
                    }
                }
            }


            // Now find the item.
            var current = _root;
            for (var y = top; y <= bottom; y++)
            {
                for (var x = left; x <= right; x++)
                {
                    current = current[pattern[y, x]];
                    if (current == null)
                        return ItemType.Nothing;
                }
            }
            
            return current[new Dimension(right - left + 1, bottom - top + 1)];
        }
    }
}

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Patterns
{
    class Program
    {
        static void Main(string[] args)
        {
            var pt = new PatternTree();

            // Register types.
            pt.Add(new ItemType[2, 1]
            {
                { ItemType.Flint },
                { ItemType.Wood }
            }, ItemType.Torch);

            pt.Add(new ItemType[1, 3]
            {
                { ItemType.Torch , ItemType.Torch, ItemType.Torch }
            }, ItemType.TorchFence);

            pt.Add(new ItemType[3, 3]
            {
                { ItemType.Wood , ItemType.Wood, ItemType.Wood },
                { ItemType.Wood , ItemType.Wood, ItemType.Wood },
                { ItemType.Wood , ItemType.Wood, ItemType.Wood }
            }, ItemType.WoodWall);

            // Test it out
            Console.WriteLine(pt[new ItemType[3, 3]
            {
                {ItemType.Nothing, ItemType.Nothing, ItemType.Flint },
                {ItemType.Nothing, ItemType.Nothing, ItemType.Wood },
                {ItemType.Nothing, ItemType.Nothing, ItemType.Nothing },
            }]);
            Console.WriteLine(pt[new ItemType[3, 3]
            {
                {ItemType.Nothing, ItemType.Nothing, ItemType.Nothing },
                {ItemType.Nothing, ItemType.Nothing, ItemType.Flint },
                {ItemType.Nothing, ItemType.Nothing, ItemType.Wood },
            }]);
            Console.WriteLine(pt[new ItemType[3, 3]
            {
                {ItemType.Torch, ItemType.Torch, ItemType.Torch },
                {ItemType.Nothing, ItemType.Nothing, ItemType.Nothing },
                {ItemType.Nothing, ItemType.Nothing, ItemType.Nothing },
            }]);
            Console.WriteLine(pt[new ItemType[3, 3]
            {
                { ItemType.Wood , ItemType.Wood, ItemType.Wood },
                { ItemType.Wood , ItemType.Wood, ItemType.Wood },
                { ItemType.Wood , ItemType.Wood, ItemType.Wood }
            }]);
            Console.WriteLine(pt[new ItemType[3, 3]
            {
                { ItemType.Wood , ItemType.Wood, ItemType.Nothing },
                { ItemType.Wood , ItemType.Wood, ItemType.Wood },
                { ItemType.Wood , ItemType.Wood, ItemType.Wood }
            }]);

            Console.ReadLine();
        }
    }
}

Output:

Torch
Torch
TorchFence
WoodWall
Nothing