Cvičení 4

Na tomto cvičení jsme se podívali na iterátory a na přetypování operátorů. Vytvořili jsme soubory list3.h, list3.cpp a priklad3.cpp.

Pozor: 30.3. cvičení odpadá

V pondělí 30.3. cvičení odpadá z důvodu mé absence (konference).

2. úkol

Tak uplynulo pár týdnů a je čas na další úkol, který by měl otestovat vaše schopnosti. Na cvičení jsme tvořili obousměrný seznam, nyní je úkolem implementovat dynamické pole.

Tedy strukturu, ke které lze přistupovat pomocí indexu (a testuje zda je index v mezích pole).

• Získání prvku (dle indexu) by mělo fungovat v čase O(1)
  
• Odebrání prvku z libovolného místa v čase O(n) - odebírání bude posouvat existující prvky
• Přidání prvku na libovolné místo v čase O(n) - přidání bude také posouvat existující prvky
• Při překročení vyhrazené paměti si objekt vyhradí dvojnásobek paměti.
• Při zmenšení obsazení paměti na 1/4 objekt část paměti zas uvolní (1/2).
• Objekt si může na začátku vyhradit paměť pro minimální počet položek.
• Při svém zániku objekt uvolní veškerou svou paměť.
• Objekt půjde zkopírovat (hluboká kopie).
• A bude obsahovat operátory pro porovnání ==, !=
• Při přidání prvku za konec pole, přístupu k neex. prvku, nebo odebrání neexistujícího prvku vyvolejte výjimku.
  

Testy
Na poli proveďte následující test použití.

1. vytvoření prázdného pole1
2. přidání 1000 prvků na náhodné indexy do pole1.
3. pole2(pole1) - zkopírování pole
4. test pole2 == pole1
5. odebrání 1 prvku z pole2
6. test pole2 != pole1
7. odebrání všech prvků z pole2 náhodným způsobem
8. uvolnění obou polí

Dobrovolné frajeřinky

1. vlastní dopředný iterátor
2. vytvoření šablonou s parametrem vnitřního typu
   

Formát odevzdání

• poslat email na "jahodfra na seznamu"
• předmět emailu nastavit na "PRC2 ukol2"
• odeslat pouze nezabalené soubory zdroj. kódu - ideálně 2-3 soubory
  
• cením si pokud program půjde bez ladění zkompilovat pod g++

Cvičení 3

Implementace obousměrného kruhového seznamu a zásobníku.
Dobrovolný úkol:

• doplňte metody třídy LinkedList
• rozšiřte příklady použití
• a implementujte podobným způsobem frontu

soubor list.h

#ifndef _LIST_H
#define _LIST_H

struct ListNode {
  ListNode *mpNext, *mpPrev;
  int mData;
};

class LinkedList {
  public:
      LinkedList();      
      LinkedList(int *array, int size);
      LinkedList(LinkedList&);
      ~LinkedList();

      void append(int data);
      void prepend(int data);
      void joinWith(LinkedList& other);

      int popLast();
      int popFirst();
      bool isEmpty() const;

      void print();
  private:
      ListNode *mpFirst;
};

class Stack {
  public:
      void push(int);
      int pop();
      bool isEmpty() const;
      void print();
  private:
      LinkedList mList;
};

#endif

soubor list.cpp

#include <iostream>

#include "list.h"

using namespace std;

LinkedList::LinkedList(): mpFirst(NULL) {}

LinkedList::LinkedList(int *array, int size)
{
}

LinkedList::LinkedList(LinkedList& list)
{
mpFirst = NULL;
if (list.mpFirst != NULL)
{
 ListNode *actual = list.mpFirst;
 do {
  append(actual->mData);
  actual = actual->mpNext;
 } while (actual != list.mpFirst);
}
}

LinkedList::~LinkedList()
{
if (mpFirst != NULL)
{
 ListNode *item = mpFirst;
 while (item->mpNext != mpFirst) {
  item = item->mpNext;
  delete item->mpPrev;
 }
 delete mpFirst;
 mpFirst = NULL;
}
}

