using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using System.Threading;
using DesertPaintCodex.Models;

namespace DesertPaintCodex.Services
{
    public class NewRecipeEventArgs : EventArgs
    {
        public NewRecipeEventArgs(string color, PaintRecipe recipe)
        {
            Color  = color;
            Recipe = recipe;
        }

        public string Color { get; }

        public PaintRecipe Recipe { get; }
    }
    
    public class RecipeGenerator
    {
        public enum SearchType {
            DepthFirst,
            BreadthFirst
        };

        public SearchType Mode { get; set; }

        public uint MinConcentration { get; private set; } // minimum paint concentration
        public uint MaxConcentration { get; private set; } // maximum paint concentration
        public uint MaxReagents { get; private set; } // maximum number of reagents to use in the recipe
        public uint MinReagents { get; private set; } // minimum number of reagents to use in the recipe
        public uint FullQuantityDepth { get; private set; } // at or equal this number of reagents, ignore ingredient settings for max quantity
        public uint FullQuantity { get; private set; }  // The max number of a reagent to use at full quantity

        public uint MaxThreads { get; set; } = 15;
        
        private bool _running = false;

        private int _runningThreads = 0;
        
        private readonly Dictionary<string, uint> _recipeCosts = new ();
        private readonly Dictionary<string, PaintRecipe> _recipes = new();

        private uint _totalReagents;

        private readonly List<Reagent> _costSortedReagents = new();

        private readonly ConcurrentQueue<RecipeSearchNode> _searchQueue = new();

        private ulong _recipeCount = 0;

        private readonly List<Thread> _generatorThreads = new();
        private readonly object _workerLock = new();

        private bool _requestCancel = false;

        private StreamWriter? _log;

        // events
        public event EventHandler? Finished;
        public event EventHandler? Progress;
        public event EventHandler<NewRecipeEventArgs>? NewRecipe;

        public RecipeGenerator()
        {
            Mode = SearchType.BreadthFirst;
            foreach (PaintColor color in PaletteService.Colors)
            {
                _recipes.Add(color.Name, new PaintRecipe());
                _recipeCosts.Add(color.Name, uint.MaxValue);
            }
            MinReagents = 1;
            MaxReagents = 5;
            MinConcentration = 10;
            MaxConcentration = 20;
        }

        public Dictionary<string, PaintRecipe> Recipes => _recipes;

        public ulong RecipeCount => _recipeCount;

        public bool CanResume => (!_running && (_searchQueue.Count > 0));

        public string? Log
        {
            set => _log = value != null ? new StreamWriter(value) : null;
        }

        public void FlushLog()
        {
            _log?.Flush();
        }

        public void CloseLog()
        {
            _log?.Close();
            _log = null;
        }

        private void WriteLog(string msg)
        {
            if (_log == null) return;
            lock (_workerLock)
            {
                _log.WriteLine(msg);
            }
        }

        private void WriteLog(string msg, params object[] args)
        {
            if (_log == null) return;
            lock(_workerLock)
            {
                _log.WriteLine(msg, args);
            }
        }

        private class ReagentCostSort : IComparer<Reagent>
        {
            public int Compare(Reagent? reagent1, Reagent? reagent2)
            {
                if (reagent1 == null)
                {
                    if (reagent2 == null) return 0;
                    return -1;
                }
                if (reagent2 == null) return 1;
                
                return (int)reagent1.Cost - (int)reagent2.Cost;
            }
        }

        public void InitRecipes(Dictionary<string, PaintRecipe> initialRecipes)
        {
            if (_running)
            {
                return;
            }
            _recipeCosts.Clear();
            _recipes.Clear();
            foreach (PaintRecipe recipe in initialRecipes.Values)
            {
                //PaintRecipe recipeCopy = new PaintRecipe(recipe);
                AddCheapestRecipe(recipe);
            }
        }

        private void InitSortedReagents()
        {
            _costSortedReagents.Clear();
            foreach (string name in ReagentService.Names)
            {
                Reagent reagent = ReagentService.GetReagent(name);
                _costSortedReagents.Add(reagent);
            }
            _costSortedReagents.Sort(new ReagentCostSort());
        }

