Horrible code bruteforcing the combinatorial Hirsch Conjectu

#define GenerateFamilies
#define Switch
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HirschBruteforcer
{
    public static class Program
    {
        public const int N = 6;
        public const int D = 3;
        public const int F = 2;
        public static List<Subset> AllSubsets;
        public static void Main(string[] args)
        {
            Stopwatch watch = Stopwatch.StartNew();
            AllSubsets = Subset.AllSubsets(Program.N, Program.D);

            //BreadthFirstHirsch.BreadthFirstHirschSearch();
            //DepthFirstHirsch.DepthFirstHirschSearch();
            FasterDepthFirstHirsch.FasterDepthFirstHirschSearch();

            watch.Stop();
            Console.WriteLine("Time taken: " + watch.Elapsed);
            while (true) { }
        }
    }
    public static class FasterDepthFirstHirsch
    {
        private static object theLock = new object();
        private static int maxT = 0;
        private static IntervalCompressedHirschSequence best = null;
        private static object counterLock = new object();
        private static int delayer = 0;
        private static int currentCounter = 0;
        private static int totalCounter = 0;
        public static void FasterDepthFirstHirschSearch()
        {
            Subset first = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags.Count(b => b) == 1).First();
            Subset second = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags[1] && s.Flags.Count(b => b) == 2).First();
            Subset third = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags.Count(b => b) == 1).First();
            Subset fourth = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2] && s.Flags.Count(b => b) == 2).First();
            IntervalCompressedHirschSequence root = new IntervalCompressedHirschSequence(first, third, fourth);
            IntervalCompressedHirschSequence root2 = new IntervalCompressedHirschSequence(root, new List<Subset>() { second }, second.Flags);
            List<IntervalCompressedHirschSequence> currentSet = new List<IntervalCompressedHirschSequence>();
            root2.TestCompatible(Program.AllSubsets);
            IntervalCompressedHirschSequenceSet cache = new IntervalCompressedHirschSequenceSet();
            root2.GenerateNewSets(currentSet, cache, 3);
            foreach (IntervalCompressedHirschSequence chs in currentSet)
            {
                todoList.Push(new ParallelData()
                {
                    currentSequence = chs,
                    t = 4
                });
            }
            currentCounter = currentSet.Count;
            totalCounter = currentSet.Count;
            Console.WriteLine("Initial generation done, for a total of " + totalCounter);
            While(() =>
            {
                lock (todoList)
                {
                    return todoList.Any();
                }
            }, () =>
            {
                ParallelData data;
                lock (todoList)
                {
                    if (todoList.Any())
                    {
                        data = todoList.Pop();
                    }
                    else
                    {
                        return;
                    }
                }
                DepthFirstHirschSearchRec(data.currentSequence, data.t, cache, third, fourth);
            });
            Console.WriteLine("Done, best t found was " + maxT);
#if GenerateFamilies
            Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