void LinkedList::append(int data) {
if (mpFirst == NULL) {
 mpFirst = new ListNode;
 mpFirst->mData = data;
 mpFirst->mpNext = mpFirst;
 mpFirst->mpPrev = mpFirst;
} else {
 ListNode *newItem = new ListNode;
 newItem->mData = data;
 newItem->mpNext = mpFirst;
 newItem->mpPrev = mpFirst->mpPrev;
 mpFirst->mpPrev = newItem;
 newItem->mpPrev->mpNext = newItem;
}
}

void LinkedList::prepend(int data)
{
append(data);
mpFirst = mpFirst->mpPrev;
}

void LinkedList::joinWith(LinkedList& other)
{
}

int LinkedList::popLast()
{
if (mpFirst == NULL)
{
 cerr << "ERROR: removing items from empty list" << endl;
 exit(1);
} else {
 ListNode *item = mpFirst->mpPrev;
 int value;
 if (item->mpNext == item)
 {
  mpFirst = NULL;
 }
 item->mpPrev->mpNext = item->mpNext;
 item->mpNext->mpPrev = item->mpPrev;
 value = item->mData;
 delete item;
 return value;
}
}

int LinkedList::popFirst()
{
int value;
mpFirst = mpFirst->mpNext;
return popLast();
}

bool LinkedList::isEmpty() const
{
return mpFirst == NULL;
}

void LinkedList::print()
{
if (mpFirst == NULL)
{
 cout << "[]" << endl;
} else {
 cout << "[";
 ListNode *actual = mpFirst;
 while (1)
 {
  cout << actual->mData;
  actual = actual->mpNext;
  if (actual == mpFirst)
  {
   break;
  }
  cout << ", ";
 }
 cout << "]" << endl;
}
}

void Stack::push(int data)
{
mList.append(data);
}

int Stack::pop()
{
return mList.popLast();
}

bool Stack::isEmpty() const
{
return mList.isEmpty();
}

void Stack::print()
{
mList.print();
}

soubor priklad3.cpp

#include <iostream>
#include "list.h"

using namespace std;

int main(int argc, char **argv) {
LinkedList list;
for (int i=1; i<=5; i++)
{
 list.append(i);
}
LinkedList list2(list);
list2.popFirst();
list2.popLast();
list2.print();
list.print();

cout << "priklad na zasobnik" << endl;
Stack s;
for (int i=1; i<=5; i++)
{
 s.push(i);
}
while(!s.isEmpty()) {
 cout << s.pop() << endl;
}
return 0;
}

1. úkol těžší varianta

Napište program, který bude načítat řádky ze standardního vstupu (cin).
Na vstupu může objevit:

• "+" - odeberou se 2 poslední čísla a, b ze zásobníku a do zásobníku se přidá a+b
• "-" - odeberou se 2 poslední čísla a, b ze zásobníku a do zásobníku se přidá a-b
• "*" - odeberou se 2 poslední čísla a, b ze zásobníku a do zásobníku se přidá a.b
• "p" - vypíše se poslední číslo na zásobníku na standardní výstup.
  
• řádky začínající znakem # ignorujte
• pokud se na vstupu objeví číslo, uložte ho do zásobníku. (za vstup předpokládejte čísla double)
• jinak nahlaste chybu vstupu
  

implementace

• vstupní řádky nejsou delší, než 50 znaků
• k implementaci zásobníku je možné použít std::stack
• k převodu na číslo lze využít funkce atof nebo tento návod, vstup 0 se nepředpokládá.
  
• v programu na konci uvolněte veškerou použitou dynamickou paměť
• nezapomeňte na ošetření případu, že na zásobníku není dost čísel a špatného vstupu
  

Příklad 1
>10
>5
>+
>p
<15

Příklad 2
>#urok
>5
>0.01
>*
>1
>+
>#vklad
>20000
>*
>p
<21000

Odevzdání

• poslat email na "jahodfra na seznamu"
• předmět emailu nastavit na "PRC2 ukol1b"
• odeslat pouze nezabalené soubory zdroj. kódu - ideálně pouze jeden soubor

Upozornění pro pokročilé v C++

