<jupyter_start><jupyter_text>AVL Balanced Tree<jupyter_code>%%writefile avl.h
#ifndef __AVL_H__
#define __AVL_H__

#include <functional>

using std::function;

template <typename T, typename R=T, T NONE=0>
class Avl {
    struct Node;

    typedef function<R(T)>      lbdKey;
    typedef function<void(T)>   lbdProc;

    Node*   root;
    int     len;
    lbdKey  key;

public:
    Avl(lbdKey key=[](T a) {return a;}) : key(key), root(nullptr), len(0) {}
    ~Avl() { destroy(root); }

    int     height()                { return height(root); }
    int     size()                  { return len; }
    void    clear()                 { destroy(root); len = 0; }

    void    add(T elem)             { add(root, elem); }
    void    inOrder(lbdProc proc)   { inOrder(root, proc); }

    void    remove(R attr);
    T       find(R attr);

private:
    void    destroy(Node*& node);
    int     height(Node* node);
    void    add(Node*& node, T elem);
    void    inOrder(Node* node, lbdProc proc);

    Node*&  greater(Node*& node);
    Node*&  find(Node*& node, R attr);

    void    updateHeight(Node* node);
    void    rotateLeft(Node*& node);
    void    rotateRight(Node*& node);
    void    balance(Node*& node);

    Node* dummynull = nullptr;

};

#include "node.cpp"
#include "avl.cpp"
#include "balance.cpp"

#endif<jupyter_output>Overwriting avl.h<jupyter_text>Implementación de la estructura o clase NodeAhora agregamos un atributo altura (height)<jupyter_code>%%writefile node.cpp
#ifndef __NODE_CPP__
#define __NODE_CPP__

#include "avl.h"

template <typename T, typename R, T NONE>
struct Avl<T, R, NONE>::Node {
    T       element;
    Node*   left;
    Node*   right;
    int     height;

    Node(T element): element(element),left(nullptr),right(nullptr),height(0) {}
};

#endif<jupyter_output>Overwriting node.cpp<jupyter_text>Método básicos del árbol AVLAhora con el método que retorna la altura del árbol<jupyter_code>%%writefile avl.cpp
#ifndef __AVL_CPP__
#define __AVL_CPP__

#include "avl.h"

template <typename T, typename R, T NONE>
void    Avl<T, R, NONE>::destroy(Node*& node) {
    if (node != nullptr) {
        destroy(node->left);
        destroy(node->right);
        delete node;
        node = nullptr;
    }
}

template <typename T, typename R, T NONE>
int     Avl<T, R, NONE>::height(Node* node) {
    return node == nullptr? -1: node->height;
}

template <typename T, typename R, T NONE>
void    Avl<T, R, NONE>::add(Node*& node, T elem) {
    if (node == nullptr) {
        node = new Node(elem);
        ++len;
    } else {
        if (key(elem) < key(node->element)) {
            add(node->left, elem);
        } else {
            add(node->right, elem);
        }
        balance(node); /* :O */
    }
}

template <typename T, typename R, T NONE>
void    Avl<T, R, NONE>::remove(R attr) {
    // TODO FALTA BALANCEAR!!
}

template <typename T, typename R, T NONE>
struct Avl<T, R, NONE>::Node*&  Avl<T, R, NONE>::greater(Node*& node) {
    return node->right != nullptr? node : greater(node->right);
}

template <typename T, typename R, T NONE>
void    Avl<T, R, NONE>::inOrder(Node* node, lbdProc proc) {
    if (node != nullptr) {
        inOrder(node->left, proc);
        proc(node->element);
        inOrder(node->right, proc);
    }
}

template <typename T, typename R, T NONE>
T       Avl<T, R, NONE>::find(R attr) {
    Node*& node = find(root, attr);
    return node == nullptr? NONE : node->element;
}

template <typename T, typename R, T NONE>
struct Avl<T, R, NONE>::Node*&  Avl<T, R, NONE>::find(Node*& node, R attr) {
    if (node == nullptr) {
        return dummynull;
    } else if (attr == key(node->element)) {
        return node;
    } else if (attr < key(node->element)) {
        return find(node->left, attr);
    } else {
        return find(node->right, attr);
    }
}

#endif<jupyter_output>Overwriting avl.cpp<jupyter_text>Médotos privados para el balanceo<jupyter_code>%%writefile balance.cpp
#ifndef __BALANCE_CPP__
#define __BALANCE_CPP__

#include "avl.h"

#define max(a, b) (((a) > (b))? (a) : (b))

template <typename T, typename R, T NONE>
void    Avl<T, R, NONE>::updateHeight(Node* node) {
    if (node != nullptr) {
        node->height = max(height(node->left), height(node->right)) + 1;
    }
}

template <typename T, typename R, T NONE>
void Avl<T, R, NONE>::rotateLeft(Node*& node) { // X = node, Y = node->right
    Node* aux = node->right;
    node->right = aux->left;
    updateHeight(node);
    aux->left = node;
    updateHeight(aux);
    node = aux;
}