        // Generate paint recipes.
        // minConcentration - the minimum permitted concentration in a recipe (10 for paint, 50 for ribbons)
        // maxConcentration - the maximum concentration for a recipe
        // minReagents - the minimum number of ingredients in a recipe
        // maxReagents - the maximum number of ingredients allowed in a recipe
        // fullQuantityDepth - at this depth of ingredient or below, allow up to fullQuantity of any reagent
        // fullQuantity - the maximum amount of any reagent to permit up to the full quantity depth. After that, reagents are limited by the
        //                per-reagent value
        public void BeginRecipeGeneration(uint minConcentration, uint maxConcentration, uint minReagents, uint maxReagents, uint fullQuantityDepth, uint fullQuantity)
        {
            if (_running)
            {
                // Already running - don't start again
                return;
            }

            MinConcentration = minConcentration;
            MaxConcentration = maxConcentration;
            MinReagents = minReagents;
            MaxReagents = maxReagents;
            FullQuantity = fullQuantity;
            FullQuantityDepth = fullQuantityDepth;

            // Sanity check
            if (MinConcentration < 10) MinConcentration = 10;
            if (MaxConcentration < MinConcentration) MaxConcentration = MinConcentration;
            if (MinReagents < 1) MinReagents = 1;
            if (MaxReagents < MinReagents) MaxReagents = MinReagents;

            // first, sort reagents by cost.
            InitSortedReagents();

            _totalReagents = (uint)_costSortedReagents.Count;

            // Pre-populate recipes list with:
            // 1) 1-ingredient recipes @ min concentration for all enabled ingredients with a count >= min concentration
            // 2) any previously-generated recipes
            WriteLog($"===================== BEGIN RECIPE GENERATION ========================== {DateTime.Now}");
            WriteLog("Pre-populating basic recipes.");
            int enabledReagentCount = 0;
            PaintRecipe recipe = new();
            foreach (var reagent in _costSortedReagents.Where(reagent => reagent.Enabled))
            {
                if (!reagent.IsCatalyst && ((reagent.RecipeMax >= minConcentration) || ((FullQuantityDepth > 0) && (FullQuantity >= minConcentration))))
                {
                    recipe.Clear();
                    recipe.AddReagent(reagent.Name, minConcentration);
                    AddCheapestRecipe(recipe);
                }
                ++enabledReagentCount;
            }
            MaxReagents = (uint)Math.Min(enabledReagentCount, MaxReagents);
            MinReagents = Math.Min(MinReagents, MaxReagents);
            
            _searchQueue.Clear();

            for (uint reagentIdx = 0; reagentIdx < _costSortedReagents.Count; ++reagentIdx)
            {
                if (!_costSortedReagents[(int) reagentIdx].Enabled) continue;
                
                // queue up all combinations of MinReagents
                RecipeSearchNode initialNode = new(_costSortedReagents, reagentIdx)
                {
                    FullQuantity      = FullQuantity,
                    FullQuantityDepth = FullQuantityDepth,
                    MinConcentration  = minConcentration,
                    MaxConcentration  = maxConcentration,
                    MinReagents       = minReagents,
                    MaxReagents       = maxReagents
                };
                initialNode.WriteLog = WriteLog;

                if (MinReagents > 1)
                {
                    while (NextReagentSetBreadthFirst(initialNode, 1, minReagents))
                    {
                        if (initialNode.ReagentCount != minReagents) continue;
                        
                        //Console.WriteLine("Initial node at size {0}/{1} with recipe: {2}", initialNode.ReagentCount, minReagents, initialNode.TestRecipe.ToString());
                        RecipeSearchNode searchNode = new RecipeSearchNode(initialNode);
                        searchNode.WriteLog = WriteLog;
                        _searchQueue.Enqueue(searchNode);
                    }
                }
                else
                {
                    _searchQueue.Enqueue(initialNode);
                }
            }

            _recipeCount = 0;

            WriteLog("Begin recipe generation: MaxConcentration={0} MinReagents={1} MaxReagents={2} FullQuantity={3} FullQuantityDepth={4}", MaxConcentration, MinReagents, MaxReagents, FullQuantity, FullQuantityDepth);

            // start worker threads to do the actual work
            ResumeRecipeGeneration();
        }

