Abstract Data Types

Abstraktsed andmetüübid, magasin ja järjekord

Abstraktsed andmetüübid

"Varajane" OOP. Eesmärk: peita realisatsiooni detailid, anda rakenduse programmeerijale probleemorienteeritud liides.
ADT - Abstract Data Type

Lubatud väärtuste hulk (väärtusvaru)
Lubatud operatsioonide hulk
(Notatsioon - tähistused väärtuste ja operatsioonide jaoks)

Näit. kompleksarvud, polünoomid, graafid, geomeetrilised kujundid, ...

OOP muutis niisuguse lähenemise kohustuslikuks.

Väärtusvaru järgi jagunemine:

lihttüübid, mille väärtustel ei ole sisemist struktuuri: arv, tõeväärtus, ...
struktuursed tüübid, mille väärtus koosneb komponentidest: massiiv, objekt (kirje), ...

Operatsioonid on OOP-s "kinnistatud" objekti juurde (kapseldus).

Kinnised operatsioonid: tulemus kuulub sama tüübi väärtusvarusse
mittekinnised operatsioonid: tulemus on mingit teist tüüpi
tüübiteisendused: tegelikud ja deklaratiivsed

Näit. kinnine operatsioon "summa" (mis iganes see ka poleks)

Imperatiivne lähenemine: m = summa (a, b) "funktsiooni summa parameetriteks on a ja b"
OOP lähenemine: m = a.summa (b) "objektile a saadetakse teade 'summa' parameetriga b"

Andmestruktuurid võib jagada:

staatilised: komponentide arv ja tüübid fikseeritud: näiteks kompleksarv
dünaamilised: väärtuse komponentide arv on muutuv, komponendid ise tavaliselt üht tüüpi: näiteks magasin, järjekord, graaf, ...

Andmestruktuuride korral on oluliseks küsimuseks juurdepääsu tagamine komponentidele ning struktuuri muutmine (vastavate operatsioonide ajaline keerukus).
"Võtmine" ja "lisamine".

Magasin (stack)

LIFO - last in first out

Magasini omadused:

dünaamiline struktuur (elementide arv on muutuv)
elemendid on sama tüüpi
elementide järjestus on oluline
juurdepääs on ainult viimasena lisatud elemendile (magasini tipp); "lisamine" lisab lõppu ja "võtmine" eemaldab lõpust
tavaliselt realiseeritavad operatsioonid: tühja magasini loomine, lisamine (push), võtmine (pop), alatäitumise (underflow) kontroll (et vältida tühjast magasinist võtmist), mõne realisatsiooni korral ka ületäitumise (overflow) kontroll (kas on "ruumi" lisamiseks), tipu lugemine ilma eemaldamiseta (optim. kaalutlustel)

Keeles Java võib magasini realisatsiooni leida klassides java.util.Stack (baseerub vektoril) või java.util.LinkedList spetsialiseerides (baseerub topeltseotud ahelal).

Magasini kasutamise näited: avaldise väärtustamine, 'return stack', puu läbimine, ...

Avaldise postfikskuju ja selle interpreteerimine

"Tavaline" infikskuju: (5-1) * 7 + 6 / 3

Prefikskuju sulgudega: +( *( -( 5, 1), 7), /(6, 3))

Postfikskuju sulgudega: (((5, 1)-, 7)*, (6, 3)/ )+

Sulgudeta postfikskuju - nn. "pööratud poola kuju": 5 1 - 7 * 6 3 / + .


                   3
   1     7      6  6  2
5  5  4  4  28 28 28 28 30
--------------------------
5  1  -  7   *  6  3  /  +

Näide. Magasini realisatsioon tavalise massiivi abil

/** Ta"isarvude magasini realisatsioon massiivi abil. */

public class Magasin {

   /** Peameetod (silumiseks). */

   public static void main (String[] argum) {
      Magasin m = new Magasin();
      System.out.println (m);
      m.push (5);
      System.out.println (m);
      m.push (1);
      System.out.println (m);
      m.op ("-");
      System.out.println (m);
      m.push (7);
      System.out.println (m);
      m.op ("*");
      System.out.println (m);
      m.push (6);
      System.out.println (m);
      m.push (3);
      System.out.println (m);
      m.op ("/");
      System.out.println (m);
      m.op ("+");
      System.out.println (m);
      int tulemus = m.pop();
      System.out.println (m);
      System.out.println (tulemus);
      Magasin koopia = m;
      System.out.println (koopia.equals (m));
      try {koopia = (Magasin)m.clone();} catch (CloneNotSupportedException e) {}
      System.out.println (koopia.equals (m));
      m.push (6);
      System.out.println (koopia.equals (m));
      m.pop();
      System.out.println (koopia.equals (m));
   } // main lopp

