// Árboles de Fibonacci: los AVL con menos nodos para cada altura.
// Un árbol de altura h tiene a la izquierda uno de altura h - 1, y a la derecha uno de altura h - 2.
#ifndef FIBONACCI_TREE_H
#define FIBONACCI_TREE_H

#include <cstddef>
#include <utility>
#include <vector>

// Cantidad mínima de nodos de un AVL de altura h.
inline long min_avl_nodes(int h) {
    long before = 0;   // la altura -1 no tiene nodos
    long current = 1;  // la altura 0 tiene uno
    for (int i = 0; i < h; i++) {
        long next = current + before + 1;
        before = current;
        current = next;
    }
    return current;
}

namespace fibonacci_detail {

struct Shape {
    int left = -1;
    int right = -1;
    int key = 0;
};

// Arma la forma de altura h y numera las claves en orden, desde next_key.
inline int build(int h, std::vector<Shape>& nodes, int& next_key) {
    if (h < 0) {
        return -1;
    }
    int left = build(h - 1, nodes, next_key);
    int key = next_key++;
    int right = build(h - 2, nodes, next_key);
    nodes.push_back({left, right, key});
    return static_cast<int>(nodes.size()) - 1;
}

}  // namespace fibonacci_detail

// Las claves 1, 2, ..., n de un árbol de Fibonacci de altura h, por niveles desde la raíz. Si se
// insertan en este orden en un AVL, cae cada una en su lugar y no hace falta ninguna rotación:
// cada árbol parcial es ese mismo árbol cortado en un nivel, y sigue balanceado.
inline std::vector<int> fibonacci_keys(int h) {
    std::vector<fibonacci_detail::Shape> nodes;
    int next_key = 1;
    int root = fibonacci_detail::build(h, nodes, next_key);
    std::vector<int> keys;
    keys.reserve(nodes.size());
    std::vector<int> level;
    if (root >= 0) {
        level.push_back(root);
    }
    while (!level.empty()) {
        std::vector<int> next;
        for (int index : level) {
            keys.push_back(nodes[index].key);
            if (nodes[index].left >= 0) {
                next.push_back(nodes[index].left);
            }
            if (nodes[index].right >= 0) {
                next.push_back(nodes[index].right);
            }
        }
        level = std::move(next);
    }
    return keys;
}

#endif