[ SuperC @ 26.09.2009. 21:42 ] @
situacija je ovakva:

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.




Code:
 #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



[ SuperC @ 26.09.2009. 22:26 ] @
pri pokusaju da uradim pravilno timeout na 10 na 6 tj performance dobijam gresku:


Status metoda rezultat (ocekivan) dobijeno Container-Inhalt (ocekivan) Container::print()
ERROR apply( f, descending ) - 11011 Functor-poziv umjesto 11... 0 1 2 3 4 5 6 7 8 9 10 13 4713... 1 2 3 4 5 6 7 8 9 10 13 4713 6...
ERROR apply( f, ascending ) - Functor-Aufruf #1 sa pogresnim... 0 1 2 3 4 5 6 7 8 9 10 13 4713... 1 2 3 4 5 6 7 8 9 10 13 4713 6...
WARNING - - Test prekinut
[ Mihajlo Cvetanović @ 27.09.2009. 18:01 ] @
Ovo nije početnički program :-) Imaš mali problem sa BHS jezikom, i teško mi je da shvatim šta želiš. Nemoj da skraćuješ smisao rečenica i reči. Zamisli da ti ocenjujemo znanje iz BHS :-). Takođe:

- Šta je "separate chaining"?
- Šta je to što se "nakon toga sortira na bazi shell sorta"?
- Šta su "10 na 5" i "10 na 6"?
- Šta je to "caching od minimuma i maximuma kao i caching sortiranih vrijednosti"?
- U datom kodu ne postoje stringovi "ERROR" i "WARNING". Ne znamo na šta se te poruke odnose (a naročito na šta se odnose brojevi u porukama). U kodu ne postoji ni funkcija apply (mada postoji apply_).

Šta je tebi u stvari problem? Program ne radi tačno, ili ne radi dovoljno brzo?
[ SuperC @ 27.09.2009. 18:23 ] @
hehehe, ma nije problem do BHS jezika, nego do skracene postavke, ovaj zadatak je potrebno testirati na odredjenoj stranici, zatvorenog tipa (username i password potrebni).

zadatak ima tri dijela:
1. implementacija strukture podataka (kod mene separate chaining)
2. implementacija sortiranja (kod mene shellsort)
3. evaluiranje i optimiranje (ovdje dolazim do timeouta problema na 10 na 6)

Sve mora biti unutar jednog fajla, sa, naravno, ekstenzijom .h.
Nakon implementiranja strukture podataka je potrebno sortiranje uz pomoc shellsorta realizirati.





Na pocetku je dat container:

Code:
#ifndef CONTAINER_H
#define CONTAINER_H
 
#include <iostream>
 
class Container {
  Container& operator=( const Container& );
public:
  class Functor;
  class Exception;
  enum Order { dontcare, ascending, descending };
 
  virtual ~Container( ) {}
 
  virtual void add( int e ) { add( &e, 1 ); }
  virtual void add( const int e[], size_t len ) = 0;
 
  virtual void remove( int e ) { remove( &e, 1 ); }
  virtual void remove( const int e[], size_t len ) = 0;
 
  virtual bool member( int e ) const = 0;
  virtual size_t size( ) const = 0;
  virtual bool empty( ) const { return size() == 0; }
 
  virtual int min( ) const = 0;
  virtual int max( ) const = 0;
 
  virtual std::ostream& print( std::ostream& o ) const = 0;
 
  virtual size_t apply( const Functor& f, Order order = dontcare ) const = 0;
};
 
inline std::ostream& operator<<( std::ostream& o, const Container& c ) { return c.print( o ); }
 
class Container::Functor {
public:
  virtual bool operator( )( int e ) const = 0;
  virtual ~Functor( ) {}
};
 
class Container::Exception : public std::exception {
  std::string msg;
public:
  explicit Exception( const std::string& msg ) : msg( msg ) {}
  virtual ~Exception() throw() {}
  virtual const char * what() const throw() { return msg.c_str(); }
};
 
