array.h

← comparison · array.h
1#pragma once23#include "common.h"4#include "hash.h"5#include "printers.h"6#include "random.h"7#include "sequence_ops.h"89#include <algorithm>10#include <initializer_list>11#include <numeric>12#include <set>13#include <string>14#include <type_traits>15#include <unordered_set>16#include <unordered_map>17#include <utility>18#include <vector>1920namespace jngen {2122template<typename T>23class GenericArray : public ReprProxy<GenericArray<T>>, public std::vector<T> {24public:25    typedef std::vector<T> Base;2627    using Base::Base;2829    GenericArray() {}30    GenericArray(const GenericArray<T>&) = default;31    GenericArray& operator=(const GenericArray<T>&) = default;32    GenericArray(GenericArray<T>&&) = default;33    GenericArray& operator=(GenericArray<T>&&) = default;3435    ~GenericArray() {}3637    /* implicit */ GenericArray(const Base& base) :38            Base(base)39    {  }4041    using Base::at;42    using Base::size;43    using Base::resize;44    using Base::begin;45    using Base::end;46    using Base::insert;47    using Base::clear;48    using Base::erase;4950    void extend(size_t requiredSize) {51        checkLargeParameter(requiredSize);52        if (requiredSize > size()) {53            resize(requiredSize);54        }55    }5657    template<typename F, typename ...Args>58    static GenericArray<T> randomf(size_t size, F func, const Args& ... args);59    template<typename F, typename ...Args>60    static GenericArray<T> randomfUnique(61            size_t size, F func, const Args& ... args);62    template<typename F, typename ...Args>63    static GenericArray<T> randomfAll(F func, const Args& ... args);6465    template<typename ...Args>66    static GenericArray<T> random(size_t size, const Args& ... args);67    template<typename ...Args>68    static GenericArray<T> randomUnique(size_t size, const Args& ... args);69    template<typename ...Args>70    static GenericArray<T> randomAll(const Args& ... args);7172    static GenericArray<T> id(size_t size, T start = T{});7374    GenericArray<T>& shuffle();75    GenericArray<T> shuffled() const;7677    GenericArray<T>& reverse();78    GenericArray<T> reversed() const;7980    GenericArray<T>& sort();81    GenericArray<T> sorted() const;8283    template<typename Comp>84    GenericArray<T>& sort(Comp&& comp);85    template<typename Comp>86    GenericArray<T> sorted(Comp&& comp) const;8788    GenericArray<T>& unique();89    GenericArray<T> uniqued() const;9091    GenericArray<T> inverse() const;9293    template<typename Integer>94    GenericArray<T> subseq(const std::vector<Integer>& indices) const;9596    template<typename Integer>97    GenericArray<T> subseq(98        const std::initializer_list<Integer>& indices) const;99100    T choice() const;101    GenericArray<T> choice(size_t count) const;102    GenericArray<T> choiceWithRepetition(size_t count) const;103104    GenericArray<T>& operator+=(const GenericArray<T>& other);105    GenericArray<T> operator+(const GenericArray<T>& other) const;106107    GenericArray<T>& operator*=(int k);108    GenericArray<T> operator*(int k) const;109110    operator std::string() const;111};112113template<typename T>114template<typename ...Args>115GenericArray<T> GenericArray<T>::random(size_t size, const Args& ... args) {116    checkLargeParameter(size);117    GenericArray<T> result(size);118    for (T& x: result) {119        x = rnd.tnext<T>(args...);120    }121    return result;122}123124template<typename T>125template<typename F, typename ...Args>126GenericArray<T> GenericArray<T>::randomf(127        size_t size,128        F func,129        const Args& ... args)130{131    checkLargeParameter(size);132    GenericArray<T> result(size);133    for (T& x: result) {134        x = func(args...);135    }136    return result;137}138139namespace detail {140141template<typename T, typename Enable = std::size_t>142struct DictContainer {143    typedef std::set<T> type;144};145146template<typename T>147struct DictContainer<T, typename std::hash<T>::result_type>148{149    typedef std::unordered_set<T> type;150};151152} // namespace detail153154template<typename T>155template<typename F, typename ...Args>156GenericArray<T> GenericArray<T>::randomfUnique(157        size_t size,158        F func,159        const Args& ... args)160{161    typename detail::DictContainer<T>::type set;162    checkLargeParameter(size);163    GenericArray<T> result;164    result.reserve(size);165166    size_t retries = (size + 10) * log(size + 10) * 2;167168    while (result.size() != size) {169        T t = func(args...);170        if (!set.count(t)) {171            set.insert(t);172            result.push_back(t);173        }174175        if (--retries == 0) {176            ensure(false, "There are not enough unique elements");177        }178179    }180181    return result;182}183184template<typename T>185template<typename ...Args>186GenericArray<T> GenericArray<T>::randomUnique(187        size_t size, const Args& ... args)188{189    return GenericArray<T>::randomfUnique(190        size,191        [](Args... args) { return rnd.tnext<T>(args...); },192        args...);193}194195template<typename T>196template<typename F, typename ...Args>197GenericArray<T> GenericArray<T>::randomfAll(198        F func,199        const Args& ... args)200{201    typename detail::DictContainer<T>::type set;202    GenericArray<T> result;203204    size_t timeAfterLastHit = 0;205206    while (true) {207        T t = func(args...);208        if (!set.count(t)) {209            set.insert(t);210            result.push_back(t);211            timeAfterLastHit = 0;212        }213214        ++timeAfterLastHit;215216        // Probability of finding not all elements is about e^{-20} ~= 1e-9217        if (timeAfterLastHit > (result.size() + 10) * 20) {218            return result;219        }220    }221}222223template<typename T>224template<typename ...Args>225GenericArray<T> GenericArray<T>::randomAll(const Args& ... args)226{227    return GenericArray<T>::randomfAll(228        [](Args... args) { return rnd.tnext<T>(args...); },229        args...);230}231232template<typename T>233GenericArray<T> GenericArray<T>::id(size_t size, T start) {234    constexpr bool enable = std::is_integral<T>::value;235    static_assert(enable, "Cannot call Array<T>::id with non-integral T");236    checkLargeParameter(size);237238    if (enable) {239        GenericArray<T> result(size);240        std::iota(result.begin(), result.end(), start);241        return result;242    } else {243        return {};244    }245}246247template<typename T>248GenericArray<T>& GenericArray<T>::shuffle() {249    jngen::shuffle(begin(), end());250    return *this;251}252253template<typename T>254GenericArray<T> GenericArray<T>::shuffled() const {255    auto res = *this;256    res.shuffle();257    return res;258}259260template<typename T>261GenericArray<T>& GenericArray<T>::reverse() {262    std::reverse(begin(), end());263    return *this;264}265266template<typename T>267GenericArray<T> GenericArray<T>::reversed() const {268    auto res = *this;269    res.reverse();270    return res;271}272273template<typename T>274GenericArray<T>& GenericArray<T>::sort() {275    std::sort(begin(), end());276    return *this;277}278279template<typename T>280GenericArray<T> GenericArray<T>::sorted() const {281    auto res = *this;282    res.sort();283    return res;284}285286template<typename T>287template<typename Comp>288GenericArray<T>& GenericArray<T>::sort(Comp&& comp) {289    std::sort(begin(), end(), comp);290    return *this;291}292293template<typename T>294template<typename Comp>295GenericArray<T> GenericArray<T>::sorted(Comp&& comp) const {296    auto res = *this;297    res.sort(comp);298    return res;299}300301template<typename T>302GenericArray<T>& GenericArray<T>::unique() {303    erase(std::unique(begin(), end()), end());304    return *this;305}306307template<typename T>308GenericArray<T> GenericArray<T>::uniqued() const {309    auto res = *this;310    res.unique();311    return res;312}313314template<typename T>315GenericArray<T> GenericArray<T>::inverse() const {316    static_assert(317        std::is_integral<T>::value,318        "Can only take inverse permutation of integral array");319    int n = size();320321    if (n == 0) {322        return *this;323    }324325    // sanity check326    ensure(*max_element(begin(), end()) == n-1 &&327        *min_element(begin(), end()) == 0,328        "Trying to take inverse of the array which is not a permutation");329330    const static T NONE = static_cast<T>(-1);331    GenericArray<T> result(n, NONE);332    for (int i = 0; i < n; ++i) {333        ensure(result[at(i)] == NONE,334            "Trying to take inverse of the array which is not a permutation");335        result[at(i)] = i;336    }337338    return result;339}340341template<typename T>342template<typename Integer>343GenericArray<T> GenericArray<T>::subseq(344        const std::vector<Integer>& indices) const345{346    GenericArray<T> result;347    result.reserve(indices.size());348    for (Integer idx: indices) {349        result.push_back(at(idx));350    }351    return result;352}353354// TODO(ifsmirnov): ever need to make it faster?355template<typename T>356template<typename Integer>357GenericArray<T> GenericArray<T>::subseq(358        const std::initializer_list<Integer>& indices) const359{360    return subseq(std::vector<T>(indices));361}362363template<typename T>364T GenericArray<T>::choice() const {365    return jngen::choice(begin(), end());366}367368template<typename T>369GenericArray<T> GenericArray<T>::choice(size_t count) const {370    ensure(371        count <= size(),372        "Use Array::choiceWithRepetition to select more than size() elements");373374    size_t n = size();375376    std::unordered_map<size_t, size_t> used;377    std::vector<size_t> res;378    for (size_t i = 0; i < count; ++i) {379        size_t oldValue = used.count(n-i-1) ? used[n-i-1] : n-i-1;380        size_t index = rnd.tnext<size_t>(n-i);381        res.push_back(used.count(index) ? used[index] : index);382        used[index] = oldValue;383    }384385    return subseq(res);386}387388template<typename T>389GenericArray<T> GenericArray<T>::choiceWithRepetition(size_t count) const {390    checkLargeParameter(count);391    GenericArray<T> res(count);392    for (T& t: res) {393        t = choice();394    }395    return res;396}397398template<typename T>399GenericArray<T>& GenericArray<T>::operator+=(const GenericArray<T>& other) {400    if (&other == this) {401        return *this *= 2;402    }403    insert(end(), other.begin(), other.end());404    return *this;405}406407template<typename T>408GenericArray<T> GenericArray<T>::operator+(const GenericArray<T>& other) const {409    GenericArray<T> copy(*this);410    return copy += other;411}412413template<typename T>414GenericArray<T>& GenericArray<T>::operator*=(int k) {415    if (k == 0) {416        clear();417        return *this;418    }419420    this->reserve(size() * k);421422    std::copy_n(begin(), size() * (k - 1), std::back_inserter(*this));423424    return *this;425}426427template<typename T>428GenericArray<T> GenericArray<T>::operator*(int k) const {429    GenericArray<T> copy(*this);430    return copy *= k;431}432433template<typename T>434GenericArray<T>::operator std::string() const {435    static_assert(std::is_same<T, char>::value, "Must not cast"436        " TArray<T> to std::string with 'T' != 'char'");437    return std::string(begin(), end());438}439440// JNGEN_EXTERN template class GenericArray<int>;441442template<typename T>443using TArray = GenericArray<T>;444445using Array = GenericArray<int>;446using Array2d = GenericArray<jngen::GenericArray<int>>;447using Array64 = GenericArray<long long>;448using Arrayf = GenericArray<double>;449using Arrayp = GenericArray<std::pair<int, int>>;450451template<typename T>452jngen::GenericArray<T> makeArray(const std::vector<T>& values) {453    return jngen::GenericArray<T>(values);454}455456template<typename T>457jngen::GenericArray<T> makeArray(const std::initializer_list<T>& values) {458    return jngen::GenericArray<T>(values);459}460461template<typename T, typename U>462TArray<std::pair<T, U>> zip(const TArray<T>& lhs, const TArray<U>& rhs) {463    ensure(464        lhs.size() == rhs.size(),465        "In zip(a, b), a and b must have the same size");466    TArray<std::pair<T, U>> result;467    for (size_t i = 0; i < lhs.size(); ++i) {468        result.emplace_back(lhs[i], rhs[i]);469    }470    return result;471}472473template<typename T, typename U>474TArray<T> arrayCast(const TArray<U>& array) {475    return TArray<T>(array.begin(), array.end());476}477478template<typename T>479struct Hash<TArray<T>> {480    uint64_t operator()(const TArray<T>& elements) const {481        return Hash<std::vector<T>>{}(elements);482    }483};484485} // namespace jngen486487JNGEN_DEFINE_STD_HASH_TEMPLATE(T, jngen::TArray<T>);488489using jngen::makeArray;490using jngen::zip;491using jngen::arrayCast;492493using jngen::TArray;494495using jngen::Array;496using jngen::Array2d;497using jngen::Array64;498using jngen::Arrayf;499using jngen::Arrayp;