#ifndef olist_hpp
#define olist_hpp

#include <stdio.h>
#include <iostream>

using namespace std;

class olist {

  class node{
    int _data;
    node *_next;
    public:
    node(int);
    int data() const {return _data;}

    node *next() const {return _next;}
    void next(node *p) { _next = p;}
  };

int n; //capacidad
int s; //Tamaño

  node *init; //puntero inicio
  public:
  olist(int);
  ~olist();

  void insert(int);

  bool search(int, int &);

  int capacity() const {return n;}
  int size() const {return s;}
  bool full() const {return s==n;}
  bool empty() const {return s==0;}

  void print();

};

#endif // olist_hpp

#include "olist.hpp"

olist::node::node(int d) {
  _data = d;
  _next = nullptr;
}

olist::olist(int c) {
  n = c;
  s = 0;
  init = nullptr;
}

olist::~olist(){
node *p = init;
while(p != nullptr){
node *q = p;
p = p->next();
delete q;
}}

void olist::insert(int x) {
  if (empty()) {
    init = new node(x);
    s++;
  } else {
    node *p = init, *q = nullptr;
    while (p != nullptr && p->data() < x) {
      q = p;
      p = p->next();
    }
    node *aux = new node(x);
    // Insertar por el final
    if (p == nullptr) {
      q->next(aux);
    }
    // Insertar por el inicio
    else if (p == init) {
      aux->next(init);
      init = aux;
    }
    // Por enmedio
    else {
      aux->next(p);
      q->next(aux);
    }
    s++;
  }
}

bool olist::search(int x, int &data){
  node *p = init;

  while(p != nullptr && p->data() < x) p = p->next();

  //return p != nullptr && p->data() == x ? p : nullptr;
  if (p != nullptr && p->data() == x){
    data = p->data();
    return true;
  }
    return false;
}

void olist::print() {
  node *p = init;
  std::cout << "[ ";
  while (p != nullptr) {
    std::cout << p->data() << " ";
    p = p->next();
  }
  std::cout << "]\n";
}

#include <iostream>
#include "olist.hpp"
#include <ctime>
#include <cstdlib>

int main() {
  srand((unsigned)time(nullptr));

  olist mylist(100);

  while(!mylist.full()){
    int x = rand()%1000+1;
    mylist.insert(x);
  }
  mylist.print();

  int x;

  cout << "\nIngrese el dato a buscar: ";
  cin >> x;

  int data;
  bool resultado = mylist.search(x, data);

  if (resultado) cout << "Sí está en la lista\n" << data << endl;
  else cout << "Te estoy diciendo que no está en la lista\n";

  return 0;
}