#endif
        }
        private struct ParallelData
        {
            public IntervalCompressedHirschSequence currentSequence;
            public int t;
        }
        private static Stack<ParallelData> todoList = new Stack<ParallelData>();
        private static IEnumerable<bool> IterateUntilFalse(Func<bool> condition)
        {
            while (condition()) yield return true;
        }
        public static void While(Func<bool> condition, Action body)
        {
            Parallel.ForEach(IterateUntilFalse(condition), new ParallelOptions()
                {
                    MaxDegreeOfParallelism = 7
                },
                ignored => body());
        }
        private static void DepthFirstHirschSearchRec(IntervalCompressedHirschSequence currentSequence, int t, IntervalCompressedHirschSequenceSet cache, Subset third, Subset fourth)
        {
            List<IntervalCompressedHirschSequence> newSet = new List<IntervalCompressedHirschSequence>();
            currentSequence.TestCompatible(Program.AllSubsets);
            currentSequence.GenerateNewSets(newSet, cache, t);
            if (newSet.Count > 0)
            {
                if ((t + 2) > maxT)
                {
                    lock (theLock)
                    {
                        if ((t + 2) > maxT)
                        {
                            Console.WriteLine("New record at " + (t + 2));
                            maxT = (t + 2);
                            best = newSet[0];
#if GenerateFamilies
                            Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
#endif
                        }
                    }
                }
                lock (todoList)
                {
                    foreach (IntervalCompressedHirschSequence chs in newSet)
                    {
                        todoList.Push(new ParallelData()
                        {
                            currentSequence = chs,
                            t = t + 1
                        });
                    }
                }
            }
            if (t == 4)
            {
                lock (counterLock)
                {
                    currentCounter--;
                    delayer++;
                    if (delayer >= 1)
                    {
                        Console.WriteLine(currentCounter + "/" + totalCounter);
                        delayer = 0;
                    }
                }
            }
        }
    }
    public class IntervalCompressedHirschSequence
    {
#if GenerateFamilies
        private IntervalCompressedHirschSequence previous;
#endif
        public const int NotUsedYet = 0;
        public const int Forbidden = 1;
        public const int Active = 2;
        public int[] SetStatus;
        public List<Subset> LastFamily;
        private bool[] UnionSubset;
        bool usedNminus1th;
        bool usedNminus2th;
        bool usedNminus12th;
        public IntervalCompressedHirschSequence(Subset lastFamily, params Subset[] forbiddenSets)
        {
            LastFamily = new List<Subset>();
            LastFamily.Add(lastFamily);
            SetStatus = new int[Program.AllSubsets.Count];
            UnionSubset = lastFamily.Flags;
            SetStatus[lastFamily.Index] = Active;
            foreach (Subset s in forbiddenSets)
            {
                SetStatus[s.Index] = Forbidden;
            }
#if GenerateFamilies
            this.previous = null;
#endif
        }
        public IntervalCompressedHirschSequence(IntervalCompressedHirschSequence intervalCompressedHirschSequence, List<Subset> newFamily, bool[] unionSubset)
        {
            usedNminus1th = intervalCompressedHirschSequence.usedNminus1th || newFamily.Any(s => s.Flags[Program.N - 1]);
            usedNminus2th = intervalCompressedHirschSequence.usedNminus2th || newFamily.Any(s => s.Flags[Program.N - 2]);
            usedNminus12th = intervalCompressedHirschSequence.usedNminus12th || newFamily.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]);
            LastFamily = new List<Subset>(newFamily);
            SetStatus = (int[])intervalCompressedHirschSequence.SetStatus.Clone();
            for (int i = 0; i < SetStatus.Length; i++)
            {
                switch (SetStatus[i])
                {
                    case NotUsedYet:
                        // Forbid B if there exists A with A subseteq B and (A subseteq (some old active set C)) and not (A subseteq (some new active set D))
                        // Equivalent to:
                        // Forbid B if there exists an old active set C such that for no new active set D, B intersect C subseteq D
                        Subset B = Program.AllSubsets[i];
                        if (intervalCompressedHirschSequence.LastFamily.Any(C => !newFamily.Any(D => Subset.IntersectionIsSubsetOf(B, C, D))))
                        {
                            SetStatus[i] = Forbidden;
                        }
                        break;
                    case Forbidden:
                        break;
                    case Active:
                        SetStatus[i] = Forbidden;
                        break;
                    default:
                        break;
                }
            }
            foreach (Subset s in newFamily)
            {
                SetStatus[s.Index] = Active;
            }
            UnionSubset = unionSubset;
#if GenerateFamilies
            this.previous = intervalCompressedHirschSequence;
