Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti
Domácí úkoly z předmětu OMO První domácí úkol Napište třídu Assignment1, která má následující (neprivátní) metody: 1. boolean f(), která vždy vrátí hodnotu true, 2. statickou boolean g(), která vždy vrátí hodnotu false, 3. int h(), která vždy vrátí počet volání metody h na této instanci (včetně právě probíhajícího volání, tzn. první volání metody h na dané instanci vrátí 1), 4. int
i(),
která
vždy
vrátí
počet
volání
metody i na
libovolné
instanci
třídy Assignment1 (včetně právě probíhajícího volání). Odevzdávaný kód (tzn. třídu Assignment1) adresáře hw/Assignment1.java.
uložte
do
svého
repozitáře
do
Druhý domácí úkol Instance třídy Node reprezentuje strom: atribut contents nese hodnotu, atributy left a right ukazují na levý a pravý podstrom aktuálního stromu, případně jsou null, pokud levý resp. pravý podstrom neexistuje. Vaším úkolem je dopsat do třídy Node tyto metody:
boolean
contains(int
value) -
vrátí true tehdy
a
pouze
tehdy,
pokud
je
hodnota value obsažena v tomto stromu a
void add(int value) - vloží hodnotu value do aktuálního stromu podle následujícího
algoritmu: pokud je hodnota v aktuálním uzlu rovná value, nedělá nic, pokud je hodnota v aktuálním uzlu větší než value, vloží value do levého podstromu, pokud je hodnota v aktuálním uzlu menší než value, vloží value do pravého podstromu; pokud levý, resp. pravý podstrom neexistuje, vytvoří ho. class Node { final int contents; Node left, right; Node(int c) { contents = c;
} boolean contains(int value) { ... } void add(int value) { ... } }
Odevzdávaný kód (tzn. souboru hw/Assignment2.java.
třídu Node)
uložte
do
svého
repozitáře
do
Třetí domácí úkol Interface OMOSetView definuje rozhraní umožňující přístup k prvkům množiny celých čísel: interface OMOSetView { boolean contains(int element); // testuje na přítomnost prvku v množině int[] toArray(); //vrátí kopii prvků množiny v poli (na pořadí prvků nezáleží) OMOSetView copy(); //vrátí kopii množiny }
Množina vrácená metodou copy() volané na instanci „a“ nebude v případě následné změny (přidání/odebrání prvků) „a“ změněna. Dopište kód následujících tříd: // třída reprezentující obecnou přidávání/odebírání prvků class OMOSet implements OMOSetView { public void add(int element) { //přidá prvek "element" do množiny }
množinu,
definuje
metody
add/remove
pro
public void remove(int element) { //odebere prvek "element" z množiny } // metody rozhraní OMOSetView } // třída reprezentující sjednocení dvou množin: A sjednoceno B class OMOSetUnion implements OMOSetView { OMOSetUnion(OMOSetView setA, OMOSetView setB) { //... } // metody rozhraní OMOSetView } // třída reprezentující průnik dvou množin: A průnik B class OMOSetIntersection implements OMOSetView { OMOSetIntersection(OMOSetView setA, OMOSetView setB) { //... } // metody rozhraní OMOSetView } // třída reprezentující A\B: doplněk množiny B vzhledem k množině A: x∈A ∧ x∉B } class OMOSetComplement implements OMOSetView { OMOSetComplement(OMOSetView setA, OMOSetView setB) { //... } // metody rozhraní OMOSetView
A\B = { x |
}
Instance tříd OMOSetUnion, OMOSetIntersection a OMOSetComplement si udržují pouze reference na instance dílčích tříd A a B (tj. neukládají si kopie jejich prvků). Pokud tedy vytvoříme například sjednocení dvou množin A a B a následovně odeberem prvek z množiny A, projeví se to i na výsledku sjedocení. Odevzdávaný kód (tzn. rozhraní OMOSetView, třídy OMOSet, OMOSetUnion, OMOSetIntersection a OMOSetComplement) uložte do svého repozitáře do souboru hw/Assignment3.java.
Čtvrtý domácí úkol Instance třídy Node reprezentuje kořen stromu obsahujícího celá čísla. Vaším úkolem je naprogramovat metody inorderIterator(), preorderIterator(), postorderIterator, které vrátí iterátory vracející prvky daného stromu v pořadí inorder, preorder resp. postorder. Jedna instance iterátoru smí v paměti alokovat maximálně konstantní prostor, tzn. paměťové nároky iterátoru nesmí růst s počtem uzlů v daném stromu. Specificky: nesmíte iterátory implementovat tak, že „přesypete“ všechny prvky do již existující kolekce a vrátíte její iterátor. Samozřejmě také nesmíte modifikovat iterovaný strom. Odevzdávaný kód (tzn. třídu Node a třídy iterátorů) uložte do svého repozitáře do adresáře hw/Assignment4.java. Pokud si ze cvičení nepamatujete co je preorder, inorder a postorder, můžete se to dozvědět na http://datastructuresnotes.blogspot.cz/2009/02/binary-treetraversal-preorder-inorder.html . interface CustomIterator { boolean hasNext(); int next(); } class Node { final int contents; final Node left, right; Node parent; Node(int contents, Node left, Node right) { this.contents = contents; this.left = left; if (left != null) left.parent = this; this.right = right; if (right != null) right.parent = this; } CustomIterator preorderIterator() { ... } CustomIterator inorderIterator() { ... } CustomIterator postorderIterator() { ... } }
Pátý domácí úkol Zadání tohoto domácího úkolu je inspirováno technologií BitTorrent, ve které si skupina uzlů navzájem posílá stahovaná data tak dlouho, až každý uzel stáhne celý soubor. Část kódu už naprogramovaná je, vaším úkolem je napsat kód třídy Assignment5 dědící ze třídy MessageVisitor. class Assignment5 extends MessageVisitor { public Assignment5(Peer peer) { super(peer); } // zde doplnte svuj kod }
„Okolí“ vašeho kódu tvoří níže uvedené třídy.
import java.util.Map; import java.util.Queue; import java.util.concurrent.LinkedBlockingQueue; /** * Instance implementujici PeerInterface reprezentuje lokalni uzel nebo uzel * pripojeny pres sit. */ interface PeerInterface { /** * Sdeli vzdalenemu uzlu, ze uzel sender prave obdrzel blok s indexem * blockIndex. */ void have(PeerInterface sender, int blockIndex); /** * Pozada vzdaleny uzel o blok s indexem blockIndex. */ void request(PeerInterface sender, int blockIndex); /** * Zasle vzdalenemu uzlu blok s indexem blockIndex. */ void piece(PeerInterface sender, int blockIndex, byte[] data); } /** * Instance tridy Peer reprezentuje lokalni uzel. */ class Peer implements PeerInterface { /** * Fronta nezpracovanych zprav. */ final Queue<Message> messageQueue = new LinkedBlockingQueue<>(); /** * Mapovani z uzlu na bitovou mapu urcujici ktere bloky ma dany uzel k * dispozici. */ final Map
peers2BlocksMap; /** * Celkovy pocet bloku ve stahovanem souboru. */ final int totalBlocksCount; /** * Pole se stazenymi bloky. */ final byte[][] data; /** * Pocet stazenych bloku. */ int downloadedBlocksCount = 0; public Peer(Map totalBlocksCount) { this.peers2BlocksMap = peers2BlocksMap; this.totalBlocksCount = totalBlocksCount; data = new byte[totalBlocksCount][]; }
peers2BlocksMap,
/** * Prijme zpravu "have" a prida ji do fronty zprav. */ public void have(PeerInterface sender, int blockIndex) { messageQueue.add(new HaveMessage(blockIndex, sender)); } /** * Prijme zpravu "request" a prida ji do fronty zprav.
int
*/ public void request(PeerInterface sender, int blockIndex) { messageQueue.add(new RequestMessage(blockIndex, sender)); } /** * Prijme zpravu "piece" a prida ji do fronty zprav. */ public void piece(PeerInterface sender, int blockIndex, byte[] data) { messageQueue.add(new PieceMessage(blockIndex, data, sender)); } /** * Vyzvedne nejstarsi zpravu z fronty zprav a zpracuje ji pomoci zadaneho * navstevnika. Pokud ve fronte zadna zprava neni, zasle sam sobe a zpracuje * zpravu "idle". Vrati true v pripade, ze tento uzel stahnul vsechny bloky, * false jinak. */ boolean processMessage(MessageVisitor visitor) { return (messageQueue.isEmpty() ? new IdleMessage(this) messageQueue.poll()).accept(visitor); } } /** * Instance tridy MessageVisitor reprezentuji navstevniky zpracovavajici zpravy. */ abstract class MessageVisitor { final Peer peer; public MessageVisitor(Peer peer) { this.peer = peer; } /* * Zpracuje zpravu "have": v lokalnim uzlu vyznaci, ze dany vzdaleny uzel ma * k dispozici blok s danym indexem. * * Vzdy vrati false. */ abstract boolean visitHaveMessage(HaveMessage message); /* * Zpracuje zpravu "request": pokud ma lokalni uzel pozadovany blok k * dispozici, obratem ho posle vzdalenemu uzlu pomoci zpravy "piece". Pokud * ne, pozadavek ignoruje. * * Vzdy vrati false. */ abstract boolean visitRequestMessage(RequestMessage message); /* * Zpracuje zpravu "piece": ulozi obdrzena data * pocet stazenych bloku a vsem vzdalenym uzlum * data obdrzel) rozesle zpravu "have". * * Vrati true, pokud lokalni uzel stahl vsechny */ abstract boolean visitPieceMessage(PieceMessage
do lokalniho uzlu, zvysi (vcetne toho, od ktereho bloky, false jinak. message);
/* * Zpracuje zpravu "idle": vybere nejvzacnejsi jeste nestazeny blok a zazada * o nej u nektereho z jeho vlastniku. Nejvzacnejsi blok je takovy, ktery * vlastni nejmene vzdalenych uzlu. Pokud je nejvzacnejsich bloku nekolik, * vybere jeden z nich. * * Vzdy vrati false. */
:
abstract boolean visitIdleMessage(IdleMessage message); } abstract class Message { final PeerInterface sender; public Message(PeerInterface sender) { this.sender = sender; } abstract boolean accept(MessageVisitor visitor); } class HaveMessage extends Message { final int blockIndex; public HaveMessage(int blockIndex, PeerInterface sender) { super(sender); this.blockIndex = blockIndex; } boolean accept(MessageVisitor visitor) { return visitor.visitHaveMessage(this); } } class RequestMessage extends Message { final int blockIndex; public RequestMessage(int blockIndex, PeerInterface sender) { super(sender); this.blockIndex = blockIndex; } boolean accept(MessageVisitor visitor) { return visitor.visitRequestMessage(this); } } class PieceMessage extends Message { final int blockIndex; final byte[] data; public PieceMessage(int blockIndex, byte[] data, PeerInterface sender) { super(sender); this.blockIndex = blockIndex; this.data = data; } boolean accept(MessageVisitor visitor) { return visitor.visitPieceMessage(this); } } class IdleMessage extends Message { public IdleMessage(PeerInterface sender) { super(sender); } @Override boolean accept(MessageVisitor visitor) { return visitor.visitIdleMessage(this); } }
Odevzdávaný kód (tzn. třídu Assignment5) souboru hw/Assignment5.java.
uložte
do
svého
repozitáře
do
Šestý domácí úkol Kvůli přílišné prodlevě ve spuštění testu byl tento domácí úkol zrušen. Pokud jste i bez testu vypracovali jeho správné řešení, pošlete ho přednášejícímu a ten vám navrhne úlevu z budoucích úkolů. Tento úkol volně navazuje na kód ze cvičení v osmém týdnu. Aktuální (nekomitnutý) stav adresáře je reprezentován mapou files, ve které jsou jména všech existujících souborů uložena jako klíče a obsahy těchto souborů jako příslušné hodnoty. Vaším úkolem je napsat metodu ChangeSet RepositoryView.createChangeSet(ImmutableMap<String, String> files), která vrátí ChangeSet reprezentující rozdíl mezi this afiles. Pokud mezi this a files žádný rozdíl není, vrátí prázdný ChangeSet. Formálně vzato má pro všechny instance Repository r, RepositoryView rv, ImmutableMap<String, String> f a String n platit r.addChangeSet(rv.createChangeSet(f)).getFileContents(n).equals(f.get(n)). Navíc musí být vaše ChangeSety co nejmenší, proto musíte využít (již naprogramovanou) metodu List DifferenceUtils.longestCommonSubsequence(String, String), která ke dvěma řetezcům vrátí seznam všech indexů shodných řádků (indexy jsou vztaženy k prvnímu z řetězců). Např. k řetězcům avokádo brambora citrón dýně jablko pomeranč
a avokádo citrón granátové jablko jablko meloun pomeranč
vrátí seznam 0, 2, 4, 5. Odevzdávaný kód (tzn. třídu RepositoryView) adresáře hw/Assignment6.java. import import import import import import import
uložte
com.google.common.collect.ImmutableList; com.google.common.collect.ImmutableMap; java.util.ArrayList; java.util.List; java.util.Objects; java.util.Arrays; java.util.LinkedList;
/** * Trida Repository reprezentuje repozitar. */ class Repository { final List changeSets = new ArrayList<>();
do
svého
repozitáře
do
/** * Vytvori prazdny repozitar. */ public Repository() { changeSets.add(new ChangeSet(null, ImmutableMap.<String, Change>of())); } /** * Prida zadany changeset do tohoto repozitare a vrati novou revizi. */ RepositoryView addChangeSet(ChangeSet changeSet) { changeSets.add(changeSet); return new RepositoryView(this, changeSets.size() - 1); } /** * Vrati revizi s danym cislem. */ RepositoryView getRevision(int number) { return new RepositoryView(this, number); }
Sedmý domácí úkol Tento a příští domácí úkol spolu budou volně spojeny, jejich společným tématem je herní engine. Hlavními rozhraními tohoto úkolu jsou rozhraní Movable, resp. Actuator: rozhraní Movable reprezentuje objekty, které se mohou pohybovat, a rozhraní Actuator reprezentuje objekty, které hýbou nějakými jinými objekty. interface Movable { /** Vrati aktualni polohu. */ Pair getPosition(); /** Pohne timto objektem o dx pixelu doprava a dy dolu. */ void move(int dx, int dy); } interface Actuator { /** Pohne objektem v parametru. */ void actuate(Movable movable); } /** Instance tridy Pair reprezentuji dvojice hodnot. */ class Pair { final A first; final B second; public Pair(A first, B second) { this.first = first; this.second = second; } }
Vaším úkolem je dopsat tříd Up, Down, Left, Right, ParallellyComposingActuator a AmplifyingActuator podle následující specifikace:
instance třídy Up při jednom volání metody actuate pohne zadaným objektem o jeden pixel nahoru,
kód
instance třídy Down pohne zadaným objektem o jeden pixel dolů,
instance třídy Left pohne zadaným objektem o jeden pixel doleva,
instance třídy Right pohne zadaným objektem o jeden pixel doprava,
instance třídy ParallellyComposingActuator sečte pohyby všech aktuátorů zadaných v konstruktoru do jednoho a
instance
třídy AmplifyingActuator zopakuje
pohyb
aktuátorem
zadaným
konstruktoru factor-krát. class Up implements Actuator { @Override public void actuate(Movable movable) { } } class Down implements Actuator { @Override public void actuate(Movable movable) { } } class Left implements Actuator { @Override public void actuate(Movable movable) { } } class Right implements Actuator { @Override public void actuate(Movable movable) { } } class ParallellyComposingActuator implements Actuator { public ParallellyComposingActuator(ImmutableList motors) { } @Override public void actuate(Movable movable) { } } class AmplifyingActuator implements Actuator { public AmplifyingActuator(Actuator motor, int factor) { } @Override public void actuate(Movable movable) { } }
v
Chování třídy SequentiallyComposingActuator je malinko složitější. Tato třída v konstruktoru dostane (nekonečný) seznam dvojic (predikát, aktuátor). Aktuátor z první dvojice vrácené iterátorem používá pro pohyb zadaného objektu tak dlouho, dokud první predikát na zadaném objektu vrací true. Poté přejde na druhou dvojici, pak na třetí atd. class SequentiallyComposingActuator implements Actuator { public SequentiallyComposingActuator(Iterable<Pair, Actuator>> iterable) { } @Override public void actuate(Movable movable) { } }
Nakonec naimplementujte metody Assignment7.getFirstActuator, Assignment7.getSecondActuator a Assignment7.get ThirdActuator:
Assignment7.getFirstActuator vrátí aktuátor, který zadaným objektem pohne o jeden
pixel doprava a o jeden pixel nahoru,
Assignment7.getSecondActuator vrátí aktuátor, který zadaným objektem pohne o
jeden
pixel
doleva,
pokud
uživatel
stiskl
klávesu
doleva
(indikováno
metodouKeyboard.leftArrowPressedDown), o jeden pixel doprava, pokud uživatel stiskl klávesu doprava (indikováno metodou Keyboard.rightArrowPressedDown) a nepohne nikam, pokud uživatel nestiskl ani jednu z kláves nebo stiskl obě naráz,
Assignment7.getThirdActuator(Actuator
firstActuator,
Actuator
secondActuator) vrátí aktuátor, který pro pohyb střídá dva zadané aktuátory -
nejprve desetkrát použijefirstActuator, potom dvacetkrát secondActuator, pak opět desetkrát firstActuator atd. class Keyboard { static boolean leftArrowPressedDown() { /* kod */ } static boolean rightArrowPressedDown() { /* kod */ } } class Assignment7 { static Actuator getFirstActuator() { } static Actuator getSecondActuator() { } static Actuator secondActuator) { } }
getThirdActuator(final
Actuator
firstActuator,
Actuator
Odevzdávaný kód (tzn. třídy Up, Down, Left, Right, ParallellyComposingActuator, AmplifyingActuator, Sequentiall yComposingActuator a Assignment7) uložte do svého repozitáře do adresáře hw/Assignment7.java. Třídu Keyboard neodevzdávejte, dodá si ji testovací systém.
Osmý domácí úkol Napište třídu HorizontalFlip implementující rozhraní ActuatorVisitor tak, aby volání actuator.accept(new HorizontalFlip()) vrátilo horizontálně převrácený aktuátor. Horizontálně převrácený aktuátor je definovaný následovně: pokud původní aktuátor v nějaké situaci pohnul s předaným objektem o (dx, dy), tak horizontální aktuátor ve stejné situaci pohne s předaným objektem o (-dx, dy). Většinu metod visit* můžete jednoduše naimplementovat tak, že vrátíte kopii aktuátoru a případně instanci Left přehodíte instanci Right (a naopak). U metodyvisitSequentiallyComposingActuator tento přístup nebude fungovat atribut iterable totiž může reprezentovat nekonečný seznam. Proto ho musíte obalit dekorátorem, který instance Left a Right zaměňuje až během iterování (tzn. při návratu z metody next). Samozřejmě jsou možné i jiné způsoby řešení, fantazii se meze nekladou. Pozor: i když tento úkol konceptuálně navazuje na úkol předchozí, implementace tříd Up, Down apod. je naše. Díky tomu můžete na obou úkolech pracovat nezávisle. Odevzdávaný kód (tzn. třídu HorizontalFlip a případné pomocné třídy) uložte do svého repozitáře do souboru hw/Assignment8.java. import com.google.common.base.Predicate; import com.google.common.collect.ImmutableList; import java.util.Iterator; interface Movable { void move(int dx, int dy); /* dalsi metody */ } class Pair { final A first; final B second; public Pair(A first, B second) { this.first = first; this.second = second; } } interface Actuator { Actuator accept(ActuatorVisitor v); void actuate(Movable movable); /* dalsi metody */ } interface ActuatorVisitor { Actuator visitUp(Up actuator); Actuator visitDown(Down actuator); Actuator visitLeft(Left actuator); Actuator visitRight(Right actuator);
Devátý domácí úkol Napište kód metody Engine.oneIteration, která
jednou pohne s každým z objektů v kolekci gameObjects,
pro každou dvojici navzájem různých objektů z gameObjects zkontroluje, jestli spolu nejsou v kolizi a
pokud
spolu
některé
dva
objekty
jsou
v
kolizi,
zavolá
na
obou
z
nich
metodu reactToCollisionWith a jako parametr jim předá objekt, se kterým jsou v kolizi. Odevzdávaný kód (tzn. souboru hw/Assignment9.java.
třídu Engine)
uložte
do
svého
repozitáře
do
import java.util.HashSet; import java.util.Set; class Engine { final Set gameObjects = new HashSet<>(); void mainLoop() { while (true) oneIteration(); } void oneIteration() { // kod } } interface Movable { Pair getPosition(); void move(int dx, int dy); } interface Actuator { void actuate(Movable movable); } class Pair { final A first; final B second; public Pair(A first, B second) { this.first = first; this.second = second; } }
Desátý domácí úkol Vaším úkolem je doprogramovat třídy implementující rozhraní Node podle následující specifikace: 1. metoda maxTreeDepth vrátí
maximální
hloubku
nějakého
listového
uzlu
(instance LeafNode), hloubka stromu o jednom uzlu je 1, 2. metoda minDepthOfLeafNode vrátí minimální hloubku nějakého listového uzlu, 3. metoda maxAlternateTreeDepth vrátí maximální hloubku pouze z těch listových uzlů, které
nejsou
potomky MarkerNode,
potomky MarkerNode, vrátí 0,
pokud
jsou
všechny
listové
uzly
4. metoda alternateTreeDepthCopy vrátí kopii daného stromu, ve které jsou podtromy pod
instancemi MarkerNode nahrazeny
InnerNode(ImmutableList.of(new
LeafNode(),
new
instancí LeafNode (např. new MarkerNode(new
LeafNode()))) je
zkonvertován na new InnerNode(ImmutableList.of(new LeafNode(), new LeafNode())). Odevzdávaný kód (rozhraní Node a třídy LeafNode, InnerNode a MarkerNode) uložte do svého repozitáře do souboru hw/Assignment10.java. import com.google.common.collect.ImmutableList; interface Node { int maxTreeDepth(); int minDepthOfLeafNode(); int maxAlternateTreeDepth(); Node alternateTreeDepthCopy(); } class LeafNode implements Node { } class InnerNode implements Node { final ImmutableList children; public InnerNode(ImmutableList children) { assert children.size() > 0; this.children = children; } } class MarkerNode implements Node { final Node child; public MarkerNode(Node child) { this.child = child; } }
Jedenáctý domácí úkol Nastudujte si jak se používá typ Optional - typ, který může sloužit jako náhrada nulového ukazatele. Poté naimplementujte generické třídy MapFunction a FunctionComposition. První třída „zkonvertuje“ mapování zadané v konstruktoru na parciální funkci (parciální funkce je funkce, která nemusí ke každému vstupu vrátit výstup), druhá složí dvě funkce a vyrobí z nich třetí. Odevzdávaný kód (třídy MapFunction a FunctionComposition) uložte do svého repozitáře do souboru hw/Assignment11.java. import com.google.common.base.Function; import com.google.common.base.Optional; import com.google.common.collect.ImmutableMap; class MapFunction implements Function> { final ImmutableMap map; public MapFunction(ImmutableMap map) { this.map = map; } @Override public Optional
