I'm struggling a bit with an exercise, develop the method int first_item (void) should return the index of the first element of the set. The int last_item (void) method must return the index of the last element in the set.
I am blocked there, I did it based on the contains function, which places me in the exact position in the small block, I would like to know if I have the algorithm of the last_item, this is the code:
#pragma once
#include <cstring>//libreria 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;
}
I get the following errors from the compiler:
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:
Thanks