0

me esta costando un poco un ejercicio, desarrollar el método int first_item(void) debe devolver el índice del primer elemento del conjunto. El método int last_item(void) debe devolver el índice del último elemento del conjunto.

Estoy bloqueado ahí, lo hice basandome en la funcion contains, que me situa en la posicion exacta en el block pequeño, me gustaria saber si tengo bien el algoritmo del last_item, este es el código:

#pragma once

#include <cstring>//libreri­a cadenas
#include <cassert>

using namespace std;

#define N_BITS_WORD (8 * sizeof(T))//pasarlo a bits, sizeof da el numero de bytes y se multiplica por 8 para tener el numero de bits 1 byte 8 bits



template <class T, size_t N>// class T, ¿size_t N?
class bitset_t
{
    private:
        T* block_;// tipo de dato dinámico que es block_, es una dirección con la que vamos apuntando a un block_ en específico  CONJUNTO GLOBAL
        int sz_;//tamaño total del conjunto global

    public:
        bitset_t(void)://constructor  por defecto, aqui se inicializa todo a 0
            block_(NULL),// esto es como si estuviésemos en el constructor 
            sz_(N/N_BITS_WORD){ // esta calculando la longitud del vector,  lo que ocupa cada posicion global del sz_, si N_BITS_WORD representa los bits de cada palabra, y N es el numero total de bits, sz_ ahora guarda el número de posiciones 

            if ((N % N_BITS_WORD) != 0)
                sz_ ++;// Si la division no es exacta, se añade una posicion mas al vector sin complicaciones, para que sobre espacio

            block_ = new T[sz_];//un nuevo block_ , block_ es el bloque GLOBAL

            for(int i = 0; i < sz_; i++)//inicializados a cero
                block_[i] = 0;// todas las posiciones del block_ global a 0 para de inicializarlas
        };


bitset_t(const bitset_t& bs):// un nuevo constructor  de copia 
        block_(NULL),// se inicializa block_ a NULL, un primer constructor para calcular el espacio de cada  conjunto , hay dos block_, si el objeto que creo en el main no le paso parámetros, se llama al constructor  por defecto, de lo contrario, se llama al de copia
        sz_(bs.sz_)
        {
            block_ = new T[sz_];    // en funcion de si hay parametros o no

            for(int i = 0; i < sz_; i++) 
                block_[i] = bs.block_[i];       
        }

        ~bitset_t(void) {
            if (block_) delete [] block_;
        }

        void insert(int i){//insertar  un bit en un conjunto o bloque

            assert(i <= N);// comprobando que i sea menor que el size total
            assert(i >= 1);// comprobando que sea mayor que 1 la posición

            i--;

            const int pos    = i/N_BITS_WORD;// se calcula la posicion de un conjunto determinado
            const int offset = i%N_BITS_WORD;// el resto de esa division o offset nos sirve para acceder a una posición concreta en ese conjunto

            block_[pos] |= (T(0x1) << offset);// la INSERCION SE HACE CON OR refiriendote al block_[1] = metiendole un 1 a la posicion 6 en el block_[1] ¿no se debería declarar una variable auxiliar T* aux ?
        }

        void remove(int i){// quitar del conjunto global, lo mismo, solo que con AND

            assert(i <= N);
            assert(i >= 1);

            i--;

            const int pos    = i/N_BITS_WORD;
            const int offset = i%N_BITS_WORD;



block_[pos] &= ~(T(0x1) << offset);
        }

        bool contains(int i) const
        {

            assert(i <= N);
            assert(i >= 1);

            i--;

            const int pos    = i/N_BITS_WORD;
            const int offset = i%N_BITS_WORD;

            return (block_[pos] & (T(0x1) << offset)) != T(0x0);  
        }
        //COMPROBAR EJEMPLO
        // 0 0 1 1 1 0 POS 3 comprobar
        // 0 0 0 0 0 1 
        // 0 0 0 1 0 0 lo desplazamos
        // 0 0 0 1 0 0  esto es lo que resulta de hacer el and de la tercera fila con la primera


        void insert(const bitset_t& bs) // insertar bloque 
        {
            for(int i = 0; i < sz_; i++)
                block_[i] |= bs.block_[i];
        }

        void remove(const bitset_t& bs) //eliminar bloque
        {
            for(int i = 0; i < sz_; i++)
                block_[i] &= ~bs.block_[i];
        }

        bool contains(const bitset_t& bs) const
        {   
            bool contains_set = true;

            int i = 0;

            while ((i < sz_) && (contains_set)){
                contains_set = contains_set && ((block_[i] & bs.block_[i]) == bs.block_[i]);
                i++;
            }



return contains_set;        
        }

        ostream& write(ostream& os) const 
        {

            string s;
            to_string(s);
            os << s;

            return os;
        }

        void union_set (const bitset_t& B, bitset_t& C){ //union de conjuntos le doy valores en el main, union de todos los elementos del vector principal
          for (int i=0; i<sz_;i++){

            C.block_[i] = block_[i] | B.block_[i];

          }
        }
        void intersec_set (const bitset_t& B, bitset_t& C){ // interseccion todos elementos del vector principal  |__| |__| |__| vector de conjuntos  + otro conjunto , hago su union,interseccion, y cada conjunto ocupa 64 bits
            for (int i=0;i<sz_;i++){
                C.block_[i]=block_[i] & B.block_[i];
            }
        }

