avl-polynomial.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_POLYNOMIAL_H
#define OPENF4_AVL_POLYNOMIAL_H

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

namespace F4
{
    struct NodeAvlPolynomial
    {        
        public:
            
            /* Constructor */
            
            NodeAvlPolynomial();
            
            /* Attributes */
        
            int _numPolynomial; 
            int _numMonomial; 
            int _nbTerms; 
            signed char _bf; 
            NodeAvlPolynomial* _parent; 
            NodeAvlPolynomial* _left; 
            NodeAvlPolynomial* _right; 
    };
    
    void printNode(NodeAvlPolynomial * p, int indent=0);
    
    
    class AvlPolynomial
    {        
        public:
            
            /* Constructor */
            
            AvlPolynomial();
            
            
            /* Miscellaneous */
            
            void printAvlPolynomial(std::ostream & stream) const;
            
            void reset();
            
            size_t size() const;
            
            /* Insertion */
            
            int insert(int numPol, int numMon, int nbTerms);
            
            
            /* Search */
            
            NodeAvlPolynomial * findBiggest ();
            
            NodeAvlPolynomial const * findBiggest () const;
            
            NodeAvlPolynomial * findNextBiggest(NodeAvlPolynomial * node);
            
            NodeAvlPolynomial const * findNextBiggest(NodeAvlPolynomial const * node) const;
        
        private:
            DynamicArray<NodeAvlPolynomial> _array; 
            NodeAvlPolynomial * _it; 
            NodeAvlPolynomial * _root; 
            size_t _size; 
    };
    
    
    /* External operators */
    
    template <typename dataType>
    std::ostream & operator<<(std::ostream & stream, AvlPolynomial const & AvlPolynomial);
}

#include "../src/avl-polynomial.inl"
#endif // OPENF4_AVL_POLYNOMIAL_H