// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
 
using System.Collections;
using System.Collections.Generic;
 
namespace Microsoft.CodeAnalysis.Shared.Collections;
 
internal static partial class IntervalTreeHelpers<T, TIntervalTree, TNode, TIntervalTreeWitness>
    where TIntervalTree : IIntervalTree<T>
    where TIntervalTreeWitness : struct, IIntervalTreeWitness<T, TIntervalTree, TNode>
{
    /// <summary>
    /// Struct based enumerator, so we can iterate an interval tree without allocating.
    /// </summary>
    private struct NodeEnumerator<TIntrospector> : IEnumerator<TNode>
        where TIntrospector : struct, IIntervalIntrospector<T>
    {
        private readonly TIntervalTree _tree;
        private readonly TIntrospector _introspector;
        private readonly int _start;
        private readonly int _end;
 
        private readonly PooledObject<Stack<TNode>> _pooledStack;
        private readonly Stack<TNode>? _stack;
 
        private bool _started;
        private TNode? _currentNode;
        private bool _currentNodeHasValue;
 
        public NodeEnumerator(TIntervalTree tree, int start, int end, in TIntrospector introspector)
        {
            _tree = tree;
            _start = start;
            _end = end;
            _introspector = introspector;
 
            _currentNodeHasValue = default(TIntervalTreeWitness).TryGetRoot(_tree, out _currentNode);
 
            // Avoid any pooling work if we don't even have a root.
            if (_currentNodeHasValue)
            {
                _pooledStack = s_nodeStackPool.GetPooledObject();
                _stack = _pooledStack.Object;
            }
        }
 
        readonly object IEnumerator.Current => this.Current!;
 
        public readonly TNode Current => _currentNode!;
 
        public bool MoveNext()
        {
            // Trivial empty case
            if (_stack is null)
                return false;
 
            // The first time through, we just want to start processing with the root node.  Every other time through,
            // after we've yielded the current element, we  want to walk down the right side of it.
            if (_started)
                _currentNodeHasValue = ShouldExamineRight(_tree, _start, _end, _currentNode!, _introspector, out _currentNode);
 
            // After we're called once, we're in the started point.
            _started = true;
 
            if (!_currentNodeHasValue && _stack.Count <= 0)
                return false;
 
            // Traverse all the way down the left side of the tree, pushing nodes onto the stack as we go.
            while (_currentNodeHasValue)
            {
                _stack.Push(_currentNode!);
                _currentNodeHasValue = ShouldExamineLeft(_tree, _start, _currentNode!, _introspector, out _currentNode);
            }
 
            Contract.ThrowIfTrue(_currentNodeHasValue);
            Contract.ThrowIfTrue(_stack.Count == 0);
            _currentNode = _stack.Pop();
            return true;
        }
 
        public readonly void Dispose()
            => _pooledStack.Dispose();
 
        public readonly void Reset()
            => throw new System.NotImplementedException();
    }
}