A vector of bunch of constant 1's

[lilzz]

1)BasedBitVector<1> locked;

what's the use of this one? what purpose?

2) BasedVector<int, 1> gate
why two types inside <>? it's a vector of int and constant 1's?

3) std::vector<std::vector<int>> related_tiles;

is that of 2D array of ints?

[AndyD]

1)BasedBitVector<1> locked;

what's the use of this one? what purpose?

Where is BasedBitVector from? How do we know what the template argument means without knowing where the code is from.

2) BasedVector<int, 1> gate
why two types inside <>? it's a vector of int and constant 1's?

Same answer as question one.

3) std::vector<std::vector<int>> related_tiles;

is that of 2D array of ints?

Essentially yes you could consider it that way. It is a vector of vectors that hold an int.

[lilzz]

Code: Select all

#ifndef PNR_BITVECTOR_HH
#define PNR_BITVECTOR_HH

#include <vector>

#include <cstddef>
#include <cstdint>
#include <cassert>

template<size_t B>
class BasedBitVector
{
  int n;
  std::vector<uint64_t> v;
  
public:
  class BitRef
  {
    std::vector<uint64_t> &v;
    size_t i;
    
  public:
    BitRef (std::vector<uint64_t> &v_, size_t i_)
      : v(v_), i(i_)
    {}
    
    BitRef &operator=(bool x)
    {
      size_t w = (i - B) / 64,
        b = (i - B) & 63;
      uint64_t m = ((uint64_t)1 << b);
      assert(w < v.size());
      if (x)
        v[w] |= m;
      else
        v[w] &= ~m;
      return *this;
    }
    
    operator bool() const
    {
      size_t w = (i - B) / 64,
        b = (i - B) & 63;
      uint64_t m = ((uint64_t)1 << b);
      assert(w < v.size());
      return v[w] & m;
    }
  };
  
  BasedBitVector() {}
  BasedBitVector(size_t n_)
    : n(n_), v((n + 63) / 64, 0)
  {
  }
  
  BasedBitVector(size_t n_, uint64_t init)
    : n(n_), v((n + 63) / 64, 0)
  {
    v[0] = init;
  }
  
  void resize(size_t n_)
  {
    n = n_;
    v.resize((n + 63) / 64, 0);
  }
  
  void zero()
  {
    std::fill(v.begin(), v.end(), 0);
  }
  size_t size() const { return n; }
  
  bool operator[](size_t i) const
  {
    assert(i >= B && i < n + B);
    size_t w = (i - B) / 64,
      b = (i - B) & 63;
    uint64_t m = ((uint64_t)1 << b);
    return v[w] & m;
  }
  BitRef operator[](size_t i)
  {
    assert(i >= B && i < n + B);
    return BitRef(v, i);
  }
};

using BitVector = BasedBitVector<0>;
using BitVector1 = BasedBitVector<1>;

#endif

here's the definition of Baedbitvector. i am lost as what this does. what's with 64, 63?

Code: Select all

assert(i >= B && i < n + B);
    size_t w = (i - B) / 64,
      b = (i - B) & 63;
    uint64_t m = ((uint64_t)1 << b);
    return v[w] & m;

what it trying to do?

[ame]

I guess you never bought that book about programming.

What's up with the 64 and 63? Well, one is probably doing a right shift by 6 bits. The other is masking the lower 6 bits (and discarding the higher bits).

As usual, you cannot expect to understand these things without studying, or without looking at their context.

[AndyD]

1)BasedBitVector<1> locked;

what's the use of this one? what purpose?

It appears that BasedVector and BaseBitVector are to allow you to have base 1 vectors (or other bases if you so wish). That is so that locked[1] refers to the first bit in the bit vector rather than locked[0].

2) BasedVector<int, 1> gate
why two types inside <>? it's a vector of int and constant 1's?

So BasedVector allows you to have a vector of a base other than zero. It appear the code only uses base one. So the int is the type in the vector and the value '1' is the base of the vector. So gate[1] refers to the first int in the vector, rather than in a standard vector gate[0].

[AndyD]

Code: Select all

assert(i >= B && i < n + B);
    size_t w = (i - B) / 64,
      b = (i - B) & 63;
    uint64_t m = ((uint64_t)1 << b);
    return v[w] & m;

what it trying to do?

The bit vector is being stored as a vector of 64 bit ints. So if your vector contains less than 64 bits, it is stored as one 64 bit int.

B is the base of the vector (as described above).

Code: Select all

size_t w = (i - B) / 64

w is the index into the member std::vector that holds the 64 bit integers. Divide by 64 as that is the number of bits held in each 64 bit integer. Subtract B from i to get rid of the base being used.

Code: Select all

b = (i - B) & 63

b is the bit number of bit to access in the 64 bit integer of interest. The value 63 is a mask, so that b is in the range [0,63].
It is the remainder from the above division. It could have been written "b = (i - B) % 64"

Code: Select all

uint64_t m = ((uint64_t)1 << b);

m is a mask to access the b'th bit in the 64 bit integer of interest.

Code: Select all

return v[w] & m;

Finally the w'th 64 bit integer from the vector of integers used to implement the bit array is retrieved. Bitwise and is used to isolate the bit of interest from the retrieved 64 bit integer. The bool type is either true or false. A non-zero integer value becomes true, a zero value becomes false. If the bit is a 1, then true is returned. if the bit is a 0, the false is returned.

[lilzz]

@andyD , your explanation is very cool. Thx