Sorting dependencies using DependencyList

DependencyList.cs

    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Linq;

    /// <summary>
    /// Represents a list whose items can be dependant on each other, and enumerating the list will sort the items
    /// as per their dependency requirements.
    /// </summary>
    /// <typeparam name="TModel">The model in the list.</typeparam>
    /// <typeparam name="TKey">The identifier type.</typeparam>
    public class DependencyList<TModel, TKey> : IList<TModel> where TKey : IEquatable<TKey>
    {
        #region Fields
        private readonly Func<TModel, IEnumerable<TKey>> _dependencyFunc;
        private readonly Func<TModel, TKey> _identifierFunc;
        private readonly List<DependencyListNode<TModel, TKey>> _nodes;

        private bool _modified;
        private List<TModel> _lastSort;
        #endregion

        #region Constructor
        /// <summary>
        /// Initialises a new instance of <see cref="DependencyList{TModel,TKey}"/>.
        /// </summary>
        /// <param name="identifierFunc">A delegate used to get the identifier for an item.</param>
        /// <param name="dependencyFunc">A delegate used to get dependencies for an item.</param>
        public DependencyList(Func<TModel, TKey> identifierFunc, Func<TModel, IEnumerable<TKey>> dependencyFunc)
        {
            if (identifierFunc == null)
                throw new ArgumentNullException("identifierFunc");
            if (dependencyFunc == null)
                throw new ArgumentNullException("dependencyFunc");

            _identifierFunc = identifierFunc;
            _dependencyFunc = dependencyFunc;

            _nodes = new List<DependencyListNode<TModel, TKey>>();
        }
        #endregion

        #region Properties
        /// <summary>
        /// Gets a count of the number of items in the list.
        /// </summary>
        public int Count { get { return _nodes.Count; } }

        /// <summary>
        /// Gets whether the list is read-only.
        /// </summary>
        public bool IsReadOnly { get { return false; } }
        #endregion

        #region Methods
        /// <summary>
        /// Adds a new item to the list.
        /// </summary>
        /// <param name="item">The item to add to the list.</param>
        public void Add(TModel item)
        {
            var identifier = _identifierFunc(item);
            var node = new DependencyListNode<TModel, TKey>(item, identifier);

            if (item is INotifyPropertyChanged)
                ((INotifyPropertyChanged)item).PropertyChanged += (s, e) => { _modified = true; };

            _nodes.Add(node);
            _modified = true;
        }

        /// <summary>
        /// Adds any dependencies required by the specified node.
        /// </summary>
        /// <param name="node">The node to add dependencies to.</param>
        private void AddDependencies(DependencyListNode<TModel, TKey> node)
        {
            // Get the dependencies from the source item.
            var dependencies = _dependencyFunc(node.Item);
            node.Dependencies.Clear();

            // No dependencies were found, leave early.
            if (dependencies == null)
                return;

            foreach (var dependency in dependencies)
            {
                // Get the dependency
                var d = dependency;

                // Attempt to locate the dependency within the source collection.
                var dependentNode = _nodes
                    .Where(n => n.Identifier.Equals(d))
                    .FirstOrDefault();

                if (dependentNode == null)
                    // Dependency has not been added to the source collection - missing dependency.
                    throw new InvalidOperationException(string.Format("Missing dependency with id '{0}'", d));

                node.Dependencies.Add(dependentNode);
            }
        }

        /// <summary>
        /// Clears the list.
        /// </summary>
        public void Clear()
        {
            _nodes.Clear();
            _modified = true;
        }

        /// <summary>
        /// Determines if the list contains the specified item.
        /// </summary>
        /// <param name="item">The item to find.</param>
        /// <returns>True if the list contains the item, otherwise false.</returns>
        public bool Contains(TModel item)
        {
            return _nodes.Any(n => n.Item.Equals(item));
        }

        /// <summary>
        /// Copies the items to the specified array.
        /// </summary>
        /// <param name="array">The target array.</param>
        /// <param name="index">The index at which to start copying.</param>
        public void CopyTo(TModel[] array, int index)
        {
            var items = Sort();

            items.CopyTo(array, index);
        }

        /// <summary>
        /// Applies the specified action to each item in the list.
        /// </summary>
        /// <param name="action"></param>
        public void ForEach(Action<TModel> action)
        {
            foreach (TModel model in Sort())
                action(model);
        }

        /// <summary>
        /// Gets an enumerator for enumerating over items in the list.
        /// </summary>
        /// <returns>An enumerator for enumerating over items in the list.</returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// Gets an enumerator for enumerating over items in the list.
        /// </summary>
        /// <returns>An enumerator for enumerating over items in the list.</returns>
        public IEnumerator<TModel> GetEnumerator()
        {
            var list = Sort();
            return list.GetEnumerator();
        }

        /// <summary>
        /// Gets the index of the specified item in the list.
        /// </summary>
        /// <param name="item">The item to find.</param>
        /// <returns>The index of the item in the list.</returns>
        public int IndexOf(TModel item)
        {
            var list = Sort();
            return list.IndexOf(item);
        }

        /// <summary>
        /// Inserts an item into the collection.  This operation is not supported.
        /// </summary>
        /// <param name="index">The index at which to insert the item.</param>
        /// <param name="item">The item to insert.</param>
        public void Insert(int index, TModel item)
        {
            throw new NotSupportedException();
        }

        /// <summary>
        /// Removes an item from the list.
        /// </summary>
        /// <param name="item">The item to remove.</param>
        /// <returns>True if the item was removed, otherwise false.</returns>
        public bool Remove(TModel item)
        {
            var node = _nodes.Where(n => n.Item.Equals(item)).FirstOrDefault();
            if (node == null)
                return false;

            _modified = true;
            return _nodes.Remove(node);
        }

        /// <summary>
        /// Removes the item at the specified index. This operation is not supported.
        /// </summary>
        /// <param name="index">The index of the item to remove.</param>
        public void RemoveAt(int index)
        {
            // We don't support manually removing nodes this way as we cannot
            // guarantee it will not break the sort.
            throw new InvalidOperationException();
        }

        /// <summary>
        /// Returns the sorted collection of items.
        /// </summary>
        /// <returns>The sorted collection of items.</returns>
        internal List<TModel> Sort()
        {
            if (_modified || _lastSort == null)
                _lastSort = SortInternal();

            return _lastSort;
        }

        /// <summary>
        /// Returns the sorted collection of items.
        /// </summary>
        /// <returns>The sorted collection of items.</returns>
        private List<TModel> SortInternal()
        {
            // Create the sorting instance.
            var sort = new TopologicalSort<TKey>();

            foreach (var node in _nodes)
            {
                // Add dependencies for every node in the collection.
                AddDependencies(node);

                if (node.Dependencies.Count == 0)
                {
                    // No dependencies, add the current node.
                    sort.Edge(node.Identifier);
                }
                else
                {
                    foreach (var dependency in node.Dependencies)
                        // Has dependency, add both the current node and it's dependency
                        sort.Edge(node.Identifier, dependency.Identifier);
                }
            }

            // Attempt the sort.
            var result = sort.TrySort();
            if (result.Item1)
            {
                // Set the collection as unmodified
                _modified = false;

                // Return the values represented by the sorted keys.
                return result.Item2
                    .Select(k => _nodes
                        .Single(n => n.Identifier.Equals(k)).Item)
                    .ToList();
            }

            // Cyclic dependency has occurred.
            throw result.Item3;
        }

        /// <summary>
        /// Gets or sets the item at the specified index. Set operations are not supported.
        /// </summary>
        /// <param name="index">The index of the item.</param>
        /// <returns>The instance at the specified index.</returns>
        public TModel this[int index]
        {
            get { return Sort()[index]; }
            set
            {
                // We do not support manual set operations on the collection as we do not know the
                // dependencies the new value may require.
                throw new NotSupportedException();
            }
        }
        #endregion
    }