#endif
        }
        private List<Subset> compatibleSubsets = new List<Subset>();
        public void TestCompatible(IEnumerable<Subset> allSubsets)
        {
            compatibleSubsets.AddRange(allSubsets.Where(s => IsCompatible(s)));
        }
        public bool IsCompatible(Subset S)
        {
            return SetStatus[S.Index] == NotUsedYet;
        }
        public void GenerateNewSets(List<IntervalCompressedHirschSequence> currentSet, IntervalCompressedHirschSequenceSet cache, int t)
        {
            if (usedNminus1th
                &&
                !compatibleSubsets.Any(s => s.Flags[Program.N - 1]))
            {
                return;
            }
            if (usedNminus2th
                &&
                !compatibleSubsets.Any(s => s.Flags[Program.N - 2]))
            {
                return;
            }
            if (usedNminus12th
                &&
                !compatibleSubsets.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]))
            {
                return;
            }
            List<Subset> newFamily = new List<Subset>();
            GenerateNewSetsRec(0, newFamily, currentSet, t, cache, false, false, false);
        }
        private void GenerateNewSetsRec(int start, List<Subset> newFamily, List<IntervalCompressedHirschSequence> currentSet, int t, IntervalCompressedHirschSequenceSet cache, bool gotNminus1th, bool gotNminus2th, bool gotNminus12th)
        {
            if (start == compatibleSubsets.Count)
            {
                if ((newFamily.Count > 0)
                    &&
                    (newFamily.Count <= Program.F)
                    &&
                    (!usedNminus1th || gotNminus1th)
                    &&
                    (!usedNminus2th || gotNminus2th)
                    &&
                    (!usedNminus12th || gotNminus12th))
                {
                    bool[] unionSubset = (bool[])UnionSubset.Clone();
                    newFamily.ForEach(s =>
                    {
                        for (int i = 0; i < s.Flags.Length; i++)
                        {
                            unionSubset[i] |= s.Flags[i];
                        }
                    });
                    if (Subset.IsAscending(unionSubset))
                    {
                        cache.GenerateIfNew(this, newFamily, unionSubset, currentSet, t);
                    }
                }
            }
            else
            {
                GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);

                if (newFamily.All(s => !s.ContainsSubset(compatibleSubsets[start])
                                       &&
                                       !s.IsContainedBySuperset(compatibleSubsets[start])))
                {
                    if (compatibleSubsets[start].Flags[Program.N - 1])
                    {
                        gotNminus1th = true;
                    }
                    if (compatibleSubsets[start].Flags[Program.N - 2])
                    {
                        gotNminus2th = true;
                    }
                    if (compatibleSubsets[start].Flags[Program.N - 1] && compatibleSubsets[start].Flags[Program.N - 2])
                    {
                        gotNminus12th = true;
                    }
                    newFamily.Add(compatibleSubsets[start]);
                    GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);
                    newFamily.RemoveAt(newFamily.Count - 1);
                }
            }
        }
        public IntervalCompressedHirschSequence Wrap(params Subset[] rest)
        {
            IntervalCompressedHirschSequence current = this;

            for (int i = 0; i < rest.Length; i++)
            {
                current = new IntervalCompressedHirschSequence(current, new List<Subset>() { rest[i] }, null);
            }

            return current;
        }
#if GenerateFamilies
        public string GenerateFamily()
        {
            StringBuilder b = new StringBuilder();

            GenerateFamilies(b);

            return b.ToString();
        }
        private void GenerateFamilies(StringBuilder b)
        {
            if (previous != null)
            {
                previous.GenerateFamilies(b);
                b.Append(" ");
            }
            GenerateFamily(b);
        }
        private void GenerateFamily(StringBuilder b)
        {
            b.Append("{");
            for (int i = 0; i < LastFamily.Count - 1; i++)
            {
                LastFamily[i].ToString(b);
                b.Append(",");
            }
            LastFamily[LastFamily.Count - 1].ToString(b);
            b.Append("}");
        }