   /** magasin ise massiivina. */

   private int [] mag;

   /** tipu indeks. */

   private int SP;

   /** vaikekonstruktor teeb 10-elemendilise magasini. */

   Magasin () {
      this (10);
   }

   /** etteantud elementide arvuga magasini konstruktor. */

   Magasin (int suurus) {
      mag = new int [suurus];
      SP = -1; // tunnus, et magasin on tyhi
   }

   /** koopia loomine. */

   public Object clone() throws CloneNotSupportedException {
      Magasin tmp = new Magasin (mag.length);
      tmp.SP = SP;
      if (SP >= 0)
         for (int i=0; i<=SP; i++)
            tmp.mag [i] = mag [i]; 
      return tmp;
   }

   /** alata"itumise kontroll. */

   public boolean magTyhi() {
      return (SP == -1);
   }

   /** yleta"itumise kontroll. */

   public boolean magLohki() {
      return ((SP + 1) >= mag.length);
   }

   /** lisamine magasini. */

   public void push (int a) {
      if (magLohki())
         throw new IndexOutOfBoundsException ("magasini yletaitumine");
      SP += 1; // increment
      mag [SP] = a;
   }

   /** eemaldamine magasinist. */

   public int pop() {
      if (magTyhi())
         throw new IndexOutOfBoundsException ("magasini alataitumine");
      int tmp = mag [SP];
      SP -= 1; // decrement
      return tmp;
   }

   /** aritmeetiline tehe tipus olevate elementide vahel (na"ide). */

   public void op (String s) {
      int op2 = pop();
      int op1 = pop();
      if (s.equals ("+")) push (op1 + op2);
      if (s.equals ("-")) push (op1 - op2);
      if (s.equals ("*")) push (op1 * op2);
      if (s.equals ("/")) push (op1 / op2);
   }
  
   /** tipu lugemine eemaldamiseta. */

   public int tos() {
      if (magTyhi())
         throw new IndexOutOfBoundsException ("magasini alataitumine");
      return mag [SP];
   }

   /** magasinide võrdsus. */

   public boolean equals (Object o) {
      if (((Magasin)o).SP != SP) return false;
      if (magTyhi()) return true; // teine ka tyhi!
      for (int i=0; i<=SP; i++)
         if (((Magasin)o).mag[i] != mag [i]) return false;
      return true;
   }

   /** teisendus so'neks (tipp paremal). */

   public String toString() {
      if (magTyhi()) return "Tyhi";
      StringBuffer b = new StringBuffer();
      for (int i=0; i<=SP; i++)
         b.append (String.valueOf (mag [i]) + " ");
      return b.toString();
   }

} // Magasin lopp

//------------------------------------
// faili lopp
//------------------------------------

Järjekord (queue)

FIFO - First In First Out

Järjekorra omadused:

dünaamiline struktuur (elementide arv on muutuv)
elemendid on sama tüüpi
elementide järjestus on oluline
juurdepääs on ainult esimesena lisatud elemendile (front); "lisamine" lisab lõppu ja "võtmine" eemaldab algusest (järjekorra metafoor)
tavaliselt realiseeritavad operatsioonid: tühja järjekorra loomine, lisamine, võtmine, alatäitumise (underflow) kontroll (et vältida tühjast järjekorrast võtmist), mõne realisatsiooni korral ka ületäitumise (overflow) kontroll (kas on "ruumi" lisamiseks), vahendid järjekorra läbivaatamiseks (näit. iteraatorid vms.)

Keeles Java võib järjekorra realisatsiooni luua klassi java.util.LinkedList spetsialiseerides (baseerub topeltseotud ahelal).

Näiteid järjekorra kasutamise kohta: ressursside jagamine (printer), tegevuste planeerimine, graafi läbimine

Eelistusjärjekord

