Chip 2000 November/Chip_2000-11_cd2.bin/chplus/Itercpp/ITERATOR.CPP

C/C++ Source or Header | 2000-10-02 | 5KB | 204 lines

////////////////////////////////////
// Soubor Iterator.cpp
// Ukazuje mozny zpusob deklarace iteratoru a jejich vyuziti
// pro deklaraci sablony funkce pro trideni kontejneru
//
// Odladeno v C++Builderu 5, lze ale snadno upravit i
// pro starsi prekladace C++
///////////////////////////////////


#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <exception.h>


const N = 10; // Pocet prvku seznamu
typedef int T;

// Nejake pole, aby bylo co tridit
int A[ N ] = {2,4,6,8,1,3,5,7,9,0};

// Pokud Vas prekladac nepodporuje vykjimky, nahradte
// prikaz throw exception() volanim tetop funkce
// a odstrante hlavickovy soubor <exception.h>
void Chyba(){cout << "prusvih" << endl; exit(1);}

struct prvek {// prvek seznamu
  T data;
  prvek* dalsi;
};

class seznam // Jednosmerny seznam se zarazkou
{
  prvek *prvni, *zarazka;
public:
  class Iterator; /* //ve starsich prekladacich musi byt tato deklarace zapsana zde jako vnorena
  {
    prvek* p;
  public:
    Iterator(prvek* _p=0): p(_p){};
    T& operator*();// Operatory prom iterator
    Iterator& operator++();
    int operator ==(Iterator j) {return p == j.p;}
    int operator !=(Iterator j) {return !(*this == j);}
  };                */
  friend class seznam::Iterator;

  seznam(); // Konstruktor a destruktor
  ~seznam();
  void VlozNaKonec(T co);// Vloz danou hodnotu do noveho prvku na konci seznamu
  T VyjmiPrvni();// Odstran prvni prvek seznamu
  Iterator begin();// Vraci iterator ukazujici na pocatek seznamu
  Iterator end();// Vraci iterator ukazujici za posledni prvek seznamu
  Iterator Najdi(T co);// Najdi prvek obsahujici danou hodnotu
};

class seznam::Iterator // Iterator na seznamu
{
  prvek* p;// Ukazatel na aktualni prvek
public:
  Iterator(prvek* _p=0): p(_p){}; // Konstruktor
  T& operator*();// "Dereferencovani" iteratoru (pristup k hodnote ulozene v prvku)
  Iterator& operator++();// Prejdi na dalsi prvek
  int operator ==(Iterator j) {return p == j.p;}// Porovnani iteratoru
  int operator !=(Iterator j) {return !(*this == j);}
};

seznam::Iterator seznam::begin() {return Iterator(prvni);}
seznam::Iterator seznam::end() {return Iterator(zarazka);}

seznam::seznam()// Konstruktor
{
 zarazka = prvni = new prvek;
 prvni -> dalsi = 0;
}

void seznam::VlozNaKonec(T co)
{
 zarazka -> dalsi = new prvek;
 zarazka -> data = co;
 zarazka = zarazka -> dalsi;
 zarazka -> dalsi = 0;
}

T seznam::VyjmiPrvni()
{
 T a = prvni->data;
 prvek* pom = prvni;
 prvni = prvni->dalsi;
 delete pom;
 return a;
}
seznam::~seznam()
{
 prvek *pom = prvni;
 while(pom)
 {
  prvni = prvni->dalsi;
  delete pom;
  pom = prvni;
 }
}
seznam::Iterator& seznam::Iterator::operator++()
{
 if(!p) throw exception();
 if(p->dalsi) p = p->dalsi;
 return *this;
}


T& seznam::Iterator::operator*()
{
 if(!p) throw exception();
 return p->data;
}

// Sablona funkce pro trideni primym vyberem
// verze pro starsi prekladace, kde je sablona vnorena
// do pomocne struktury, aby mohla mit i parametry, ktere nepouzijeme
// jako typ parametru funkce
template<class ITER, class Typ>
struct Pom{
  static void sort(ITER beg, ITER end)
  {
   for(ITER i = beg; i != end; ++i)
   {
     ITER ix = i; // Prvni prvek v prohledavanem useku
     for(ITER u = i; u != end; ++u) // Projdi usek
       if(*u < *ix) ix = u; // Zapamatuj si nejmensi
     if(ix != i)// Neni-li to prvni, prohod s prvnim v useku (*i)
     {
        Typ x = *i;
        *i = *ix;
        *ix = x;
     }
   }
  }
};

// Totez, ale pro nove prekladace
// Pouzivate-li starsi prekladac, nasledujici sablonu odstrante
template<class ITER, class Typ>
void sort(ITER beg, ITER end)
{
 for(ITER i = beg; i != end; ++i)
 {
   ITER ix = i; // Prvni prvek v prohledavanem useku
   for(ITER u = i; u != end; ++u) // Projdi usek
     if(*u < *ix) ix = u; // Zapamatuj si nejmensi
   if(ix != i) // Neni-li to prvni, prohod s prvnim v useku (*i)
   {
      Typ x = *i;
      *i = *ix;
      *ix = x;
   }
 }
}
// Az po tento komentar odstrante, mate-li starsi prekladac,
// ktery nepodporuje pripojovani parametru sablony v lomenych
// zavorkach ke jmenu funkce

seznam::Iterator seznam::Najdi(T co)
{
 Iterator i(prvni);
 zarazka -> data = co;
 while(*i != co)++i;
 return i;
}

// A nekolk prikladu pouziti
void main(){
  seznam S;
// Tady se nic nestane, takov² prvek v seznamu neexistuije
  seznam::Iterator x = S.Najdi(11);
  ++x;
  clrscr();
// Napl≥ seznam nßhodn²mi Φφsly
  for (int i = 0; i < N; i++)
    S.VlozNaKonec(rand());

// VypiÜ ho
  for(seznam::Iterator I = S.begin(); I != S.end(); ++I)
  cout << *I << endl;

// Najdi prvek a pokud tam je, zv∞tÜi ho o 100
  seznam::Iterator k = S.Najdi(7117);
  if(k != S.end())
    *k += 100;
  cout << "================" << endl;

// set°i∩ pole a seznam
/* Pro starÜφ p°ekladaΦe
  Pom<int*, int>::sort(A, &A[N]);
  Pom<seznam::Iterator, int>::sort(S.begin(), S.end());
*/
  sort<int*, int>(A, &A[N]);
  sort<seznam::Iterator, int>(S.begin(), S.end());

// VypiÜ seznam
  for(seznam::Iterator I(S.begin()); I != S.end(); ++I)
  cout << *I << endl;

}