#endif
    }
    public class IntervalCompressedHirschSequenceSet
    {
        private class Node<T>
        {
            public Node<T>[] lookup1;
            public Node<T>[] lookup2;
            public T value;
            public Node<T> Retrieve1(int p)
            {
                if (lookup1 == null)
                {
                    lock (this)
                    {
                        if (lookup1 == null)
                        {
                            lookup1 = new Node<T>[Program.AllSubsets.Count];
                        }
                    }
                }
                if (lookup1[p] == null)
                {
                    lock (lookup1)
                    {
                        if (lookup1[p] == null)
                        {
                            lookup1[p] = new Node<T>();
                        }
                    }
                }
                return lookup1[p];
            }
            public Node<T> Retrieve2(int p)
            {
                if (lookup2 == null)
                {
                    lock (this)
                    {
                        if (lookup2 == null)
                        {
                            lookup2 = new Node<T>[Program.AllSubsets.Count];
                        }
                    }
                }
                if (lookup2[p] == null)
                {
                    lock (lookup2)
                    {
                        if (lookup2[p] == null)
                        {
                            lookup2[p] = new Node<T>();
                        }
                    }
                }
                return lookup2[p];
            }
        }
        Node<int> root = new Node<int>();
        public void GenerateIfNew(IntervalCompressedHirschSequence compressedHirschSequence, List<Subset> newFamily, bool[] unionSubset, List<IntervalCompressedHirschSequence> currentSet, int t)
        {
            IntervalCompressedHirschSequence newHirschSequence = new IntervalCompressedHirschSequence(compressedHirschSequence, newFamily, unionSubset);
            Node<int> current = root;
            for (int i = 0; i < newHirschSequence.SetStatus.Length; i++)
            {
                switch (newHirschSequence.SetStatus[i])
                {
                    case IntervalCompressedHirschSequence.NotUsedYet:
                        break;
                    case IntervalCompressedHirschSequence.Active:
                        current = current.Retrieve1(i);
                        break;
                    case IntervalCompressedHirschSequence.Forbidden:
                        current = current.Retrieve2(i);
                        break;
                }
            }
            if (current.value < t)
            {
                lock (current)
                {
                    if (current.value < t)
                    {
                        current.value = t;
                        currentSet.Add(newHirschSequence);
                    }
                }
            }
        }
    }
    public static class DepthFirstHirsch
    {
        private static object theLock = new object();
        private static int maxT = 0;
        private static CompressedHirschSequence best = null;
        private static int delayer = 0;
        private static List<int> currentCounters = new List<int>();
        private static List<int> totalCounters = new List<int>();
        public static void DepthFirstHirschSearch()
        {
            Subset first = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags.Count(b => b) == 1).First();
            Subset second = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags[1] && s.Flags.Count(b => b) == 2).First();
            Subset third = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags.Count(b => b) == 1).First();
            Subset fourth = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2] && s.Flags.Count(b => b) == 2).First();
            CompressedHirschSequence root = new CompressedHirschSequence(first, third, fourth);
            root.UnionAll[2] = true;
            CompressedHirschSequence root2 = new CompressedHirschSequence(root, new List<Subset>() { second }, second.Flags);
            root.UnionAll[2] = false;
            List<CompressedHirschSequence> currentSet = new List<CompressedHirschSequence>();
            root2.TestCompatible(Program.AllSubsets);
            CompressedHirschSequenceSet cache = new CompressedHirschSequenceSet();
            root2.GenerateNewSets(currentSet, cache, 3);
            DepthFirstHirschSearchRec(currentSet, 4, cache, third, fourth);
            Console.WriteLine("Done, best t found was " + maxT);
#if GenerateFamilies
            Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