#endif //CONTAINER_H
[ Mihajlo Cvetanović @ 27.09.2009. 18:32 ] @
Fino, ali nisi odgovorio ni na jedno moje pitanje :-)
[ SuperC @ 27.09.2009. 18:45 ] @
- Šta je "separate chaining"?
- Šta je to što se "nakon toga sortira na bazi shell sorta"?
- Šta su "10 na 5" i "10 na 6"?
- Šta je to "caching od minimuma i maximuma kao i caching sortiranih vrijednosti"?
- U datom kodu ne postoje stringovi "ERROR" i "WARNING". Ne znamo na šta se te poruke odnose (a naročito na šta se odnose brojevi u porukama). U kodu ne postoji ni funkcija apply (mada postoji apply_).


1. http://sr.wikipedia.org/wiki/%...%D0%B0%D0%B1%D0%B5%D0%BB%D0%B0
2. znaci hash vrijednosti se sortiraju (functor na array primijeniti, obrisati, broj obradjenih vrijednosti vratiti)
3. u performance dijelu, koji se radi tako da se uploadira fajl na stranicu interni test program testira sam kod na pozive metoda add (key), add( Key[], size_t), member( Key ), size(), min(), apply( Functor f, Order order ), sa n elemenata
4. vidi kod5. error i warning dobijam od test programa na samoj web stranici. primijenjuje se apply_
[ Mihajlo Cvetanović @ 27.09.2009. 19:28 ] @
1. Znam šta je heš funkcija, ali ne znam šta je separate chaining (možda nije ni bitno, ali trenutno ne znam da li jeste ili nije bitno).
2. Ne razumem rečenicu "functor na array primijeniti, obrisati, broj obradjenih vrijednosti vratiti", niti kako je to odgovor na drugo pitanje. Možda misliš da te zamajavam, ali stvarno ne razumem i pokušavam da ti pomognem. Pomozi mi da ti pomognem!
3. Da li su "10 na 5" i "10 na 6" zapravo dva testna slučaja gde n može da bude 10^5 i 10^6?
4. Teško mi je da gledam ako ne znam u šta gledam. Tvoj kod je kompleksan, i što je najvažnije ne znam koju grešku da jurim, jer nisi rekao šta ti je problem. Što bih se ja bespotrebno mučio ako tebe mrzi da objasniš. Nisam ni plaćen da pomažem...
5. Šta znače oni brojevi u ERROR porukama?

I glavno pitanje ostaje: Šta je tebi u stvari problem? Program ne radi tačno, ili ne radi dovoljno brzo?
[ SuperC @ 27.09.2009. 19:47 ] @
1. sepchain je jedno od mogucih rjesenja kada dolazi do kolizija u hash-tabelama, tacnije receno odvojeno ili dijeljeno lancano vezivanje, radjeno na principu modula
2. pa ovdje je caka sto hash jednom slozi sve, i onda sa shellsortom treba opet sve sloziti u rastucem i opadajucem redoslijedu kao i naci min i max, sto sam ja i uradio i to radi, barem prema testnom programu na serveru
3. da to su dva testna slucaja, odnosno, kada ja uploadujem ovaj kod, onda program na serveru testira slucajeve: 10, 10 na 2, 10 na 3, 10 na 4, 10 na 5 i 10 na 6. U svim slucajevima ja dobijam odgovor success, osim u slucaju 10 na 6 gdje dobijam timeout
4. evo pokusavam
5. neke imaginarne vrijednosti koje taj program sa servera unosi. ocekivane i dobijene vrijednosti moraju biti iste, ako se razlikuju negdje u kodu ima nesto sto pravi tu gresku


Meni je problem, sto se sve radi u tri faze.
1. implementacija strukture podataka. to sam odradio
2. implementacija sortiranja, i to sam odradio

i u oba gornja slucaja dobio od testnog programa na serveru success, odnosno da je sve uradjeno kako je trazeno

samo u trecoj fazi (performance odnosno optimiranje) imam problem kod 10 na 6, gdje dobijam timeout i onda dodatno moram implementirati caching u navedenim slucajevima.

ps. hvala na pomoci, trudim se da ovo nekako pojednostavim da svi mogu da shvate
[ Mihajlo Cvetanović @ 27.09.2009. 20:52 ] @
Ako je problem perfomansa rešenja, to jest tajmaut za slučaj 10 na 6, zašto onda testni program ispisuje ERROR? Trebalo bi valjda da ispiše da je isteklo vreme. Koliko vremena je dozvoljeno za jedan test?