        void diff_set (const bitset_t& B, bitset_t& C){ // recuerda que la lectura se realiza en un fichero si en A tengo 1 y B 0 a and no b, un vacio de b es igual a 1, tengo  diferencia de conjuntos:  la diferencia entre dos conjuntos es una operación que resulta en otro conjunto, cuyos elementos son todos aquellos en el primero de los conjuntos iniciales que no estén en el segundo.
            for (int i=0;i<sz_;i++){
                C.block_[i]= block_[i] &~ B.block_[i];
            }
        }

        int cardinality (void){ // tres cosas que te faltaban, una, que cada bit evaluado se arrastra una posicion a la derecha dando paso al siguiente bit evaluar(comparar con el valor 1 del one)
        // la otra cosa, que necesitas una sentencia while que diga que mientras sea distinto de cero evaluar directamente, porque como en one hay un 1 fijado eso significa que la comparacion
        // con los bits a 0 del block_ siempre va a dar cero, un while es  mucho mas eficiente que un for

            T one = 0x1;  //¿o block?
            int card = 0; 

            int j=0;


            for(int j=0;j<sz_;j++){ // RECUERDA QUE N_BITS_WORD es el numero de bits que ocupa cada conjunto pequeño y estarias recorriendo 64 veces el mismo conjunto, por 
            // se le pone sz_ que es el tamaño global 

            T block = block_[j]; // necesitas guardar una copia del block_ original para que no se pierda, ten en cuenta que el block con el que vas a hacer operaciones se producen desplazamientos
            // esto es mas eficiente, block es una posicion y a cada vuelta del for estas guardando ahí una posicion del bloque, no hace falta guardar ahí todos los bloques 

            while (block!=0){
                if ((block & one)==1){
                card++;
                }
                block >>= 1;
            }

            //for (int i= 0; i<N_BITS_WORD; i++){
                //if ((block_ & one)== 1)
                //card++;
            }
            return card;

            }

            int first_item(void){
                bool firstone = 0;
                int j=0,i=-1;
                T one = 0x1;
                    while(i<sz_ && !firstone){
                        i++;
                        j=0;
                        T block = block_[i];
                        while (block!=0 && !firstone){
                            if ((block & one)==1)
                                firstone=1;
                            block >>= 1;
                            j++;

                        }

                    }
                    return ((i*N_BITS_WORD)+j);
            }







            int last_item(void){
                int j= N; // N empieza desde 1, siguiendo el modelo de contains, ahi hace el assert, o sea, ahi calcula la posicion exacta en minibloque
                bool lastone = 0;

                contains(j);

                T block = block_[j];
                while (block!=0 && !lastone){
                    if ((block & contains(j))==1){
                    lastone = 1;
                    }
                    block <<=1;

                    j++;
                }


            }
};

    private:

         void to_string(string& s) const 
         {
            for(int j = 0; j < sz_; j++){

                const int sz = min(N_BITS_WORD, N - j * N_BITS_WORD);

                T block = block_[j];        

                for(int i = 0; i < sz; i++)
                {
                    const char c = '0' + (block & T(0x1));
                    s.insert(s.begin(),c); 
                    block >>= 1;
                }
            }
         }
};

ostream& operator<<(ostream& os, const bitset_t<long int, 80>& bs)
{
    bs.write(os);
    return os;
}

me dan los siguientes errores el compilador:

In file included from p6main_bs.cpp:13:0:
p6bitset_t.hpp: In member function ‘std::ostream& bitset_t<T, N>::write(std::ostream&) const’:
p6bitset_t.hpp:123:15: error: there are no arguments to ‘to_string’ that depend on a template parameter, so a declaration of ‘to_string’ must be available [-fpermissive]
    to_string(s);
               ^
p6bitset_t.hpp:123:15: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
p6bitset_t.hpp: At global scope:
p6bitset_t.hpp:225:2: error: expected unqualified-id before ‘private’
  private:

Gracias

1 respuesta 1

0
ostream& write(ostream& os) const 
{
    string s;
    to_string(s);
    os << s;

    return os;
}

El error no es del todo obvio pero ahí está. Estas usando un método que el compilador aun desconoce. Puedes resolver el problema usando this o poniendo una declaración de la función to_string en algún punto anterior a la implementación de la función que te indico arriba.

Solución mediante this:

ostream& write(ostream& os) const 
{
    string s;
    this->to_string(s);
    os << s;

    return os;
}

Por cierto, la librería de cadenas de C++ es string. cstring y string.h son dos versiones casi idénticas de la implementación heredada de C y orientada al trabajo con arreglos de tipo char.

Otro error se encuentra aquí:

   int last_item(void){
// ^^^ Dices que la funcion devuelve un entero...
       int j= N;
       bool lastone = 0;

       contains(j);

       T block = block_[j];
       while (block!=0 && !lastone){
           if ((block & contains(j))==1){
               lastone = 1;
           }
           block <<=1;

           j++;
       }
   } // ... ¿Y el return?

Por cierto, en C++ no hace falta poner void en las funciones que no admiten argumentos... es redundante y la norma general es evitar el uso de void en estos casos:

int last_item()

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.