//-------------------------------------------------------------------------------------------------------
// Copyright (C) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.
//-------------------------------------------------------------------------------------------------------
namespace UnifiedRegex
{
    template <typename C>
    class CharSet;

    template <typename C>
    class RuntimeCharSet;

    class CharBitvec : private Chars<char>
    {
    public:
        static const int Width = Chars<char>::CharWidth;
        static const int Size = NumChars;

    private:
        static const int wordSize = sizeof(uint32) * 8;
        static const int vecSize = Size / wordSize;
        static const uint32 ones = (uint32)-1;

        static const uint8 oneBits[Size];

        uint32 vec[vecSize];

        inline static void setrng(uint32 &v, uint l, uint h)
        {
            uint w = h - l + 1;
            if (w == wordSize)
            {
                v = ones;
            }
            else
            {
                v |= ((1U << w) - 1) << l;
            }
        }

        inline static void clearrng(uint32 &v, uint l, uint h)
        {
            uint w = h - l + 1;
            if (w == wordSize)
            {
                v = 0;
            }
            else
            {
                v &= ~(((1U << w) - 1) << l);
            }
        }

    public:
        inline void CloneFrom(const CharBitvec& other)
        {
            for (int w = 0; w < vecSize; w++)
            {
                vec[w] = other.vec[w];
            }
        }

        inline void Clear()
        {
            for (int w = 0; w < vecSize; w++)
            {
                vec[w] = 0;
            }
        }

        inline void SetAll()
        {
            for (int w = 0; w < vecSize; w++)
            {
                vec[w] = ones;
            }
        }

        inline void Set(uint k)
        {
            Assert(k < Size);
            __assume(k < Size);
            if (k < Size)
            {
                vec[k / wordSize] |= 1U << (k % wordSize);
            }
        }

        inline void SetRange(uint l, uint h)
        {
            Assert(l < Size);
            Assert(h < Size);
            __assume(l < Size);
            __assume(h < Size);
            if (l < Size && h < Size)
            {
                if (l == h)
                {
                    vec[l / wordSize] |= 1U << (l % wordSize);
                }
                else if (l < h)
                {
                    int lw = l / wordSize;
                    int hw = h / wordSize;
                    int lo = l % wordSize;
                    int hio = h % wordSize;
                    if (lw == hw)
                    {
                        setrng(vec[lw], lo, hio);
                    }
                    else
                    {
                        setrng(vec[lw], lo, wordSize - 1);
                        for (int w = lw + 1; w < hw; w++)
                        {
                            vec[w] = ones;
                        }
                        setrng(vec[hw], 0, hio);
                    }
                }
            }
        }

        inline void ClearRange(uint l, uint h)
        {
            Assert(l < Size);
            Assert(h < Size);
            __assume(l < Size);
            __assume(h < Size);
            if (l < Size && h < Size)
            {
                if (l == h)
                {
                    vec[l / wordSize] &= ~(1U << (l % wordSize));
                }
                else if (l < h)
                {
                    int lw = l / wordSize;
                    int hw = h / wordSize;
                    int lo = l % wordSize;
                    int hio = h % wordSize;
                    if (lw == hw)
                    {
                        clearrng(vec[lw], lo, hio);
                    }
                    else
                    {
                        clearrng(vec[lw], lo, wordSize - 1);
                        for (int w = lw + 1; w < hw; w++)
                        {
                            vec[w] = 0;
                        }
                        clearrng(vec[hw], 0, hio);
                    }
                }
            }
        }

        inline bool IsEmpty()
        {
            for (int i = 0; i < vecSize; i++)
            {
                if (vec[i] != 0)
                {
                    return false;
                }
            }
            return true;
        }

        inline void UnionInPlace(const CharBitvec& other)
        {
            for (int w = 0; w < vecSize; w++)
            {
                vec[w] |= other.vec[w];
            }
        }

        inline bool UnionInPlaceFullCheck(const CharBitvec& other)
        {
            bool isFull = true;
            for (int w = 0; w < vecSize; w++)
            {
                vec[w] |= other.vec[w];
                if (vec[w] != ones)
                {
                    isFull = false;
                }
            }
            return isFull;
        }

        inline bool Get(uint k) const
        {
            Assert(k < Size);
            __assume(k < Size);
            return ((vec[k / wordSize] >> (k % wordSize)) & 1) != 0;
        }

        inline bool IsFull() const
        {
            for (int w = 0; w < vecSize; w++)
            {
                if (vec[w] != ones)
                {
                    return false;
                }
            }
            return true;
        }

