Računalništvo 1 (PRA)

public class Seznam {
  private boolean prazen; // == true, ce je seznam prazen
  private Object element; // prvi element
  private Seznam ostali;  // ostanek seznama

  public Seznam(Object ee, Seznam oo) {
    element = ee;  ostali = oo;  prazen = false;
  }

  public Seznam() {
    element = null; ostali = null; prazen = true;
  }

  public Seznam dodaj(Object obj) { return new Seznam(obj, this); }

  public Object prvi() { return element; }

  public Seznam ostanek() { return ostali; }

  public boolean prazen() { return prazen; }

} // class

import java.io.*;

public class SeznamTest5 {

  public static void main(String[] aa) throws IOException {
    String vrsta;
    BufferedReader vhod;
    vhod = new BufferedReader(new InputStreamReader(System.in));

    Seznam ll = Seznam.napolni(aa);

    System.out.println("VSTAVLJANJE");
    int ii = 1;
    while ((vrsta = vhod.readLine()) != null) {
      if (vrsta.length() == 0) break;
      int index = Integer.parseInt(vrsta);
      System.out.println(ll.vstavi("NOV"+ii, index));
      System.out.println(ll);
      ii++;
    }
    System.out.println("BRISANJE");
    while ((vrsta = vhod.readLine()) != null) {
      if (vrsta.length() == 0) break;
      int index = Integer.parseInt(vrsta);
      System.out.println(ll.zbrisi(index));
      System.out.println(ll);
    }

  } // main

} // class

public class Seznam {

  // komponente:

  // prazen označuje, da je to prazen seznam; vrednosti element in
  // ostali sta v tem primeru nepomembni (običajno sta null).
  // To potrebujemo zato, da je tudi prazen seznam objekt, da lahko
  // na njem kličemo objektne metode. Lahko bi napisali podoben
  // razred, ki bi za prazen seznam uporabljal vrednost null (kar bi
  // bilo običajno) in bi zato imel predvsem statične metode.
  // Če nimamo objekta, ki je prazen seznam, npr. ne moremo poklicati
  // metode dodaj na praznem seznamu.
  boolean prazen;

  // element vsebuje objekt, ki je (prvi) element seznama
  Object element;

  // ostali je seznam ostalih elementov
  Seznam ostali;

  // konstruktor praznega seznama
  public Seznam(Object ee, Seznam oo) {
    element = ee;  ostali = oo;  prazen = false;
  } // Seznam

  // konstruktor elementa seznama
  public Seznam() {
    element = null;  ostali = null;  prazen = true;
  } // Seznam

  // na začetek seznama this dodamo nov element ee in nov seznam
  // vrnemo kot vrednost funkcije
  public Seznam dodaj(Object ee) {
    return new Seznam(ee,this);
  } // dodaj

  // vrnemo prvi element seznama this
  public Object prvi() {
    return element;
  } // prvi

  // vrne ostanek seznama this (brez prvega elementa)
  public Seznam ostanek() {
    return ostali;
  } // ostanek

  // vrne true natanko tedaj, ko je seznam this prazen
  public boolean prazen() {
    return prazen;
  } // prazen

  // metoda, ki ugotavlja strukturno enakost dveh seznamov: this in oo
  // nadomešča metodo Object.equals
  public boolean equals(Object oo) {
    Seznam ss = (Seznam)oo;
    // prazna seznama sta enaka
    if (this.prazen() && ss.prazen()) return true;
    // če je eden prazen in drugi ni, nista enaka
    if (this.prazen() != ss.prazen()) return false;
    // enaka sta natanko tedaj, ko sta enaka prva elementa in ko sta
    // enaka ostanka
    return element.equals(ss.prvi()) && ostali.equals(ss.ostali);
  } // equals

  // metoda, ki seznam pretvori v String; nadomešča Object.toString
  // Elementi seznama so ločeni s presledki, cel seznam pa je v
  // oklepajih. Prazen seznam je "()".
  // Elementi seznama so lahko poljubni objekti, vključno s seznami
  // in tudi vrednostjo null.
  // V tej metodi dovolimo, da se seznam konča z vrednostjo null in
  // ne le s pravim praznim seznamom.
  public String toString() {
    String ss = "(";
    Seznam ll = this;
    while (ll != null && !ll.prazen()) {
      if (ll.element != null) ss += ll.element.toString();
      else ss += "()";
      ll = ll.ostali;
      if (ll != null && !ll.prazen()) ss += ", ";
    }
    ss += ")";
    return ss;
  } // toString

  // elemente iz tabele tbl od indeksa index naprej pretvorimo v
  // seznam, ki ga vrnemo kot vrednost metode.
  public static Seznam napolni(Object[] tbl, int index) {
    if (index >= tbl.length) return new Seznam();
    return new Seznam(tbl[index], napolni(tbl,index+1));
  } // napolni

  // Vse elemente tabele tbl pretvorimo v seznam, ki ga vrnemo kot
  // vrednost metode.
  public static Seznam napolni(Object[] tbl) {
    return napolni(tbl,0);
  } // napolni

