3.3. Kolekcijas

Ievads

  • Aprakstīt kolekciju (datu struktūru) hierarhiju Java 2 SDK
  • Rakstīt programmu, kura lieto kopas (set) un sarakstus (list)
  • Rakstīt programmu iterācijām pa kolekciju

Kolekciju interfeisi

Kolekcija (collection) ir objekts, kurš reprezentē objektu grupu - kolekcijas elementus Kolekciju interfeisi ļauj grupēt objektus šādos veidos:

  • Kolekcija (Collection) - grupa ar objektiem, kurus sauc par elementiem; sakārtojuma attiecība (vai tās neesamība), iespēja kolekcijā iekļaut dublikātus - atkarīgas no konkrētajām implementācijām
  • Kopa (Set) - nesakārtota kolekcija; dublikāti nav atļauti
  • Saraksts (List) - sakārtota kolekcija; dublikāti ir atļauti

Asociatīvi masīvi (map)

  • Attēlojums starp Javas objektiem - attēlojums ir definēts noteiktam, galīgam skaitam atslēgu. Katrai atslēgai (key) tas piekārto noteiktu vērtību (value). Nevar saturēt vairākas vērtības tai pašai atslēgai.
  • Sauc par "vārdnīcu", "mapu" vai "asociatīvu masīvu"
  • Asociatīvs masīvs nepieder pie kolekcijām, toties šī masīva visas atslēgas veido kopu, un var aplūkot arī atslēgu-vērtību pārīšu kolekciju

Kolekciju API

Kolekciju API

Piemērs, kurš lieto Set

1  import java.util.*;
2  
3  public class SetExample {
4      public static void main(String[] args) {
5          Set set = new HashSet();
6          set.add("one");
7          set.add("second");
8          set.add("3rd");
9          set.add(new Integer(4));
10         set.add(new Float(5.0F));
11         set.add("second");          // dublikāts, netiek pievienots
12         set.add(new Integer(4));    // dublikāts, netiek pievienots
13         System.out.println(set);
14     }
15 }

Šīs programmas izvade:

[one, second, 5.0, 3rd, 4]

Piemērs, kurš lieto List

1  import java.util.*
2  
3  public class ListExample {
4      public static void main(String[] args) {
5          List list = new ArrayList();
6          list.add("one");
7          list.add("second");
8          list.add("3rd");
9          list.add(new Integer(4));
10         list.add(new Float(5.0F));
11         list.add("second");          // dublikāts, tiek pievienots
12         list.add(new Integer(4));    // dublikāts, tiek pievienots
13         System.out.println(list);
14     }
15 }

Šīs programmas izvade:

[one, second, 3rd, 4, 5.0, second, 4]

Iteratori

  • Iterācijas ir process, kura laikā mēs apstrādājam visus kolekcijas elementus
  • Kopas (Set) iterators (Iterator) ir nesakārtots
  • Saraksta iterators (ListIterator) var tikt pārlūkots uz priekšu (izmantojot metodi next) vai atpakaļ (izmantojot metodi previous)
List list = new ArrayList();
// add some elements
Iterator elements = list.iterator();
while ( elements.hasNext() ) {
    System.out.println(elements.next());
}

Iteratoru interfeisu hierarhija

Iteratoru interfeisu hierarhija

Kolekcijas kopš JDK 1.1

  • Vector, kurš implementē List interfeisu.
  • Stack ir Vector apakšklase; tas atbalsta metodes push, pop un peek
  • Hashtable, kurš implementē Map interfeisu
  • Uzskaitījums (Enumeration) ir iteratora (Iterator) interfeisa senāka variācija, kurai citādi nosauktas metodes un nav iespējas dzēst sarakstā elementus ar remove().
  • Uzskaitījumu (Enumeration) atgriež elements metode objektiem Vector, Stack un Hashtable.
  • Klases Vector, Stack, Hashtable ir pavediendrošas.

Stila jautājumi

List p = new LinkedList(); 

ir labāks par:

LinkedList p = new LinkedList();

Pirmo variantu var būt grūtāk nokompilēt, jo mainīgais "p" drīkst izsaukt tikai interfeisa "List" metodes. Toties var viegli pārslēgties uz citu implementāciju:

List p = new ArrayList();

Polimorfisms

Visi konteineri satur Object tipa elementus. Tāpēc tos var izmantot jebkādu elementu - objektu vai masīvu glabāšanai. (Izņemot pamattipus, piemēram, int ir jāglabā kā objekts java.lang.Integer)

Izšķir divu tipu polimorfismu:

List[File] files; // nav atļauts tā rakstīt

// toties var darīt šādi:
List files = new LinkedList(); 
File f = new File(...); 
files.add(f); 
...
File x = files.get(0); // nav atļauts
File y = (File)files.get(0); 

Var būt ieteicami izveidot īpašu metodi, kura manto no skeletveida klases "AbstractSet" un kurai ir īpaša metode:

public File getFile(int i) { ... }

Skati (view)