        inline bool IsSubsetOf(const CharBitvec& other) const
        {
            for (int w = 0; w < vecSize; w++)
            {
                uint32 v = other.vec[w];
                if (v != (vec[w] | v))
                {
                    return false;
                }
            }
            return true;
        }

        inline bool IsEqualTo(const CharBitvec& other) const
        {
            for (int w = 0; w < vecSize; w++)
            {
                if (vec[w] != other.vec[w])
                {
                    return false;
                }
            }
            return true;
        }

        uint Count() const;

        int NextSet(int k) const;
        int NextClear(int k) const;

        template <typename C>
        void ToComplement(ArenaAllocator* allocator, uint base, CharSet<C>& result) const;

        template <typename C>
        void ToEquivClass(ArenaAllocator* allocator, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset = 0x0) const;
    };

    template <typename C>
    class CharSet {};

    struct CharSetNode : protected Chars<char16>
    {
        static const int directBits = Chars<char>::CharWidth;
        static const uint directSize = Chars<char>::NumChars;

        static const uint bitsPerInnerLevel = 4;
        static const uint branchingPerInnerLevel = 1 << bitsPerInnerLevel;
        static const uint innerMask = branchingPerInnerLevel - 1;

        static const int bitsPerLeafLevel = CharBitvec::Width;
        static const int branchingPerLeafLevel = CharBitvec::Size;
        static const uint leafMask = branchingPerLeafLevel - 1;

        static const uint levels = 1 + (CharWidth - bitsPerLeafLevel) / bitsPerInnerLevel;

        inline static uint innerIdx(uint level, uint v)
        {
            return (v >> ((level + 1) * bitsPerInnerLevel)) & innerMask;
        }

        inline static uint indexToValue(uint level, uint index, uint offset)
        {
            Assert((index & innerMask) == index);
            Assert((uint)(1 << ((level + 1) * bitsPerInnerLevel)) > offset);

            return (index << ((level + 1) * bitsPerInnerLevel)) + offset;
        }

        inline static uint leafIdx(uint v)
        {
            return v & leafMask;
        }

        inline static uint lim(uint level)
        {
            return (1U << (bitsPerLeafLevel + level * bitsPerInnerLevel)) - 1;
        }

        inline static uint remain(uint level, uint v)
        {
            return v & lim(level);
        }

        virtual void FreeSelf(ArenaAllocator* allocator) = 0;
        virtual CharSetNode* Clone(ArenaAllocator* allocator) const = 0;
        virtual CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) = 0;
        virtual CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) = 0;
        virtual CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) = 0;
        virtual bool Get(uint level, uint k) const = 0;
        virtual void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const = 0;
        virtual void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const = 0;
        virtual void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const = 0;
        virtual bool IsSubsetOf(uint level, const CharSetNode* other) const = 0;
        virtual bool IsEqualTo(uint level, const CharSetNode* other) const = 0;
        virtual uint Count(uint level) const = 0;
        _Success_(return) virtual bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const = 0;
#if DBG
        virtual bool IsLeaf() const = 0;
#endif

        static CharSetNode* For(ArenaAllocator* allocator, int level);
    };

    struct CharSetFull : CharSetNode
    {
    private:
        template <typename C>
        void ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset = 0x0) const;
    public:
        static CharSetFull Instance;
        static CharSetFull * const TheFullNode;

        CharSetFull();

        void FreeSelf(ArenaAllocator* allocator) override;
        CharSetNode* Clone(ArenaAllocator* allocator) const override;
        CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) override;
        CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) override;
        CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) override;
        bool Get(uint level, uint k) const override;
        void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const override;
        void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const override;
        void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const override;
        bool IsSubsetOf(uint level, const CharSetNode* other) const override;
        bool IsEqualTo(uint level, const CharSetNode* other) const override;
        uint Count(uint level) const override;
        _Success_(return) bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const override;
#if DBG
        bool IsLeaf() const override;
#endif
    };

    struct CharSetInner sealed : CharSetNode
    {
    private:
        template <typename C>
        void ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result) const;
    public:
        CharSetNode * children[branchingPerInnerLevel];

        CharSetInner();
        void FreeSelf(ArenaAllocator* allocator) override;
        CharSetNode* Clone(ArenaAllocator* allocator) const override;
        CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) override;
        CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) override;
        CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) override;
        bool Get(uint level, uint k) const override;
        void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const override;
        void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const override;
        void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const override;
        bool IsSubsetOf(uint level, const CharSetNode* other) const override;
        bool IsEqualTo(uint level, const CharSetNode* other) const override;
        uint Count(uint level) const override;
        _Success_(return) bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const override;