        public void ResumeRecipeGeneration()
        {
            if (_running)
            {
                // Already running - don't start again
                return;
            }
            _running = true;
            _requestCancel = false;

            WriteLog("Resuming recipe generation: pre-threads={0} reagent count={1} search queue={2}", _runningThreads, _costSortedReagents.Count, _searchQueue.Count);
            _runningThreads = 0; // presumably!

            int threadCount = Math.Min(Math.Min(_costSortedReagents.Count, _searchQueue.Count), (int)MaxThreads);
            if (threadCount == 0)
            {
                Finished?.Invoke(this, EventArgs.Empty);
            }
            _generatorThreads.Clear();
            Console.WriteLine("Starting {0} generator threads.", threadCount);
            WriteLog($"===== Starting {threadCount} threads.");
            for (int i = 0; i < threadCount; ++i)
            {
                Thread thr = new(Generate) {Priority = ThreadPriority.BelowNormal};
                _generatorThreads.Add(thr);
            }
            foreach (Thread thr in _generatorThreads)
            {
                thr.Start();
            }
        }

        public bool SaveState(string file)
        {
            if (_running)
            {
                // can't save state while running
                return false;
            }

            lock(_workerLock)
            {
                using StreamWriter writer = new(file, false);
                writer.WriteLine("MinReagents: {0}", MinReagents);
                writer.WriteLine("MaxReagents: {0}", MaxReagents);
                writer.WriteLine("FullQuantityDepth: {0}", FullQuantityDepth);
                writer.WriteLine("FullQuantity: {0}", FullQuantity);
                writer.WriteLine("TotalReagents: {0}", _totalReagents);
                writer.WriteLine("RecipeCount: {0}", _recipeCount);
                writer.WriteLine("SearchType: {0}", Mode.ToString());
                foreach (KeyValuePair<string, PaintRecipe> pair in _recipes)
                {
                    PaintRecipe recipe    = pair.Value;
                    string      colorName = PaletteService.FindNearest(recipe.ReactedColor);
                    writer.WriteLine("BeginRecipe: {0}", colorName);
                    foreach (PaintRecipe.ReagentQuantity reagent in recipe.Reagents)
                    {
                        writer.WriteLine("Ingredient: {0}={1}", reagent.Name, reagent.Quantity);
                    }
                    writer.WriteLine("EndRecipe: {0}", colorName);
                }
                writer.WriteLine("SearchNodes: {0}", _searchQueue.Count);
                foreach (RecipeSearchNode node in _searchQueue)
                {
                    node.SaveState(writer);
                }
            }
            return true;
        }

        private static readonly Regex _keyValueRegex = new Regex(@"(?<key>\w+)\:\s*(?<value>.+)\s*");
        private static readonly Regex _reagentRegex = new Regex(@"(?<ingredient>(\w+\s)*\w+)\s*=\s*(?<quantity>\d)\s*");
        
