diccionario.cpp Source File

00001 
00006 #include <cassert>
00007 #include <diccionario.h>
00008 
00009 /* _________________________________________________________________________ */
00010 
00011 template<class Tk, class Ti>
00012 bool Diccionario<Tk,Ti>::posicion_indice(int& pos, const Tk& llave) const
00013 {
00014   int izq=0, der=nelementos-1,centro;
00015 
00016   while (der-izq>=0) {
00017     centro=(izq+der)/2;
00018     if (llave<parejas[centro].primero)
00019       der=centro-1;
00020     else if (llave>parejas[centro].primero)
00021            izq=centro+1;
00022          else {
00023            pos=centro;
00024            return true;
00025          }
00026   }
00027   pos= izq;
00028   return false;
00029 }
00030 
00031 
00032 /* _________________________________________________________________________ */
00033 
00034 template<class Tk, class Ti>
00035 void Diccionario<Tk,Ti>::expandir()
00036 {
00037   reservados= (nelementos==0)?1:nelementos*2;
00038   Par<Tk,Ti> * nuevas_parejas= new Par<Tk,Ti>[reservados];
00039   for (int j= 0; j<nelementos ;++j)
00040     nuevas_parejas[j]= parejas[j];
00041   delete[] parejas;
00042   parejas= nuevas_parejas;
00043 }
00044 
00045 /* _________________________________________________________________________ */
00046 
00047 template<class Tk, class Ti>
00048 void Diccionario<Tk,Ti>::contraer()
00049 {
00050   assert(nelementos<=reservados/2);
00051   reservados= reservados/2;
00052   Par<Tk,Ti> * nuevas_parejas= new Par<Tk,Ti>[reservados];
00053   for (int j= 0; j<nelementos ;++j)
00054     nuevas_parejas[j]= parejas[j];
00055   delete[] parejas;
00056   parejas= nuevas_parejas;
00057 }
00058 
00059 /* _________________________________________________________________________ */
00060 
00061 template<class Tk, class Ti>
00062 Diccionario<Tk,Ti>::Diccionario<Tk,Ti>()
00063 {
00064   parejas=0;
00065   nelementos=reservados=0;
00066 }
00067 
00068 /* _________________________________________________________________________ */
00069 
00070 template<class Tk, class Ti>
00071 Diccionario<Tk,Ti>::Diccionario<Tk,Ti>(const Diccionario<Tk,Ti>& orig)
00072 {
00073   reservados= nelementos= orig.nelementos;
00074   if (nelementos>0) {
00075     parejas= new Par<Tk,Ti>[nelementos];
00076     for (int i=0; i<nelementos;++i)
00077       parejas[i]= original.parejas[i];
00078   }
00079   else parejas=0;
00080 }
00081 
00082 /* _________________________________________________________________________ */
00083 
00084 template<class Tk, class Ti>
00085 Diccionario<Tk,Ti>::~Diccionario<Tk,Ti>()
00086 {
00087   if (reservados>0)
00088     delete[] parejas;
00089 }
00090 
00091 /* _________________________________________________________________________ */
00092 
00093 template<class Tk, class Ti>
00094 Diccionario<Tk,Ti>&
00095     Diccionario<Tk,Ti>::operator= (const Diccionario<Tk,Ti>& original)
00096 {
00097   if (this!= &original) {
00098     if (reservados>0)
00099       delete[] parejas;
00100     reservados= nelementos= orig.nelementos;
00101     if (nelementos>0) {
00102       parejas= new Par<Tk,Ti>[nelementos];
00103       for (int i=0; i<nelementos;++i)
00104         parejas[i]= original.parejas[i];
00105     }
00106     else parejas=0;
00107   }
00108   return *this;
00109 }
00110 
00111 /* _________________________________________________________________________ */
00112 
00113 template<class Tk, class Ti>
00114 void Diccionario<Tk,Ti>::insertar(const Tk& llave, const Ti& valor)
00115 {
00116   int pos;
00117   if (posicion_indice(pos,llave)) // ya está
00118     parejas[pos].segundo=valor;
00119   else { // hay que insertarlo
00120       if (nelementos==reservados)
00121          expandir();
00122       for (int j=nelementos; j>pos; --j)
00123           parejas[j]= parejas[j-1];
00124       parejas[pos].primero= llave;
00125       parejas[pos].segundo= valor;
00126       ++nelementos;
00127   }
00128 }
00129 
00130 /* _________________________________________________________________________ */
00131 
00132 template<class Tk, class Ti>
00133 Diccionario<Tk,Ti>::iterador Diccionario<Tk,Ti>::borrar(iterador it)
00134 {
00135   assert(it!=end());
00136   nelementos= nelementos-1;
00137   int pos=it.puntero-parejas;
00138   for (int j=pos;j<nelementos;++j)
00139          parejas[j]=parejas[j+1];
00140   if (nelementos<reservados/4)
00141         contraer();
00142 }
00143 
00144 /* _________________________________________________________________________ */
00145 
00146 template<class Tk, class Ti>
00147 Diccionario<Tk,Ti>::iterador Diccionario<Tk,Ti>::buscar(const Tk& llave)
00148 {
00149   int pos;
00150   if (posicion_indice(pos,llave))
00151     return iterador(parejas+pos);
00152   else return iterador(parejas+nelementos); // end()
00153 }
00154 
00155 /* Fin diccionario.cpp */