#if DBG
        bool IsLeaf() const override;
#endif
    };

    struct CharSetLeaf sealed : CharSetNode
    {
    private:
        template <typename C>
        void ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset = 0x0) const;
    public:
        CharBitvec vec;

        CharSetLeaf();
        void FreeSelf(ArenaAllocator* allocator) override;
        CharSetNode* Clone(ArenaAllocator* allocator) const override;
        CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) override;
        CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) override;
        CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) override;
        bool Get(uint level, uint k) const override;
        void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const override;
        void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const override;
        void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const override;
        bool IsSubsetOf(uint level, const CharSetNode* other) const override;
        bool IsEqualTo(uint level, const CharSetNode* other) const override;
        uint Count(uint level) const override;
        _Success_(return) bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const override;
#if DBG
        bool IsLeaf() const override;
#endif
    };

    template <>
    class CharSet<char16> : private Chars<char16>
    {
    public:
        static const uint MaxCompact = 4;

        static const uint emptySlot = (uint)-1;

        struct CompactRep
        {
            // 1 + number of distinct characters, 1..MaxCompact+1
            size_t countPlusOne;
            // Characters, in no particular order, or (uint)-1 for tail empty slots
            uint cs[MaxCompact];
            uint8 padding[sizeof(CharBitvec) - sizeof(uint) * MaxCompact];
        };

        struct FullRep
        {
            // Trie for remaining characters. Pointer value will be 0 or >> MaxCompact.
            CharSetNode* root;
            // Entries for first 256 characters
            CharBitvec direct;
        };

        union Rep
        {
            struct CompactRep compact;
            struct FullRep full;
        } rep;

        static const int compactSize = sizeof(CompactRep);
        static const int fullSize = sizeof(FullRep);

        inline bool IsCompact() const { return rep.compact.countPlusOne - 1 <= MaxCompact; }
        void SwitchRepresentations(ArenaAllocator* allocator);
        void Sort();

    public:
        CharSet();
        void FreeBody(ArenaAllocator* allocator);
        void Clear(ArenaAllocator* allocator);
        void CloneFrom(ArenaAllocator* allocator, const CharSet<Char>& other);
        void CloneNonSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<Char>& other);
        void CloneSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<Char>& other);

        inline void Set(ArenaAllocator* allocator, Char kc) { SetRange(allocator, kc, kc); }

        void SetRange(ArenaAllocator* allocator, Char lc, Char hc);
        void SubtractRange(ArenaAllocator* allocator, Char lc, Char hc);
        void SetRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs);
        void SetNotRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs);
        void UnionInPlace(ArenaAllocator* allocator, const  CharSet<Char>& other);
        _Success_(return) bool GetNextRange(Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar);
        bool Get_helper(uint k) const;

        inline bool Get(Char kc) const
        {
            if (IsCompact())
            {
                Assert(MaxCompact == 4);
                return rep.compact.cs[0] == CTU(kc) ||
                    rep.compact.cs[1] == CTU(kc) ||
                    rep.compact.cs[2] == CTU(kc) ||
                    rep.compact.cs[3] == CTU(kc);
            }
            else
            {
                if (CTU(kc) < CharSetNode::directSize)
                {
                    return rep.full.direct.Get(CTU(kc));
                }
                else if (rep.full.root == 0)
                {
                    return false;
                }
                else
                {
                    return Get_helper(CTU(kc));
                }
            }
        }

        inline bool IsEmpty() const
        {
            return rep.compact.countPlusOne == 1;
        }

        inline bool IsSingleton() const
        {
            return rep.compact.countPlusOne == 2;
        }

        // Helpers to clean up the code

        inline uint GetCompactLength() const
        {
            Assert(IsCompact());
            return (uint)(rep.compact.countPlusOne - 1u);
        }

        inline void SetCompactLength(size_t length)
        {
            rep.compact.countPlusOne = length + 1;
        }

        inline uint GetCompactCharU(uint index) const
        {
            Assert(index < this->GetCompactLength());
            Assert(IsCompact());
            Assert(rep.compact.cs[index] <= MaxUChar);
            return rep.compact.cs[index];
        }

        inline Char GetCompactChar(uint index) const
        {
            return (Char)(GetCompactCharU(index));
        }

        //Replaces an existing character with a new value
        inline void ReplaceCompactCharU(uint index, uint value)
        {
            Assert(index < this->GetCompactLength());
            Assert(IsCompact());
            Assert(value <= MaxUChar);
            rep.compact.cs[index] = value;
        }

        inline void ClearCompactChar(uint index)
        {
            Assert(index < this->GetCompactLength());
            Assert(IsCompact());
            rep.compact.cs[index] = emptySlot;
        }

        // Adds the character to the end, assuming there is enough space. (Assert in place)
        // Increments count.
        inline void AddCompactCharU(uint value)
        {
            Assert(this->GetCompactLength() < MaxCompact);
            Assert(IsCompact());
            rep.compact.cs[this->GetCompactLength()] = value;
            rep.compact.countPlusOne += 1;
        }

        // Adds the character to the end, assuming there is enough space. (Assert in place)
        // Increments count.
        inline void AddCompactChar(Char value)
        {
            AddCompactCharU((Char)(value));
        }

        // This performs a check to see if the index is the last char, if so sets it to emptySlot
        // If not, replaces it with last index.
        inline void RemoveCompactChar(uint index)
        {
            Assert(index < this->GetCompactLength());
            Assert(IsCompact());

            if (index == this->GetCompactLength() - 1)
            {
                this->ClearCompactChar(index);
            }
            else
            {
                this->ReplaceCompactCharU(index, this->GetCompactCharU((uint)this->GetCompactLength() - 1));
            }

            rep.compact.countPlusOne -= 1;
        }

        inline char16 Singleton() const
        {
            Assert(IsSingleton());
            Assert(rep.compact.cs[0] <= MaxUChar);
            return UTC(rep.compact.cs[0]);
        }

        int GetCompactEntries(uint max, __out_ecount(max) Char* entries) const;

        bool IsSubsetOf(const CharSet<Char>& other) const;
        bool IsEqualTo(const CharSet<Char>& other) const;

        inline uint Count() const
        {
            if (IsCompact())
            {
                return (uint)rep.compact.countPlusOne - 1;
            }
            else if (rep.full.root == 0)
            {
                return rep.full.direct.Count();
            }
            else
            {
                //The bit vector
                Assert(rep.full.root == CharSetFull::TheFullNode || rep.full.root->Count(CharSetNode::levels - 1) <= 0xFF00);
                return rep.full.direct.Count() + (rep.full.root == CharSetFull::TheFullNode ? 0xFF00 : rep.full.root->Count(CharSetNode::levels - 1));
            }
        }

        // NOTE: These are not 'const' methods since they may sort the compact representation internally
        void ToComplement(ArenaAllocator* allocator, CharSet<Char>& result);
        void ToEquivClass(ArenaAllocator* allocator, CharSet<Char>& result);
        void ToEquivClassCP(ArenaAllocator* allocator, CharSet<codepoint_t>& result, codepoint_t baseOffset);