#endif
        }
        private static void DepthFirstHirschSearchRec(List<CompressedHirschSequence> currentSet, int t, CompressedHirschSequenceSet cache, Subset third, Subset fourth)
        {
            while (currentCounters.Count <= t)
            {
                currentCounters.Add(0);
                totalCounters.Add(0);
            }
            lock (currentCounters)
            {
                currentCounters[t] += currentSet.Count;
                totalCounters[t] += currentSet.Count;
                delayer += currentSet.Count;
                if (delayer > 100000)
                {
                    delayer = 0;
                    for (int i = 4; i < currentCounters.Count; i++)
                    {
                        Console.Write(currentCounters[i]);
                        Console.Write(" ");
                    }
                    Console.WriteLine();
                    for (int i = 4; i < totalCounters.Count; i++)
                    {
                        Console.Write(totalCounters[i]);
                        Console.Write(" ");
                    }
                    Console.WriteLine();
                }
            }
            Parallel.ForEach(currentSet, chs =>
            {
                List<CompressedHirschSequence> newSet = new List<CompressedHirschSequence>();
                chs.TestCompatible(Program.AllSubsets);
                chs.GenerateNewSets(newSet, cache, t);
                if (newSet.Count > 0)
                {
                    if ((t + 2) > maxT)
                    {
                        lock (theLock)
                        {
                            if ((t + 2) > maxT)
                            {
                                Console.WriteLine("New record at " + (t+2));
                                maxT = (t + 2);
                                best = newSet[0];
#if GenerateFamilies
                                Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
#endif
                            }
                        }
                    }
                    DepthFirstHirschSearchRec(newSet, t + 1, cache, third, fourth);
                }
                if (t == 4)
                {
                    lock (currentCounters)
                    {
                        currentCounters[t]--;
                    }
                }
            });
            if (t != 4)
            {
                lock (currentCounters)
                {
                    currentCounters[t] -= currentSet.Count;
                }
            }
        }
    }
    public static class BreadthFirstHirsch
    {
        public static void BreadthFirstHirschSearch()
        {
            List<Subset> allSubsets = Subset.AllSubsets(Program.N, Program.D);
            Subset last = allSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags.Count(b => b) == 1).First();
            int maxT = 0;
            CompressedHirschSequence best = null;
            CompressedHirschSequence root = new CompressedHirschSequence(allSubsets[0]);
            List<CompressedHirschSequence> currentSet = new List<CompressedHirschSequence>();
            root.TestCompatible(allSubsets);
            CompressedHirschSequenceSet cache = new CompressedHirschSequenceSet();
            root.GenerateNewSets(currentSet, cache, 2);
            int t = 2;
            while (currentSet.Count > 0)
            {
                Console.WriteLine("Found " + currentSet.Count + " sequences for t=" + (t+1));
                if ((t + 1) > maxT)
                {
                    maxT = (t + 1);
                    best = currentSet[0];
                }
                t++;
                List<CompressedHirschSequence> newSet = new List<CompressedHirschSequence>();
                foreach (CompressedHirschSequence chs in currentSet)
                {
                    chs.TestCompatible(allSubsets);
                    chs.GenerateNewSets(newSet, cache, t);
                }
                currentSet = newSet;
            }
            Console.WriteLine("Done, best t found was " + maxT);
#if GenerateFamilies
            Console.WriteLine("An example is " + best.Wrap(last).GenerateFamily());
#endif
        }
    }
    public class CompressedHirschSequence
    {
#if GenerateFamilies
        private CompressedHirschSequence previous;
#endif
        public List<Subset> LastFamily = new List<Subset>();
        public List<Subset> UnionOfPreviousFamilies = new List<Subset>();
        public bool[] UnionAll;
        private bool[] UnionSubset;
        bool usedNminus1th;
        bool usedNminus2th;
        bool usedNminus12th;
        public CompressedHirschSequence(Subset lastFamily, params Subset[] forbiddenSets)
        {
            usedNminus1th = lastFamily.Flags[Program.N - 1];
            usedNminus2th = lastFamily.Flags[Program.N - 2];
            LastFamily.Add(lastFamily);
            UnionSubset = lastFamily.Flags;
            UnionAll = new bool[Program.AllSubsets.Count];
            UnionAll[lastFamily.Index] = true;
            foreach (Subset s in forbiddenSets)
            {
                UnionAll[s.Index] = true;
            }
#if GenerateFamilies
            this.previous = null;
#endif
        }
        public CompressedHirschSequence(CompressedHirschSequence compressedHirschSequence, List<Subset> newFamily, bool[] unionSubset)
        {
            usedNminus1th = compressedHirschSequence.usedNminus1th || newFamily.Any(s => s.Flags[Program.N - 1]);
            usedNminus2th = compressedHirschSequence.usedNminus2th || newFamily.Any(s => s.Flags[Program.N - 2]);
            usedNminus12th = compressedHirschSequence.usedNminus12th || newFamily.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]);
            LastFamily = new List<Subset>(newFamily);
            UnionOfPreviousFamilies = new List<Subset>(compressedHirschSequence.UnionOfPreviousFamilies);
            UnionOfPreviousFamilies.AddRange(compressedHirschSequence.LastFamily);
            UnionOfPreviousFamilies.Sort((s1, s2) => s1.Index.CompareTo(s2.Index));
            UnionAll = (bool[])compressedHirschSequence.UnionAll.Clone();
            UnionSubset = unionSubset;
#if GenerateFamilies
            this.previous = compressedHirschSequence;