        public bool LoadState(string file)
        {
            // cannot be running, and reactions must be set
            if (_running)
            {
                return false;
            }

            InitSortedReagents();
            bool success = true;

            PaintRecipe? currentRecipe = null;
            using StreamReader reader = new(file, false);
            string? line;
            while (success && ((line = reader.ReadLine()) != null))
            {
                Match match = _keyValueRegex.Match(line);
                if (match.Success)
                {
                    string value = match.Groups["value"].Value;
                    switch(match.Groups["key"].Value)
                    {
                        case "MinReagents":
                            MinReagents = uint.Parse(value);
                            MaxReagents = Math.Max(MinReagents, MaxReagents);
                            break;
                        case "MaxReagents":
                            MaxReagents = uint.Parse(value);
                            MinReagents = Math.Min(MinReagents, MaxReagents);
                            break;
                        case "FullQuantityDepth":
                            FullQuantityDepth = uint.Parse(value);
                            break;
                        case "FullQuantity":
                            FullQuantity = uint.Parse(value);
                            break;
                        case "TotalReagents":
                            _totalReagents = uint.Parse(value);
                            break;
                        case "RecipeCount":
                            if (!ulong.TryParse(value, out _recipeCount))
                            {
                                // must have rolled to negative - try as an int and convert
                                long recipeCountInt = int.Parse(value);
                                _recipeCount = (ulong)(recipeCountInt & 0x00000000ffffffffL);
                            }
                            break;
                        case "BeginRecipe":
                            currentRecipe = new PaintRecipe();
                            break;
                        case "EndRecipe":
                            if (currentRecipe != null)
                            {
                                PaintColor color = currentRecipe.ReactedColor;
                                uint       cost  = currentRecipe.Cost;
                                _recipes[color.Name]     = currentRecipe; // replace
                                _recipeCosts[color.Name] = cost;
                                currentRecipe            = null;
                            }
                            break;
                        case "Ingredient":
                            if (currentRecipe != null)
                            {
                                Match ingredientMatch = _reagentRegex.Match(match.Groups["value"].Value);
                                if (ingredientMatch.Success)
                                {
                                    uint quantity = uint.Parse(ingredientMatch.Groups["quantity"].Value);
                                    currentRecipe.AddReagent(ingredientMatch.Groups["ingredient"].Value, quantity);
                                }
                                else
                                {
                                    success = false;
                                }
                            }
                            break;
                        case "SearchNodes":
                            int nodeCount = int.Parse(match.Groups["value"].Value);
                            for (int i = 0; i < nodeCount; ++i)
                            {
                                RecipeSearchNode node = new(_costSortedReagents)
                                {
                                    FullQuantity      = FullQuantity,
                                    FullQuantityDepth = FullQuantityDepth,
                                    MinReagents       = MinReagents,
                                    MaxReagents       = MaxReagents,
                                    MaxConcentration  = MaxConcentration
                                };
                                node.WriteLog = WriteLog;
                                success                = success && node.LoadState(reader);
                                if (success)
                                {
                                    _searchQueue.Enqueue(node);
                                }
                            }
                            break;
                        case "SearchType":
                            Mode = (SearchType)Enum.Parse(typeof(SearchType), match.Groups["value"].Value);
                            break;
                        default:
                            success = false;
                            break;
                    }
                }
                else
                {
                    success = false;
                    break;
                }
            }
            return success;
        }

        private void Generate()
        {
            lock(_workerLock)
            {
                ++_runningThreads;
            }

            bool ok;
            do
            {
                RecipeSearchNode? node;
                lock (_workerLock)
                {
                    ok = _searchQueue.TryDequeue(out node);
                }

                if (!ok) break;
                
                Debug.Assert(node != null);

                node.WriteLog = WriteLog;
                
                if (Mode == SearchType.DepthFirst)
                {
                    uint targetQuantity = (node.ReagentCount <= FullQuantityDepth)
                        ? ((uint)node.ReagentCount * FullQuantity) 
                        : node.MaxConcentration + 1;
                    do {
                        --targetQuantity;
                        if (node.ShouldLog)
                        {
                            WriteLog($" == Initializing {node} for quantity {targetQuantity}");
                        }
                        node.InitForQuantity(targetQuantity);
                    } while (targetQuantity > MinConcentration && (node.CurrentTargetQuantity != node.UsedQuantity));
    
                    while ((ok = IterateDepthFirst(node)) && !_requestCancel)
                    {
                        Progress?.Invoke(this, EventArgs.Empty);
                    }
                }
                else
                {
                    // breadth-first search
                    uint targetQuantity = MinConcentration - 1;
                    uint quantityLimit = (node.ReagentCount <= FullQuantityDepth) 
                        ? (FullQuantity * (uint)node.ReagentCount) 
                        : node.MaxConcentration;
                    do {
                        ++targetQuantity;
                        if (node.ShouldLog)
                        {
                            WriteLog($" == Initializing {node} for quantity {targetQuantity}");
                        }
                        node.InitForQuantity(targetQuantity);
                    } while ((targetQuantity < quantityLimit) && (node.CurrentTargetQuantity != node.UsedQuantity));
    
                    while ((ok = IterateBreadthFirst(node)) && !_requestCancel)
                    {
                        Progress?.Invoke(this, EventArgs.Empty);
                    }
                }
                if (ok)
                {
                    // stopped because cancel was requested - requeue the node in its current state for resume
                    _searchQueue.Enqueue(node);
                }
            } while (!_requestCancel);

            bool done;
            lock(_workerLock)
            {
                --_runningThreads;
                //generatorThreads.Remove(Thread.CurrentThread);

                done = (_runningThreads == 0);
            }

            if (!done) return;
            
            _running       = false;
            if (!_requestCancel && !_searchQueue.IsEmpty)
            {
                Debug.WriteLine($"Recipe generation complete, but search queue isn't empty {_searchQueue.Count}.");
                WriteLog($"Recipe generation complete, but search queue isn't empty {_searchQueue.Count}.");
                _searchQueue.Clear();
            }
            _requestCancel = false;
            Finished?.Invoke(this, EventArgs.Empty);
        }