Järjekord, milles on olulised elementide (võtmete) väärtused. Prioriteetidega järjekord. "Lisamine" on sisuliselt hulgateoreetiline lisamine ja "võtmine" on vähima (suurima) võtmeväärtusega elemendi eemaldamine. Kui prioriteedid on staatilised (ei muutu elemendi järjekorras olemise ajal), siis saab "lisamise" teha pistemeetodi abil "Õigesse kohta".

Muutuvate eelistustega järjekord

Kui elemendi prioriteet võib elemendi järjekorras olemise ajal dünaamiliselt muutuda (niisugust järjekorda nim. muutuvate eelistustega järjekorraks), siis tuleb "võtmine" realiseerida järjekorra läbivaatusena ("lisamine" on selle eest lihtne). Teine võimalus on kajastada iga prioriteedimuutust kohe järjekorras, aga see ei pruugi olla hea lahendus (näiteks kui muutusi on palju, aga võtmisi vähe).

Näide.

//---------------------------------------
// Fail Jarjekord.java
//---------------------------------------

/** Ta"isarvude ja"rjekorra realisatsioon massiivi abil. */

public class Jarjekord {

   /** Peameetod (silumiseks). */

   public static void main (String[] argum) {
      Jarjekord q = new Jarjekord();
      System.out.println (q); // Tyhi
      q.lisa (1);
      System.out.println (q); // 1
      q.lisa (3);
      System.out.println (q); // 1 3
      int tulemus = q.eemalda();
      System.out.println (q); // 3
      System.out.println (tulemus); // 1
      Jarjekord koopia = q;
      System.out.println (koopia.equals (q)); //true
      try {
         koopia = (Jarjekord)q.clone();
      }
      catch (CloneNotSupportedException e) {
      }
      System.out.println (koopia.equals (q)); // true
      tulemus = koopia.eemalda();
      koopia.lisa (7);
      System.out.println (koopia.equals (q)); // false
      System.out.println (q); // 3
      System.out.println (koopia); // 7
   }

   /** ja"rjekord ise massiivina. */

   private int [] jrk;

   /** tipu indeks. */

   private int lKoht, eKoht, elArv;

   /** vaikekonstruktor teeb 10-elemendilise ja"rjekorra. */

   Jarjekord () {
      this (10);
   }

   /** etteantud elementide arvuga ja"rjekorra konstruktor. */

   Jarjekord (int suurus) {
      jrk = new int [suurus];
      lKoht = 0;  // lisamise indeks
      eKoht = 0;  // eemaldamise indeks
      elArv = 0;  // tegelik elementide arv
   }

   /** koopia loomine. */

   public Object clone() throws CloneNotSupportedException {
      Jarjekord tmp = new Jarjekord (jrk.length);
      tmp.lKoht = lKoht;
      tmp.eKoht = eKoht;
      tmp.elArv = elArv;
      if (elArv > 0)
         for (int i=0; i<elArv; i++)
            tmp.jrk [(i+eKoht)%jrk.length] = jrk [(i+eKoht)%jrk.length]; 
      return tmp;
   }

   /** alata"itumise kontroll. */

   public boolean jrkTyhi() {
      return (elArv <= 0);
   }

   /** yleta"itumise kontroll. */

   public boolean jrkLohki() {
      return (elArv >= jrk.length);
   }

   /** lisamine ja"rjekorda. */

   public void lisa (int a) {
      if (jrkLohki())
         throw new IndexOutOfBoundsException ("jarjekorra yletaitumine");
      elArv += 1;
      jrk [lKoht] = a;
      lKoht = (lKoht + 1)%jrk.length;
   }

   /** eemaldamine ja"rjekorrast. */

   public int eemalda() {
      if (jrkTyhi())
         throw new IndexOutOfBoundsException ("jarjekorra alataitumine");
      elArv -= 1;
      int tmp = jrk [eKoht];
      eKoht = (eKoht + 1)%jrk.length;
      return tmp;
   }

   /** ja"rjekordade võrdsus. */

   public boolean equals (Object o) {
      if (((Jarjekord)o).elArv != elArv) return false;
      if (jrkTyhi()) return true; // teine ka tyhi!
      for (int i=0; i<elArv; i++)
         if (((Jarjekord)o).jrk
            [(i+((Jarjekord)o).eKoht)%((Jarjekord)o).jrk.length] !=
            jrk [(i+eKoht)%jrk.length]) return false;
      return true;
   }

   /** teisendus so'neks (viimane paremal). */