Kdo měl zájem o přímé odevzdání zápočtového programu (tedy ti, kteří již znají C++ i s šablonami) nechť se mi ozve na email nebo jsem do komentářů do pátku 27. března. Zároveň uveďte téma zápočtového programu.

Podotýkám, že na vás budu trochu náročnější, než na úplné začátečníky (ale jen v rámci splnění podmínek, které jsem popsal). Tato možnost by měla umožnit těm, kteří domácí úkoly z cvik zvládají levou zadní, se jim vyhnout a tedy očekávám, že jsou schopni takové programy implementovat sami. Pokud se prokáže, že svému zápočtovému programu nerozumíte budu chtít dopracování domácích úkolů.

Definice polí v C++

Vytvořil jsem malý příklad na práci s poli. Pole jsou v C/C++ indexována od 0 a poslední prvek je (počet prvků - 1). Přístup mimo vyhrazenou paměť operační systém trestá okamžitou terminací. Při vytváření pole zvažte v jakém pořadí do něj budete přistupovat, pro převládající přístup po řádkách zvolte pole[řádek][sloupec], pro přístup po sloupcích pole[sloupec][řádek].

int main() {
    const int cx = 40;
    const int cy = 20;
    int x = 40;
    int y = 20;
        
    /*------ both static ---------------*/
    int sa1[cy][cx];
    sa1[4][5] = 0;
    
    //ugly and possible
    4[ 5[sa1] ] = 0;

    //!!!!!!! REALLY REALLY BAD !!!!!!!!
    //int **matrix = (int **) new int[cy][cx];
    
    int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    int m[][2] = {{1,2},{3,4}};
    
    /*------ one dynamic -------------- */   
    int (*sa2)[cx];
    sa2 = new int[y][cx];
    sa2[4][5] = 0;
    delete sa2;
    
    /*------ both bounds dynamic -------*/    
    //linear array
    int *a1;
    a1 = new int[20*40];
    a1[4*x + 5] = 0; //means a1[4][5] = 0
    delete a1;

    //double pointer    
    int **a2;
    a2 = new int*[y];
    a2[0] = new int[x*y];
    for (int i=0; i<y; i++) {
        a2[i] = a2[0] + i*x;
    }
    a2[4][5] = 0;
    delete a2[0];
    delete a2;

    return 0;    
}

Cvičení 2

probráno

• new, delete, new[], delete[]
• statické atributy
• konstruktor, destruktor
• vytváření pole dynamické velikosti
• ukázka std::vector a iterátorů

soubor priklad2.cpp

#include <iostream>
#include <iomanip>

#include "car.h"

using namespace std;

int main() {
 Vehicle v1("Skoda 105", 2000);
 Vehicle v2("Fiat Uno", 12000);
 cout << Vehicle::getCount() << endl;
 return 0;
}

soubor car.h

/** Library which contains class Vehicle
*/

#ifndef CAR_h
#define CAR_h

#include <string>

using namespace std;

class Vehicle
{
public:
   Vehicle(string Type, int Price);
   ~Vehicle();
   friend ostream& operator <<(ostream& out, Vehicle& v);
   static int getCount();
protected:
private:
   int mPrice;
   string mType;
   static int msCount;
};

ostream& operator <<(ostream& out, Vehicle& v);

#endif  // _XX_h_

soubor car.cpp - nová část

#include <iostream>
#include "car.h"

using namespace std;

int Vehicle::msCount = 0;

Vehicle::Vehicle(string Type, int Price): mType(Type), mPrice(Price) {
       msCount++;
}

Vehicle::~Vehicle() {
       msCount--;
}

int Vehicle::getCount() {
       return msCount;
}

1. úkol

Napište variantu UNIXového programu tail. Který bude načítat řádky ze standardního vstupu (cin) a vypíše posledních n řádek na standardní výstup (cout).

volitelné
počet výstupních řádek může být zadán jako parametr příkazové řádky.
použití: ./tail 5 <vstup

implementace

