avl-monomial.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_MONOMIAL_H
#define OPENF4_AVL_MONOMIAL_H

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

namespace F4
{
    struct NodeAvlMonomial
    {        
        public:
            
            /* Constructor */
            
            NodeAvlMonomial();
            
            /* Attributes */
        
            int _numMonomial; 
            bool _lt; 
            signed char _bf; 
            NodeAvlMonomial* _parent; 
            NodeAvlMonomial* _left; 
            NodeAvlMonomial* _right; 
    };
    
    void printNode(NodeAvlMonomial * p, int indent=0);
    
    
    class AvlMonomial
    {        
        public:
            
            /* Constructor */
            
            AvlMonomial();
            
            
            /* Miscellaneous */
            
            void printAvlMonomial(std::ostream & stream) const;
            
            void reset();
            
            size_t size() const;
            
            void setLT(int numMon);
            
            
            /* Insertion */
            
            int insert(int numMon, bool lt);
            
            
            /* Search */
            
            NodeAvlMonomial * findBiggest ();
            
            NodeAvlMonomial * findNextBiggest(NodeAvlMonomial * node);
        
        private:
            DynamicArray<NodeAvlMonomial> _array; 
            unordered_set<int> _umon; 
            unordered_set<int> _lt; 
            NodeAvlMonomial * _it; 
            NodeAvlMonomial * _root; 
            NodeAvlMonomial _node; 
    };
    
    
    /* External operators */
    
    template <typename dataType>
    std::ostream & operator<<(std::ostream & stream, AvlMonomial const & avlMonomial);
}

#include "../src/avl-monomial.inl"
#endif // OPENF4_AVL_MONOMIAL_H