#if ENABLE_REGEX_CONFIG_OPTIONS
        void Print(DebugWriter* w) const;
#endif
    };

    template <>
    class CharSet<codepoint_t> : private Chars<codepoint_t>
    {
        static const int NumberOfPlanes = 17;
    private:
        // Character planes are composed of 65536 characters each.
        // First plane is the Basic Multilingual Plane (characters 0 - 65535)
        // Every subsequent plane also stores characters in the form [0 - 65535]; to get the actual value, add 'index * 0x10000' to it
        CharSet<char16> characterPlanes[NumberOfPlanes];

        // Takes a character, and returns the index of the CharSet<char16> that holds it.
        inline int CharToIndex(Char c) const
        {
            Assert(c <= Chars<codepoint_t>::MaxUChar);
            return (int)(CTU(c) / (Chars<char16>::MaxUChar + 1));
        }

        // Takes a character, and removes the offset to make it < 0x10000
        inline char16 RemoveOffset(Char c) const
        {
            Assert(c <= Chars<codepoint_t>::MaxUChar);
            return (char16)(CTU(c) % 0x10000);
        }

        // Takes a character, and removes the offset to make it < 0x10000
        inline Char AddOffset(char16 c, int index) const
        {
            Assert(c <= Chars<char16>::MaxUChar);
            Assert(index >= 0);
            Assert(index < NumberOfPlanes);
            return ((Char)c) + 0x10000 * index;
        }

    public:
        CharSet();
        void FreeBody(ArenaAllocator* allocator);
        void Clear(ArenaAllocator* allocator);
        void CloneFrom(ArenaAllocator* allocator, const CharSet<Char>& other);
        void CloneSimpleCharsTo(ArenaAllocator* allocator, CharSet<char16>& other) const;

        inline void CloneNonSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<char16>& other)
        {
            Assert(this->SimpleCharCount() > 0);
            AssertMsg(this->ContainSurrogateCodeUnits(), "This doesn't contain surrogate code units, a simple clone is faster.");
            this->characterPlanes[0].CloneNonSurrogateCodeUnitsTo(allocator, other);
        }

        inline void CloneSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<char16>& other)
        {
            Assert(this->SimpleCharCount() > 0);
            AssertMsg(this->ContainSurrogateCodeUnits(), "This doesn't contain surrogate code units, will not produce any result.");
            this->characterPlanes[0].CloneSurrogateCodeUnitsTo(allocator, other);
        }

        inline void Set(ArenaAllocator* allocator, Char kc) { SetRange(allocator, kc, kc); }

        inline bool ContainSurrogateCodeUnits()
        {
            char16 outLower = 0xFFFF, ignore = 0x0;
            return this->characterPlanes[0].GetNextRange(0xD800, &outLower, &ignore) ? outLower <= 0xDFFF : false;
        }

        void SetRange(ArenaAllocator* allocator, Char lc, Char hc);
        void SetRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs);
        void SetNotRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs);
        void UnionInPlace(ArenaAllocator* allocator, const  CharSet<Char>& other);
        void UnionInPlace(ArenaAllocator* allocator, const  CharSet<char16>& other);
        _Success_(return) bool GetNextRange(Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar);

        inline bool Get(Char kc) const
        {
            return this->characterPlanes[CharToIndex(kc)].Get(RemoveOffset(kc));
        }

        inline bool IsEmpty() const
        {
            for (int i = 0; i < NumberOfPlanes; i++)
            {
                if (!this->characterPlanes[i].IsEmpty())
                {
                    return false;
                }
            }

            return true;
        }

        inline bool IsSimpleCharASingleton() const
        {
            return this->characterPlanes[0].IsSingleton();
        }

        inline char16 SimpleCharSingleton() const
        {
            return this->characterPlanes[0].Singleton();
        }

        inline bool IsSingleton() const
        {
            return this->Count() == 1;
        }

        inline codepoint_t Singleton() const
        {
            Assert(IsSingleton());

            for (int i = 0; i < NumberOfPlanes; i++)
            {
                if (this->characterPlanes[i].IsSingleton())
                {
                    return AddOffset(this->characterPlanes[i].Singleton(), i);
                }
            }

            AssertMsg(false, "Should not reach here, first Assert verifies we are a singleton.");
            return INVALID_CODEPOINT;
        }

        bool IsSubsetOf(const CharSet<Char>& other) const;
        bool IsEqualTo(const CharSet<Char>& other) const;

        inline uint Count() const
        {
            uint totalCount = 0;

            for (int i = 0; i < NumberOfPlanes; i++)
            {
                totalCount += this->characterPlanes[i].Count();
            }

            return totalCount;
        }

        inline uint SimpleCharCount() const
        {
            return this->characterPlanes[0].Count();
        }

        // NOTE: These are not 'const' methods since they may sort the compact representation internally
        void ToComplement(ArenaAllocator* allocator, CharSet<Char>& result);
        void ToSimpleComplement(ArenaAllocator* allocator, CharSet<codepoint_t>& result);
        void ToSimpleComplement(ArenaAllocator* allocator, CharSet<char16>& result);
        void ToEquivClass(ArenaAllocator* allocator, CharSet<Char>& result);
        void ToSurrogateEquivClass(ArenaAllocator* allocator, CharSet<Char>& result);
#if ENABLE_REGEX_CONFIG_OPTIONS
        void Print(DebugWriter* w) const;
#endif
    };


    template <>
    class RuntimeCharSet<char16> : private Chars<char16>
    {
    private:
        // Trie for remaining characters. Pointer value will be 0 or >> MaxCompact.
        CharSetNode * root;
        // Entries for first 256 characters
        CharBitvec direct;

    public:
        RuntimeCharSet();
        void FreeBody(ArenaAllocator* allocator);
        void CloneFrom(ArenaAllocator* allocator, const CharSet<Char>& other);
        bool Get_helper(uint k) const;

        inline bool Get(Char kc) const
        {
            if (CTU(kc) < CharSetNode::directSize)
            {
                return direct.Get(CTU(kc));
            }
            else if (root == 0)
            {
                return false;
            }
            else
            {
                return Get_helper(CTU(kc));
            }
        }

#if ENABLE_REGEX_CONFIG_OPTIONS
        void Print(DebugWriter* w) const;
#endif
    };

    typedef CharSet<char16> UnicodeCharSet;
    typedef RuntimeCharSet<char16> UnicodeRuntimeCharSet;
}