avl-critical-pair.h

Go to the documentation of this file.

/* 
 * Copyright (C) 2015 Antoine Joux, Vanessa Vitse and Titouan Coladon
 * 
 * This file is part of openf4.
 * 
 * openf4 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.
 * 
 * openf4 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 openf4.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef OPENF4_AVL_CRITICAL_PAIR_H
#define OPENF4_AVL_CRITICAL_PAIR_H

#include "global.h"
#include <iostream>
#include <cassert>
#include <iomanip>
#include "critical-pair.h"
#include "dynamic-array.h"

namespace F4
{
    template<typename Element>
    struct NodeAvlCriticalPair
    {        
        public:
            
            /* Constructor */
            
            NodeAvlCriticalPair();
            
            /* Attributes */
        
            CriticalPair<Element> _cp; 
            signed char _bf; 
            NodeAvlCriticalPair* _parent; 
            NodeAvlCriticalPair* _left; 
            NodeAvlCriticalPair* _right; 
    };
    
    template<typename Element>
    void printNode(NodeAvlCriticalPair<Element> * p, int indent=0);
    
    
    template<typename Element>
    class AvlCriticalPair
    {        
        public:
            
            /* Constructor */
            
            AvlCriticalPair();
            
            
            /* Miscellaneous */
            
            void printAvlCriticalPair(std::ostream & stream) const;
            
            void reset();
            
            size_t size() const;
            
            bool isEmpty() const;
            
            void testAVL();
            
            /* Insertion */
            
            int insert(CriticalPair<Element> cp);
            
            
            /* Deletion */
            
            NodeAvlCriticalPair<Element> * erase(NodeAvlCriticalPair<Element> * node);
            
            
            /* Search */
            
            NodeAvlCriticalPair<Element> * findBiggest ();
            
            NodeAvlCriticalPair<Element> const * findBiggest () const;
            
            NodeAvlCriticalPair<Element> * findNextBiggest(NodeAvlCriticalPair<Element> * node);
            
            NodeAvlCriticalPair<Element> const * findNextBiggest(NodeAvlCriticalPair<Element> const * node) const;
            
            NodeAvlCriticalPair<Element> * findSmallest ();
            
            NodeAvlCriticalPair<Element> const * findSmallest () const;
            
            NodeAvlCriticalPair<Element> * findNextSmallest(NodeAvlCriticalPair<Element> * node);
            
            NodeAvlCriticalPair<Element> const * findNextSmallest(NodeAvlCriticalPair<Element> const * node) const;
        
        private:
            DynamicArray<NodeAvlCriticalPair<Element>> _array; 
            NodeAvlCriticalPair<Element> * _it; 
            NodeAvlCriticalPair<Element> * _root; 
            size_t _size; 
    };
    
    template <typename Element>
    std::ostream & operator<<(std::ostream & stream, AvlCriticalPair<Element> const & avlCriticalPair);
}

#include "../src/avl-critical-pair.inl"
#endif // OPENF4_AVL_CRITICAL_PAIR_H