template <typename T, typename R, T NONE>
void Avl<T, R, NONE>::rotateRight(Node*& node) { // Y = node, X = node->left
    Node* aux = node->left;
    node->left = aux->right;
    updateHeight(node);
    aux->right = node;
    updateHeight(aux);
    node = aux;
}

template <typename T, typename R, T NONE>
void    Avl<T, R, NONE>::balance(Node*& node) {
    int hl = height(node->left);
    int hr = height(node->right);

    if (hr - hl < -1) {
        hl = height(node->left->left);
        hr = height(node->left->right);
        if (hr > hl) {
            rotateLeft(node->left);
        }
        rotateRight(node);
    } else if (hr - hl > 1) {
        hl = height(node->right->left);
        hr = height(node->right->right);
        if (hl > hr) {
            rotateRight(node->right);
        }
        rotateLeft(node);
    } else {
        updateHeight(node);
    }
}

#endif
%%writefile avlTest.cpp
#include <iostream>
#include <string>
#include "avl.h"

using namespace std;

int main() {
    typedef Avl<float*, float, nullptr> avlptrss;
    avlptrss* avl = new avlptrss([](float* a) { return *a; });

    for (int i = 0; i < (int)1e4; ++i) {
        float* x = new float();
        *x = i * 1.;
        avl->add(x);
    }

    cout << avl->height() << endl;

    delete avl;

    return 0;
}
!g++ -std=c++17 avlTest.cpp && ./a.out
%%writefile avlTest2.cpp
#include <iostream>
#include <sstream>
#include <string>
#include "avl.h"

using namespace std;

int main() {
    typedef Avl<string*, string, nullptr> avlptrss;
    avlptrss* avl = new avlptrss([](string* a) { return *a; });

    for (int i = 0; i < (int)1e6; ++i) {
        stringstream ss;
        ss << (i+1)*10.1;
        avl->add(new string(ss.str()));
    }

    cout << avl->height() << endl;

    delete avl;

    return 0;
}
!g++ -std=c++17 avlTest2.cpp && ./a.out
%%writefile persona.h
#ifndef __PERSONA_H__
#define __PERSONA_H__

#include <string>

using std::string;

class Persona {
    string  dni;
    string  apaterno;
    string  amaterno;
    string  nombres;
    string  fecnac;
    float   estatura;
public:
    Persona(string  dni="",
            string  apaterno="",
            string  amaterno="",
            string  nombres="",
            string  fecnac="",
            float   estatura=.0f) : dni(dni),
                                    apaterno(apaterno),
                                    amaterno(amaterno),
                                    nombres(nombres),
                                    fecnac(fecnac),
                                    estatura(estatura) {}
               
    string  getDni()        { return dni; }
    string  getApaterno()   { return apaterno; }
    string  getAmaterno()   { return amaterno; }
    string  getNombres()    { return nombres; }
    string  getFecnac()     { return fecnac; }
    float   getEstatura()   { return estatura; }
    
    void    setDni(string dni)              { this->dni         =  dni; }
    void    setApaterno(string apaterno)    { this->apaterno    =  apaterno; }
    void    setAmaterno(string amaterno)    { this->amaterno    =  amaterno; }
    void    setNombres(string nombres)      { this->nombres     =  nombres; }
    void    setFecnac(string fecnac)        { this->fecnac      =  fecnac; }
    void    setEstatura(float estatura)     { this->estatura    =  estatura; }
};

#endif
%%writefile avlTest3.cpp
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include "persona.h"
#include "avl.h"

using namespace std;

void loadData(vector<string>& vec, string filename) {
    ifstream file(filename);
    string str;
    while (file >> str) {
        vec.push_back(str);
    }
    file.close();
}

Persona* randPersona(vector<string>& names, vector<string>& lastnames, int i) {
    stringstream ssdni, ssfec;
    ssdni << setfill('0') << setw(8) << i;
    ssfec << (1920 + rand() % 90) << "-"
          << setfill('0') << setw(2) << (1 + rand() % 12) << "-"
          << setfill('0') << setw(2) << (1 + rand() % 28);
    return new Persona(ssdni.str(),
                       lastnames[rand() % lastnames.size()],
                       lastnames[rand() % lastnames.size()],
                       names[rand() % names.size()],
                       ssfec.str(),
                       (90 + rand() % 160) / 100.);
}

ostream& operator<<(ostream& os, Persona* p) {
    os << std::setw(8)  << p->getDni()
       << std::setw(15) << p->getApaterno()
       << std::setw(15) << p->getAmaterno()
       << std::setw(15) << p->getNombres()
       << std::setw(12) << p->getFecnac()
       << std::setw(5)  << p->getEstatura();
    return os;
}

