BasicEnumeration.h

Go to the documentation of this file.

#pragma once

#include "EnumerationInference.h"

// We require that each NT leads to a nonterminal -- if not, we
// can run into problem where some integers do not map to trees. In this case,
// we throw this assumption
struct EnumerationNotInjectiveException : std::exception {};

template<typename Grammar_t>
class BasicEnumeration {
public:

    Grammar_t* grammar;

    BasicEnumeration(Grammar_t* g) : grammar(g) {}
    
    virtual Node toNode(IntegerizedStack& is, const nonterminal_t& nt)  {
    
        // NOTE: for now this doesn't work when nt only has finitely many expansions/trees
        // below it. Otherwise we'll get an assertion error eventually.
        enumerationidx_t numterm = this->grammar->count_terminals(nt);
        if(is.get_value() < numterm) {
            return this->grammar->makeNode(this->grammar->get_rule(nt, is.get_value()));    // whatever terminal we wanted
        }
        else {
            // Otherwise it is encoding numterm+which_terminal
            is -= numterm; 
            
            const auto numnonterm = this->grammar->count_nonterminals(nt);
            if(numnonterm == 0) throw EnumerationNotInjectiveException(); 
            
            auto ri = is.pop(numnonterm); // this already includes the shift from all the nonterminals
            
            Rule* r = this->grammar->get_rule(nt, ri+numterm); // shift index from terminals (because they are first!)
            Node out = this->grammar->makeNode(r);
            
            int i=0;
            for(auto v : is.split(r->N)) {
                // note that this recurses on the enumerationidx_t format -- so it makes a new IntegerizedStack for each child
                out.set_child(i, toNode(v, r->type(i)) ); 
                i++;
            }
            
            return out;                 
        }
    }
    
    [[nodiscard]] virtual Node toNode(enumerationidx_t z, const nonterminal_t nt)  {
        IntegerizedStack is(z);
        return toNode(is, nt);
    }
    
    [[nodiscard]] virtual Node toNode(const nonterminal_t nt, enumerationidx_t z)  {
        // include this because we are SO bad at getting the order right
        assert(false && "*** You got the order of nonterminal_t and enumerationidx_t wrong and I'm really friendly because I'm here just to tell you that you should switch the order. ");
    }
    
    virtual enumerationidx_t toInteger(const Node& n)  {
        // inverse of the above function -- what order would we be enumerated in?
        if(n.nchildren() == 0) {
            return this->grammar->get_index_of(n.rule);
        }
        else {
            // here we work backwards to encode 
            nonterminal_t nt = n.rule->nt;
            enumerationidx_t numterm = this->grammar->count_terminals(nt);
            
            IntegerizedStack is(toInteger(n.child(n.rule->N-1)));
            for(int i=n.rule->N-2;i>=0;i--) {
                is.push(toInteger(n.child(i)));
            }
            is.push(this->grammar->get_index_of(n.rule)-numterm, this->grammar->count_nonterminals(nt));
            is += numterm;
            return is.get_value();
        }
    }
};