DependencyListNode.cs

    using System.Collections.Generic;

    /// <summary>
    /// Represents a node within a dependency list.
    /// </summary>
    /// <typeparam name="TModel">The model in the list.</typeparam>
    /// <typeparam name="TKey">The identifier type.</typeparam>
    internal class DependencyListNode<TModel, TKey>
    {
        #region Constructor
        /// <summary>
        /// Initialises a new instance of <see cref="DependencyListNode{TModel,TKey}"/>
        /// </summary>
        /// <param name="item">The item.</param>
        /// <param name="identifier">The identifier of the item.</param>
        public DependencyListNode(TModel item, TKey identifier)
        {
            Item = item;
            Identifier = identifier;

            Dependencies = new List<DependencyListNode<TModel, TKey>>();
        }
        #endregion

        #region Properties
        /// <summary>
        /// Gets the list of dependencies.
        /// </summary>
        public List<DependencyListNode<TModel, TKey>> Dependencies { get; private set; }

        /// <summary>
        /// Gets or sets the identifier.
        /// </summary>
        public TKey Identifier { get; set; }

        /// <summary>
        /// Gets or sets the model instance.
        /// </summary>
        public TModel Item { get; set; }

        /// <summary>
        /// Gets the root item.
        /// </summary>
        public DependencyListNode<TModel, TKey> Root { get; set; }

        /// <summary>
        /// Gets or sets whether this item has been visited.
        /// </summary>
        public bool Visited { get; set; }
        #endregion
    }

