Sada úkolů pro předmět DSA A7B36DSA http://neuron.felk.cvut.cz/dsa/index.html
Ing. Martin Chlumecký Katedra počítačů ČVUT v Praze, FEL
Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti
Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti
Domácí úkoly z předmětu DSA Domácí úkoly Domácí úkoly mají dvě varianty: lehčí a těžší. Lehčí varianta je za jeden bod, těžší vzhledem k větší míře samostatné práce za čtyři body. U řešitelů těžších domácích úkolů se předpokládá znalost Featherweight Javy.
Přístupové údaje k repozitáři URL vašeho repozitáře je https://cvut.repositoryhosting.com/svn/cvut_
/ URL pro brouzdání po vašem repozitáři na webu je https://cvut.repositoryhosting.com/trac/cvut_/browser Login je vaše uživatelské jméno v síti ČVUT Počáteční heslo je shodné s vaším uživatelským jménem (není se sítí ČVUT synchronizováno) URL pro přihlášení do administračního rozhraní na webu je https://cvut.repositoryhosting.com
Zadání lehčích domácích úkolů Lehčí domácí úkoly odevzdávejte přes repozitář. Každý úkol umístěte do adresáře homeworks a souboru homework.java, kde je číslo úkolu. Všechny odevzdávané třídy dělejte neveřejné (aby mohly být v jednom souboru) a neumísťujte je do žádného balíčku. Kromě vašeho kódu neodevzdávejte nic jiného - třídy a rozhraní, která jsou součástí zadání, si k vašemu kódu přilinkujeme sami. Pokud chcete ve zdrojácích používat češtinu, používejte kódování ISO8859-2. Pokud se ještě s testovacím systémem objeví problémy, dejte o nich (mailem) vědět přednášejícímu nebo cvičícím - jinak se nápravy nedočkáte.
První Naimplementujte třídu Homework1 implementující rozhraní Mergesort. interface int[] int[] int[] int[] }
Mergesort { getFirstHalfOf(int[] array); // vrati nesetridenou kopii prvni poloviny (horni celou cast) pole array getSecondHalfOf(int[] array); // vrati nesetridenou kopii druhe poloviny (dolni celou cast) pole array merge(int[] firstHalf, int[] secondHalf); // slije prvky v firstHalf a secondHalf do jednoho pole a vrati ho mergesort(int[] array); // vrati setridenou kopii pole array
Druhý Naimplementujte třídu Homework2 implementující rozhraní Matrix. Násobení matic musí být implementováno Strassenovým algoritmem, tzn. metoda times volaná na netriviální matici (matici větší než 1×1) musí svůj výsledek získat pouze pomocí volání metod plus, minus a times na podmaticích. Všechny vaše metody by měly fungovat s jakoukoli korektní implementací rozhraní Matrix. /** Rozhrani Matrix reprezentuje ctvercovou matici, jejiz rozmer je mocnina dvojky. */ interface Matrix { /* Vrati rozmer matice. */ int getSize(); /* Vrati prvek na indexu n, m (1 <= n <= getSize(), 1 <= m <= getSize()). */ int getElement(int n, int m); /* Vrati levou horni podmatici. */ Matrix getTopLeftSubmatrix(); /* Vrati pravou horni podmatici. */ public Matrix getTopRightSubmatrix(); /* Vrati levou dolni podmatici. */ public Matrix getBottomLeftSubmatrix(); /* Vrati pravou dolni podmatici. */ public Matrix getBottomRightSubmatrix(); /* Vrati soucet matic this a other (muzete predpokladat, ze this.getSize() == other.getSize()). */
public Matrix plus(Matrix other); /* Vrati rozdil matic this a other (muzete predpokladat, ze this.getSize() == other.getSize()). */ public Matrix minus(Matrix other); /* Vrati soucin matic this a other (muzete predpokladat, ze this.getSize() == other.getSize()). */ public Matrix times(Matrix other); } class Homework2 implements Matrix { /** Vytvori novou matici (muzete predpokladat, ze contents je ctvercove pole, jehoz rozmer je mocnina dvojky). */ public Homework2(int[][] contents) { /* ... */ } /*
Zbytek tridy Homework2. */
}
Třetí Naimplementujte třídu Homework3 implementující rozhraní HeapStorage a třídu Heap. Za korektní implementaci třídy Homework3 získáte jeden bod, za korektní implementaci třídyHeap další. interface DSAComparable<E> { /** Vrati true, pokud je this (ostre) mensi nez other, false jinak. */ boolean less(E other); /** Vrati nejmensi prvek ze vsech prvku typu E (tzn. prvek, ktery je mensi nez * jakykoli jiny prvek typu E). Vracena hodnota nezavisi na this, jen na E. */ E getLeastElement(); /** Vrati nejvetsi prvek ze vsech prvku typu E (tzn. prvek, ktery je vetsi * nez jakykoli jiny prvek typu E). Vracena hodnota nezavisi na this, jen na E. */ E getGreatestElement(); } /** Rozhrani HeapStorage reprezentuje pole, do ktereho si halda uklada svoje prvky. */ interface HeapStorage<E extends DSAComparable<E>> { /** Vrati aktualni velikost HeapStorage. */ int getSize(); /** Vrati true, pokud je aktualni velikost HeapStorage nulova. */ boolean isEmpty(); /** Vrati prvek na indexu index (1 <= index <= getSize()). Pokud je index
* mensi nebo roven nule, vrati nejvetsi prvek. Pokud je index vetsi nez * velikost pole, vrati nejmensi prvek. V obou pripadech muzete predpokladat, * ze v HeapStorage je alespon jeden prvek. */ E getElement(int index); /** Prohodi prvky na indexech index a index2 (1 <= index, index2 <= getSize()). */ void swap(int index, int index2); /** Odstrani posledni prvek (tzn. snizi velikost teto HeapStorage) a vrati jeho hodnotu. */ E extractLast(); /** Vlozi prvek a vrati jeho index. Muzete predpokladat, ze ve spodnim poli je dost mista. */ int insertLast(E element); } class Homework3<E extends DSAComparable<E>> implements HeapStorage<E>{ /** Vytvori novy objekt HeapStorage nad polem elements, jeho velikost je stejna jako delka pole. */ Homework3(E[] elements) { /* kod */ } /* metody */ } /** Trida Heap reprezentuje haldu (s maximem ve vrcholu). */ class Heap<E extends DSAComparable<E>> { HeapStorage<E> storage; /** Vytvori haldu nad danym HeapStorage (tzn. zavola algoritmus build heap). */ Heap(HeapStorage<E> storage) { /* kod */ } /** Zavola algoritmus heapify nad uzlem na indexu index. */ void heapify(int index) { /* kod */ } /** Vlozi do haldy novy prvek. Muzete predpokladat, ze v poli uvnitr HeapStorage na nej misto je. */ void insert(E element) { /* kod */
} /** Odstrani a vrati z haldy maximalni prvek. */ E extractMax() { /* kod */ } /** Vrati true, pokud je halda prazdna. */ boolean isEmpty() { /* kod */ } /** Pomoci algoritmu trideni haldou vzestupne setridi pole array. */ static <E extends DSAComparable<E>> void heapsort(E[] array) { /* kod */ } }
Soutěž Pokud chcete, můžete se zúčastnit soutěže o nejelegantnější implementaci třetího domácího úkolu. Kritéria elegance jsou zejména: srozumitelnost kódu, jeho kompaktnost a jeho snadná modifikovatelnost. Pro přihlášení do soutěže pošlete email přednášejícímu, uzávěrka přihlášek je shodná s datem odevzdání úkolu, tj. 14. 11. O vítězi rozhodně porota složená z cvičících předmětu, hlavní cena je bod za aktivitu.
Čtvrtý Naimplementujte třídu DSAHashTable (kvůli omezení Javy musíte generické pole alokovat takto: (Set<Pair >[]) new Set[size]). import java.util.Iterator; import java.util.Set; /** Trida Pair reprezentuje dvojici (klic, hodnota). */ class Pair { K key; V value;
Pair(K k, V v) { key = k; value = v; } public int hashCode() { return key.hashCode() + 3 * value.hashCode(); } public boolean equals(Object other) { if (! (other instanceof Pair)) return false; Pair o = (Pair) other; return key.equals(o.key) && value.equals(o.value); } } /** Trida DSAHashTable reprezentuje rozptylovaci tabulku se zřetězením (první varianta v učebnici). */ class DSAHashTable { /** Vytvori prazdnou instanci DSAHashTable, delka vnitrniho pole je nastavena na size, obsah vnitrniho pole * je inicializovan na prazdne mnoziny. */ DSAHashTable(int size) { /* kod */ } /** Ulozi dvojici (key, value) do rozptylovaci tabulky. Pokud uz v tabulce je jina dvojice se stejnym klicem, * je smazana. Klic ani hodnota nesmi byt null. Pokud by pocet dvojic v tabulce po vykonani put mel vzrust nad * dvojnasobek delky vnitrniho pole, vnitrni pole zdvojnasobi. */ void put(K key, V value) { /* kod */ } /** Vrati hodnotu asociovanou s danym klicem nebo null, pokud dany klic v tabulce neni. */ V get(K key) { /* kod */ } /** Smaze dvojici s danym klicem. Pokud v tabulce dany klic neni, nedela nic. */ void remove(K key) { /* kod */ } /** Vrati vnitrni pole. Prvni vnitrniho pole mohou byt instance trid v balicku java.util, tzn. nemusite psat * vlastni implementaci rozhrani java.util.Set. */ Set<Pair>[] getArray() { /* kod */ } /** Pro dany klic vrati index v poli. Jako hashovaci funkce se pouzije key.hashCode. */ int getIndexOf(K key) { /* kod */ } /** Pokud je pocet prvku mensi nebo roven dvojnasobku delky vnitrniho pole, vrati true, jinak vrati false. */ boolean isBigEnough() { /* kod */ } /** Zmeni delku vnitrniho pole, nainicializuje jej prazdnymi mnozinami a zkopiruje do nej vsechny dvojice. */ void resize(int newSize) { /* kod */ }
/** Vrati iterator pres vsechny dvojice v tabulce. Iterator nemusi mit implementovanou metodu remove. */ Iterator<Pair> iterator() { /* kod */ } }
Pátý Naimplementujte třídu Tree. import java.util.Iterator; interface DSAComparable<E extends DSAComparable<E>> { boolean lessOrEqual(E other); boolean greater(E other); boolean equal(E other); } class Node<E extends DSAComparable<E>> { E contents; private Node<E> parent; Node<E> left, right; /** Vrati naslednika (tzn. uzel obsahujici nejblizssi vyssi hodnotu) tohoto uzlu. */ Node<E> succ() { if (right != null) { Node<E> temp = right; while (temp.left != null) temp = temp.left; return temp; } else { Node<E> temp = this; Node<E> parent = this.parent; while (parent != null && parent.right == temp) { parent = parent.parent; temp = temp.parent; } return parent; } } Node(E elem, Node<E> parent) { this.contents = elem; this.parent = parent; }
void setParent(Node<E> p) { parent = p; } } /** * Trida Tree reprezentuje binarni vyhledavaci strom, ve kterem pro kazdy uzel n plati * n.left == null || n.left.contents.lessOrEqual(n.contents) a * n.right == null || n.right.contents.greater(n.contents). */ class Tree<E extends DSAComparable<E>> { Node<E> root; /** Vrati minimum z tohoto stromu nebo null, pokud je strom prazdny. */ E minimum() { /* kod */ } /** Vrati minimum ze zadaneho podstromu nebo null, pokud je podstrom prazdny. */ E subtreeMin(Node<E> n) { /* kod */ } /** Vrati maximum z tohoto podstromu nebo null, pokud je strom prazdny. */ E maximum() { /* kod */ } /** Vrati maximum ze zadaneho podstromu nebo null, pokud je podstrom prazdny. */ E subtreeMax(Node<E> n) { /* kod */ } /** Vlozi prvek do stromu, pripadne duplicity ponechava (tzn. stejny prvek muze * byt ve stromu vickrat). */ void insert(E elem) { /* kod */ } /** * Projde strom smerem za uzlem s hodnotou elem a vrati: * - uzel s hodnotou elem, pokud existuje, * - posledni potkany koncovy uzel (=uzel s maximalne jednim potomkem), pokud uzel s hodnotou elem neexistuje nebo * null pokud je cely strom prazdny. */ Node<E> find(E elem) { /* kod */ } /** Vrati true, pokud tento strom obsahuje prvek elem. */ boolean contains(E elem) { /* kod */ } /** Odstrani jeden vyskyt prvku elem z tohoto stromu. */ void remove(E elem) { /* kod */ } /** Vrati iterator pres cely strom (od nejmensiho po nejvetsi). */ Iterator<E> iterator() { /* kod */ } /** Vrati iterator prochazejici pres interval [lowerBound, higherBound] vcetne. */ Iterator<E> boundedIterator(E lowerBound, E higherBound) { /* kod */ } /** Vrati korenovy uzel tohoto stromu. */ Node<E> getRootNode() { /* kod */ } }
Šestý Dynamické programování je vlastně rekurze zkřížená s memoizací. Samotný rekurzivní popis algoritmu je pro každou úlohu jiný, ale memoizace je pořád stejná - řešení podúloh se zaznamenává do tabulky a znovupoužívá, když je potřeba. Vaším úkolem je naprogramovat metodu Machine.solve, ve které bude právě ta memoizace. Metodasolve by při zavolání měla: 1. mrknout do tabulky a pokud v ní řešení už je, vrátit ho, 2. pokud v tabulce řešení není, měla by si ze zadané úlohy vytáhnout možná podřešení a vybrat to nejlepší (s nejvyšší hodnotou) a 3. před vrácením nejlepšího řešení by si ho měla uložit do tabulky. import import import import
java.util.HashMap; java.util.HashSet; java.util.Map; java.util.Set;
/** Trida Pair reprezentuje dvojici. */ class Pair { First first; Second second; Pair(First f, Second s) { first = f; second = s; } First getFirst() { return first; } Second getSecond() { return second; } } /** Instance rozhrani Task reprezentuji optimalizacni ulohu. */ interface Task, S extends Solution, W extends Comparable<W>> { /** Vrati vsechna mozna (ne nutne optimalni) reseni teto ulohy. Vzdy vrati alespon jedno reseni. */ Set<S> getPossibleSolutions(); } /** Instance rozhrani Solution reprezentuji reseni nejake konkretni optimalizacni ulohy. */
interface Solution, S extends Solution, W extends Comparable<W>> { /** Vrati hodnotu tohoto reseni. */ W getWorth(Machine m); } class Machine, S extends Solution, W extends Comparable<W>> { Map> cache = new HashMap>(); Pair<S, W> solve(T task) { /* kod */ } } class RodTask implements Task { final int length; final int[] table; final Set sols = new HashSet(); static int instanceCount; RodTask(int length, int[] table) { this.length = length; this.table = table; for (int i = 1; i <= length; i++) sols.add(new RodSolution(i, length - i, table)); instanceCount++; } public Set getPossibleSolutions() { return sols; } public int hashCode() { int code = length; for (int i : table) code += 3 * i; return code; } public boolean equals(Object o) { if (!(o instanceof RodTask)) return false; RodTask other = (RodTask) o; if (length != other.length || table.length != other.table.length) return false; for (int i = 0; i < table.length; i++) if (table[i] != other.table[i]) return false;
return true; } } class RodSolution implements Solution { final int first; final int rest; final int[] table; RodSolution(int first, int rest, int[] table) { this.first = first; this.rest = rest; this.table = table; } public Integer getWorth(Machine m) { int worth = table[first]; if (rest > 0) worth += m.solve(new RodTask(rest, table)).getSecond(); return worth; } }
Sedmý Naprogramujte B-strom. import java.util.List; /** Instance tridy Tree reprezentuji B-strom. */ class Tree { /** Koren tohoto stromu. */ Node root; /* atributy */ /** Vytvori prazdny B-strom se zadanou kapacitou uzlu. Kapacita uzlu je * maximalni pocet klicu, ktere se v jednom uzlu mohou objevit. */ Tree(int nodeCapacity) { /* kod */ }
/** Indikuje, jestli tento strom obsahuje zadany klic. */ boolean contains(Integer key) { /* kod */ } /** Prida zadany klic do stromu. Pokud tento strom zadany klic uz obsahuje, * neudela nic. */ void add(Integer key) { /* kod */ } /** Odebere zadany klic ze stromu. Pokud tento strom zadany klic neobsahuje, * neudela nic. */ void remove(Integer key) { /* kod */ } /* kod */ } class Node { /* atributy */ /** Vrati klice ulozene v tomto uzlu serazene vzestupne. */ List getKeys() { /* kod */ } /** Vrati ukazatele na podstromy ulozene v tomto uzlu serazene v poradi odpovidajicim * poradi klicu. Pozor: vzdy musi platit, ze pocet_ukazatelu_na_podstromy = pocet_klicu + 1, * u listovych uzlu proto musite vracet seznam nullu. */ List getSubtrees() { /* kod */ } }
Zadání těžších domácích úkolů První
Ve Featherweight Javě naimplementujte datovou strukturu v C. Okasaki: Purely Functional Data Structures označovanou jako persistent binary random-access list. Pro počáteční nasměrování a dodatečné informace kontaktujte přednášejícího. Základní knihovnu FJ z minulého semestru najdete nahttps://cvut.repositoryhosting.com/trac/cvut_lectures/browser/Lecture14/src/lecture14/Lecture14.java
Druhý Naimplementujte níže uvedené třídy a rozhraní a s jejich pomocí napište následující algoritmy: řazení vkládáním, řazení sléváním, quicksort, quick seleck a řazení haldou. Pokud bude potřeba, můžete níže uvedenou strukturu tříd obohatit o nové metody nebo mírně změnit, ale měli byste zachovat stejného ducha. /** Instance implementujici toto rozhrani reprezentuji multimnozinu, * ktera se po vytvoreni uz nezmeni. */ interface ImmutableMultiset<E> { /** Vrati sjednoceni teto a zadane multimnoziny. */ ImmutableMultiset<E> union(ImmutableMultiset<E> other); /** Vrati rozdil teto a zadane multimnoziny. */ ImmutableMultiset<E> difference(ImmutableMultiset<E> other); /** Vrati, zda tato multimnozina obsahuje zadany prvek. */ ImmutableBoolean contains(E elem); /** Vrati velikost teto multimnoziny. */ ImmutableInteger size(); } /** Instance teto tridy reprezentuji prazdnou multimnozinu. */ class EmptyMultiset<E> implements ImmutableMultiset<E> { static <E> EmptyMultiset<E> createEmptyMultiset(); } /** Instance teto tridy reprezentuji multimnozinu s jednim prvkem. */ class SingletonMultiset<E> implements ImmutableMultiset<E> { static <E> SingletonMultiset<E> createSingletonMultiset(E elem); } /** Instance teto tridy reprezentuji sjednoceni dvou multimnozin. */ class Union<E> implements ImmutableMultiset<E> { static <E> Union<E> createUnion(ImmutableMultiset<E> first, ImmutableMultiset<E> second); }
/** Instance teto tridy reprezentuji rozdil dvou multimnozin. */ class Difference<E> implements ImmutableMultiset<E> { static <E> Difference<E> createDifference(ImmutableMultiset<E> first, ImmutableMultiset<E> second); } /** Instance implementujici toto rozhrani reprezentuji sekvenci, * ktera se po vytvoreni uz nezmeni. */ interface ImmutableSequence<E> { /** Vrati spojeni teto a zadane sekvence. */ ImmutableSequence<E> concat(ImmutableSequence<E> other); /** Vrati podsekvenci zadane sekvence. Prvni prvek sekvence ma index nula. */ ImmutableSequence<E> subsequence(ImmutableInteger from, ImmutableInteger to); /** Vrati delku teto sekvence. */ ImmutableInteger size(); /** Vrati prvek na zadanem indexu. Prvni prvek ma index nula. */ E elementAt(ImmutableInteger position); } /** Instance teto tridy reprezentuji prazdnou sekvenci. */ class EmptySequence<E> implements ImmutableSequence<E> { static <E> EmptySequence<E> createEmptySequence(); } /** Instance teto tridy reprezentuji sekvenci delky jedna. */ class SingletonSequence<E> implements ImmutableSequence<E> { static <E> SingletonSequence<E> createSingletonSequence(E elem); } /** Instance teto tridy reprezentuji spojeni dvou sekvenci. */ class Concatenation<E> implements ImmutableSequence<E> { static <E> Concatenation<E> createConcatenation(Sequence<E> first, Sequence<E> second); } /** Instance teto tridy reprezentuji podsekvenci nejake sekvence. */ class Subsequence<E> implements ImmutableSequence<E> { static <E> Subsequence<E> createSubseqence(Sequence<E> seq, ImmutableInteger from, ImmutableInteger to); } /** Instance teto tridy reprezentuji cele cislo, ktere se po vytvoreni jiz nezmeni. */ interface ImmutableInteger { /** Vrati soucet tohoto a zadaneho cisla. */ ImmutableInteger plus(ImmutableInteger other);
/** Vrati rozdil tohoto a zadaneho cisla. */ ImmutableInteger minus(ImmutableInteger other); /** Vrati soucin tohoto a zadaneho cisla. */ ImmutableInteger times(ImmutableInteger other); /** Vrati podil tohoto a zadaneho cisla. */ ImmutableInteger dividedBy(ImmutableInteger other); /** Indikuje, zda je toto cislo mensi, nez zadane. */ ImmutableBoolean less(ImmutableInteger other); /** Indikuje, zda je toto cislo shodne jako zadane. */ ImmutableBoolean equal(ImmutableInteger other); /** Indikuje, zda je toto cislo vetsi, nez zadane. */ ImmutableBoolean greater(ImmutableInteger other); } /** Instance teto tridy reprezentuji konstantu. */ class Constant implements ImmutableInteger { static Constant createConstant(int c); } /** Instance teto tridy reprezentuji soucet dvou cisel. */ class Plus implements ImmutableInteger { static Plus createPlus(ImmutableInteger first, ImmutableInteger second); } /** Instance teto tridy reprezentuji rozdil dvou cisel. */ class Minus implements ImmutableInteger { static Minus createMinus(ImmutableInteger first, ImmutableInteger second); } /** Instance teto tridy reprezentuji soucin dvou cisel. */ class Product implements ImmutableInteger { static Product createProduct(ImmutableInteger first, ImmutableInteger second); } /** Instance teto tridy reprezentuji podil dvou cisel. */ class Division implements ImmutableInteger { static Division createDivision(ImmutableInteger first, ImmutableInteger second); } /** Instance implementujici toto rozhrani reprezentuji pravdivostni hodnotu, * ktera se po vytvoreni jiz nezmeni. */ interface ImmutableBoolean {
/** Vrati negaci teto hodnoty. */ ImmutableBoolean not(); /** Vrati konjunkci teto a zadane hodnoty. */ ImmutableBoolean and(ImmutableBoolean other); /** Vrati disjunkci teto a zadane hodnoty. */ ImmutableBoolean or(ImmutableBoolean other); } /** Instance teto tridy reprezentuji pravdu. */ class True implements ImmutableBoolean { static True createTrue(); } /** Instance teto tridy reprezentuji nepravdu. */ class False implements ImmutableBoolean { static False createFalse(); } /** Instance teto tridy reprezentuji negaci nejake pravdivostni hodnoty. */ class Negation implements ImmutableBoolean { static Negation createNegation(); } /** Instance teto tridy reprezentuji konjunkci dvou pravdivostnich hodnot. */ class Conjunction implements ImmutableBoolean { static Conjunction createConjunction(ImmutableBoolean other); } /** Instance teto tridy reprezentuji disjunkci dvou pravdivostnich hodnot. */ class Disjunction implements ImmutableBoolean { static Disjunction createDisjunction(ImmutableBoolean other); } /** Instance teto tridy reprezentuji multimnozinu. Obsah multimnoziny je reprezentovan * v promenne inner. */ class DSAMultiset<E> { ImmutableMultiset<E> inner; /* Vytvori a vrati prazdnou multimnozinu. */ static DSAMultiset createEmptyMultiset(); /* Vytvori a vrati multimnozinu s jednim prvkem. */ static <E> DSAMultiset<E> createSingletonMultiset(E elem); /* Prida zadany prvek do teto multimnoziny. */
void add(E elem); /* Prida vsechny prvky v zadane multimnozine do teto multimnoziny. */ void addAll(DSAMultiset<E> ms); /* Odstrani zadany prvek z teto multimnoziny. */ void remove(E elem); /* Odstrani vzechny prvky v zadane multimnozine z teto multimnoziny. */ void removeAll(DSAMultiset<E> elem); /* Vyrobi kopii teto multimnoziny. */ DSAMultiset<E> clone(); /* Vrati velikost teto multimnoziny. */ ImmutableInteger size(); /* Indikuje, zda tato mnozina obsahuje zadany prvek. */ ImmutableBoolean contains(E elem); } /** Instance teto tridy reprezentuji sekvenci. Obsah sekvence je reprezentovan * v promenne inner. */ class DSASequence<E> { ImmutableSequence<E> inner; /* Vytvori a vrati prazdnou sekvenci. */ static DSASequence createEmptySequence(); /* Vytvori a vrati multimnozinu o delce jedna. */ static <E> DSASequence<E> createSingletonSequence(E elem); /* Pripoji zadanou sekvenci do teto sekvence. */ DSASequence<E> append(DSASequence<E> other); /* Pripoji zadanou sekvenci na zacatek teto sekvence. */ DSASequence<E> prepend(DSASequence<E> other); /* Vrati podsekvenci teto sekvence (jako nezavisly objekt). */ DSASequence<E> subseq(ImmutableInteger from, ImmutableInteger to); /* Vrati velikost teto sekvence. */ ImmutableInteger size(); /* Vrati prvek na zadanem indexu, prvni prvek ma index nula. */ E elementAt(ImmutableInteger elem); }
