TVector.h

Go to the documentation of this file.

#pragma once
 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <initializer_list>
#include <cstdarg>
#include <cstdint>
#include <locale>
#include "TRand.h"
 
 // TVector
 
template <class Item>
class TVector
{
private:
    TVector<int>* idx = nullptr;    
    Item* v = nullptr;              
    int sz = 0;                     
    int count = 0;                  
    void Size(int size);
 
    void QuickSort(int start, int end);
 
    void Insertion(int start, int end);
 
    void Exch(int i, int j) { Item a = v[i]; v[i] = v[j]; v[j] = a; }
 
    void QuickSortIdx(int start, int end);
 
    void ExchIdx(int i, int j) { int a = (*idx)[i]; (*idx)[i] = (*idx)[j]; (*idx)[j] = a; }
 
    static inline int Min(int a, int b) noexcept { return (a < b) ? a : b; }
 
    static inline int Max(int a, int b) noexcept { return (a > b) ? a : b; }
 
public:
    static Item erro;  
 
    TVector(int size = 0);
 
    TVector(int size, Item const* init);
 
    virtual ~TVector() noexcept;
 
 
    TVector(const TVector& o);
 
    TVector& operator=(const TVector& o);
 
    TVector(TVector&& o) noexcept;
 
    TVector(std::initializer_list<Item> init) {
        Count(static_cast<int>(init.size())); // ajusta capacidade 
        int i = 0;
        for (const auto& val : init)
            v[i++] = val;
    }
 
 
    TVector(const char* str) {}
 
    TVector& operator=(TVector&& o) noexcept;
 
 
    TVector& operator+=(const TVector& o);
 
    TVector& operator+=(std::initializer_list<Item> init) {
        int oldCount = Count();
        Count(oldCount + static_cast<int>(init.size()));
        int i = 0;
        for (const auto& val : init)
            v[oldCount + i++] = val;
        return *this;
    }
 
    TVector<Item>& operator+=(const char* str) = delete; // desabilitado para tipos genéricos; implementado para TVector<int>
 
 
 
    inline TVector<Item>& Add(Item a) { operator[](count) = a; return *this; }
 
    TVector<Item>& Insert(TVector<Item>& v, int index = 0);
 
    TVector<Item>& Insert(Item a, int index = 0);
 
    inline TVector<Item>& Push(Item a) { return Add(a); }
 
    inline Item& Pop() { return (count > 0 ? v[--count] : TVector<Item>::erro); }
 
    Item& operator[](int i);
 
    const Item& operator[](int i) const;
 
    Item* Data() { return v; }
    const Item* Data() const { return v; }
 
    inline Item& First() { return (count > 0 ? v[0] : TVector<Item>::erro); }
 
    inline Item& Last() { return (count > 0 ? v[count - 1] : TVector<Item>::erro); }
 
    int Count() const { return count; }
 
    virtual bool Empty() const { return (count == 0); }
 
    TVector<Item>& Count(int value)
    {
        if (value > sz)
            Size(value);
        count = value;
        return *this;
    }
 
    Item& Random() { return (count > 0 ? operator[](TRand::rand() % count) : TVector<Item>::erro); }
 
 
    TVector<Item>& BeASet();
 
    TVector<Item>& Union(const TVector<Item>& v);
 
    TVector<Item>& Intersection(const TVector<Item>& v);
 
    TVector<Item>& Difference(const TVector<Item>& v);
 
    bool Equal(const TVector<Item>& v) const;
 
    bool Contained(const TVector<Item>& v) const;
 
 
    TVector<Item>& Delete(int i);
 
    TVector<Item>& Remove(Item const& i);
 
    int Find(Item& i, bool binary = false, int left = 0, int right = -1);
 
    TVector<Item>& Replace(Item const& iold, Item const& inew);
 
    TVector<Item>& Sort(TVector<int>* idxvect = nullptr);
 
    void Sort(int start, int end = -1);
 
    TVector<Item>& RandomOrder();
 
    TVector<Item>& Invert();
 
    TVector<Item>& Reset(Item const& i);
 
    int Distance(TVector<Item>& v, int type = 0);
 
