Sorting Patches Topologically

PatchSorting.cs

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

public static class Program
{
	public static void Main()
	{
		// syntax is: patch,patch,patch
		// where patch is: LETTER PRIO BEFORE AFTER
		// format for patch: [A-Z] [-0+] (<[a-z]+) (>[a-z]+)
		Run("A0,B0,C0", "ABC");
		Run("A0>c,B0>c,C0", "CAB");
		Run("A-<c,B+<d,C-,D+,E0", "BDEAC");
		Run("A-,B+,C->a,D+>b,E0", "BDEAC");
		Run("A0>b,B0>c,C0>a", "cycle");
	}

	public static List<Patch> Sort(IEnumerable<Patch> patches)
	{
		SplitTypes(patches, out var deps, out var indeps);
		//Tools.Log("deps", deps);
		//Tools.Log("indeps", indeps);

		var result = new List<Patch>();
		while (deps.Any())
		{
			var tops = Top(deps).ToList();
			if (tops.Any() == false)
				return null;
			tops.Sort();
			var patch = tops.First();
			result.Add(patch);
			deps.Remove(patch);
		}
		var remaining = indeps.ToList();
		remaining.Sort();
		foreach (var indep in remaining)
		{
			var idx = result.FindLastIndex(patch => patch.CompareTo(indep) != 1);
			result.Insert(idx + 1, indep);
		}
		return result;
	}

	public static HashSet<Patch> Top(HashSet<Patch> nodes)
	{
		HashSet<Patch> result = new HashSet<Patch>(nodes);
		foreach (var node in nodes)
		{
			foreach (var name in node.before)
				result.Remove(Patch.Ref(nodes, name));
			if (nodes.Select(n => n.name).Intersect(node.after).Any())
				result.Remove(node);
		}
		return result;
	}

	public static void SplitTypes(IEnumerable<Patch> patches, out HashSet<Patch> deps, out HashSet<Patch> indeps)
	{
		deps = new HashSet<Patch>();
		indeps = new HashSet<Patch>();
		foreach (var p in patches)
		{
			if (p.before.Count + p.after.Count > 0)
				deps.Add(p);
			foreach (var name in p.before.Union(p.after))
				deps.Add(Patch.Ref(patches, name));
		}
		indeps = new HashSet<Patch>(patches.Except(deps));
	}

	//

	public static void Run(string patchStr, string expected = null)
	{
		var patches = GeneratePatches(patchStr);
		Console.WriteLine("# " + patchStr);
		var sorted = Program.Sort(patches);
		if (sorted == null)
		{
			var ok = expected == "cycle" ? "✅" : "❌";
			Console.WriteLine("-> cycle " + ok);
			Console.WriteLine();
			return;
		}
		var s = "";
		foreach (var patch in sorted)
			s += patch.name;
		Console.WriteLine("-> " + s);
		if (expected != null)
		{
			var ok = s == expected ? "✅" : "❌";
			Console.WriteLine($"-> {expected} {ok}");
		}
		Console.WriteLine();
	}

	static string prioStr = "-0+";
	public static List<Patch> GeneratePatches(string str)
	{
		var patches = new List<Patch>();
		foreach (var s in str.Replace(" ", "").Split(','))
		{
			var name = "" + s[0];
			var prio = prioStr.IndexOf(s[1]) - 1;
			var s2 = s.Substring(2);
			var before = new List<string>();
			if (s2.Length > 0 && s2[0] == '<')
			{
				s2 = s2.Substring(1);
				while (s2.Length > 0 && s2[0] != '>')
				{
					before.Add(("" + s2[0]).ToUpper());
					s2 = s2.Substring(1);
				}
			}
			var after = new List<string>();
			if (s2.Length > 0 && s2[0] == '>')
			{
				s2 = s2.Substring(1);
				while (s2.Length > 0)
				{
					after.Add(("" + s2[0]).ToUpper());
					s2 = s2.Substring(1);
				}
			}
			var patch = new Patch(patches.Count, name, prio);
			foreach (var p in before)
				patch.Before(p);
			foreach (var p in after)
				patch.After(p);
			patches.Add(patch);
		}
		return patches;
	}
}

public class Patch : IComparable<Patch>
{
	public string name;
	public int idx;
	public int prio;
	public List<string> before = new List<string>();
	public List<string> after = new List<string>();

	public Patch(int idx, string name, int prio)
	{
		this.name = name;
		this.idx = idx;
		this.prio = prio;
	}

	public Patch Before(string s)
	{
		before.Add(s);
		return this;
	}

	public Patch After(string s)
	{
		after.Add(s);
		return this;
	}

	public static Patch Ref(IEnumerable<Patch> patches, string name)
	{
		return patches.First(p => p.name == name);
	}

	public int CompareTo(Patch other)
	{
		var n1 = -prio * 100 + idx;
		var n2 = -other.prio * 100 + other.idx;
		return n1.CompareTo(n2);
	}

	public override string ToString()
	{
		return name;
	}
}

public static class Tools
{
	public static void Log(string msg, IEnumerable<Patch> patches)
	{
		var s = "";
		foreach (var patch in patches)
			s += patch.name;
		Console.WriteLine($"{msg}: {s}");
	}
}