  // Elemente seznama ll dodamo na konec seznama this.
  // Seznam this pri tem destruktivno spremenimo, prav tako
  // NE napravimo kopije seznama ll.
  public void dodajNaKonec(Seznam ll) {
    if (prazen()) { // this je prazen, postane kar prvi element ll
      prazen = ll.prazen;
      element = ll.element;
      ostali = ll.ostali;
    }
    // če smo na koncu seznama this, prilepimo seznam ll
    else if (ostali == null || ostali.prazen()) ostali = ll;
    // sicer dodamo ll na konec ostanka seznama this
    else ostali.dodajNaKonec(ll);
  } // dodajNaKonec

  // vrnemo kopijo seznama this
  public Seznam kopija() {
    // če je seznam prazen, vrnemo nov prazen seznam
    if (prazen()) return new Seznam();
    // sicer pa vrnemo nov seznam, ki se sestoji iz prvega elementa
    // in kopije ostanka
    return new Seznam(element,ostali.kopija());
  } // kopija

  // vrnemo seznam, ki ima za elemente najprej vse elemente seznama
  // aa in nato vse elemente seznama bb
  public static Seznam zlepi(Seznam aa, Seznam bb) {
    // če je seznam aa prazen, vrnemo kar seznam bb
    if (aa == null || aa.prazen()) return bb;
    // sicer pa vrnemmo seznam iz prvega elementa in zlepljenega
    // ostanka in bb
    return new Seznam(aa.prvi(), zlepi(aa.ostanek(),bb));
  } // zlepi

  // obrnemo vrstni red elementov v seznamu
  public Seznam obrni() {
    // obrnjen prazen seznam je spet prazen seznam
    if (prazen()) return new Seznam();
    // sicer pa na obrnjen ostanek seznama prilepimo seznam s samo
    // prvim elementom
    return zlepi(ostali.obrni(),new Seznam(element,new Seznam()));
  } // obrni

  // vrnemo število elementov v sezamu
  public int steviloElementov() {
    // število elementov praznega seznama je 0
    if (prazen()) return 0;
    // sicer pa je za 1 večje od števila elementov ostanka
    return 1 + ostanek().steviloElementov();
  } // steviloElementov

  // vrnemo index-ti element seznama; če je index zunaj območja,
  // vrnemo null (nikoli ne povzročimo napake)
  public Object elementNa(int index) {
    if (index < 0) return null;                    // index premajhen
    if (prazen()) return null;                      // index prevelik
    if (index == 0) return prvi();        // prvi element ima index 0
    return ostanek().elementNa(index-1);  // (index-1)-ti elt ostanka
  } // elementNa

  // na index-to mesto vstavimo nov element oo; po vstavljanju bo
  // elementNa(index) == oo
  // vrnemo podseznam, ki se začne z novim objektom, ali null, če
  // smo dobili neumen index
  public Seznam vstavi(Object oo, int index) {
    if (index < 0) return null;                    // premajhen index
    if (index == 0) {                       // vstavljanje na začetku
      // ker vrednosti this ne moremo popraviti, bomo najprej this
      // skopirali v nov objekt in nato v this popravili njegove
      // komponente tako, da bo to postal nov element seznama
      Seznam nn = prazen ? new Seznam() : new Seznam(element,ostali);
      element = oo;  ostali = nn;  prazen = false;
      return this;
    }
    Seznam ll = this;                     // trenutni element seznama
    Seznam pp = null;                     // prejšnji element seznama
    // po seznamu se peljemo dokler ne pridemo do konca ali pa do
    // index-tega elementa
    while (index > 0 && !ll.prazen()) {
      index--; pp = ll; ll = ll.ostanek();
    }
    if (index > 0) return null;      // smo na koncu, prevelik indeks
    // pp ne more biti null, ker smo primer index==0 obdelali posebej
    // naredimo nov objekt, ki vsebuje nov element in kaže naprej
    // na ll. nato prejšnji element seznama nastavimo tako, da mu
    // sledi nov element
    Seznam nn = new Seznam(oo,ll);
    pp.ostali = nn;
    return nn;
  } // vstavi

  // iz seznama zbrišemo element na index-tem mestu
  // vrnemo zbrisan objekt ali null, če smo dobili neumen index
  public Object zbrisi(int index) {
    Object zbrisan;                    // zapomnimo si zbrisan objekt
    if (index < 0) return null;                    // premajhen index
    if (prazen) return null; // iz praznega seznama ne moremo brisati
    if (index == 0) {                          // brisanje na začetku
      // ker vrednosti this ne moremo popraviti, iz prvega objekta
      // naredimo drugega
      zbrisan = element;               // zapomnimo si zbrisan objekt
      if (ostali.prazen()) {         // zbrisati moramo edini element
        element = null; ostali = null; prazen = true;
      }
      else {             // brišemo prvi element, naslednik ni prazen
        element = ostali.element;  ostali = ostali.ostali;
      }
      return zbrisan;
    }
    Seznam ll = this;                     // trenutni element seznama
    Seznam pp = null;                     // prejšnji element seznama
    // po seznamu se peljemo dokler ne pridemo do konca ali pa do
    // index-tega elementa
    while (index > 0 && !ll.prazen()) {
      index--; pp = ll; ll = ll.ostanek();
    }
    if (ll.prazen()) return null;    // smo na koncu, prevelik indeks
    zbrisan = ll.element;              // zapomnimo si zbrisan objekt
    // ker smo index==0 obdelali prej, pp ne more biti null
    pp.ostali = ll.ostali;                     // brisanje na sredini
    return zbrisan;
  } // zbrisi

} // class