Napiši ceo tekst koji ide uz ERROR poruke (naravno bez brojeva ako ih ima milion). Možeš da iskoristiš Google translator da jezik brzo prebaciš s nemačkog na engleski.
[ SuperC @ 27.09.2009. 21:18 ] @
da, i ja sam tako mislio, no problem je sto je testni program podijeljen na dva dijela: test koda, samog programa i performance test. unutar performance testa onda dolazi do greske koju sam spomenuo

nema nikakvog ekstra teksta uz error poruku, to izgleda ovako:

Code:

Error

Methode    apply( f, descending )
Ergebnis (erwartet)    -
Ergebnis    11011 Functor-Aufrufe statt 11012; 
Container-Inhalt (erwartet)    0 1 2 3 4 5 6 7 8 9 10 13 4713 65549 66767 131085 196621 262157 327693 393229 458765 524301 563618 589837 625672 655373 720909 786445 851981 917517 983053 1048589 1114125 1122523 1179661 1184577 1245197 1310733 1376269 1441805 1507341 1572877 1638413 1681428 1703949 1743482 1769485 1835021 1900557 1966093 2031629 2097165 2162701 2228237 2240333 2293773 2359309 2424845 2490381 2555917 2621453 2686989 2752525 2799238 2818061 2883597 2949133 3014669 3080205 3145741 3211277 
....(ovdje sam sada skratio ovu tabelu jer je previse duga)

Container::print()    1 2 3 4 5 6 7 8 9 10 13 4713 65549 66767 131085 196621 262157 327693 393229 458765 524301 563618 589837 625672 655373 720909 786445 851981 917517 983053 1048589 1114125 1122523 1179661 1184577 1245197 1310733 1376269 1441805 1507341 1572877 1638413 1681428 1703949 1743482 1769485 1835021 1900557 1966093 2031629 2097165 2162701 2228237 2240333 2293773 2359309 2424845 2490381 2555917 2621453 2686989 2752525 2799238 2818061 2883597 2949133 3014669 3080205 3145741 3211277 


kod druge greske to izgleda ovako:

Code:

ERROR

Methode    apply( f, ascending )
Ergebnis (erwartet)    -
Ergebnis    Functor-Aufruf #1 mit falschem key 1 (statt 0); 
Container-Inhalt (erwartet)    0 1 2 3 4 5 6 7 8 9 10 13 4713 65549 66767 131085 196621 262157 327693 393229 458765 524301 563618 589837 625672 

Container::print()    1 2 3 4 5 6 7 8 9 10 13 4713 65549 66767 131085 196621 262157 327693 393229 458765 524301 563618 589837 625672 655373

[ Mihajlo Cvetanović @ 27.09.2009. 21:25 ] @
A gde je vrednost nula kad se izvršava print? Razlikuju se ulaz i izlaz za taj jedan element.
[ SuperC @ 27.09.2009. 21:33 ] @
eh to je pitanje?? :)
[ Mihajlo Cvetanović @ 27.09.2009. 21:54 ] @
U međuvremenu male primedbe:

- U funkciji AhmetHT<E>::HTelement::delete_ brisanje radiš rekurzivno. Efikasnije je da se radi iterativno: zapamti sledeći, obriši trenutni, trenutni = sledeći, ponavljaj do kraja.

- U funkciji AhmetHT<E>::min (kao i max) imaš sledeće
Code:

        if (mine > hashtablevalues[counterHT].min()) {
            mine = hashtablevalues[counterHT].min();
        }

Bespotrebno pozivaš funkciju dva puta. Treba da zapamtiš vrednost u privremenoj promenljivoj, pa onda tu vrednost koristi dva puta.

- Isti slučaj je i u funkciji AhmetHT<E>::member_, gde pozivaš funkciju htdata[index].member_ dva puta.

- Funkcija AhmetHT<E>::remove možda može da se optimizuje. Ako bi ulazni niz e sortirao po vrednostima heš funkcije onda ne bi morao za svaki element da polaziš od početka heš tabele, nego bi mogao da nastaviš od sledeće vrednosti u tabeli. Funkcija void remove_(Node* node, const E& e) bi tada morala da vraća sledeći element u listi (next od obrisanog), i još nešto bi tu moralo da se zakomplikuje, ali uklanjanje niza elemenata bi se brže izvršavalo.