    Item* begin()       noexcept { return v; }
    Item* end()         noexcept { return v + count; }
    const Item* begin() const noexcept { return v; }
    const Item* end()   const noexcept { return v + count; }
 
 
    TVector<Item>& operator+=(const Item& x) { return Add(x); }
 
    TVector<Item>& operator-=(const Item& x) { return Remove(x); }
 
    friend TVector<Item> operator+(TVector<Item> a, const TVector<Item>& b) { a += b; return a; }
 
    friend bool operator==(const TVector<Item>& a, const TVector<Item>& b) { return a.Equal(b); }
 
    friend bool operator!=(const TVector<Item>& a, const TVector<Item>& b) { return !a.Equal(b); }
};
 
//----------------------------------------------------------------------------
// instanciação da variável com o conteúdo de erro
//----------------------------------------------------------------------------
 
template <class Item>
Item TVector<Item>::erro;
 
 
 
 
//----------------------------------------------------------------------------
// Redimensionamento interno
//----------------------------------------------------------------------------
 
template <class Item>
void TVector<Item>::Size(int size)
{
    if (size <= 0) {
        delete[] v;
        v = nullptr;
        sz = 0;
        return;
    }
    Item* aux = new Item[size];
    if (v != nullptr) {
        int limite = (count < size ? count : size);
        for (int k = limite - 1; k >= 0; --k)
            aux[k] = v[k];
        delete[] v;
    }
    v = aux;
    sz = size;
}
 
 
//----------------------------------------------------------------------------
// Construtor com inicialização
//----------------------------------------------------------------------------
 
 
template <class Item>
TVector<Item>::TVector(int size)
    : idx(nullptr), v(nullptr), sz(0), count(0)
{
    if (size > 0)
        Size(size);
}
 
 
template <class Item>
TVector<Item>::TVector(int size, Item const* init)
{
    v = nullptr;
    sz = 0;
    count = 0;
    if (size > 0) {
        Size(size);
        for (int k = 0; k < size; ++k)
            operator[](k) = init[k];
    }
}
 
template <class Item>
TVector<Item>::~TVector() noexcept
{
    delete[] v;
}
 
 
template <class Item>
TVector<Item>::TVector(const TVector<Item>& o)
{
    *this = o;
}
 
template <class Item>
TVector<Item>& TVector<Item>::operator=(const TVector<Item>& o)
{
    if (this != &o) {
        // garante capacidade e atualiza count
        Count(o.count);
        // copia elementos
        for (int i = 0; i < o.count; ++i) {
            v[i] = o.v[i];
        }
    }
    return *this;
}
 
template <class Item>
TVector<Item>::TVector(TVector<Item>&& o) noexcept
    : v(o.v), sz(o.sz), count(o.count)
{
    o.v = nullptr;
    o.sz = 0;
    o.count = 0;
}
 
template <class Item>
TVector<Item>& TVector<Item>::operator=(TVector<Item>&& o) noexcept
{
    if (this != &o) {
        delete[] v;
        v = o.v;
        sz = o.sz;
        count = o.count;
        o.v = nullptr;
        o.sz = 0;
        o.count = 0;
    }
    return *this;
}
 
template <class Item>
TVector<Item>& TVector<Item>::operator+=(const TVector<Item>& o)
{
    int oldCount = count;
    // ajusta tamanho lógico e realoca se necessário
    Count(oldCount + o.count);
    // copia elementos
    for (int k = 0; k < o.count; ++k) {
        v[oldCount + k] = o.v[k];
    }
    return *this;
}
 
 
 
//----------------------------------------------------------------------------
// Implementação de operator[] para auto-expansão
//----------------------------------------------------------------------------
 
template <class Item>
Item& TVector<Item>::operator[](int i)
{
    if (i >= sz)
        Size(2 * (i + 1));
 
    if (i >= count)
        count = i + 1;
 
    return v[i];
}
 
 
template <class Item>
const Item& TVector<Item>::operator[](int i) const
{
    if (i < 0 || i >= count)
        return TVector<Item>::erro;
 
    return v[i];
}
 
//----------------------------------------------------------------------------
// Pesquisa de elementos
//----------------------------------------------------------------------------
 
