uradio sam zadatak koji radi separate chaining i nakon toga sortira na bazi shell sorta, tako je trazeno u zadatku kao i da nadje najmanji i najveci to je sortira opadajuce i rastuce, taj dio je prosao odgovarajuci program na web stranici od profa.
ono sto on jos trazi je sljedece:
1. da program prodjeni odredjeni test performance bez timeouta (da bi bilo jasnije rijesio da radio bez greske do 10 na 5 no kod 10 na 6 javlja gresku)
2. i da unutar program optimizaciju dodam tako da radi caching od minimuma i maximuma kao i caching sortiranih vrijednosti
Ispod je code zadatka koji je prosao prva dva dijela zadatka: implementaciju separate chaininga i shell sorta bez greske. Svaka pomoc je dobrodosla jer mi istice rok do kada ovo moram da predam odnosno testiram na internoj stranici.
#ifndef AHMETHT_H
#define AHMETHT_H
#include <iostream>
#include "Container.h"
// Glavna klasa
template <typename E>
class AhmetHT : public Container<E> {
// separate chain element
// sluzi kao nosac za podatke (E)
class Node {
public:
E e;
Node * prev ;
Node * next ;
Node( const E& e ) : e( e ), prev( 0 ), next( 0 ) {};
~Node( ) { };
};
// hash table element u glavnom nizu istih
// sadrzi hash_key vrednost i pokazivac na prvi i poslednji element u Separate Chain
// osim konstruktora i destruktora sadrzi potrebne operacije za
// dodavanje, trazenje (odredjenog elementa ili min ili max), brisanje jednog elementa,
// racunanje duzine lanca i prikaz sadrzaja lanca
// ako su first i last postavljeni na 0 onda je element prazan bez obzira na sadrzaj hash_key
class HTelement {
public:
unsigned long hash_key;
Node * first ;
Node * last ;
HTelement( unsigned long hash_key = 0 ) : hash_key( hash_key ), first( 0 ), last( 0 ) {} ;
virtual ~HTelement( ) { delete_( first ); };
void add_( Node* node, const E& e );
void remove_( Node* node, const E& e );
bool member_( Node* node, const E& e ) const;
size_t size_( Node* node ) const;
std::ostream& print_( Node* node, std::ostream &o ) const;
void delete_( Node* node );
E min( ) const;
E max( ) const;
size_t size( ) const;
};
// niz hash elemenata
HTelement * hashtablevalues;
// ukupna duzina hash tabele
size_t nmax;
// iskoristena duzina hash tabele (uvek je <= od nmax)
size_t currlength;
// pomocna funkcija za dodavanje elementa u hash tabelu
void add_( HTelement* htdata, const E& e );
// pomocna funkcija za brisanje elementa iz hash tabele
void remove_( HTelement* htdata, const E& e );
// pomocna funkcija za ispitivanje postojanja elementa u hash tabeli
bool member_( HTelement* htdata, const E& e ) const;
// pomocna funkcija za ispitivanje postojanja elementa u hash tabeli
bool empty_( HTelement* htdata ) const;
// pomocna funkcija za nalazenje ukupnog broja elemenata u objektu
size_t size_( HTelement* htdata ) const;
// pomocna funkcija za stampanje elementa iz hash tabele
std::ostream& print_( HTelement* htdata, std::ostream &o ) const;
// pomocna funkcija za sortiranje elementa iz hash tabele i ispitivanje Functor-a
size_t apply_( HTelement* htdata, const Functor<E>& f, Order order ) const ;
// pomocna funkcija za brisanje hash tabele
void delete_( HTelement* htdata );
// pomocna funkcija za razmenu sadrzaja elementa iz hash tabele
void swap_( HTelement* htdata1, HTelement* htdata2 ) const ;
public:
AhmetHT<E>() : hashtablevalues( 0 ), nmax(0), currlength(0) { }
virtual ~AhmetHT<E>( ) { delete_( hashtablevalues ); }
using Container<E>::add;
virtual void add( const E e[], size_t s );
using Container<E>::remove;
virtual void remove( const E e[], size_t s );
virtual bool member( const E& e ) const { return member_( hashtablevalues, e ); }
virtual size_t size( ) const { return size_( hashtablevalues ); }
virtual bool empty( ) const { return empty_(hashtablevalues); }
virtual size_t apply( const Functor<E>& f, Order order = dontcare ) const {size_t n=apply_( hashtablevalues, f, order ); return n; }
virtual E min( ) const;
virtual E max( ) const;
virtual std::ostream& print( std::ostream &o ) const { return print_( hashtablevalues, o ); }
};
// racuna se duzina Separate Chain lanca zakacenog za neki red u hash tabeli
template <typename E>
size_t AhmetHT<E>::HTelement::size( ) const {
if (!first) {
// ako je polje first 0 smatramo da je lanac prazan
return 0;
}
return size_(first);
}
// dodaje se novi element u Separate Chain lanac zakacen za neki red u hash tabeli
template <typename E>
void AhmetHT<E>::HTelement::add_(AhmetHT<E>::Node* node, const E& e ) {
Node * curr = node;
if (!first) {
// ako je polje first 0 novi element ubacujemo na pocetak lanca i podesavamo ogovarajuce pointere
first = new Node( e );
first->next = 0;
first->prev = 0;
last = first;
return;
}
while (curr != last) {
if (e == curr->e) {
// ako je novi element jednak nekom postojecem odustajemo od dodavanja
return;
}
/*
if (curr->e > e) {
// ako je novi element manji od trenutno dostignutog elementa u Separate Chain dodajemo ga pre njega (interno sortiramo elemente u Separate Chain)
if (curr == first) {
// ako je dostignuti element u stvari onaj prvi, ubacujemo novi ispred njega. azuriraju se i pointeri
first = new Node( e );
first->next = curr;
curr->prev = first;
} else {
// u suprotnom ubacujemo novi element ispred dostignutog. azuriraju se i pointeri. pazi se samo da se ne prekine lanac.
(curr->prev)->next = new Node( e );
((curr->prev)->next)->prev = curr->prev;
((curr->prev)->next)->next = curr;
curr->prev = (curr->prev)->next;
}
return;
}
*/
curr = curr->next;
}
// ako je novi element jednak zadnjem odustajemo od dodavanja
if (e == last->e) {
return;
}
/*
if (last->e > e) {
// ako je novi element manji od zadnjeg elementa u Separate Chain dodajemo ga pre njega (interno sortiramo elemente u Separate Chain)
if (last == first) {
// ako je zadnji element u stvari onaj prvi, ubacujemo novi ispred njega. azuriraju se i pointeri
first = new Node( e );
first->next = last;
last->prev = first;
} else {
// u suprotnom ubacujemo novi element ispred zadnjeg. azuriraju se i pointeri. pazi se samo da se ne prekine lanac.
(last->prev)->next = new Node( e );
((last->prev)->next)->prev = last->prev;
((last->prev)->next)->next = last;
last->prev = (last->prev)->next;
}
return;
}
*/
// ostaje nam samo da novi element ubacimo na kraj liste. azuriraju se pointeri.
last->next = new Node( e );
(last->next)->prev = last;
(last->next)->next = 0;
last = last->next;
}
// brise se element u Separate Chain zakacen za neki red u hash tabeli
template <typename E>
void AhmetHT<E>::HTelement::remove_( Node* node, const E& e ) {
Node * curr = first;
if (!node) return;
if (!first) return;
// ako su ulazni podatak i polje first prazni onda smo vec pobegli pre ove tacke.
while (curr != last) {
// u petlji trazimo element koji cemo brisati. petljom kruzimo dok ne izvrtimo ceo lanac ili dok ne nadjemo trazeni.
if (e == curr->e) {
// ako smo nasli taj element prepakujemo pointere koji uvezuju lanac da oslobodimo tekuci jer njega treba brisemo.
Node * Cprev = curr->prev;
Node * Cnext = curr->next;
Cprev->next = Cnext;
Cnext->prev = Cprev;
delete curr;
curr = 0;
return;
}
curr = curr->next;
}
// izvrteli smo petlju i jos je ostalo da uradimo proveru da nije bas onaj zadnji taj kog treba obrisati.
if (e == last->e) {
// ako jeste pripreme se razlikuju ako je zadnji isto sto i prvi ili ako nije.
if ( first == last ) {
curr=last;
first=0;
last=0;
} else {
Node * Cprev = last->prev;
Cprev->next = 0;
last = Cprev;
}
// brisemo nadjeni element
delete curr;
curr = 0;
return;
}
}
// ispitivanje postojanja elementa u Separate Chain
template <typename E>
bool AhmetHT<E>::HTelement::member_(AhmetHT<E>::Node* node, const E& e) const {
Node * curr = first;
if (!node) {
return false;
}
if (!first) {
return false;
}
// ako su ulazni podatak i polje first prazni onda smo vec pobegli pre ove tacke.
while (curr != last) {
// u petlji trazimo zadati element. petljom kruzimo dok ne izvrtimo ceo lanac ili dok ne nadjemo trazeni.
if (e == curr->e) {
// ako smo ga nasli vrati true
return true;
}
curr = curr->next;
}
// izvrteli smo petlju i jos je ostalo da uradimo proveru da nije bas onaj zadnji taj kog trazimo.
if (e == last->e) {
// ako smo ga nasli vrati true
return true;
}
// ako smo ovde stigli vrati false jer trazeni element nije nadjen.
return false;
}
// prebrojavanje elemenata u Separate Chain
template <typename E>
size_t AhmetHT<E>::HTelement::size_( AhmetHT<E>::Node* node ) const {
Node * curr = first;
size_t nodesize = 0;
if (!node) {
return nodesize;
}
if (!first) {
return nodesize;
}
// ako su ulazni podatak i polje first prazni onda smo vec pobegli pre ove tacke.
while (curr != 0) {
// u petlji prebrojavamo elemente. petljom kruzimo dok ne izvrtimo ceo lanac. usput za svaki element uvecavamo brojac.
curr = curr->next;
nodesize++;
}
// vrati sadrzaj brojaca
return nodesize;
}
// stampanje elemenata u Separate Chain
template <typename E>
std::ostream& AhmetHT<E>::HTelement::print_( AhmetHT<E>::Node* node, std::ostream &o ) const {
if (node) {
// ako ulazni podatak nije 0 odstampaj i rekurzivno pozovi da da odstampas sledeci
o << node->e;
o << ' ';
print_( node->next, o );
}
return o;
}
// brisanje Separate Chain vezanog za neki red u hash tabeli
template <typename E>
void AhmetHT<E>::HTelement::delete_( AhmetHT<E>::Node* node ) {
if (node) {
// ako ulazni podatak nije 0 rekurzivno pozovi da obrises sledeci
delete_( node->next );
// brisi trenutno dostignuti element i azuriraj pointer
delete node;
node = 0;
}
}
// trazenje najmanjeg elementa u Separate Chain
template <typename E>
E AhmetHT<E>::HTelement::min( ) const {
if (!first) throw typename Container<E>::Exception( "HTelement::min(): empty" );
Node* current = first;
Node* minnode = first;
while (current != 0) {
// u petlji ispitujemo da li ima neki manji element od prvog. petljom kruzimo dok ne izvrtimo ceo lanac.
// zbog optimizacije add_ funkcije nismo ni morali da idemo u petlju. (add_ funkcija sortira elemente u Separate Chain u rastucem redosledu)
// trebalo je samo proglasiti prvi za najmanji
if (minnode->e > current->e) {
// ako ima manji proglasi ga za najmanji
minnode = current;
}
current = current->next;
}
// vrati nadjeni najmanji
return minnode->e;
}
// trazenje najveceg elementa u Separate Chain
template <typename E>
E AhmetHT<E>::HTelement::max( ) const {
if (!first) throw typename Container<E>::Exception( "HTelement::max(): empty" );
Node* current = first;
Node* maxnode = first;
while (current != 0) {
// u petlji ispitujemo da li ima neki veci element od prvog. petljom kruzimo dok ne izvrtimo ceo lanac.
// zbog optimizacije add_ funkcije nismo ni morali da idemo u petlju. (add_ funkcija sortira elemente u Separate Chain u rastucem redosledu)
// trebalo je samo proglasiti zadnji za najveci
if (current->e > maxnode->e) {
// ako ima veci proglasi ga za najveci
maxnode = current;
}
current = current->next;
}
return maxnode->e;
}
// brisanje hash tabele
template <typename E>
void AhmetHT<E>::delete_( AhmetHT<E>::HTelement* htdata ) {
if (htdata) {
// ako trazena tabela nije prazna brisemo redove.
size_t i=0;
while (i < nmax) {
// za svaki red u tabeli proveravaj da li ima neki separate chain zakacen za njega i ako ima pozovi delete funkciju za taj lanac.
if ((htdata[i].first)&&(htdata[i].last)) htdata[i].delete_(htdata[i].first);
// posle brisanja azuriraj podatke
htdata[i].first = 0;
htdata[i].last = 0;
htdata[i].hash_key = 0;
i++;
}
// posto je sada tabela prazna pozovi DELETE
delete[] htdata;
htdata = 0;
}
}
// izmena redova u hash tabeli
template <typename E>
void AhmetHT<E>::swap_( AhmetHT<E>::HTelement* htdata1, AhmetHT<E>::HTelement* htdata2 ) const {
HTelement temp;
if ((htdata1!=0) && (htdata2!=0)) {
// ako predati pointeri nisu 0 razmeni njihov sadrzaj koristeci pomocnu velicinu temp.
temp.hash_key = htdata2->hash_key ;
temp.first = htdata2->first ;
temp.last = htdata2->last ;
htdata2->hash_key = htdata1->hash_key ;
htdata2->first = htdata1->first ;
htdata2->last = htdata1->last ;
htdata1->hash_key = temp.hash_key ;
htdata1->first = temp.first ;
htdata1->last = temp.last ;
temp.hash_key = 0 ;
temp.first = 0 ;
temp.last = 0 ;
}
}
// dodaje se novi element u hash tabelu
template <typename E>
void AhmetHT<E>::add_( AhmetHT<E>::HTelement* htdata, const E& e ) {
if (htdata == 0) {
// pri kreiranju objekta hash tabela je prazna i bez elemenata. zato se inicijalno rezervise prostor za prvih 101 element.
size_t newnmax = 101;
HTelement * newvalues = 0;
newvalues = new HTelement[newnmax];
hashtablevalues = newvalues;
htdata = newvalues;
nmax = newnmax;
// inicijalizacija novih redova u hash tabeli
for (size_t i = 0; i < nmax; ++i) {
hashtablevalues[i].hash_key = 0;
hashtablevalues[i].first = 0;
hashtablevalues[i].last = 0;
}
} else if (currlength + 1 > nmax) {
// ako je broj zeljenih elemenata premasio broj mogucih idemo na sirenje tabele.
size_t newnmax , repacksize , currE ;
HTelement * newvalues ;
E *repackarr ; // pointer za niz svih unetih podataka kako bi se mogao uraditi ponovni add nad novonastalom tabelom.
Node* node;
newnmax = nmax;
repacksize = this->size(); // ukupan broj elemenata za koje treba uraditi rehash.
currE = 0;
newvalues = 0;
repackarr = 0;
node = 0;
while (currlength + 1 > newnmax) newnmax = (size_t)( newnmax * 1.2 + 2 ); // izracunaj novi nmax koji je dovoljno veliki da se smesti trazeni broj elemenata.
// inicijalizacija nove hash tabele
newvalues = new HTelement[newnmax];
for (size_t i = 0; i < newnmax; ++i) {
newvalues[i].hash_key = 0;
newvalues[i].first = 0;
newvalues[i].last = 0;
}
// kreiramo niz za cuvanje do sada unetih podataka kako bi se uradio ponovo add za njih (radi regenerisanja hash_keys)
repackarr = new E[repacksize];
// trazimo po postojecoj hash tabeli elemente i dodajemo ih u niz za cuvanje
for (size_t i = 0; i < nmax; ++i) {
if ( !hashtablevalues[i].first ) continue ; // ako je polje first prazno element hash tabele nije aktivan
node = hashtablevalues[i].first ;
while ( node ) {
// vadimo jedan po jedan element iz Separate Chain vezanog za tekuci red u hash tabeli
repackarr[currE] = (node->e) ;
currE++;
node = node->next;
}
}
// brisemo staru hash tabelu i proglasavamo novu za tekucu, uz podesavanje duzina prema novoj tabeli
delete[] hashtablevalues;
hashtablevalues = newvalues;
htdata = newvalues;
nmax = newnmax;
currlength = 0;
this->add(repackarr, repacksize); // na kraju ovog dela ceo onaj niz vracamo u hash tabelu uz rehash.
delete[] repackarr;
repackarr = 0;
}
unsigned long currhashValue = hashValue(e); // racunamo hash elementa koji se dodaje.
size_t i ;
for (i = 0; i<currlength; i++) {
// trazimo da li izracunati hash vec postoji u tabeli.
if ( htdata[i].hash_key == currhashValue ) {
break;
};
};
bool didEexist = this->member( e ); // proveravamo da li slucajno element koji zelimo dodati vec postoji u hash tabeli.
if ((!didEexist) && (i==currlength)) {
// ako ne postoji ni hash ni sam element do sada zauzmi novo polje u tabeli za njegov smestaj.
currlength++;
htdata[currlength-1].hash_key = currhashValue;
};
if (didEexist) return ; // ako element postoji vracamo se nazad bez generisanja duplikata
for (i = 0; i<currlength; i++) {
// nadji slot u kome je hash trenutnog elementa i ubaci ga u njegov Separate Chain
if ( htdata[i].hash_key == currhashValue ) {
if (!htdata[i].member_(htdata[i].first, e)) {
htdata[i].add_(htdata[i].first, e);
return;
};
};
};
}
// dodaj niz elemenata u hash tabelu
template <typename E>
void AhmetHT<E>::add( const E e[], size_t s ) {
for (size_t i = 0; i < s; ++i) {
add_( hashtablevalues , e[i] );
}
}
// brisanje trazenog elementa iz hash tabele
template <typename E>
void AhmetHT<E>::remove_( AhmetHT<E>::HTelement* htdata, const E& e ) {
unsigned long currhashValue = 0;
if (!htdata) return; // ako je tabela prazna idi nazad
currhashValue = hashValue(e); // izracunaj hash vrednost elementa
for (size_t index = 0; index < nmax ; index++ ) {
// nadji odakle se brise trazeni element
if ((!htdata[index].first)&&(!htdata[index].last)) continue; // ako su polja first ili last na 0 vrati se nazad na pocetak petlje.
// if (currhashValue == htdata[index].hash_key) {
if (htdata[index].member_(htdata[index].first, e)) {
// ako je nadjen index u hash tabeli iz koje se brise element pozovi remove iz tog Separate Chain-a da izbrise isti.
htdata[index].remove_(htdata[index].first, e);
if (htdata[index].first == 0) {
// ako je posle brisanja polje first postalo 0 znaci taj separate chain nije vise u upotrebi te se ostatak tabele prepakuje...
htdata[index].hash_key = 0;
htdata[index].first = 0;
htdata[index].last = 0;
for (size_t i=(index+1); i<currlength; i++) {
// pomeri sve elemente posle njega za jedno mesto unazad
HTelement *htdid = &htdata[i-1] ;
HTelement *htdi = &htdata[i] ;
swap_( htdid, htdi );
}
// umanji brojac zauzetih elenata.
currlength--;
}
return;
}
}
}
template <typename E>
void AhmetHT<E>::remove( const E e[], size_t s ) {
for (size_t i = 0; i < s; ++i) {
AhmetHT<E>::remove_( hashtablevalues, e[i] );
}
}
template <typename E>
bool AhmetHT<E>::member_( AhmetHT<E>::HTelement* htdata, const E& e ) const {
unsigned long currhashValue = 0;
if (!htdata) return false;
size_t loccurrlength = currlength;
currhashValue = hashValue(e);
for (size_t index = 0; index < loccurrlength ; index++ ) {
if (!htdata[index].first) continue;
if (!htdata[index].last) continue;
if (htdata[index].member_(htdata[index].first, e)) {
return htdata[index].member_(htdata[index].first, e);
}
}
return false;
}
template <typename E>
size_t AhmetHT<E>::size_( AhmetHT<E>::HTelement* htdata ) const {
size_t htelsize = 0;
size_t nodesize = 0;
if (!htdata) {
return nodesize;
}
while (htelsize < nmax) {
if (htdata[htelsize].first != 0) {
nodesize += htdata[htelsize].size();
}
htelsize++;
}
return nodesize;
}
template <typename E>
bool AhmetHT<E>::empty_( AhmetHT<E>::HTelement* htdata ) const {
size_t htelsize = 0;
if (!htdata) {
return true;
}
while (htelsize < nmax) {
if (htdata[htelsize].first != 0) {
return false;
}
htelsize++;
}
return true;
}
template <typename E>
E AhmetHT<E>::min( ) const {
size_t counterHT = 0;
E mine ;
if (!hashtablevalues) throw typename Container<E>::Exception( "Ahmet::min(): empty" );
while (hashtablevalues[counterHT].first == 0) {
counterHT++;
if ( counterHT > nmax ) throw typename Container<E>::Exception( "Ahmet::min(): empty" );
}
mine = hashtablevalues[counterHT].first->e;
for (counterHT=0;counterHT<nmax;counterHT++) {
if ( ! hashtablevalues[counterHT].first ) {
continue;
}
if (mine > hashtablevalues[counterHT].min()) {
mine = hashtablevalues[counterHT].min();
}
}
return mine;
}
template <typename E>
E AhmetHT<E>::max( ) const {
size_t counterHT = 0;
E maxe;
if (!hashtablevalues) throw typename Container<E>::Exception( "Ahmet::max(): empty" );
while (hashtablevalues[counterHT].first == 0) {
counterHT++;
if ( counterHT > nmax ) throw typename Container<E>::Exception( "Ahmet::max(): empty" );
}
maxe = hashtablevalues[counterHT].first->e;
for (counterHT=0;counterHT<nmax;counterHT++) {
if ( ! hashtablevalues[counterHT].first ) {
continue;
}
if (hashtablevalues[counterHT].max() > maxe) {
maxe = hashtablevalues[counterHT].max();
}
}
return maxe;
}
template <typename E>
std::ostream& AhmetHT<E>::print_( AhmetHT<E>::HTelement* htdata , std::ostream &o ) const {
size_t i = 0;
if (htdata) {
for (i=0;i<nmax;i++) {
if ( ! htdata[i].first ) {
continue;
}
htdata[i].print_(htdata[i].first, o);
}
}
return o;
}
template <typename E>
size_t AhmetHT<E>::apply_( AhmetHT<E>::HTelement* htdata, const Functor<E>& f, Order order) const {
if(nmax==0)
return 0;
HTelement temp;
Node *node;
int counterETupple = 0;
size_t repacksize, currE=0;
if (order == dontcare) {
bool apply=true;
for (size_t i = 0;apply&& i < nmax; ++i) {
if ( !htdata[i].first ) continue ;
if ( !htdata[i].last ) continue ;
node = htdata[i].first ;
while ( node ) {
counterETupple++;
if(!f((node->e))){
apply=false;
break;
}
node = node->next;
}
}
return counterETupple;
}
E **repackarr ;
repacksize = this->size();
repackarr = new E *[repacksize];
for (size_t i = 0; i < nmax; ++i) {
if ( !htdata[i].first ) continue ;
if ( !htdata[i].last ) continue ;
node = htdata[i].first ;
while ( node ) {
repackarr[currE] = &(node->e) ;
currE++;
node = node->next;
}
}
//shell sort
int flag1 = 1;
int d1 = repacksize;
while( flag1 || (d1 > 1)) // boolean flag (true when not equal to 0)
{
flag1 = 0; // reset flag to 0 to check for future swaps
d1 = (d1+1) / 2;
for (size_t i = 0; i < (repacksize - d1); i++)
{
if (!(*repackarr[i + d1] > *repackarr[i]))
{ std::swap(*repackarr[i],*repackarr[i+d1]);
flag1 = 1; // tells swap has occurred
}
}
}
if (order == descending) {
for (int ii=(repacksize-1);ii>=0;ii--) {
counterETupple++;
if (!f(*repackarr[ii])) {
break;
}
}
} else {
for (size_t i=0;i<repacksize;i++) {
counterETupple++;
if (!f(*repackarr[i])) {
break;
}
}
}
delete[] repackarr;
repackarr=NULL;
return counterETupple;
}
#endif //AHMETHT_H