   public String toString() {
      if (jrkTyhi()) return "Tyhi";
      StringBuffer b = new StringBuffer();
      for (int i=0; i<elArv; i++)
         b.append (String.valueOf (jrk [(i+eKoht)%jrk.length]) + " ");
      return b.toString();
   }

} // Jarjekord lopp

//------------------------------------
// faili lopp
//------------------------------------

Abstraktsed jadad

Vt. Goodrich/Tamassia "Data Structures and Algorithms in Java" peatükid 3 ja 4.

Kood abstraktsete jadade jaoks

//====================================================================
// Fail Sequences.java
//====================================================================

import java.util.LinkedList;

/**
 * Abstraktsed jadad Goodrich/Tamassia raamatust.
 * @author Jaanus Poial
 * @version 0.1 sygis 2000
 * @since JDK 1.2
 */

public class Sequences {

   /** peameetod. */
   static public void main (String[] argum) {
      SequenceADT jada = new Sequence();
      jada.insertFirst ("esim");
      System.out.println (jada);
   } // main lopp

} // Sequences lopp

/** Liides indeksitega jada jaoks. */

interface RankedSequenceADT {

   /** jada element, millele eelneb r elementi. */
   public Object elemAtRank (int r) 
      throws IndexOutOfBoundsException;

   /** asendada element indeksiga r objektiga e.
    * @returns endine element.
    */
   public Object replaceElemAtRank (int r, Object e) 
      throws IndexOutOfBoundsException;

   /** lisada uus element e nii, et e indeksiks saab r. */
   public void insertElemAtRank (int r, Object e) 
      throws IndexOutOfBoundsException;

   /** eemaldada element indeksiga r.
    * @returns eemaldatud element.
    */
   public Object removeElemAtRank (int r) 
      throws IndexOutOfBoundsException;

   /** elementide arv. */
   public int size();

   /** kas jada on tyhi. */
   public boolean isEmpty();
   
} // RankedSequenceADT lopp

/** Indeksitega jada realisatsioon topeltseotud ahela abil. */

class RankedSequence 
   extends java.util.LinkedList
   implements RankedSequenceADT {

   public Object elemAtRank (int r) 
      throws IndexOutOfBoundsException {
      return get (r);
   }

   public Object replaceElemAtRank (int r, Object e) 
      throws IndexOutOfBoundsException {
      return set (r, e);
   }

   public void insertElemAtRank (int r, Object e) 
      throws IndexOutOfBoundsException {
      add (r, e);
   }

   public Object removeElemAtRank (int r) 
      throws IndexOutOfBoundsException {
      return remove (r);
   }

   public boolean isEmpty() {
      return (size() == 0);
   }

} // RankedSequence lopp

/** Liides "koht jadas". */

interface Position {

   /** tagastab sellel kohal oleva elemendi. */
   public Object element();

   /** tagastab jada, mille koht see on. */
   public PositionalSequenceADT container();

   /** paneb antud objekti e sellele kohale. */
   public void setElement (Object e);

} // Position lopp

/** Klass, mis realiseerib liidest "koht jadas". */

class PosElement implements Position {

   private Object elem;
   private PositionalSequenceADT cont;

   /** konstruktor. */
   PosElement (Object e, PositionalSequenceADT c) {
      setElement (e);
      setContainer (c);
   }

   public Object element() {
      return elem;
   }

   public PositionalSequenceADT container() {
      return cont;
   }

   public void setElement (Object e) {
      elem = e;
   }

   void setContainer (PositionalSequenceADT c) {
      cont = c;
   }

} // PosElement lopp

/** Liides kohtadega jada jaoks. */

interface PositionalSequenceADT {

   public Position first();
   public Position last();
   public Position before (Position p);
   public Position after (Position p);
   public int size();
   public boolean isEmpty();
   public Object replace (Position p, Object e);
   public void swap (Position p, Position q);
   public Position insertFirst (Object e);
   public Position insertLast (Object e);
   public Position insertBefore (Position p, Object e);
   public Position insertAfter (Position p, Object e);
   public Object remove (Position p);

} // PositionalSequenceADT lopp

/** Klass, mis realiseerib liidese kohtadega jada jaoks. */