template <class Item>
int TVector<Item>::Find(Item& i, bool binary, int left, int right)
{
    if (binary) {
        if (right < 0 || right > count - 1) right = count - 1;
        if (left  < 0 || left  > right)    left = 0;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (v[mid] == i) return mid;
            if (v[mid] < i) left = mid + 1;
            else              right = mid - 1;
        }
    }
    else {
        for (int k = 0; k < count; ++k)
            if (v[k] == i)
                return k;
    }
    return -1;
}
 
//----------------------------------------------------------------------------
// Ordenação
//----------------------------------------------------------------------------
 
template <class Item>
TVector<Item>& TVector<Item>::Sort(TVector<int>* idxvect)
{
    if (idxvect == nullptr) {
        QuickSort(0, count - 1);
        Insertion(0, count - 1);
    }
    else {
        idx = idxvect;
        idx->Count(count);
        for (int k = 0; k < count; ++k)
            (*idx)[k] = k;
        QuickSortIdx(0, count - 1);
    }
    return *this;
}
 
 
template <class Item>
void TVector<Item>::Sort(int start, int end)
{
    if (end > count - 1 || end < 0) end = count - 1;
    if (start < 0)                  start = 0;
    if (start < end) {
        QuickSort(start, end);
        Insertion(start, end);
    }
}
 
 
template <class Item>
void TVector<Item>::QuickSort(int start, int end)
{
    if (end - start > 32) {
        // pivôs median-of-three
        Exch((start + end) >> 1, end - 1);
        if (v[end - 1] < v[start]) Exch(end - 1, start);
        if (v[end] < v[start]) Exch(end, start);
        if (v[end] < v[end - 1]) Exch(end, end - 1);
 
        start++; end--;
 
        // partição
        int i = start - 1, j = end;
        Item pivot = v[end];
        for (;;) {
            while (v[++i] < pivot);
            while (pivot < v[--j] && j > start);
            if (i >= j) break;
            Exch(i, j);
        }
        Exch(i, end);
 
        QuickSort(start - 1, i - 1);
        QuickSort(i + 1, end + 1);
    }
}
 
 
template <class Item>
void TVector<Item>::Insertion(int start, int end)
{
    for (int i = end; i > start; --i)
        if (v[i - 1] > v[i])
            Exch(i - 1, i);
 
    for (int i = start + 2; i <= end; ++i) {
        Item tmp = v[i];
        int j = i;
        while (tmp < v[j - 1]) {
            v[j] = v[j - 1];
            --j;
        }
        v[j] = tmp;
    }
}
 
 
 
template <class Item>
void TVector<Item>::QuickSortIdx(int start, int end)
{
    if (end - start < 3) {
        // pequenos casos
        if (end - start == 1) {
            if (v[(*idx)[end]] < v[(*idx)[start]])
                ExchIdx(end, start);
        }
        else if (end - start == 2) {
            if (v[(*idx)[end - 1]] < v[(*idx)[start]])
                ExchIdx(end - 1, start);
            if (v[(*idx)[end]] < v[(*idx)[start]])
                ExchIdx(end, start);
            if (v[(*idx)[end]] < v[(*idx)[end - 1]])
                ExchIdx(end, end - 1);
        }
    }
    else {
        // pivôs median-of-three em idx
        ExchIdx((start + end) >> 1, end - 1);
        if (v[(*idx)[end - 1]] < v[(*idx)[start]])
            ExchIdx(end - 1, start);
        if (v[(*idx)[end]] < v[(*idx)[start]])
            ExchIdx(end, start);
        if (v[(*idx)[end]] < v[(*idx)[end - 1]])
            ExchIdx(end, end - 1);
 
        start++; end--;
 
        // partição em idx
        int i = start - 1, j = end;
        Item pivot = v[(*idx)[end]];
        for (;;) {
            while (v[(*idx)[++i]] < pivot);
            while (pivot < v[(*idx)[--j]] && j > start);
            if (i >= j) break;
            ExchIdx(i, j);
        }
        ExchIdx(i, end);
 
        if (i > start)         QuickSortIdx(start - 1, i - 1);
        if (i < end)           QuickSortIdx(i + 1, end + 1);
    }
}
 
 
//----------------------------------------------------------------------------
// Baralhar
//----------------------------------------------------------------------------
 