Program.cs

    namespace ConsoleApplication3
    {
        class Program
        {
            static void Main(string[] args)
            {
                var container = new CompositionContainer(new AssemblyCatalog(typeof(Program).Assembly));

                var manager = container.GetExportedValue<PipelineManager>();
                var pipeline = manager.BuildPipeline("bbcode");

                var context = new PipelineContext("Hello World");

                foreach (var plugin in pipeline)
                    plugin.Process(context);

                Console.Write(context.Content);
                Console.ReadKey();
            }
        }

        [Export]
        public class PipelineManager
        {
            [ImportMany]
            public IEnumerable<Lazy<IPipelinePlugin, IPipelinePluginMetadata>> Plugins { get; set; }

            public Queue<IPipelinePlugin> BuildPipeline(string name)
            {
                // Get the plugins.
                var plugins = Plugins
                    .Where(p => p.Metadata.Pipelines == null || p.Metadata.Pipelines.Contains(name)).ToList();
                
                // Create our dependency list.
                var dependencyList = new DependencyList<Lazy<IPipelinePlugin, IPipelinePluginMetadata>, string>(
                    l => l.Metadata.Name,
                    l => l.Metadata.Dependencies);

                // Add each available plugin to the list.
                plugins.ForEach(dependencyList.Add);

                // Create our pipeline.
                var pipeline = new Queue<IPipelinePlugin>();

                // Now, when we enumerate over it, it will be sorted.
                dependencyList.ForEach(p => pipeline.Enqueue(p.Value));

                return pipeline;
            }
        }

        public class PipelineContext
        {
            public PipelineContext(string content)
            {
                if (string.IsNullOrWhiteSpace(content))
                    throw new ArgumentException("No content for pipeline context.", "content");

                Content = content;
            }

            public string Content { get; set; }
        }

        public interface IPipelinePlugin
        {
            void Process(PipelineContext context);
        }

        public interface IPipelinePluginMetadata
        {
            string Name { get; }
            string[] Dependencies { get; }
            string[] Pipelines { get; }
        }

        public abstract class PipelinePluginBase : IPipelinePlugin
        {
            public virtual void Process(PipelineContext context)
            {
                
            }
        }

        [Pipeline("ApplyColour", Dependencies = new[] { "MakeItalic" }, Pipelines = new[] { "bbcode" })]
        public class ApplyColourPipelinePlugin : PipelinePluginBase
        {
            public override void Process(PipelineContext context)
            {
                context.Content = "[color=f00]" + context.Content + "[/color]";
            }
        }

        [Pipeline("MakeBold", Pipelines = new[] { "bbcode" })]
        public class MakeBoldPipelinePlugin : PipelinePluginBase
        {
            public override void Process(PipelineContext context)
            {
                context.Content = "[b]" + context.Content + "[/b]";
            }
        }

        [Pipeline("MakeItalic", Dependencies = new[] { "MakeBold" }, Pipelines = new[] { "bbcode" })]
        public class MakeItalicAfterBoldPipelinePlugin : PipelinePluginBase
        {
            public override void Process(PipelineContext context)
            {
                context.Content = "[i]" + context.Content + "[/i]";
            }
        }

        [MetadataAttribute]
        [AttributeUsage(AttributeTargets.Class | AttributeTargets.Property | AttributeTargets.Method, AllowMultiple = false)]
        public class PipelineAttribute : ExportAttribute, IPipelinePluginMetadata
        {
            public PipelineAttribute(string name)
                : base(typeof(IPipelinePlugin))
            {
                if (string.IsNullOrWhiteSpace(name))
                    throw new ArgumentException("A pipeline plugin requires a name.", "name");

                Name = name;
            }

            public string Name { get; private set; }
            public string[] Dependencies { get; set; }
            public string[] Pipelines { get; set; }
        }
    }