        // Add the cheapest recipe to the recipe list
        // returns the discarded recipe from the pair (or null if no original recipe to replace)
        private void AddCheapestRecipe(PaintRecipe recipe)
        {
            if (!recipe.IsValidForConcentration(MinConcentration)) return;
            
            string colorName = PaletteService.FindNearest(recipe.ReactedColor);
            lock (_workerLock)
            {
                uint newCost = recipe.Cost;
                if (_recipeCosts.TryGetValue(colorName, out var cost))
                {
                    if (cost < newCost)
                    {
                        // WriteLog($"Skipping recipe (cost {newCost} > {cost}): {recipe}");
                        return;
                    }
                    PaintRecipe origRecipe = _recipes[colorName];
                    if (cost == newCost && recipe.Concentration >= origRecipe.Concentration)
                    {
                        // Same cost, greater concentration - use the lower concentration recipe
                        WriteLog($"Skipping recipe (cost {newCost}, {recipe.Concentration} >= {origRecipe.Concentration}): {recipe}");
                        return;
                    }
                        
                    _recipes[colorName].CopyFrom(recipe); // Copy recipe because the one passed in should be const and will get overwritten
                    _recipeCosts[colorName] = newCost;
                    WriteLog($"Replacing recipe (cost {newCost} < {cost}): {recipe}");
                        
                    if (NewRecipe == null) return;
                        
                    NewRecipeEventArgs args = new(colorName, _recipes[colorName]);
                    NewRecipe(this, args);
                }
                else
                {
                    // This would be an error!
                    _recipeCosts.Add(colorName, newCost);
                    PaintRecipe newRecipe = new PaintRecipe(recipe); // Copy recipe because the one passed in should be const and will get overwritten
                    _recipes.Add(colorName, newRecipe);

                    WriteLog($"New recipe (cost {newCost}): {recipe}");

                    if (NewRecipe == null) return;
                        
                    NewRecipeEventArgs args = new(colorName, newRecipe);
                    NewRecipe(this, args);
                }
            }
        }

