class Nodo {
  public String info;
  public Nodo next;
}

public class Buffer {
  // rappresentazione degli oggetti
  private int capacitares;
  private Nodo nodoinit;

  // metodi pubblici
  public Buffer(int c) {
    capacitares = c;
    nodoinit = null;
  }

  public int capacitaResidua() {
    return capacitares;
  }

  public int numDati() {
    int cont = 0;
    Nodo p = nodoinit;
    while (p!=null) {
      cont++;
      p = p.next;
    }
    return cont;
  }

  public void aggiungiDato(String d) {
    if (d.length() > capacitares) throw new RuntimeException("Buffer Pieno");
    else {
      capacitares = capacitares - d.length();
      nodoinit = aggiungiUltimo(nodoinit, d);
    }
  }

  /*
  public void aggiungiDato(String d) {
    if (d.length() > capacitares) throw new RuntimeException("Buffer Pieno");
    else {
      capacitares = capacitares - d.length();
      Nodo a = new Nodo(); // nodo generatore
      a.next = nodoinit;
      Nodo p = a;
      while (p.next != null) 
        p = p.next;
      p.next = new Nodo();
      p = p.next;
      p.info = d;
      p.next = null;
      nodoinit = a.next; // elimino nodo generatore
      }
  }
  */

  public String estraiDato(int i) {
    if (i < 0 || i >= numDati()) 
      throw new RuntimeException("Indice fuori dai limiti");
    else {
      Nodo a = new Nodo(); // nodo generatore;
      a.next = nodoinit;
      Nodo p = a;
      for(int j = 0; j < i; j++)  // sposto il puntatore i volte
        p = p.next;               // considerando che parto dal nodo
      String ris = p.next.info;   // generatore
      capacitares = capacitares + ris.length();
      p.next = p.next.next;
      return ris;
    }
  }
   
  public int contaOccorrenze(String d) {
    int num = 0;
    Nodo p = nodoinit;
    while (p != null) {
      if (p.info.equals(d)) num++;
      p = p.next;
    }
    return num;
  }

  public int[] qualiPosizioni(String d) {
    int[] ris = new int[contaOccorrenze(d)];
    int i = 0;
    int pos = 0;
    Nodo p = nodoinit;
    while (p != null) {
      if (p.info.equals(d)) {
        ris[i] = pos;
        i++;
      }
      p = p.next;
      pos++;
    }
    return ris;
  }


  // metodi ausiliari
  private static Nodo aggiungiUltimo(Nodo p, String d) {
    if (p == null) {
      Nodo ris = new Nodo();
      ris.info = d;
      ris.next = null;
      return ris;
    } else {
      p.next = aggiungiUltimo(p.next,d);
      return p;
    }
  }
}