AIKBSplayTree.h

Go to the documentation of this file.

//    Copyright (C) 2004-2007 Dylan Blair
//
//    email: dblair@alumni.cs.utexas.edu
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 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
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#ifndef AIKBSPLAYTREE_H
#define AIKBSPLAYTREE_H

#include "AIKB.h"

namespace OpenSkyNet {
    namespace AI {
        class KBSplayTree : public KB {
            class BinaryNode {
                std::list<Record> _records;
                BinaryNode *_left, *_right;

                BinaryNode() : _left(0), _right(0) {}
                BinaryNode(const std::list<Record>& records_, BinaryNode* left_, BinaryNode* right_)
                    : _records(records_), _left(left_), _right(right_) {}

                friend class KBSplayTree;
            };

            BinaryNode* _root;
            int _size;

            void reclaimMemory(BinaryNode* t) const;

            BinaryNode* clone(BinaryNode* t) const;

            float calcStateScore(int stateId, BinaryNode* t, bool first) const;


            void rotateWithLeftChild(BinaryNode*& k2) const;
            void rotateWithRightChild(BinaryNode*& k1) const;

            void splay(const Record& x, BinaryNode*& t) const;
        public:
            KBSplayTree() : _root(0), _size(0) {}
            KBSplayTree(int maxRecords_, unsigned int reservedRecords_, 
                unsigned int initParamsSizeOfReservedRecords_) : KB(maxRecords_,
                reservedRecords_,initParamsSizeOfReservedRecords_), _root(0), _size(0) {}
            KBSplayTree(const KBSplayTree& rhs_) { *this = rhs_; }
            const KBSplayTree& operator=(const KBSplayTree& rhs_);
            virtual ~KBSplayTree() { clear(); }

            virtual bool add(const Record& record_, bool disallowIfPremNameExists_=false);
            virtual void remove(const Record& record_, bool all_, int numOfParamsToCheck_=-1);
            virtual const std::list<Record>& find(const Record& record_);
            virtual bool isEmpty() const;
            virtual void clear();
            virtual int size() const;
            virtual float calcStateScore(int stateId_) const;
        };
    }
}

#endif //AIKBSPLAYTREE_H