#endif
        }
        private List<Subset> compatibleSubsets = new List<Subset>();
        public void TestCompatible(IEnumerable<Subset> allSubsets)
        {
            compatibleSubsets.AddRange(allSubsets.Where(s => IsCompatible(s)));
        }
        public bool IsCompatible(Subset S)
        {
            return !UnionAll[S.Index] && UnionOfPreviousFamilies.All(R => LastFamily.Any(T => Enumerable.Range(0, S.Flags.Length).All(i=>!R.Flags[i] || !S.Flags[i] || T.Flags[i])));
        }
        public void GenerateNewSets(List<CompressedHirschSequence> currentSet, CompressedHirschSequenceSet cache, int t)
        {
            if (usedNminus1th
                &&
                !compatibleSubsets.Any(s => s.Flags[Program.N - 1]))
            {
                return;
            }
            if (usedNminus2th
                &&
                !compatibleSubsets.Any(s => s.Flags[Program.N - 2]))
            {
                return;
            }
            if (usedNminus12th
                &&
                !compatibleSubsets.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]))
            {
                return;
            }
            List<Subset> newFamily = new List<Subset>();
            GenerateNewSetsRec(0, newFamily, currentSet, t, cache, false, false, false);
        }
        private void GenerateNewSetsRec(int start, List<Subset> newFamily, List<CompressedHirschSequence> currentSet, int t, CompressedHirschSequenceSet cache, bool gotNminus1th, bool gotNminus2th, bool gotNminus12th)
        {
            if (start == compatibleSubsets.Count)
            {
                if ((newFamily.Count > 0)
                    &&
                    (newFamily.Count <= Program.F)
                    &&
                    (!usedNminus1th || gotNminus1th)
                    &&
                    (!usedNminus2th || gotNminus2th)
                    &&
                    (!usedNminus12th || gotNminus12th))
                {
                    bool[] unionSubset = (bool[])UnionSubset.Clone();
                    newFamily.ForEach(s =>
                    {
                        for (int i = 0; i < s.Flags.Length; i++)
                        {
                            unionSubset[i] |= s.Flags[i];
                        }
                    });
                    if (Subset.IsAscending(unionSubset))
                    {
                        cache.GenerateIfNew(this, newFamily, unionSubset, currentSet, t);
                    }
                }
            }
            else
            {
                GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);

                if (newFamily.All(s => !s.ContainsSubset(compatibleSubsets[start])
                                       &&
                                       !s.IsContainedBySuperset(compatibleSubsets[start])))
                {
                    if (compatibleSubsets[start].Flags[Program.N - 1])
                    {
                        gotNminus1th = true;
                    }
                    if (compatibleSubsets[start].Flags[Program.N - 2])
                    {
                        gotNminus2th = true;
                    }
                    if (compatibleSubsets[start].Flags[Program.N - 1] && compatibleSubsets[start].Flags[Program.N - 2])
                    {
                        gotNminus12th = true;
                    }
                    newFamily.Add(compatibleSubsets[start]);
                    UnionAll[compatibleSubsets[start].Index] = true;
                    GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);
                    newFamily.RemoveAt(newFamily.Count - 1);
                    UnionAll[compatibleSubsets[start].Index] = false;
                }
            }
        }
        public CompressedHirschSequence Wrap(params Subset[] rest)
        {
            CompressedHirschSequence current = this;

            for (int i = 0; i < rest.Length; i++)
            {
                current = new CompressedHirschSequence(current, new List<Subset>() { rest[i] }, null);
            }

            return current;
        }
#if GenerateFamilies
        public string GenerateFamily()
        {
            StringBuilder b = new StringBuilder();

            GenerateFamilies(b);

            return b.ToString();
        }
        private void GenerateFamilies(StringBuilder b)
        {
            if (previous != null)
            {
                previous.GenerateFamilies(b);
                b.Append(" ");
            }
            GenerateFamily(b);
        }
        private void GenerateFamily(StringBuilder b)
        {
            b.Append("{");
            for (int i = 0; i < LastFamily.Count - 1; i++)
            {
                LastFamily[i].ToString(b);
                b.Append(",");
            }
            LastFamily[LastFamily.Count - 1].ToString(b);
            b.Append("}");
        }
