KSG-Framework/Trie.h

#pragma once

#include "CharMap.h"

namespace Framework
{
    template<class T, class M> struct TrieIteratorData
    {
        M* map;
        TrieIteratorData* parent;

        TrieIteratorData()
        {
            map = 0;
            parent = 0;
        }

        TrieIteratorData(M* zMap, TrieIteratorData parent)
        {
            map = zMap;
            this->parent = new TrieIteratorData(parent);
        }

        TrieIteratorData(const TrieIteratorData& data)
        {
            map = data.map;
            if (data.parent)
                parent = new TrieIteratorData(*data.parent);
            else
                parent = 0;
        }

        ~TrieIteratorData()
        {
            delete parent;
        }

        TrieIteratorData& operator=(const TrieIteratorData& data)
        {
            map = data.map;
            TrieIteratorData* tmp = parent;
            if (data.parent)
                parent = new TrieIteratorData(*data.parent);
            else
                parent = 0;
            delete tmp;
            return *this;
        }

        void set(M* zMap, TrieIteratorData parent)
        {
            map = zMap;
            parent = new TrieIteratorData(parent);
        }
    };

    template<class T, class M> class TrieIterator
    {
    private:
        TrieIteratorData<T, M> data;

    public:
        TrieIterator(TrieIteratorData<T, M> data)
        {
            this->data = data;
        }

        TrieIterator next()
        {
            for (unsigned char i = 0; true; i++)
            {
                if (data.map->z(i))
                    return TrieIterator(
                        TrieIteratorData<T, M>(data.map->z(i)->map, data));
                if (i == 255) break;
            }
            if (!data.parent || !data.parent->map)
                return TrieIterator(
                    TrieIteratorData<T, M>(0, TrieIteratorData<T, M>()));
            TrieIteratorData<T, M> d = data;
            do
            {
                for (unsigned char i = 0; true; i++)
                {
                    if (d.parent->map->z(i)
                        && d.parent->map->z(i)->map == d.map)
                    {
                        if (i < 256)
                        {
                            for (unsigned char j = (unsigned char)(i + 1); true;
                                 j++)
                            {
                                if (d.parent->map->z(j))
                                    return TrieIterator(TrieIteratorData<T, M>(
                                        d.parent->map->z(j)->map, *d.parent));
                                if (j == 255) break;
                            }
                        }
                        d = *d.parent;
                        break;
                    }
                    if (i == 255) break;
                }
            } while (d.parent && d.parent->map);
            return TrieIterator(TrieIteratorData<T, M>(0, TrieIteratorData<T, M>()));
        }

        TrieIterator& operator++() //! prefix
        {
            data = next().data;
            return *this;
        }

        TrieIterator operator++(int) //! postfix
        {
            TrieIterator temp(*this);
            data = next().data;
            return temp;
        }

        operator bool()
        {
            return data.map != 0;
        }

        operator T*()
        {
            return data.map->zValue();
        }

        T* operator->()
        {
            return data.map->zValue();
        }

        T* val()
        {
            return data.map->zValue();
        }
    };

    template<class T> class Trie : public virtual ReferenceCounter
    {
    private:
        CharMap<Trie<T>, T>* map;

    public:
        Trie()
            : ReferenceCounter()
        {
            map = new CharMap<Trie<T>, T>();
        }

        ~Trie()
        {
            map->release();
        }

        void set(const char* addr, int addrLen, T value)
        {
            if (!addrLen)
                map->setValue(value);
            else
            {
                if (!map->z(*addr)) map->set(*addr, new Trie<T>());
                map->z(*addr)->set(addr + 1, addrLen - 1, value);
            }
        }

        void remove(const char* addr, int addrLen)
        {
            if (!addrLen)
                map->setValue(0);
            else
            {
                if (!map->z(*addr)) return;
                map->z(*addr)->remove(addr + 1, addrLen - 1);
            }
        }

        T get(const char* addr, int addrLen) const
        {
            if (!addrLen)
                return map->getValue();
            else
            {
                if (!map->z(*addr)) return 0;
                return map->z(*addr)->get(addr + 1, addrLen - 1);
            }
        }

        void leeren()
        {
            map->release();
            map = new CharMap<Trie<T>, T>();
        }

        TrieIterator<T, CharMap<Trie<T>, T>> getIterator()
        {
            return TrieIterator<T, CharMap<Trie<T>, T>>(
                TrieIteratorData<T, CharMap<Trie<T>, T>>(
                map, TrieIteratorData<T, CharMap<Trie<T>, T>>()));
        }

        friend TrieIterator<T, CharMap<Trie<T>, T>>;
    };

    template<class T> class RCTrie : public virtual ReferenceCounter
    {
    private:
        RCCharMap<RCTrie<T>, T>* map;

    public:
        RCTrie()
            : ReferenceCounter()
        {
            map = new RCCharMap<RCTrie<T>, T>();
        }

        ~RCTrie()
        {
            map->release();
        }

        void set(const char* addr, int addrLen, T* value)
        {
            if (!addrLen)
                map->setValue(value);
            else
            {
                if (!map->z(*addr)) map->set(*addr, new RCTrie<T>());
                map->z(*addr)->set(addr + 1, addrLen - 1, value);
            }
        }

        void remove(const char* addr, int addrLen)
        {
            if (!addrLen)
                map->setValue(0);
            else
            {
                if (!map->z(*addr)) return;
                map->z(*addr)->remove(addr + 1, addrLen - 1);
            }
        }

        T* get(const char* addr, int addrLen)
        {
            if (!addrLen)
                return map->getValue();
            else
            {
                if (!map->z(*addr)) return 0;
                return map->z(*addr)->get(addr + 1, addrLen - 1);
            }
        }

        T* z(const char* addr, int addrLen) const
        {
            if (!addrLen)
                return map->zValue();
            else
            {
                if (!map->z(*addr)) return 0;
                return map->z(*addr)->z(addr + 1, addrLen - 1);
            }
        }

        void leeren()
        {
            map->release();
            map = new RCCharMap<RCTrie<T>, T>();
        }

        TrieIterator<T, RCCharMap<RCTrie<T>, T>> getIterator()
        {
            return TrieIterator<T, RCCharMap<RCTrie<T>, T>>(
                TrieIteratorData<T, RCCharMap<RCTrie<T>, T>>(
                map, TrieIteratorData<T, RCCharMap<RCTrie<T>, T>>()));
        }

        friend TrieIterator<T, RCCharMap<RCTrie<T>, T>>;
    };
} // namespace Framework