TVector.h

Go to the documentation of this file.

#pragma once
 
#include <stdlib.h>
#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& operator=(TVector&& o) noexcept;
 
    TVector& operator+=(const TVector& o);
 
 
 
    inline TVector<Item>& Add(Item a) { operator[](count) = a; return *this; }
 
    TVector<Item>& Insert(Item a, int index = 0);
 
    TVector<Item>& Insert(TVector<Item>& v, 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;
 
 
    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; }
 
    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);
 
    TVector<Item>& operator-=(const Item& 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)
{
    Item* aux = new Item[size];
    if (v != nullptr) {
        for (int k = 0; k < count; ++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;
}