public class SSeznam {

  Object element;
  SSeznam ostali;

  public SSeznam(Object ee, SSeznam oo) {
    element = ee;  ostali = oo;
  } // SSeznam

  public static SSeznam dodaj(Object ee, SSeznam oo) {
    return new SSeznam(ee,oo);
  } // dodaj

  public static Object prvi(SSeznam ss) {
    return ss.element;
  } // prvi

  public static SSeznam ostanek(SSeznam ss) {
    return ss.ostali;
  } // ostanek

  public static boolean prazen(SSeznam ss) {
    return ss == null;
  } // prazen

  public boolean equals(Object oo) {
    return equals(this,(SSeznam)oo);
  } // equals

  public static boolean equals(SSeznam aa, SSeznam bb) {
    boolean ok;
    if (prazen(aa) != prazen(bb)) return false;
    if (prazen(aa) && prazen(bb)) return true;
    if ((prvi(aa)==null) != (prvi(bb)==null)) return false;
    return ( ((prvi(aa) == null) && (prvi(bb) == null))
           || (prvi(aa).equals(prvi(bb))) )
        && equals(ostanek(aa),ostanek(bb));
  } // equals

  public String toString() {
    return toString(this);
  } // toString

  public static String toString(SSeznam ll) {
    String ss = "(";
    while (!prazen(ll)) {
      Object pp = prvi(ll);
      if (pp == null) ss += "()";
      else ss += prvi(ll).toString();
      ll = ostanek(ll);
      if (!prazen(ll)) ss += ", ";
    }
    ss += ")";
    return ss;
  } // toString

  public static SSeznam napolni(Object[] tbl, int index) {
    if (index >= tbl.length) return null;
    return dodaj(tbl[index], napolni(tbl,index+1));
  } // napolni

  public static SSeznam napolni(Object[] tbl) {
    return napolni(tbl,0);
  } // napolni

  public static SSeznam kopija(SSeznam aa) {
    if (prazen(aa)) return null;
    return dodaj(prvi(aa),kopija(ostanek(aa)));
  } // kopija

  public static SSeznam dodajNaKonec(SSeznam aa, SSeznam bb) {
    if (prazen(aa)) return bb;
    if (prazen(ostanek(aa))) aa.ostali = bb;
    else dodajNaKonec(ostanek(aa),bb);
    return aa;
  } // dodajNaKonec

  public static SSeznam zlepi(SSeznam aa, SSeznam bb) {
    if (prazen(aa)) return bb;
    return dodaj(prvi(aa), zlepi(ostanek(aa),bb));
  } // dodajNaKonec

  public static void main(String[] aa) {
    String[] ss = {"Veni", "vidi", "vici"};
    String[] tt = {"Ceterum", "censeo", "Carthaginem", "esse", "delendam"};

    SSeznam ll = SSeznam.napolni(ss);
    SSeznam mm = SSeznam.napolni(ss);
    SSeznam nn = SSeznam.napolni(tt);

    System.out.println(ll);
    System.out.println(mm);
    System.out.println(nn);

    System.out.println(ll.equals(mm));
    System.out.println(ll == mm);
    System.out.println(ll.equals(nn));

    mm = dodaj(null,mm);
    System.out.println(mm);

    SSeznam kk = null;
    kk = dodaj("GHI",kk);
    kk = dodaj("DEF",kk);
    kk = dodaj("ABC",kk);
    System.out.println(kk);

    ll = dodaj(nn,ll);
    System.out.println(ll);

    ll = SSeznam.napolni(ss);
    ll = dodaj(ll,ll);
    System.out.println(ll);

    ll = napolni(ss);
    nn = napolni(tt);

    System.out.println(ll);
    System.out.println(nn);

    mm = dodaj(nn,ll);
    System.out.println(mm);

    ll = dodajNaKonec(ll,nn);
    System.out.println(ll);

    ll = napolni(ss);
    ll = dodaj(ll,ll);
    ll = dodaj("!!!",ll);
    ll = dodajNaKonec(ll,dodaj("???",null));
    System.out.println(ll);

    ll = napolni(ss);
    ll = dodaj(ll,kopija(ll));
    ll = dodaj("!!!",ll);
    ll = zlepi(ll,dodaj("???",null));
    System.out.println(ll);

  } // main

} // class