• nelze používat funkce/metody seek, fseek
• program by si měl pamatovat pouze řádky, které potřebuje.
• řádky může reprezentovat pomocí std::string nebo char*
• vstupní řádky nejsou delší, než 200 znaků
• pro uložení řádek lze použít std::list nebo kruhový buffer
• v programu uvolněte veškerou použitou dynamickou paměť
• n se funkci main předává přes parametry argc, argv a lze ho zpracovat pomocí funkce atoi nebo objektu istringstream.
  

odevzdání

• poslat email na "jahodfra na seznamu" do příštího pondělí
• předmět emailu nastavit na "PRC2 ukol1"
• odeslat pouze nezabalené soubory zdroj. kódu - ideálně pouze jeden soubor

Deterministické funkce

Implementoval jsem příklad na kešování argumentů a hodnot deterministických funkcí (jednoho ze zápočtových zadání). Zvolil jsem Python, takže stále existuje prostor pro implementaci zadání v C++ za pomoci šablon (řešení v Pythonu bude jistě mnohem pomalejší). Cílem je zrychlit vyhodnocení některých rekurzivních funkcí.

V následujícím případě je ilustrováno použití na vyhodocení Fibonacciho čísel, při zapamatování si posledních 3 vyhodnocenných hodnot. Rozšíření definice funkce o tuto možnost je při použítí dekorátorů z Pythonu zvášť jednoduché.

@deterministic(LRU(3))
def fibonacci(n):
if n >= 2:
    return fibonacci(n-1) + fibonacci(n-2)
else:
    # F(0) = 0, F(1) = 1
    return n

Pro vyhodnocení 50. Fibonacciho čísla dojde pouze k 51 volání funkce. Zatímco bez použití dekorátoru jsem čekání na výsledek po několik 10s vzdal. Příklad také ukazuje, že použití správného algoritmu je důležitější než zrychlení dané použitím rychlejšího jazyka.

Celá implementace:

class Cache:
   '''
   Cache interface
   '''
  def __contains__(self, arg): pass
  def __setitem__(self, arg, value): pass
  def __getitem__(self, arg): pass

class LRU(Cache):
   '''
   Implementation of Last Recently Used algorithm.
   Only -size- last recently used items are stored in cache
   '''
  def __init__(self, size):
      self._cache = {}
      self._order = []
      self.size = size
    
  def __contains__(self, arg):
      return arg in self._cache
    
  def __setitem__(self, arg, value):
      self._order.append(arg)
      self._cache[arg] = value
      if len(self._cache) > self.size:
          i = self._order[0]
          del self._order[0]
          del self._cache[i]

  def __getitem__(self, arg):
      self._order.remove(arg)
      self._order.append(arg)
      return self._cache[arg]

#lambda function which enables adding cache as parameter to
#_deterministic, because
# > @decor(a,b,c)
# > def func(args): pass
#is syntactic sugar for
# > func = decor(a,b,c)(func)
deterministic = lambda cache: lambda f: _deterministic(f, cache)

def _deterministic(f, cache):
   '''
   decorator which remembers function arguments and returned values
   in cache  

   WARNING: should be used only for function which for the same set of
   arguments returns same value.  
   
   IMPORTANT: function arguments must be hashable
   '''
  def df(*args):
      if args in cache:
          return cache[args]
      else:          
          v = f(*args)          
          cache[args] = v
          return v
  return df

@deterministic(LRU(3))
def fibonacci(n):
  fibonacci.ncalls += 1
  if n >= 2:
      return fibonacci(n-1) + fibonacci(n-2)
  else:
      # F(0) = 0, F(1) = 1
      return n

n = 50
fibonacci.ncalls = 0
print 'f(%d): ' % n, fibonacci(n)
print 'number of calls: ',fibonacci.ncalls

Teoretické základy OOP

Našel jsem pěkný článek popisující základní vlastnosti objektů a odvozené vlastnosti objektů, se kterými se setkáme ve většině programovacích jazyků.

Jak má vypadat koncový zápočtový program

Program odevzdaný na konci semestru určující zápočet a známku by měl splňovat..

Formální parametry

• třídy, metody a funkce by měli obsahovat doxygen komentáře a ze souborů by měla být vytvořena doxygen dokumentace.
• zdrojový kód, komentáře i dokumentace by měla být napsána v angličtině
• dodržení standardů zdrojového kódu.
  