template <class Item>
TVector<Item>& TVector<Item>::RandomOrder()
{
    for (int k = count - 1; k > 0; --k)
        Exch(k, TRand::rand() % (k + 1));
    return *this;
}
 
template <class Item>
TVector<Item>& TVector<Item>::Remove(const Item& i)
{
    int k = 0;
    for (int w = 0; w < count; ++w) {
        if (v[w] != i) {
            v[k++] = v[w];
        }
    }
    count = k;
    return *this;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::Reset(const Item& i)
{
    for (int j = 0; j < count; ++j) {
        v[j] = i;
    }
    return *this;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::Replace(const Item& iold, const Item& inew)
{
    for (int k = 0; k < count; ++k) {
        if (v[k] == iold) {
            v[k] = inew;
        }
    }
    return *this;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::Delete(int i)
{
    for (int k = i; k < count - 1; ++k) {
        v[k] = v[k + 1];
    }
    --count;
    return *this;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::BeASet()
{
    if (count > 0) {
        Sort();
        int k = 0, w = 1;
        while (w < count) {
            if (v[k] != v[w]) {
                v[++k] = v[w];
            }
            ++w;
        }
        count = k + 1;
    }
    return *this;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::Union(const TVector<Item>& other)
{
    int k = 0, w = 0, s = Count();
    while (k < other.Count()) {
        while (w < s && operator[](w) < other[k]) {
            ++w;
        }
        if (w >= s || operator[](w) > other[k]) {
            Add(other[k++]);
        }
        else {
            ++k;
        }
    }
    Sort();
    return *this;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::Intersection(const TVector<Item>& other)
{
    int k = 0, w = 0, z = 0;
    while (k < other.Count() && w < Count()) {
        if (operator[](w) < other[k]) {
            ++w;
        }
        else if (operator[](w) == other[k]) {
            v[z++] = v[w++];
            ++k;
        }
        else {
            ++k;
        }
    }
    Count(z);
    return *this;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::Difference(const TVector<Item>& other)
{
    int k = 0, w = 0, z = 0;
    while (k < other.Count() && w < Count()) {
        if (v[w] < other[k]) {
            v[z++] = v[w++];
        }
        else if (v[w] == other[k]) {
            ++w; ++k;
        }
        else {
            ++k;
        }
    }
    while (w < Count()) {
        v[z++] = v[w++];
    }
    Count(z);
    return *this;
}
 
template <class Item>
bool TVector<Item>::Equal(const TVector<Item>& other) const
{
    if (count != other.Count()) return false;
    for (int k = 0; k < count; ++k) {
        if (v[k] != other[k]) return false;
    }
    return true;
}
 
 
template <class Item>
bool TVector<Item>::Contained(const TVector<Item>& other) const
{
    if (count > other.Count()) return false;
    int k2 = 0;
    for (int k = 0; k < count; ++k) {
        while (k2 < other.Count() && v[k2] < v[k]) {
            ++k2;
        }
        if (k2 >= other.Count() || other[k2] != v[k]) {
            return false;
        }
    }
    return true;
}
 
 
template <class Item>
TVector<Item>& TVector<Item>::Insert(TVector<Item>& src, int index)
{
    if (index < 0) index = Count();
    int w = src.Count();
    if (w > 0) {
        int oldCount = Count();
        Count(oldCount + w);
        if (index > oldCount) index = oldCount;
        for (int k = oldCount - 1; k >= index; --k) {
            v[k + w] = v[k];
        }
        for (int k = 0; k < w; ++k) {
            v[index + k] = src[k];
        }
    }
    return *this;
}
 
template <class Item>
TVector<Item>& TVector<Item>::Insert(Item a, int index)
{
    if (index < 0) index = Count();
    int oldCount = Count();
    Count(oldCount + 1);
    if (index > oldCount) index = oldCount;
    for (int k = oldCount - 1; k >= index; --k) {
        v[k + 1] = v[k];
    }
    v[index] = a;
    return *this;
}
 
template <class Item>
TVector<Item>& TVector<Item>::Invert()
{
    for (int k = 0; k < count / 2; ++k) {
        Exch(k, count - 1 - k);
    }
    return *this;
}
 
 
template <class Item>
int TVector<Item>::Distance(TVector<Item>& other, int type)
{
    int result = 0;
    int n1 = Count(), n2 = other.Count();
 
    if (type == 0) {
        result = abs(n1 - n2);
        int m = Min(n1, n2);
        for (int i = 0; i < m; ++i) {
            if (v[i] != other[i]) ++result;
        }
    }
    else if (type == 1) {
        int m = Min(n1, n2);
        for (int i = 0; i < m; ++i) {
            result += abs(v[i] - other[i]);
        }
    }
    else if (type == 2) {
        result = Max(n1, n2);
        for (int i = 0; i + 1 < n1; ++i) {
            int j = other.Find(v[i]);
            if (j >= 0 && j + 1 < n2 && v[i + 1] == other[j + 1]) {
                --result;
            }
        }
    }
    else if (type == 3) {
        int rows = n1 + 1, cols = n2 + 1;
        TVector<int> mtx(rows * cols);
        // inicialização da matriz
        for (int i = 0; i < rows; ++i) mtx[i] = i;
        for (int j = 1; j < cols; ++j) mtx[j * rows] = j;
        // cálculo da distância de edição
        for (int i = 1; i < rows; ++i) {
            for (int j = 1; j < cols; ++j) {
                int cost = (v[i - 1] == other[j - 1] ? 0 : 1);
                int val = mtx[(i - 1) + rows * (j - 1)] + cost;
                val = Min(val, mtx[(i - 1) + rows * j] + 1);
                val = Min(val, mtx[i + rows * (j - 1)] + 1);
                mtx[i + rows * j] = val;
            }
        }
        result = mtx[n1 + rows * n2];
    }
 
    return result;
}
 
 
class TString : public TVector<char> {
private:
    // Função auxiliar para fopen compatível com MSVC
    // usado em readLines e writeLines
    static FILE* fopen_compat(const char* filename, const char* mode) {
#ifdef _MSC_VER
        FILE* f = nullptr;
        fopen_s(&f, filename, mode);
        return f;
#else
        return std::fopen(filename, mode);
#endif
    }
 
public:
    using TVector<char>::TVector; // herdar construtores
 
    TString() {
        Count(1);
        Last() = 0;
    }
 
    // construtor a partir de const char*
    TString(const char* s) {
        if (!s) {
            Count(1);
            Last() = 0;
            return;
        }
        int n = (int)strlen(s);
        Count(n + 1);
        memcpy(Data(), s, n + 1);
        Last() = 0;
    }
 
    // permite converter int direto: TString(valorInt)
    TString(int v) {
        printf("%d", v);
    }
 
    // conversão implícita para const char*
    operator const char* () const noexcept {
        return Data();
    }
 
    // devolve const char* de forma curta:
    // em vez de printf("%s",(const char*)nome); basta printf("%s",*nome);
    const char* operator*() const noexcept {
        return Data();
    }
 
    // printf, adiciona o texto formatado à string atual
    TString& printf(const char* fmt, ...) {
        // calcular tamanho necessário
        va_list args;
        va_start(args, fmt);
        int needed = vsnprintf(nullptr, 0, fmt, args);
        va_end(args);
 
        if (needed < 0)
            return *this;
 
        // remover o '\0' anterior
        Pop();
        int old = Count();
 
        // expandir para conter o novo texto + '\0'
        Count(Count() + needed + 1);
 
        // escrever no fim
        va_start(args, fmt);
        vsnprintf(Data() + old, needed + 1, fmt, args);
        va_end(args);
 
        return *this;
    }
 
    // concatenação com outra TString
    TString& operator+=(const TString& other) {
        Pop(); // remover '\0'
        TVector<char>::operator+=(other);
        Last() = 0;
        return *this;
    }
 
    bool Empty() const { return (Count() <= 1); }
 
    // hash da string usando o algoritmo djb2
    unsigned int Hash() const
    {
        unsigned int hash = 5381;
        for (unsigned char c : *this)
            hash = ((hash << 5) + hash) + c; // hash * 33 + c
        return hash;
    }
 
    // tokenização: divide a string em partes usando os delimitadores fornecidos
    TVector<TString> tok(const char* delim = " \t\n\r") const {
        TVector<TString> out;
        const char* s = Data();
        int n = Count();
        int i = 0;
        while (i < n) {
            // saltar delimitadores
            while (i < n && strchr(delim, s[i]))
                i++;
 
            if (i >= n || s[i] == 0)
                break;
 
            int start = i;
 
            // avançar até próximo delimitador
            while (i < n && s[i] != 0 && !strchr(delim, s[i]))
                i++;
 
            // extrair token
            int len = i - start;
            TString tok;
            tok.Count(len + 1);
            memcpy(tok.Data(), s + start, len);
            tok[len] = 0;
 
            out += tok;
        }
 
        return out;
    }
 
    // métodos de conveniência (leitura/gravação em ficheiros de texto)
    TVector<TString> readLines() {
        TVector<TString> lines;
        TString line;
        int c;
        FILE* f = fopen_compat(Data(), "r");
        if (!f) return lines;
        while ((c = fgetc(f)) != EOF)
            if (c == '\n') { // tratar apenas \n como quebra de linha
                lines += line;
                line = TString();
            }
            else if (c != '\r') { // ignorar sempre \r
                line.Last() = c;
                line.Add(0);
            }
        lines += line;
        fclose(f);
        return lines;
    }
    TString& writeLines(const TVector<TString>& lines, bool append = false) {
        FILE* f = fopen_compat(Data(), append ? "ab" : "wb");
        if (!f) return *this;
        for (const auto& line : lines)
            fprintf(f, "%s\n", *line);
        fclose(f);
        return *this;
    }
 
 
};
 
class TBits : public TVector<uint64_t> {
public:
    // Construtores herdados
    TBits(int words = 0) : TVector<uint64_t>(words) { Count(words); Reset(0ULL); }
 
    inline unsigned int Hash() const;
 
    // --- Operações binárias entre TBits ---
    inline TBits operator&(const TBits& other) const;
    inline TBits operator|(const TBits& other) const;
    inline TBits operator^(const TBits& other) const;
    inline TBits operator~() const;
 
    TBits& operator&=(const TBits& other) { return *this = *this & other; }
    TBits& operator|=(const TBits& other) { return *this = *this | other; }
    TBits& operator^=(const TBits& other) { return *this = *this ^ other; }
 
    // permite usar if (a & b) em que a e b são TBits, para verificar se há algum bit em comum
    explicit operator bool() const {
        for (int i = 0; i < Count(); i++)
            if (Data()[i] != 0ULL)
                return true;
        return false;
    }
 
    // --- Bits individuais ---
    inline bool GetBit(int index) const;
    inline void SetBit(int index, bool value);
 
    // --- Inserir / extrair inteiros pequenos ---
    inline void SetBits(uint64_t value, int bitIndex, int bitCount);
    inline uint64_t GetBits(int bitIndex, int bitCount) const;
};
 
unsigned int TBits::Hash() const {
    // utilizando FNV-1 hash (http://www.isthe.com/chongo/tech/comp/fnv/)
    uint32_t h = 2166136261;
    for (uint64_t word : *this) {
        // processar cada octeto 
        // quando o valor fica 0, já não interessa
        // já que existindo dados, são distintos de 0
        for (int i = 0; i < 8 && word; i++) {
            unsigned char octeto = word & 255;
            word >>= 8;
            h *= 16777619;
            h ^= octeto;
        }
    }
    return h;
}
 
TBits TBits::operator&(const TBits& other) const {
    int n = (Count() < other.Count() ? Count() : other.Count());
    TBits r(n);
    for (int i = 0; i < n; i++)
        r[i] = Data()[i] & other[i];
    return r;
}
 
TBits TBits::operator|(const TBits& other) const {
    int n = (Count() > other.Count() ? Count() : other.Count());
    TBits r(n);
    for (int i = 0; i < n; i++) {
        uint64_t a = (i < Count()) ? Data()[i] : 0;
        uint64_t b = (i < other.Count()) ? other[i] : 0;
        r[i] = a | b;
    }
    return r;
}
 
TBits TBits::operator^(const TBits& other) const {
    int n = (Count() > other.Count() ? Count() : other.Count());
    TBits r(n);
    for (int i = 0; i < n; i++) {
        uint64_t a = (i < Count()) ? Data()[i] : 0;
        uint64_t b = (i < other.Count()) ? other[i] : 0;
        r[i] = a ^ b;
    }
    return r;
}
 
TBits TBits::operator~() const {
    TBits r(Count());
    for (int i = 0; i < Count(); i++)
        r[i] = ~Data()[i];
    return r;
}
 
bool TBits::GetBit(int index) const {
    int w = index >> 6;
    int o = index & 63;
    if (w >= Count()) return false;
    return (Data()[w] >> o) & 1ULL;
}
 
uint64_t TBits::GetBits(int bitIndex, int bitCount) const {
    int w = bitIndex >> 6;
    int o = bitIndex & 63;
 
    uint64_t v = (w < Count()) ? (Data()[w] >> o) : 0;
 
    if (o + bitCount > 64 && w + 1 < Count())
        v |= Data()[w + 1] << (64 - o);
 
    return v & (bitCount == 64 ? ~0ULL : ((1ULL << bitCount) - 1));
}
 
 
void TBits::SetBit(int index, bool value) {
    int w = index >> 6;
    int o = index & 63;
    if (w >= Count()) {
        int currentWords = Count();
        Count(w + 1);
        while (currentWords < Count()) 
            Data()[currentWords++] = 0ULL;
    }
 
    uint64_t& word = (*this)[w];
    if (value)
        word |= (1ULL << o);
    else
        word &= ~(1ULL << o);
}
 
void TBits::SetBits(uint64_t value, int bitIndex, int bitCount) {
    int w = bitIndex >> 6;
    int o = bitIndex & 63;
 
    if (w + 1 >= Count()) {
        int currentWords = Count();
        Count(w + 2);
        while (currentWords < Count())
            Data()[currentWords++] = 0ULL;
    }
 
    uint64_t mask = (bitCount == 64 ? ~0ULL : ((1ULL << bitCount) - 1)) << o;
    Data()[w] = (Data()[w] & ~mask) | ((value << o) & mask);
 
    if (o + bitCount > 64) {
        int spill = (o + bitCount) - 64;
        uint64_t mask2 = (1ULL << spill) - 1;
        Data()[w + 1] = (Data()[w + 1] & ~mask2) | (value >> (64 - o));
    }
}
 
 
template<>
inline TVector<int>::TVector(const char* str) {
    TString buffer(str);
    char* token = buffer.Data();
    char* pt;
    if (!str || *str == '\0')
        return;
 
    // separar por vírgulas
    if ((pt = strchr(token, ','))) {
        *pt = 0;
        *this = TVector(token);
        do {
            token = pt + 1;
            if ((pt = strchr(token, ',')))
                *pt = 0;
            *this += TVector(token);
        } while (pt);
    }
    else {
        // procurar por : (intervalo)
        if ((pt = strchr(token, ':'))) {
            char* pt2;
            *pt = 0;
            int A = atoi(token);
            int C = 1;
            if ((pt2 = strchr(pt + 1, ':'))) { // A:B:C
                *pt2 = 0;
                if ((C = atoi(pt2 + 1)) <= 0)
                    C = 1;
            } // c.c. A:B
            int B = atoi(pt + 1);
            if (A > B) { // ordem não interessa
                int aux = A;
                A = B;
                B = aux;
            }
            for (int i = A; i <= B; i += C)
                *this += i;
        }
        else // inteiro apenas
            *this += atoi(token);
    }
    BeASet();
}
 
template<>
inline TVector<int>& TVector<int>::operator+=(const char* str) {
    *this += TVector<int>(str);
    return *this;
}
 
// permite fazer for(auto x : _TV("1:10,15:50:3,73")) printf("%d ", x);
inline TVector<int> _TV(const char* str) {
    return TVector<int>(str);
}