        private bool IterateDepthFirst(RecipeSearchNode node)
        {
            TestCurrentRecipe(node);

            // pick recipe quantities at current recipe ingredients/size
            if (NextRecipe(node))
            {
                lock(_workerLock)
                {
                    ++_recipeCount;
                }
                //System.Console.WriteLine("Found next recipe at size {0} qty {1}", node.Reagents.Count, node.CurrentTargetQuantity);
                return true;
            }

            if (NextRecipeSize(node))
            {
                //System.Console.WriteLine("Found next recipe size {0}", node.CurrentTargetQuantity);
                return true;
            }

            // Search for next ingredient combo - all quantity combos for previous were searched
            //System.Console.WriteLine("Finding next ingredient combo");
            do
            {
                if (node.AddNextReagent()) continue;
                
                while ((node.ReagentCount > node.MinReagents) && (node.LastReagent == (_totalReagents-1)))
                {
                    node.RemoveLastReagent();
                }
                if (node.ReagentCount == node.MinReagents)
                {
                    // done
                    return false;
                }
                uint nextReagent = node.NextFreeReagent(node.LastReagent);
                while ((node.ReagentCount > node.MinReagents) && (nextReagent >= _totalReagents))
                {
                    // No more reagents to try at this level
                    node.RemoveLastReagent();
                    if (node.ReagentCount > node.MinReagents)
                    {
                        nextReagent = node.NextFreeReagent(node.LastReagent);
                    }
                }
                if (node.ReagentCount == node.MinReagents)
                {
                    // done
                    return false;
                }
                node.ReplaceLastReagent(nextReagent);
            } while (node.MaxConcentration < (node.MinConcentration + node.CatalystCount));
            node.InitForQuantity(node.MaxConcentration);

            //string outStr = "{0} : {1} : ";
            //for (int i = 0; i < currentReagents.Count; ++i)
            //{
            //    Reagent reagent = costSortedReagents[(int)currentReagents[i]];
            //    if (i > 0)
            //    {
            //        outStr += ", ";
            //    }
            //    outStr += reagent.Name + " (" + reagent.Cost + ")";
            //}
            //Console.WriteLine(outStr, currentReagents.Count, recipeCount);
            return true;
        }

        private bool IterateBreadthFirst(RecipeSearchNode node)
        {
            // pick recipe quantities at current recipe ingredients/size
            TestCurrentRecipe(node);
            lock(_workerLock)
            {
                ++_recipeCount;
            }

            // search all quantities of current recipe
            if (NextRecipe(node))
            {
                //System.Console.WriteLine("Found next recipe at size {0} qty {1}", node.ReagentCount, node.CurrentTargetQuantity);
                return true;
            }

            string origNodeVal = node.ToString();

            // Try next quantity
            uint newQuantity;
            uint quantityLimit = ((uint)node.ReagentCount <= FullQuantityDepth) ? ((uint)node.ReagentCount * FullQuantity) : node.MaxConcentration;
            do {
                newQuantity = node.CurrentTargetQuantity + 1;
                //Console.WriteLine("Try quantity {0}", newQuantity);
                if (newQuantity > quantityLimit) continue;

                if (node.ShouldLog)
                {
                    WriteLog($" == Initializing {node} for quantity {newQuantity}");
                }
                node.InitForQuantity(newQuantity);
                if (node.CurrentTargetQuantity <= node.UsedQuantity)
                {
                    //if (log != null) { lock(log) { log.WriteLine("Update quantity to {0}", node.CurrentTargetQuantity); } }
                    if (node.ShouldLog)
                    {
                        WriteLog($"  == {node} quantity {newQuantity}");
                    }
                    return true;
                }
            } while (newQuantity < quantityLimit);

            bool ok = NextReagentSetBreadthFirst(node, node.MinReagents, node.MaxReagents);
            if (node.ShouldLog)
            {
                if (ok)
                {
                    WriteLog($"==== {origNodeVal} next reagent set: {node} @ {node.CurrentTargetQuantity}");
                }
                else
                {
                    WriteLog($"==== done with reagent set: {origNodeVal}");
                }
            }
            return ok;
        }