TopologicalSort.cs

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

    /// <summary>
    /// Defines a topological sort.
    /// </summary>
    /// <typeparam name="T">The model type.</typeparam>
    public class TopologicalSort<T> where T : IEquatable<T>
    {
        #region Fields
        private readonly IDictionary<T, Node> _nodes = new Dictionary<T, Node>();
        #endregion

        #region Methods
        /// <summary>
        /// Builds an exception with cycle information.
        /// </summary>
        private InvalidOperationException BuildException()
        {
            return new InvalidOperationException(
                string.Format("A cyclic dependency has been detected for item with key '{0}'", _nodes.Keys.First()));
        }

        /// <summary>
        /// Adds a node to the edge of the graph.
        /// </summary>
        /// <param name="key">The node key.</param>
        /// <returns>True if the node was added, otherwise false.</returns>
        public bool Edge(T key)
        {
            if (key == null)
                return false;

            if (!_nodes.ContainsKey(key))
                _nodes.Add(key, new Node());

            return true;
        }

        /// <summary>
        /// Adds a node to the edge of the graph which depends on a predecessor.
        /// </summary>
        /// <param name="successor"></param>
        /// <param name="predecessor"></param>
        /// <returns></returns>
        public bool Edge(T successor, T predecessor)
        {
            // Add both nodes.
            if (!Edge(successor)) return false;
            if (!Edge(predecessor)) return false;

            // If we have a direct cycle - fail fast.
            if (successor.Equals(predecessor)) return false;

            // Get the list of current successors for the predecessor.
            var successorsOfPredecessors = _nodes[predecessor].Successors;

            // Make sure we only add it the once.
            if (!successorsOfPredecessors.Contains(successor))
            {
                // Add the successor to the predecessor.
                successorsOfPredecessors.Add(successor);

                // Increment the predecessor count.
                _nodes[successor].PredecessorCount++;
            }

            return true;
        }

        /// <summary>
        /// Attempts to sort.
        /// </summary>
        /// <returns>True </returns>
        public Tuple<bool, Queue<T>, Exception> TrySort()
        {
            var result = new Queue<T>();
            var work = new Queue<T>();

            // Get the edge nodes and add it to the working queue.
            foreach (var pair in _nodes)
                if (pair.Value.PredecessorCount == 0)
                    work.Enqueue(pair.Key);


            while (work.Count != 0)
            {
                // Get the key.
                T key = work.Dequeue();

                // Queue it in the result.
                result.Enqueue(key);

                // Get the node.
                var node = _nodes[key];

                // Remove the node from the collection.
                _nodes.Remove(key);

                foreach (T successor in node.Successors)
                    if (--_nodes[successor].PredecessorCount == 0)
                        // Add any additional edges to the work queue.
                        work.Enqueue(successor);

                // Clear the successors.
                node.Successors.Clear();
            }

            // We cleared all the nodes.
            if (_nodes.Count == 0)
                // Return the result.
                return Tuple.Create(true, result, (Exception)null);

            return Tuple.Create(false, (Queue<T>)null, (Exception)BuildException());
        }
        #endregion

        #region Types
        /// <summary>
        /// Defines a node in the graph.
        /// </summary>
        private class Node
        {
            #region Constructor
            /// <summary>
            /// Initialises a new instance of <see cref="Node"/>.
            /// </summary>
            public Node()
            {
                Successors = new List<T>();
            }
            #endregion

            #region Properties
            /// <summary>
            /// Gets or sets the count of predecessors.
            /// </summary>
            public int PredecessorCount { get; set; }

            /// <summary>
            /// Gets the list of successors.
            /// </summary>
            public List<T> Successors { get; private set; }
            #endregion
        }
        #endregion
    }