class PositionalSequence extends LinkedList
   implements PositionalSequenceADT {
   
   public Position first() {
      return (Position) getFirst();
   }

   public Position last() {
      return (Position) getLast();
   }

   public Position before (Position p) {
      int i = indexOf (p); // siia kontrollid vaja panna
      return (Position)get (i-1);
   }

   public Position after (Position p) {
      int i = indexOf (p); // siia kontroll!!
      return (Position)get (i+1);
   }

   public boolean isEmpty() {
      return (size()==0);
   }

   public Object replace (Position p, Object e) {
      Object old = p.element();
      p.setElement (e);
      return old;
   }

   public void swap (Position p, Position q) {
      Object tmp = p.element();
      p.setElement (q.element());
      q.setElement (tmp);
   }

   public Position insertFirst (Object e) {
      Position p = new PosElement (e, this);
      addFirst (p);
      return p;
   }

   public Position insertLast (Object e) {
      Position p = new PosElement (e, this);
      addLast (p);
      return p;
   }

   public Position insertBefore (Position p, Object e) {
      Position q = new PosElement (e, this);
      add (indexOf (p), q);
      return q;
   }

   public Position insertAfter (Position p, Object e) {
      Position q = new PosElement (e, this);
      add (indexOf (p)+1, q); // siia veel yks kontroll vaja
      return q;
   }

   public Object remove (Position p) {
      Object e = p.element();
      if (! super.remove (p))
         throw new java.util.NoSuchElementException (" positsioon"); 
      return e;
   }

} // PositionalSequence lopp

/** Liides abstraktse jada jaoks. */

interface SequenceADT extends RankedSequenceADT, PositionalSequenceADT {
   
   /** elemendi indeksiga r positsioon, */
   public Position atRank (int r);

   /** positsiooni p indeks. */
   public int rankOf (Position p);

   /** teisendus so'neks, et saaks siluda. */
   public String toString();

} // SequenceADT lopp

/** Klass, mis realiseerib abstraktse jada. */

class Sequence extends PositionalSequence
   implements SequenceADT {

   public Position atRank (int r) {
      return (Position) get (r);
   }

   public int rankOf (Position p) {
      return indexOf (p);
   }

   public Object elemAtRank (int r)
      throws IndexOutOfBoundsException {
      return ((Position)get (r)).element();
   }

   public Object replaceElemAtRank (int r, Object e)
      throws IndexOutOfBoundsException {
      Object tmp = atRank (r).element();
      atRank (r).setElement (e);
      return tmp;
   }

   public void insertElemAtRank (int r, Object e)
      throws IndexOutOfBoundsException {
      add (r, new PosElement (e, this));
   }

   public Object removeElemAtRank (int r)
      throws IndexOutOfBoundsException {
      return ((Position)remove (r)).element();
   }
 
   public String toString() {
      if (isEmpty()) return "Tyhi";
      StringBuffer b = new StringBuffer();
      for (int i=0; i < size(); i++)
         b.append (elemAtRank (i).toString() + " ");
      return b.toString();
   }

} // Sequence lopp

// ===================================
// Faili l6pp
// ===================================

Sisuliselt on see teema Java APIs küllalt hästi esindatud: java.util.LinkedList, java.util.Vector, java.util.Stack, ...

Ahelad (jutupunktid)

Ahel koosneb muutuvast arvust elementidest, mis on omavahel seotud viitadega. Keeles Java ei ole viidatüüpi operatsioone ilmutatud kujul olemas - iga objektitüüpi väärtus on "tegelikult" viit.

Lihtahel - iga element sisaldab viita järgmisele (Java seisukohalt - sisaldab järgmist elementi isendimuutujana), ahela lõpetab nullviit
Topeltseotud ahel - iga element sisaldab kaht viita: järgmisele elemendile ja eelmisele elemendile
Ringahel - puudub ahelat lõpetav nullviit (Javas objekti puudumist tähistav null), elemendid moodustavad "ringi"
Päisega ahel - ahelale on lisatud formaalne lüli, mis ei kuulu ahela koosseisu, aga viitab esimesele (topeltseotud ahela korral ka viimasele) lülile. Vajalik selleks, et tühi ahel kujutuks objektina (mitte nullviidana).

Järgnevalt analüüsitakse lihtahela operatsioone: lisamine algusesse, suuruse poolest sobivale kohale, lõppu; eemaldamine; otsimine; ...

Kood lihtahela jaoks

Magasini realiseerimisest lihtahela abil.

Jaanus Pöial