• použití pouze C++ výrazů a knihoven, pokud možno žádné C alokace a uvolnění paměti a použití C++ proudů.
  
• objekty a metody by po sobě měly uvolnit veškerou paměť
• důsledné dodržování principu zapouzdření. (co má být private, ať je private)

Vlastní zadání
Úkolem by mělo být implementovat šablonovou knihovnu reprezentující datovou strukturu. A k této šabloně vytvořit ukázkový program. Je doporučeno se inspirovat šablonami ve standardní knihovně např. vector.

• Parametrem šablony by měl být typ prvku obsaženého v datové struktuře.
• Šablona by měla obsahovat iterátor pro procházení datové struktury.
• Smysluplné použití přetypování operátorů je vítáno.
• Využití vlastností jako je specializace šablon a šablonové meta-programování je též vítáno.
• Tam kde je potřeba vyvolat vyjímku, nechť se tak stane - definujte si na to vlastní třídu.
• Definujte kopírovací konstruktor.
  
• Destruktor nutný

Příklady šablon

• binární strom
• obousměrná fronta
• asociativní tabulka (hash tabulka)
  
• řídká matice
• matice
• množina
• vektor z lineární algebry a k němu vektorový obal
  
• apod..

Pokročilejší úkoly

• šablona, která dostane za parametr funkci a zapamatuje si n parametrů a návratových hodnot funkce a při opakovaném volání se stejnými parametry ihned vrátí návratovou hodnotu funkce, bez jejího samotného volání. + k tomuto úkolu napsat webovou stránku, jak to funguje. (nezaručuji, že lze implementovat)

Očekávám, že mi program pošlete na email a teprve poté se dohodneme na setkání, kde ověřím zda programu rozumíte a zapsání zápočtu.

Cvičení na vstupně, výstupní proudy

Probrali jsme:

• výstup a vstup ze standardních proudů, metodu getline, setw, setprecision z knihoven iostream, iomanip.
• kompilace programu pomocí příkazu make a souboru Makefile.
  
• vytvoření hlavičkového souboru, příkazy preprocesoru zabraňující několikanásobnému vložení hlavičký, komentáře doxygenu
• definice třídy, konstruktor, metody, operátory přístupu, deklarace friend
  
• předefinování operátoru výstupu do proudu

obsah souborů ze cvičení
soubor priklad1.cpp

#include <iostream>
#include <iomanip>

#include "car.h"

using namespace std;

int main() {
  Vehicle v("Skoda 105", 2000);
  cout << v << endl;
  return 0;
}

soubor car.h

/** Library which contains class Vehicle
 */

#ifndef CAR_h
#define CAR_h

#include <string>

using namespace std;

class Vehicle
{
public:
    Vehicle(string Type, int Price);
    friend ostream& operator <<(ostream& out, Vehicle& v);
protected:
private:
    int mPrice;
    string mType;
};

ostream& operator <<(ostream& out, Vehicle& v);

#endif  // _XX_h_

soubor car.cpp

#include <iostream>
#include "car.h"

using namespace std;

Vehicle::Vehicle(string Type, int Price): mType(Type), mPrice(Price) {}

ostream& operator <<(ostream& out, Vehicle& v)
{
    return out << "Vehicle(" << v.mType \
               << ", Price: " << v.mPrice << ")";
}

Začátek

Vítám studenty pondělního cvičení z PRC2 v 13:30 na tomto blogu, kde hodlám publikovat informace k cvičení popř. i části programů. Příspěvků snad nebude tolik a budou krátké, ale snad bude stát za to přidat si blog do RSS čtečky.

Cvičení je možné absolvovat dvěma způsoby.

1. pravidelně ho navštěvovat a odevzdat programy zadané v rámci cvičení spolu s posledním programem, podle kterého se určí hodnota klasifikovaného zápočtu.
2. domluvou se mnou zveřejnit téma knihovny.

Studentům, kteří se budou řídit 1. variantou, trochu přilepším.

Pro vytváření programů se řiďte těmito standardy pro tvorbu zdrojového kódu. Jejichž splnění budu u koncových programů vyžadovat.