        private bool NextReagentSetBreadthFirst(RecipeSearchNode node, uint minReagents, uint maxReagents)
        {
            // search all variants at this depth of recipe
            // increase recipe depth

            // next reagent in last position
            // if at end, pop reagent
            //Console.WriteLine("Finding new recipe after quantity {0}/{1} used {2}", newQuantity, node.MaxConcentration, node.UsedQuantity);
            if (node.ShouldLog)
            {
                WriteLog($" == Initializing {node} for quantity {node.MinConcentration + node.CatalystCount}");
            }
            node.InitForQuantity(node.MinConcentration + node.CatalystCount); // reset quantity
            int currentDepth = node.ReagentCount;
            bool recipeFound;
            do {
                //Console.WriteLine("Current depth: {0}/{1}", currentDepth, node.MaxReagents);
                do {
                    recipeFound = false;
                    
                    // back out until we find a node that can be incremented
                    if (currentDepth <= minReagents) continue;
                    
                    while (node.ReagentCount > minReagents)
                    {
                        if (node.LastReagent < (_totalReagents - 1))
                        {
                            var nextReagent = node.NextFreeReagent(node.LastReagent);
                            if (nextReagent < _totalReagents)
                            {
                                //Console.WriteLine("Replace last reagent with {0}", nextReagent);
                                node.ReplaceLastReagent(nextReagent);
                                break;
                            }
                            else
                            {
                                // shouldn't happen
                                //Console.WriteLine("No available reagents at depth {0}!", node.ReagentCount);
                                node.RemoveLastReagent();
                                if (node.ReagentCount == minReagents)
                                {
                                    // just popped the last reagent at the top level
                                    ++currentDepth;
                                    //if (log != null) { lock(log) { log.WriteLine("Increased depth to {0}/{1}", currentDepth, node.MaxReagents); } }
                                }
                            }
                        }
                        else
                        {
                            //Console.WriteLine("Pop last reagent");
                            node.RemoveLastReagent();
                            if (node.ReagentCount == minReagents)
                            {
                                // just popped the last reagent at the top level
                                ++currentDepth;
                                //if (log != null) { lock(log) { log.WriteLine("Increased depth to {0}/{1} [pop last reagent at top level]", currentDepth, node.MaxReagents); } }
                            }
                        }
                    }
                    // fill in the nodes up to the current depth
                    if (node.ReagentCount >= minReagents && currentDepth <= maxReagents)
                    {
                        recipeFound = true;
                        while (node.ReagentCount < currentDepth)
                        {
                            if (! node.AddNextReagent())
                            {
                                //if (log != null) { lock(log) { log.WriteLine("Failed to add reagent {0}/{1}", node.ReagentCount+1, currentDepth); } }
                                recipeFound = false;
                            }
                        }
                    }
                    //Console.WriteLine("Catalysts: {0} Reagents: {1} Min: {2}", node.CatalystCount, node.ReagentCount, node.MinReagents);
                } while ((node.CatalystCount >= node.ReagentCount) && (node.ReagentCount >= minReagents)); // make sure to skip all-catalyst combinations

                if (recipeFound)
                {
                    break;
                }
                else
                {
                    ++currentDepth;
                    //if (log != null) { lock(log) { log.WriteLine("Increased depth to {0}/{1} [no recipe]", currentDepth, node.MaxReagents); } }
                }
            } while (currentDepth <= maxReagents);

            if (!recipeFound)
            {
                if (node.ShouldLog)
                {
                    WriteLog($" == no more recipes for {node}");
                }
                return false;
            }
            
            node.InitForQuantity(node.MinConcentration+node.CatalystCount); // minimum quantity for this recipe
            
            node.TestRecipe ??= new PaintRecipe();
            node.TestRecipe.Clear();
            
            for (int i = 0; i < node.ReagentCount; ++i)
            {
                node.TestRecipe.AddReagent(node.GetReagent(i).Name, node.CurrentWeights[i]);
            }

            return recipeFound;
        }

        private void TestCurrentRecipe(RecipeSearchNode node)
        {
            node.TestRecipe ??= new PaintRecipe();
            node.TestRecipe.Clear();
            for (int i = 0; i < node.ReagentCount; ++i)
            {
                node.TestRecipe.AddReagent(node.GetReagent(i).Name, node.CurrentWeights[i]);
            }
            if (node.ShouldLog)
            {
                WriteLog($"   -> {node.TestRecipe}");
            }
            AddCheapestRecipe(node.TestRecipe);
            //if (log != null) { lock(log) { log.WriteLine("Tested recipe: {0}", node.TestRecipe); } }
        }

