CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
Path: blob/master/Common/Data/Collections/TinySet.h
Views: 1401
#pragma once12#include <vector>34#include "Common/Log.h"56// Insert-only small-set implementation. Performs no allocation unless MaxFastSize is exceeded.7// Can also be used as a small vector, then use push_back (or push_in_place) instead of insert.8// Duplicates are thus allowed if you use that, but not if you exclusively use insert.9template <class T, int MaxFastSize>10struct TinySet {11~TinySet() { delete slowLookup_; }12inline void insert(const T &t) {13// Fast linear scan.14for (int i = 0; i < fastCount_; i++) {15if (fastLookup_[i] == t)16return; // We already have it.17}18// Fast insertion19if (fastCount_ < MaxFastSize) {20fastLookup_[fastCount_++] = t;21return;22}23// Fall back to slow path.24insertSlow(t);25}26inline void push_back(const T &t) {27if (fastCount_ < MaxFastSize) {28fastLookup_[fastCount_++] = t;29return;30}31if (!slowLookup_) {32slowLookup_ = new std::vector<T>();33}34slowLookup_->push_back(t);35}36inline T &push_uninitialized() {37if (fastCount_ < MaxFastSize) {38return fastLookup_[fastCount_++];39}40if (!slowLookup_) {41slowLookup_ = new std::vector<T>();42}4344// The slow lookup is also slow at adding.45T t;46slowLookup_->push_back(t);47return *slowLookup_->back();48}49void append(const TinySet<T, MaxFastSize> &other) {50size_t otherSize = other.size();51if (size() + otherSize <= MaxFastSize) {52// Fast case53for (size_t i = 0; i < otherSize; i++) {54fastLookup_[fastCount_ + i] = other.fastLookup_[i];55}56fastCount_ += other.fastCount_;57} else {58for (size_t i = 0; i < otherSize; i++) {59push_back(other[i]);60}61}62}63bool contains(T t) const {64for (int i = 0; i < fastCount_; i++) {65if (fastLookup_[i] == t)66return true;67}68if (slowLookup_) {69for (auto x : *slowLookup_) {70if (x == t)71return true;72}73}74return false;75}76bool contains(const TinySet<T, MaxFastSize> &otherSet) {77// Awkward, kind of ruins the fun.78for (int i = 0; i < fastCount_; i++) {79if (otherSet.contains(fastLookup_[i]))80return true;81}82if (slowLookup_) {83for (auto x : *slowLookup_) {84if (otherSet.contains(x))85return true;86}87}88return false;89}90void clear() {91// TODO: Keep slowLookup_ around? That would be more similar to real vector behavior.92delete slowLookup_;93slowLookup_ = nullptr;94fastCount_ = 0;95}96bool empty() const {97return fastCount_ == 0;98}99size_t size() const {100if (!slowLookup_) {101return fastCount_;102} else {103return slowLookup_->size() + MaxFastSize;104}105}106T &operator[] (size_t index) {107if (index < MaxFastSize) {108return fastLookup_[index];109} else {110return (*slowLookup_)[index - MaxFastSize];111}112}113const T &operator[] (size_t index) const {114if (index < MaxFastSize) {115return fastLookup_[index];116} else {117return (*slowLookup_)[index - MaxFastSize];118}119}120const T &back() const {121return (*this)[size() - 1];122}123124private:125void insertSlow(T t) {126if (!slowLookup_) {127slowLookup_ = new std::vector<T>();128} else {129for (size_t i = 0; i < slowLookup_->size(); i++) {130if ((*slowLookup_)[i] == t)131return;132}133}134slowLookup_->push_back(t);135}136int fastCount_ = 0; // first in the struct just so it's more visible in the VS debugger.137T fastLookup_[MaxFastSize];138std::vector<T> *slowLookup_ = nullptr;139};140141template <class T, int MaxSize>142struct FixedVec {143~FixedVec() {}144// WARNING: Can fail if you exceed MaxSize!145inline bool push_back(const T &t) {146if (count_ < MaxSize) {147data_[count_++] = t;148return true;149} else {150return false;151}152}153154// WARNING: Can fail if you exceed MaxSize!155inline T &push_uninitialized() {156if (count_ < MaxSize) {157return &data_[count_++];158}159_dbg_assert_(false);160return *data_[MaxSize - 1]; // BAD161}162163// Invalid if empty().164void pop_back() { count_--; }165166// Unlike TinySet, we can trivially support begin/end as pointers.167T *begin() { return data_; }168T *end() { return data_ + count_; }169const T *begin() const { return data_; }170const T *end() const { return data_ + count_; }171172size_t capacity() const { return MaxSize; }173void clear() { count_ = 0; }174bool empty() const { return count_ == 0; }175size_t size() const { return count_; }176177bool contains(T t) const {178for (int i = 0; i < count_; i++) {179if (data_[i] == t)180return true;181}182return false;183}184185// Out of bounds (past size() - 1) is undefined behavior.186T &operator[] (const size_t index) { return data_[index]; }187const T &operator[] (const size_t index) const { return data_[index]; }188189// These two are invalid if empty().190const T &back() const { return (*this)[size() - 1]; }191const T &front() const { return (*this)[0]; }192193bool operator == (const FixedVec<T, MaxSize> &other) const {194if (count_ != other.count_)195return false;196for (int i = 0; i < count_; i++) {197if (!(data_[i] == other.data_[i])) {198return false;199}200}201return true;202}203204private:205int count_ = 0; // first in the struct just so it's more visible in the VS debugger.206T data_[MaxSize];207};208209210