- Funkcija AhmetHT<E>::remove_ mi je malo čudna. Zar nije poenta heš tabele da odmah znaš u kom polju u tabeli treba da tražiš element? Ti prolaziš kroz čitavu tabelu, umesto da izračunaš heš vrednost datog elementa (sa hashValue funkcijom) i odmah ubodeš index gde element može da bude.

- Imaš using Container<E>::add (kao i remove), ali nije mi jasno kako bazna klasa Container zna kako da radi sa elementima iz tvoje izvedene klase. Kako to radi?

EDIT: shvatio sam ovo poslednje, sad sam primetio kod klase Container.



[Ovu poruku je menjao Mihajlo Cvetanović dana 27.09.2009. u 23:12 GMT+1]
[ SuperC @ 28.09.2009. 13:27 ] @
mislim da cu morati brzo doci do rjesenja koji ce zadovoljiti testni program na serveru, a onda nekad u slobodno vrijeme pokusati to sto mi ti predlazes, sada sam u malenom nedostatku vremena


ako imas prijedlog sta konkretno odnosno kako da kod izgleda zamolit cu te da ovdje postavis, naravno ako imas vremena za to, a ja onda mogu vidjeti da li ce to testni program prihvatiti
[ Mihajlo Cvetanović @ 28.09.2009. 13:42 ] @
Da li je problem to što u rezultatu 10^6 testa nedostaje element nula?
[ SuperC @ 28.09.2009. 14:03 ] @
evo kako to izgleda:


AddTest I: Container::add( const E )
Status n Tests Zeit
(ms) verbrauchter Speicher
(Byte netto) max. belegter Speicher
(Byte netto) angeforderter Speicher
(Byte netto) Speichereffizienz
(netto)
SUCCESS 1 65536 0.008252 1648 1648 1648 0.24%
SUCCESS 10 65536 0.001483 1756 1756 1756 2.28%
SUCCESS 100 4096 0.001592 2836 2836 2836 14.10%
SUCCESS 1000 16 0.038476 30532 49352 196248 13.10%
SUCCESS 10000 1 0.580875 286148 442984 1924904 13.98%
TIMEOUT 100000 ? ? ? ? ?


takvih testova ima 11, i na 55 imam tacno odnosno vrijednosti a na svakom n=100000 dobijam Time Out, i takvih vrijednosti imam 11. :)
[ Mihajlo Cvetanović @ 28.09.2009. 15:14 ] @
Tek sad sam bacio pogled na funkciju add_. Nešto slično što sam spomenuo za funkciju remove_ važi i ovde. Svrha postojanja heš mape je da potraživanje elementa bude najkraće fizički moguće. Treba da se izvršava za nanosekundu. To se postiže tako što tačno znaš gde treba da tražiš element. Do traženog elementa ne smeš da dođeš pretragom svih članova niza hashtablevalues, nego direktnim skokom na poznati indeks. Indeks dobijaš funkcijom hashValue. Moraš da znaš koji je opseg vrednosti koje ova funkcija vraća kao rezultat. Pitaj nekog ako ne znaš. Tabela hashtablevalues u početku nije prazna nego od početka do kraja rada zauzima tačno onoliko mesta koliki je opseg rezultata funkcije hashValue, ali su sve vrednosti u njoj postavljene na nulu. Drugim rečima hashtablevalues nije HTelement *hashtablevalues, nego je HTelement hashtablevalues[<unapred_poznata_vrednost>].

Postojanje članice HTelement::hash_key nema smisla. Ukloni hash_key, i ukloni sve pretrage po hash_key. Indeks elementa i u nizu hashtablevalues je upravo hash_key. Kad dobiješ vrednost funkcije hashValue automatski si suzio svoju pretragu na samo taj jedan HTelement.
[ Mihajlo Cvetanović @ 28.09.2009. 15:44 ] @
Uzgred, i funkcija apply_ bi možda mogla da se optimizuje. Preduslov je da su svi lanci sortirani (već to bi ti automatski optimizovalo dodavanje i brisanje elementa, jer bi umesto kompleksnosti O(n) imao O(n/2)). Ako su svi lanci sortirani, onda umesto sortiranja n elemenata imaš sortiranje maksimalno m elemenata, gde je m opseg funkcije hashValues. Svaki put kad primeniš funktor na elementu iz lanca prelaziš na sledeći element lanca, kome treba naći mesto u osnovnoj sortiranoj listi od m. Ali to je već programersko iživljavanje :-)