        private bool NextRecipe(RecipeSearchNode node)
        {
            // check for the next recipe
            uint remainingWeight = node.CurrentTargetQuantity - node.CatalystCount;
            if (remainingWeight < MinConcentration)
            {
                // not possible to make a valid recipe
                //Console.WriteLine("Insufficient remaining weight");
                if (node.ShouldLog)
                {
                    WriteLog($" ***** Not enough remaining weight in recipe {node} at target quantity {node.CurrentTargetQuantity} catalysts {node.CatalystCount} min concentration {MinConcentration}");
                }
                return false;
            }
            //uint remainingReagents = (uint)node.Reagents.Count - node.CatalystCount;

            uint depth = (uint)node.ReagentCount;
            uint weightToConsume = 0;
            uint spaceBelow = 0;
            int reagentsBelow = 0;
            // Start from the end of the current reagent list and work to the front
            for (int i = (int)depth-1 ; i >= 0; --i)
            {
                uint currentWeight = node.CurrentWeights[i];

                if ((spaceBelow >= (weightToConsume+1)) && (currentWeight > 1))
                {
                    // reduce this node by 1, allocate remaining weight to reagents below it
                    node.SetWeight(i, currentWeight-1);
                    weightToConsume += 1;
                    for (int j = i+1; j < depth; ++j)
                    {
                        --reagentsBelow;
                        Reagent reagent = node.GetReagent(j);
                        uint allocated = (uint)Math.Min(reagent.IsCatalyst ? 1 : (depth <= FullQuantityDepth ? FullQuantity : reagent.RecipeMax), weightToConsume - reagentsBelow);
                        if (allocated > 100)
                        {
                            Console.WriteLine("ACK: allocated = {0}", allocated);
                        }
                        node.SetWeight(j, allocated);
                        weightToConsume -= allocated;
                    }
                    break;
                }
                else
                {
                    Reagent reagent = node.GetReagent(i);
                    spaceBelow += (reagent.IsCatalyst ? 1 : (depth <= FullQuantityDepth ? FullQuantity : reagent.RecipeMax));
                    weightToConsume += currentWeight;
                    ++reagentsBelow;
                }
            }

            //int recipeWeight = 0;
            //foreach (int weight in node.CurrentWeights)
            //{
            //    recipeWeight += weight;
            //}
            //if ((weightToConsume != 0) || (recipeWeight != node.CurrentTargetQuantity))
            //{
            //    Console.WriteLine("Failed recipe with leftover weight {0} ({1}/{2}):", weightToConsume, recipeWeight, node.CurrentTargetQuantity);
            //    for (int i = 0; i < node.Reagents.Count; ++i)
            //    {
            //        Console.WriteLine("   > {0} {1}", node.Reagent(i).Name, node.CurrentWeights[i]);
            //    }
            //}
            
            return (weightToConsume == 0);
        }

        private static bool NextRecipeSize(RecipeSearchNode node)
        {
            uint newQuantity = node.CurrentTargetQuantity - 1;
            if (newQuantity < (node.MinConcentration + node.CatalystCount))
            {
                return false;
            }

            node.InitForQuantity(newQuantity);
            return node.CurrentTargetQuantity <= node.UsedQuantity;
        }

        public void Wait()
        {
            if (_generatorThreads.Count <= 0) return;
            
            foreach (Thread thr in _generatorThreads)
            {
                thr.Join();
            }
            _generatorThreads.Clear();
        }

        public void Stop()
        {
            _requestCancel = true;
        }

        public void ResetQueue()
        {
            lock (_workerLock)
            {
                // Don't reset the queue ever while running
                if (_running) return;
                _searchQueue.Clear();
            }
        }

        public void Reset()
        {
            foreach (PaintRecipe recipe in _recipes.Values)
            {
                recipe.Clear();
            }
            foreach (string key in _recipeCosts.Keys)
            {
                _recipeCosts[key] = uint.MaxValue;
            }
        }        
    }
}