conjunto.cpp Source File

00001 
00006 #include<cassert>
00007 // #include<conjunto.h> Este codigo se incluye en conjunto.h
00008 
00009 /* _________________________________________________________________________ */
00010 
00011 template<class T>
00012 bool Conjunto<T>::posicion_elemento(int& pos, T e) const
00013 {
00014   int izq=0, der=nelementos-1,centro;
00015 
00016   while (der-izq>=0) {
00017     centro=(izq+der)/2;
00018     if (e<v[centro])
00019       der=centro-1;
00020     else if (e>v[centro])
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 template<class T>
00034 bool Conjunto<T>::insertar(T e)
00035 {
00036   int pos;
00037   if (posicion_elemento(pos,e))
00038     return false;
00039   else {
00040     if (v.size()==nelementos)
00041       if (v.size()==0)
00042          v.resize(1);
00043       else v.resize(2*v.size());
00044     for (int j=nelementos; j>pos; --j)
00045       v[j]=v[j-1];
00046     v[pos]= e;
00047     nelementos++;
00048     return true;
00049   }
00050 }
00051 /* _________________________________________________________________________ */
00052 
00053 template<class T>
00054 bool Conjunto<T>::borrar(T e)
00055 {
00056   int pos;
00057   if (posicion_elemento(pos,e)) {
00058     nelementos--;
00059     for (int j=pos;j<nelementos;++j)
00060       v[j]=v[j+1];
00061     if (nelementos<v.size()/4)
00062       v.resize(v.size()/2);
00063     return true;
00064   }
00065   else return false;
00066 }