kodovi/skup/Skup.java

   1 /**
   2  * Tip podataka skup - predstavlja kolekciju razlicitih objekata zadatog tipa.
   3  *
   4  * Pomocni materijal na kursu SPA1, DMI, PMF, UNS www.dmi.rs
   5  *
   6  * v1.0.0
   7  *
   8  * @param <T> - tip podataka koji ce biti skladisten u instanci ove klase.
   9  */
  10 public class Skup<T> {
  11
  12         class Element {
  13                 T info;
  14                 Element veza;
  15
  16                 public Element() {
  17                         this.info = null;
  18                         this.veza = null;
  19                 }
  20
  21                 public Element(T podatak) {
  22                         this.info = podatak;
  23                         this.veza = null;
  24                 }
  25
  26         }
  27
  28         Element zaglavlje;
  29
  30         public Skup() {
  31                 zaglavlje = new Element();
  32                 zaglavlje.veza = zaglavlje;
  33         }
  34
  35         public String toString() {
  36                 String rezultat = "Skup {";
  37                 Element tekuci = zaglavlje.veza;
  38                 if (tekuci != zaglavlje) {
  39                         rezultat += " " + tekuci.info;
  40                         tekuci = tekuci.veza;
  41                 }
  42                 while (tekuci != zaglavlje) {
  43                         rezultat += ", " + tekuci.info;
  44                         tekuci = tekuci.veza;
  45                 }
  46                 return rezultat + " }";
  47         }
  48
  49         public boolean pripada(T clan) {
  50                 zaglavlje.info = clan;
  51                 Element tekuci = zaglavlje.veza;
  52                 while (!tekuci.info.equals(clan)) {
  53                         tekuci = tekuci.veza;
  54                 }
  55                 return tekuci != zaglavlje;
  56         }
  57
  58         public boolean ubaci(T clan) {
  59                 if (!pripada(clan)) {
  60                         Element novi = new Element();
  61                         novi.info = clan;
  62                         novi.veza = zaglavlje.veza;
  63                         zaglavlje.veza = novi;
  64                         return true;
  65                 } else {
  66                         return false;
  67                 }
  68         }
  69
  70         public boolean izbaci(T clan) {
  71                 zaglavlje.info = clan;
  72                 Element prethodni = zaglavlje;
  73                 while (!prethodni.veza.info.equals(clan)) {
  74                         prethodni = prethodni.veza;
  75                 }
  76                 if (prethodni.veza != zaglavlje) {
  77                         prethodni.veza = prethodni.veza.veza;
  78                         return true;
  79                 } else {
  80                         return false;
  81                 }
  82         }
  83
  84         public void ubaciSve(Skup<T> skup) {
  85                 Element tekuci = skup.zaglavlje.veza;
  86                 while (tekuci != skup.zaglavlje) {
  87                         ubaci(tekuci.info);
  88                         tekuci = tekuci.veza;
  89                 }
  90         }
  91
  92         public Skup<T> unija(Skup<T> drugi) {
  93                 Skup<T> rezultat = new Skup<T>();
  94                 rezultat.ubaciSve(this);
  95                 rezultat.ubaciSve(drugi);
  96                 return rezultat;
  97         }
  98
  99         public Skup<T> presek(Skup<T> drugi) {
 100                 Skup<T> rezultat = new Skup<T>();
 101                 Element tekuci = zaglavlje.veza;
 102                 while (tekuci != zaglavlje) {
 103                         if (drugi.pripada(tekuci.info)) {
 104                                 rezultat.ubaci(tekuci.info);
 105                         }
 106                         tekuci = tekuci.veza;
 107                 }
 108                 return rezultat;
 109         }
 110
 111         public Skup<T> razlika(Skup<T> drugi) {
 112                 Skup<T> rezultat = new Skup<T>();
 113                 Element tekuci = zaglavlje.veza;
 114                 while (tekuci != zaglavlje) {
 115                         if (!drugi.pripada(tekuci.info)) {
 116                                 rezultat.ubaci(tekuci.info);
 117                         }
 118                         tekuci = tekuci.veza;
 119                 }
 120                 return rezultat;
 121         }
 122
 123         public boolean podskupOd(Skup<T> drugi) {
 124                 Element tekuci = zaglavlje.veza;
 125                 while (tekuci != zaglavlje) {
 126                         if (!drugi.pripada(tekuci.info)) {
 127                                 return false;
 128                         }
 129                         tekuci = tekuci.veza;
 130                 }
 131                 return true;
 132         }
 133 }