#endif
    }
    public class CompressedHirschSequenceSet
    {
        private class Node<T>
        {
            public Node<T>[] lookup;
            public T value;
            public Node<T> Retrieve(int p)
            {
                if (lookup == null)
                {
                    lock (this)
                    {
                        if (lookup == null)
                        {
                            lookup = new Node<T>[Program.AllSubsets.Count];
                        }
                    }
                }
                if (lookup[p] == null)
                {
                    lock(this)
                    {
                        if (lookup[p] == null)
                        {
                            lookup[p] = new Node<T>();
                        }
                    }
                }
                return lookup[p];
            }
        }
        Node<Node<int>> root = new Node<Node<int>>();
        public void GenerateIfNew(CompressedHirschSequence compressedHirschSequence, List<Subset> newFamily, bool[] unionSubset, List<CompressedHirschSequence> currentSet, int t)
        {
            Node<Node<int>> current1 = root;
            foreach (Subset s in newFamily)
            {
                current1 = current1.Retrieve(s.Index);
            }
            if (current1.value == null)
            {
                lock (current1)
                {
                    if (current1.value == null)
                    {
                        current1.value = new Node<int>();
                    }
                }
            }
            Node<int> current2 = current1.value;
            int unionIndex = 0;
            int lastIndex = 0;
            while (unionIndex < compressedHirschSequence.UnionOfPreviousFamilies.Count
                   ||
                   lastIndex < compressedHirschSequence.LastFamily.Count)
            {
                if (unionIndex == compressedHirschSequence.UnionOfPreviousFamilies.Count)
                {
                    current2 = current2.Retrieve(compressedHirschSequence.LastFamily[lastIndex].Index);
                    lastIndex++;
                }
                else if (lastIndex == compressedHirschSequence.LastFamily.Count)
                {
                    current2 = current2.Retrieve(compressedHirschSequence.UnionOfPreviousFamilies[unionIndex].Index);
                    unionIndex++;
                }
                else
                {
                    if (compressedHirschSequence.LastFamily[lastIndex].Index < compressedHirschSequence.UnionOfPreviousFamilies[unionIndex].Index)
                    {
                        current2 = current2.Retrieve(compressedHirschSequence.LastFamily[lastIndex].Index);
                        lastIndex++;
                    }
                    else
                    {
                        current2 = current2.Retrieve(compressedHirschSequence.UnionOfPreviousFamilies[unionIndex].Index);
                        unionIndex++;
                    }
                }
            }
            if (current2.value < t)
            {
                lock (current2)
                {
                    if (current2.value < t)
                    {
                        current2.value = t;
                        currentSet.Add(new CompressedHirschSequence(compressedHirschSequence, newFamily, unionSubset));
                    }
                }
            }
        }
    }
    public class Subset
    {
        public int Index;
        public bool[] Flags;
        public static List<Subset> AllSubsets(int n, int d)
        {
            bool[] template = new bool[n];
            List<Subset> result = new List<Subset>();

            AllSubsetsRec(n, d, 0, n, template, result);

            return result;
        }
        public static void AllSubsetsRec(int n, int d, int size, int current, bool[] template, List<Subset> result)
        {
            if (current == 0)
            {
                if (size > 0)
                {
                    result.Add(new Subset()
                    {
                        Index = result.Count,
                        Flags = (bool[])template.Clone()
                    });
                }
            }
            else
            {
                AllSubsetsRec(n, d, size, current - 1 , template, result);
                if (size < d)
                {
                    template[current - 1] = true;
                    AllSubsetsRec(n, d, size + 1, current - 1, template, result);
                    template[current - 1] = false;
                }
            }
        }
        public bool IsContainedBySuperset(Subset subset)
        {
            return Enumerable.Range(0, Flags.Length).All(i => !Flags[i] || subset.Flags[i]);
        }
        public bool ContainsSubset(Subset subset)
        {
            return Enumerable.Range(0, Flags.Length).All(i => Flags[i] || !subset.Flags[i]);
        }
#if GenerateFamilies
        public void ToString(StringBuilder b)
        {
            for (int i = 0; i < Flags.Length; i++)
            {
                if (Flags[i])
                {
                    b.Append(i);
                }
            }
        }
#endif
        public bool IsAscending()
        {
            return IsAscending(Flags);
        }
        public static bool IsAscending(bool[] flags)
        {
            int index = 0;
            while (index < flags.Length && flags[index])
            {
                index++;
            }
            for (int i = index; i < flags.Length; i++)
            {
                if (flags[i])
                {
                    return false;
                }
            }
            return true;
        }
        public static bool IntersectionIsSubsetOf(Subset B, Subset C, Subset D)
        {
            // return B intersect C subseteq D
            return Enumerable.Range(0, B.Flags.Length).All(i => !(B.Flags[i] && C.Flags[i]) || D.Flags[i]);
        }
    }
}