Skats ir noderīgs, bet sarežģīts mehānisms, kurš lietotājam sniedz datu struktūru noteiktā šķērsgriezumā un ļauj veikt uz tās dažādas darbības, t.sk. mainīt sākotnējo datu struktūru. Skatus lieto šādiem mērķiem:

  • Skati paplašina funkcionalitāti, nesarežģījot pašas datu struktūras interfeisu. Metodes next(), hasNext() (pat remove()) atrodas iteratorā, kuru var iegūt no kolekcijas, bet ne pašā kolekcijā.
  • Skati nodrošina atpārošanu (decoupling). Teiksim Map.keySet() metode ļauj darboties tikai ar asociatīvā masīva atslēgām, neaiztiekot pašu masīvu
  • Skats kā koordinātu transformācija. Ar subList metodi var izgriezt no saraksta fragmentu un pa to staigāt

Daži skati ļauj modificēt tikai pašu skatu, bet citi iespaido arī pašu datu struktūru. Tas atkarīgs no konkrētās metodes.

Datu struktūras un Reprezentācijas invarianti

Rep. invarianta jēdziens

  • Rep. invariants ir atklāti formulēts nosacījums, kuru pielietojot konkrētas abstrakta datutipa realizācijas konkrētam objektam var pateikt, vai tas ir pareizi veidots
  • Rep. invariants ļauj pārbaudīt datu struktūras instanču pareizību pārbaudot katru manipulācijas metodi atsevišķi.

Reprezentācijas invarianta apdraudēšana (representation exposure)

Situācija, kur metodes, kuras nepieder pie konkrētāš datu struktūras objekta metodēm var sākt iespaidot reprezentācijas invariantu. Piemērs: metode ArrayList.toArray():

private int size; 
private Object elementData[];
...
public Object[] toArray() {
    Object[] result = new Object[size]; 
        System.arraycopy(elementDate, 0, result, 0, size); 
        return result; 
}

Morāle: Ārējam izsaucējam atgriežam sava masīva kopiju, nevis pašu masīvu. Vienkāršos gadījumos (ja masīvs drīkst saturēt visu ko) ārējais izsaucējs nevarēs izjaukt rep. invariantu. Bet, ja datu struktūra, piemēram, garantē, ka tur visi elementi ir dažādi, tad ārējais izsaucējs to varēs izjaukt, izveidojot masīvā divus vienādus elementus.

Piemērs: Heštabula (Hashtable)

Heštabulas datu struktūra

Rep. invariants heštabulai: katrs objekts atrodas tajā spainītī (bucket), kura vieta masīvā atbilst objekta hešfunkcijas vērtībai.

Šī invarianta iespējamais apdraudējums

Ja heštabulā glabā vienīgi nemaināmus (immutable) objektus, tad pārsteigumi nerodas. Citādi ir tad, ja šajā datu struktūrā ievietots objekts var mainīties (vienlaikus pamainot arī savu hešfunkcijas vērtību).

import java.util.*;

public class Mod11 {
    public static void main(String[] args) {
        Set s = new HashSet();     // tukša heštabula
        List x = new LinkedList(); // tukšs saraksts
        s.add(x);                  // pievienojam sarakstu heštabulai
                System.out.println(s.contains(x)); // s satur x'u
        x.add("AAA");              // modificējam sarakstu
        System.out.println(s.contains(x)); // s vairs nesatur x'u
                List y = new LinkedList(); // y - cits tukšs saraksts
        System.out.println(s.contains(y)); // s nesatur y'u
                System.out.println(s.size()); // heštabulas izmērs tomēr ir 1

                Iterator i = s.iterator(); 
                while(i.hasNext()) {
                        List z = (List)i.next(); 
                        System.out.print("saraksts: " + z); 
                        // sarakstu heštabulā var sameklēt tikai ar iteratoru
                }
    }
}

Programmas izvade:

true
false
false
false
1
saraksts: [AAA]

Visticamāk, nav iespējams izveidot objektu z, kuram s.contains(z) būtu true, bet saraksts tomēr nav tukšs. Objekts izmainās, bet joprojām piekārtots tam pašam (tagad jau nepareizajam) heštabulas spainītim.

Sakārtojuma attiecības un kolekcijas

  • Interfeisa java.lang.Comparable metode compareTo(Object) definē objektu klasei, kura implementē šo interfeisu "dabisko sakārtojumu"
  • Uzskatām, ka objekts a ir "mazāks par"/"sakārtojumā atrodas pirms" objekta b, ja a.compareTo(b)<0.
  • Metodēm "Object.equals" un "Object.hashCode" ĻOTI VĒLAMS būt tādām, lai,
    (x.compareTo(y)==0) == (x.equals(y))
    
  • No Comparable objektiem var veidot SortedSet un SortedMap datu struktūras
  • Tie, kuri nodarbojas ar sakārtotas kopas objektu mutācijām riskē izjaukt attiecīgās datu struktūras reprezentācijas invariantu.