// 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;
using System.Collections.Generic;
using Microsoft.CodeAnalysis.PooledObjects;
using Roslyn.Utilities;

namespace Microsoft.CodeAnalysis
{
    /// <summary>
    /// A representation of a string of characters that requires O(1) extra space to concatenate two ropes.
    /// </summary>
    internal abstract class Rope
    {
        public static readonly Rope Empty = ForString("");
        public abstract override string ToString();
        public abstract int Length { get; }
        protected abstract IEnumerable<char> GetChars();
        private Rope() { }

        /// <summary>
        /// A rope can wrap a simple string.
        /// </summary>
        public static Rope ForString(string s)
        {
            if (s == null)
                throw new ArgumentNullException(nameof(s));

            return new StringRope(s);
        }

        /// <summary>
        /// A rope can be formed from the concatenation of two ropes.
        /// </summary>
        public static Rope Concat(Rope r1, Rope r2)
        {
            if (r1 == null)
                throw new ArgumentNullException(nameof(r1));

            if (r2 == null)
                throw new ArgumentNullException(nameof(r2));

            return
                r1.Length == 0 ? r2 :
                r2.Length == 0 ? r1 :
                checked(r1.Length + r2.Length < 32) ? ForString(r1.ToString() + r2.ToString()) :
                new ConcatRope(r1, r2);
        }

        /// <summary>
        /// Two ropes are "the same" if they represent the same sequence of characters.
        /// </summary>
        public override bool Equals(object? obj)
        {
            if (!(obj is Rope other) || Length != other.Length)
                return false;
            if (Length == 0)
                return true;
            var chars0 = GetChars().GetEnumerator();
            var chars1 = other.GetChars().GetEnumerator();
            while (chars0.MoveNext() && chars1.MoveNext())
            {
                if (chars0.Current != chars1.Current)
                    return false;
            }

            return true;
        }

        public override int GetHashCode()
        {
            int result = Length;
            foreach (char c in GetChars())
                result = Hash.Combine((int)c, result);

            return result;
        }

        /// <summary>
        /// A rope that wraps a simple string.
        /// </summary>
        private sealed class StringRope : Rope
        {
            private readonly string _value;
            public StringRope(string value) => _value = value;
            public override string ToString() => _value;
            public override int Length => _value.Length;
            protected override IEnumerable<char> GetChars() => _value;
        }

        /// <summary>
        /// A rope that represents the concatenation of two ropes.
        /// </summary>
        private sealed class ConcatRope : Rope
        {
            private readonly Rope _left, _right;
            public override int Length { get; }

            public ConcatRope(Rope left, Rope right)
            {
                _left = left;
                _right = right;
                Length = checked(left.Length + right.Length);
            }

            public override string ToString()
            {
                var psb = PooledStringBuilder.GetInstance();
                var stack = new Stack<Rope>();
                stack.Push(this);
                while (stack.Count != 0)
                {
                    switch (stack.Pop())
                    {
                        case StringRope s:
                            psb.Builder.Append(s.ToString());
                            break;
                        case ConcatRope c:
                            stack.Push(c._right);
                            stack.Push(c._left);
                            break;
                        case var v:
                            throw ExceptionUtilities.UnexpectedValue(v.GetType().Name);
                    }
                }

                return psb.ToStringAndFree();
            }

            protected override IEnumerable<char> GetChars()
            {
                var stack = new Stack<Rope>();
                stack.Push(this);
                while (stack.Count != 0)
                {
                    switch (stack.Pop())
                    {
                        case StringRope s:
                            foreach (var c in s.ToString())
                                yield return c;
                            break;
                        case ConcatRope c:
                            stack.Push(c._right);
                            stack.Push(c._left);
                            break;
                        case var v:
                            throw ExceptionUtilities.UnexpectedValue(v.GetType().Name);
                    }
                }
            }
        }
    }
}
