/*

   Copyright (C) 2008 Apple, Inc

   This library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Library General Public

   License as published by the Free Software Foundation; either

   version 2 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public License

   along with this library; see the file COPYING.LIB.  If not, write to

   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

   Boston, MA 02110-1301, USA.

 */

#ifndef SVGGlyphMap_h

#define SVGGlyphMap_h

#if ENABLE(SVG_FONTS)

#include "SVGGlyphElement.h"

namespace WebCore {

    struct GlyphMapNode;

    typedef HashMap<UChar, RefPtr<GlyphMapNode> > GlyphMapLayer;

    struct GlyphMapNode : public RefCounted<GlyphMapNode> {

    private:

        GlyphMapNode() { }

    public:

        static PassRefPtr<GlyphMapNode> create() { return adoptRef(new GlyphMapNode); }

        Vector<SVGGlyphIdentifier> glyphs;

        GlyphMapLayer children;

    };

    class SVGGlyphMap {

    public:

        SVGGlyphMap() : m_currentPriority(0) { }

        void add(const String& string, const SVGGlyphIdentifier& glyph) 

        {

            size_t len = string.length();

            GlyphMapLayer* currentLayer = &m_rootLayer;

            RefPtr<GlyphMapNode> node;

            for (size_t i = 0; i < len; i++) {

                UChar curChar = string[i];

                node = currentLayer->get(curChar);

                if (!node) {

                    node = GlyphMapNode::create();

                    currentLayer->set(curChar, node);

                }

                currentLayer = &node->children;

            }

            if (node) {

                node->glyphs.append(glyph);

                node->glyphs.last().priority = m_currentPriority++;

                node->glyphs.last().nameLength = len;

                node->glyphs.last().isValid = true;

            }

        }

        static inline bool compareGlyphPriority(const SVGGlyphIdentifier& first, const SVGGlyphIdentifier& second)

        {

            return first.priority < second.priority;

        }

        void get(const String& string, Vector<SVGGlyphIdentifier>& glyphs)

        {

            GlyphMapLayer* currentLayer = &m_rootLayer;

            for (size_t i = 0; i < string.length(); i++) {

                UChar curChar = string[i];

                RefPtr<GlyphMapNode> node = currentLayer->get(curChar);

                if (!node)

                    break;

                glyphs.append(node->glyphs);

                currentLayer = &node->children;

            }

            std::sort(glyphs.begin(), glyphs.end(), compareGlyphPriority);

        }

        void clear() 

        { 

            m_rootLayer.clear(); 

            m_currentPriority = 0;

        }

    private:

        GlyphMapLayer m_rootLayer;

        int m_currentPriority;

    };

}

#endif // ENABLE(SVG_FONTS)

#endif //SVGGlyphMap_h