int main() {
    vector<string> names, lastnames;
    loadData(names, "names.txt");
    loadData(lastnames, "lastnames.txt");

    typedef Avl<Persona*, string, nullptr> avlps;
    typedef Avl<Persona*, float, nullptr>  avlpf;

    avlps* avlNom = new avlps([](Persona* a) { return a->getNombres(); });
    avlps* avlApa = new avlps([](Persona* a) { return a->getApaterno(); });
    avlpf* avlEst = new avlpf([](Persona* a) { return a->getEstatura(); });

    Persona* persona;

    srand(1981);
    for (int i = 0; i < 1000000; ++i) {
        persona = randPersona(names, lastnames, i+1);
        avlNom->add(persona);
        avlApa->add(persona);
        avlEst->add(persona);
    }

    cout << "Personas generadas e indexadas correctamente\n";

    cout << "Altura del índice por nombre: " << avlNom->height() << endl;
    cout << "Altura del índice por apellido: " << avlApa->height() << endl;
    cout << "Altura del índice por estatura: " << avlEst->height() << endl;

    persona = avlNom->find("Harry");
    if (persona != nullptr) cout << persona << endl; else cout << ":(\n"; 
    persona = avlNom->find("Zayan");
    if (persona != nullptr) cout << persona << endl; else cout << ":(\n"; 

    persona = avlApa->find("Rice");
    if (persona != nullptr) cout << persona << endl; else cout << ":(\n";
    persona = avlApa->find("Smith");
    if (persona != nullptr) cout << persona << endl; else cout << ":(\n";
    persona = avlApa->find("Perez");
    if (persona != nullptr) cout << persona << endl; else cout << ":(\n";

    persona = avlEst->find(1.55);
    if (persona != nullptr) cout << persona << endl; else cout << ":(\n";
    persona = avlEst->find(1.99);
    if (persona != nullptr) cout << persona << endl; else cout << ":(\n";

    avlNom->inOrder([](Persona* a) { delete a; });
    avlApa->inOrder([](Persona* a) { delete a; });
    avlEst->inOrder([](Persona* a) { delete a; });

    delete avlNom;
    delete avlApa;
    delete avlEst;

    return 0;
}
%%writefile names.txt
Eshaal
Lilian
Muskaan
Jiya
Mahi
Naseem
Afsana
Jodi
Lynsey
Menachem
Jamelia
Harry
Affan
Micah
<NAME>
Miles
Sonny
Kingsley
Ayah
Gemma
Natalya
Beverly
Lucie
Cyrus
Rickie
Carys
Holli
Shakil
Callie
Harper
Tj
Joy
Hayleigh
Steffan
Mina
Melvin
Mylo
Seb
Emily
Jed
Kiaan
Leanna
Martha
Aliya
Jarvis
Jorja
Rahima
Pearce
Jill
Taine
Ottilie
Jimmie
Sila
Tamanna
Briana
Kaylan
Wendy
Atlanta
Jaidan
Alima
Bjorn
Darrell
Rhodri
Henrietta
Homer
Meg
Zayan
Ocean
Wanda
Aleisha
Inayah
Neel
Lubna
Caiden
Mahira
Muhamed
Shamima
Arnas
Makenzie
Antonina
Sheldon
Zayaan
Nora
Braydon
Leela
Maddie
Kenny
Ralphy
Nicole
Matteo
Julian
Garry
Kaitlyn
Hayden
Teigan
Kenzo
Yusra
Taran
Ravi
Jude
%%writefile lastnames.txt
Whiteley
Frost
Handley
Robertson
Stanton
West
Kramer
Hardy
Holder
Duke
Lyons
Mitchell
Pennington
Thatcher
May
Hardin
Sullivan
Greenaway
Clifford
Sandoval
Barrow
Mercer
Clayton
Maguire
Rasmussen
Ashton
Bone
Bowers
Lindsay
Owens
Knight
Booker
Lowry
Strong
Wardle
Nava
Oconnor
Ross
Smith
Shea
Pearson
Dudley
Everett
Ruiz
Feeney
Rooney
Flowers
Farmer
Kirby
Ball
Woods
Ballard
Michael
Begum
Ritter
Le
Carson
Raymond
Bean
Barnes
Branch
Rice
Churchill
Aldred
Fuller
Salt
Hickman
Mohammed
Easton
Munro
Millar
Mckay
Arias
Melton
Butt
Hogan
Gregory
Houston
Sykes
Parks
Shannon
Sanderson
Hobbs
Cain
Keeling
Neville
Rigby
Dougherty
Valenzuela
Mcfadden
Whitmore
North
Reyes
Byers
Skinner
Lloyd
Battle
Norton
Phelps
Houghton
!g++ -std=c++17 -O2 avlTest3.cpp -o programita && ./programita<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14502079573098955, 'fraction_numerical': 0.006984226634230558, 'mean_word_length': 2.7068062827225132, 'pattern_counts': {'":': 7, '<': 196, '<?xml version=': 0, '>': 150, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '478387', 'license': 'CC0-1.0', 'n_tokens_mistral': 4894, 'n_tokens_neox': 4704, 'n_words': 1207, 'path': '20202/aed_20202_131_avl_tree.ipynb', 'repo_name': 'pcsilcan/aed', 'size': '12748'}