ItemSetTree.h

/**************************************************************************
 * Copyright (c) 2007 Clifford Conley Owens III                           *
 *                                                                        *
 * This file is part of Biorithm.                                         *
 *                                                                        *
 * Biorithm is free software: you can redistribute it and/or modify       *
 * it under the terms of the GNU General Public License as published by   *
 * the Free Software Foundation, either version 3 of the License, or      *
 * (at your option) any later version.                                    *
 *                                                                        *
 * Biorithm 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 General Public License for more details.                           *
 *                                                                        *
 * You should have received a copy of the GNU General Public License      *
 * along with Biorithm.  If not, see <http://www.gnu.org/licenses/>.      *
 *                                                                        *
 **************************************************************************/

#ifndef ITEMSETTREE_H
#define ITEMSETTREE_H

#define SIZE_BYTE 8

// ---------------------------- Internal Headers ---------------------------- //

#include "ItemSet.h"

template <typename t> class ItemSetTree
{
    public:
        struct node
        {
            struct node* parent;
            vector<struct node*> derivs;
            t val;
        };
    
    private:
        // The set of items
        struct node root;

        // The number of different items
        unsigned int max;

        // The total size
        unsigned int tsize;

        // The livel sizes
        vector<unsigned int> lsizes;

        // The last position
        struct node* lastpos;

        // The itemset representing the last position
        ItemSet lastis;

        // Helper methods
        void copy(struct node* target, const struct node* subroot)
        {
            target->val = subroot->val;
            for (unsigned int i = 0; i < subroot->derivs.size(); i++)
            {
                if (subroot->derivs[i])
                {
                    target->derivs[i] = new struct node;
                    target->derivs[i]->parent = target->derivs[i];
                    target->derivs[i]->derivs.resize(
                        subroot->derivs[i]->derivs.size(), NULL);
                    copy(target->derivs[i], subroot->derivs[i]);
                }
            }
        }

        void clearHelper(struct node* subroot)
        {
            // Go through all the potential children of the subroot 
            for (unsigned int i = 0; i < subroot->derivs.size(); i++)
            {
                if (subroot->derivs[i])
                {
                    clearHelper(subroot->derivs[i]);
                    delete subroot->derivs[i];
                }
            }
        }


    public:
        class ConstIterator;

        // The iterator class
        class Iterator
        {
            private:
                struct node* pos;
                ItemSet is;
                unsigned int max;

            public:
                Iterator(struct node* pos = NULL, unsigned int max = 0)
                {
                    this->pos = pos;
                    this->max = max;
                }

                Iterator(const Iterator& src)
                {
                    *this = src;
                }

                ~Iterator()
                {

                }

                Iterator& operator =(const Iterator& rhs)
                {
                    pos = rhs.pos;
                    is = rhs.is;
                    max = rhs.max;
                }

                bool operator ==(const Iterator& rhs) const
                {
                    return pos == rhs.pos;
                }

                bool operator !=(const Iterator& rhs) const
                {
                    return pos != rhs.pos;
                }

                t& operator *() const
                {
                    return pos->val;
                }

                void advance_down()
                {
                    // Make sure we aren't already at the end
                    if (pos == NULL)
                    {
                        return;
                    }

                    int lastindex = (int)is.size() - 1;
                    int pitem;
                    if (lastindex == -1)
                    {
                        pitem = -1;
                    }
                    else
                    {
                        pitem = is[lastindex];
                    }
                    for (unsigned int i = 0; i < (max - pitem) - 1; i++)
                    {
                        if (pos->derivs[i])
                        {
                            advance_down(i + pitem + 1);
                            return;
                        }
                    }
                    pos = NULL;
                }

                void advance_down(unsigned int item)
                {
                    // Make sure we aren't already at the end
                    if (pos == NULL)
                    {
                        return;
                    }

                    int lastindex = is.size() - 1;
                    int pitem;
                    if (lastindex == -1)
                    {
                        pitem = -1;
                    }
                    else
                    {
                        pitem = is[lastindex];
                    }
                    if (pos->derivs[(item - pitem) - 1])
                    {
                        pos = pos->derivs[(item - pitem) - 1];
                        is.insert(item);
                        return;
                    }
                    pos = NULL;
                }

                void setval(const t& val)
                {
                    pos->val = val;
                }

                const ItemSet& itemset() const
                {
                    return is;
                }

                friend class ConstIterator;
        };

        // The const iterator class
        class ConstIterator
        {
            private:
                const struct node* pos;
                ItemSet is;
                unsigned int max;

            public:
                ConstIterator(const struct node* pos = NULL,
                    unsigned int max = 0)
                {
                    this->pos = pos;
                    this->max = max;
                }

                ConstIterator(const ConstIterator& src)
                {
                    *this = src;
                }

                ~ConstIterator()
                {

                }

                ConstIterator(const Iterator& src)
                {
                    *this = src;
                }

                ConstIterator& operator =(const ConstIterator& rhs)
                {
                    pos = rhs.pos;
                    is = rhs.is;
                    max = rhs.max;
                }

                ConstIterator& operator =(const Iterator& rhs)
                {
                    pos = rhs.pos;
                    is = rhs.is;
                    max = rhs.max;
                }

                bool operator ==(const ConstIterator& rhs) const
                {
                    return pos == rhs.pos;
                }

                bool operator !=(const ConstIterator& rhs) const
                {
                    return pos != rhs.pos;
                }

                const t& operator *() const
                {
                    return pos->val;
                }

                void advance_up()
                {
                    // Make sure we aren't already at the end
                    if (pos == NULL)
                    {
                        return;
                    }

                    if (!is.empty()) 
                    {
                        is.remove();
                    }
                    pos = pos->parent;
                }

                void advance_down()
                {
                    // Make sure we aren't already at the end
                    if (pos == NULL)
                    {
                        return;
                    }

                    int lastindex = (int)is.size() - 1;
                    int pitem;
                    if (lastindex == -1)
                    {
                        pitem = -1;
                    }
                    else
                    {
                        pitem = is[lastindex];
                    }
                    for (unsigned int i = 0; i < (max - pitem) - 1; i++)
                    {
                        if (pos->derivs[i])
                        {
                            advance_down(i + pitem + 1);
                            return;
                        }
                    }
                    pos = NULL;
                }

                void advance_down(unsigned int item)
                {
                    // Make sure we aren't already at the end
                    if (pos == NULL)
                    {
                        return;
                    }

                    int lastindex = is.size() - 1;
                    int pitem;
                    if (lastindex == -1)
                    {
                        pitem = -1;
                    }
                    else
                    {
                        pitem = is[lastindex];
                    }
                    if (pos->derivs[(item - pitem) - 1])
                    {
                        pos = pos->derivs[(item - pitem) - 1];
                        is.insert(item);
                        return;
                    }
                    pos = NULL;
                }

                void advance_rightp()
                {
                    // Make sure we aren't already at the end
                    if (pos == NULL)
                    {
                        return;
                    }

                    // No move to the right keeping the same parent
                    int lastindex = is.size() - 1;
                    if (lastindex == -1)
                    {
                        pos = NULL;
                        return;
                    }
                    unsigned int curitem = is[lastindex];
                    int pitem;
                    if (!lastindex)
                    {
                        pitem = -1;
                    }
                    else
                    {
                        pitem = is[lastindex - 1];
                    }
                    advance_up();
                    for (unsigned int i = curitem - pitem;
                        i < (max - pitem) - 1; i++)
                    {
                        if (pos->derivs[i])
                        {
                            advance_down(pitem + i + 1);
                            return;
                        }
                    }
                    pos = NULL;
                }

                void advance_right()
                {
                    // Make sure we aren't already at the end
                    if (pos == NULL)
                    {
                        return;
                    }

                    // First let's just see if we can move right with respect
                    // to a parent
                    ConstIterator iterbu = *this;
                    advance_rightp();
                    if (pos != NULL)
                    {
                        return;
                    }

                    // We must move upward, so let's start over
                    *this = iterbu;
                    advance_up();
                    advance_right();
                    iterbu = *this;
                    advance_down();
                    while (!pos)
                    {
                        *this = iterbu;
                        advance_right();
                        if (!pos)
                        {
                            return;
                        }
                        iterbu = *this;
                        advance_down();
                    }
                }

                const ItemSet& itemset() const
                {
                    return is;
                }
        };

        ItemSetTree(unsigned int max = 0)
        {
            this->max = max;
            root.derivs.resize(max, NULL);
            root.parent = NULL;
            tsize = 1;
            lsizes.push_back(1);
            lastpos = &root;
        }

        ItemSetTree(const ItemSetTree& src)
        {
            *this = src;
        }

        ~ItemSetTree()
        {
            clear();
        }

        ItemSetTree& operator =(const ItemSetTree& rhs)
        {
            clear();
            max = rhs.max;
            tsize = rhs.tsize;
            lsizes = rhs.lsizes;
            root.derivs.resize(max, NULL);
            copy(&root, &rhs.root);
            // lastpos broken on copy
            lastpos = &root;
            return *this;
        }

        void clear()
        {
            clearHelper(&root);
            for (unsigned int i = 0; i < max; i++)
            {
                root.derivs[i] = NULL;
            }
        }

        Iterator end()
        {
            return Iterator(NULL, max);
        }

        ConstIterator end() const
        {
            return ConstIterator(NULL, max);
        }

    private:

        Iterator begin_down(const Iterator& iter, unsigned int level)
        {
            if (!level)
            {
                return iter;
            }

            Iterator c = end();
            int start;
            if (iter.itemset().empty())
            {
                start = 0;
            }
            else
            {
                start = iter.itemset().back() + 1;
            }
            for (unsigned int i = start; i < max && c == end(); i++)
            {
                c = iter;
                c.advance_down(i);
                if (c != end())
                {
                    c = begin_down(c, level - 1);
                }
            }
            return c;
        }

    public:

        Iterator begin()
        {
            return Iterator(&root, max);
        }

        ConstIterator begin() const
        {
            return ConstIterator(&root, max);
        }

        Iterator begin(unsigned int level)
        {
            return begin_down(begin(), level);
        }

        ConstIterator begin(unsigned int level) const
        {
            return begin_down(begin(), level);
        }

        Iterator find(const ItemSet& is)
        {
            Iterator iter = begin();
            for (unsigned int i = 0; i < is.size() && iter != end(); i++)
            {
                iter.advance_down(is[i]);
            }
            return iter;
        }

        ConstIterator find(const ItemSet& is) const
        {
            ConstIterator iter = begin();
            for (unsigned int i = 0; i < is.size() && iter != end(); i++)
            {
                iter.advance_down(is[i]);
            }
            return iter;
        }

        unsigned int size() const
        {
            return tsize;
        }

        unsigned int size(unsigned int level) const
        {
            if (level < lsizes.size()) 
            {
                return lsizes[level];
            }
            return 0;
        }

        bool empty() const
        {
            return !tsize;
        }

        bool empty(unsigned int level) const
        {
            return !size(level);
        }

        void insert(const ItemSet& is, const t& val)
        {
            // Broken if we have not built the tree up
            struct node* pos = &root;
            int previtem = -1;
            int lastindex = is.size() - 1;
            for (int i = 0; pos && i < lastindex; i++)
            {
                pos = pos->derivs[(is[i] - previtem) - 1];
                previtem = is[i];
            }
            unsigned int lastitem = (is[lastindex] - previtem) - 1;
            pos->derivs[lastitem] = new struct node;
            pos->derivs[lastitem]->parent = pos;
            pos->derivs[lastitem]->val = val;
            pos->derivs[lastitem]->derivs.resize((max - is.back()) - 1, NULL);
            lastpos = pos->derivs[lastitem];
            lastis = is;
            if (lsizes.size() <= is.size())
            {
                lsizes.resize(is.size() + 1, 0);
            }
            lsizes[is.size()]++;
            tsize++;
        }

        void remove()
        {
            struct node* temppos = lastpos->parent;
            int pitem;
            if (lastis.size() < 2)
            {
                pitem = -1;
            }
            else
            {
                pitem = lastis[lastis.size() - 2];
            }
            temppos->derivs[(lastis.back() - pitem) - 1] = NULL;
            delete lastpos;
            lastpos = temppos;
            lsizes[lastis.size()]--;
            tsize--;
            lastis.remove();
        }

        void setval(const t& val) const
        {
            lastpos->val = val;
        }

        t& getval() const
        {
            return lastpos->val;
        }
};

#endif