Promotable

template<typename RegType, template<typename> class MergeOp, template<typename, typename> class MapType, typename KeyType, std::size_t Size, std::size_t CompactionThreshold, std::size_t PromotionThreshold>
class Promotable

Sparse to Dense data structure for Sketch objects.

Provides a unified interface to the Sparse and Dense containers, allowing for seamless “promotion” of a Sparse representation to a Dense one.

Template Parameters:

  • RegType – The type held by each register.

  • MergeOp – An template merge operator to combine two sketches.

  • MapType – The underlying map class to use for buffered updates to the underlying compacting_map.

  • KeyType – The key type to use for this underlying compacting map.

  • Size – The maximum number of registers. Must equal the embedding dimension of the transform to be used.

Public Types

using register_type = RegType

Alias for the fully-templated Dense container.

using sparse_type = krowkee::sketch::Sparse<register_type, MergeOp, MapType, KeyType, Size, CompactionThreshold>

Alias for the fully-templated Sparse container.

using self_type = Promotable<register_type, MergeOp, MapType, KeyType, Size, CompactionThreshold, PromotionThreshold>

Alias for the fully-templated Promotable container.

Public Functions

inline Promotable()

Initialize the size parameters and create the base container.

inline Promotable(const self_type &rhs)

Copy constructor.

Note

Must explicitly copy contents of rhs’s container, not just copy the pointer.

Parameters:

rhs – container to be copied.

inline self_type &operator=(self_type rhs)

Copy-and-swap assignment operator.

Note

https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

Parameters:

rhs – The other container.

Returns:

sparse_type& this, having been swapped with rhs.

inline constexpr std::size_t size() const

The size of the underlying Sparse or Dense container, depending on the mode.

inline constexpr bool is_compact() const

True unless we are in Sparse mode and uncompacted.

inline constexpr bool is_sparse() const

Return true if in sparse mode.

inline constexpr promotable_mode_type mode() const

Get the current mode.

inline dense_registers_type registers() const

Get a copy of the raw register vector.

The vector will be sparse, with zeros for unset indices, if we are in Sparse mode.

Returns:

std::vector<register_type> Copy of the register vector.

inline dense_registers_type scaled_registers(const double scaling_factor) const

Get a copy of the scaled register vector.

The vector will be sparse, with zeros for unset indices, if we are in Sparse mode.

Parameters:

scaling_factor – the scalar scaling factor.

Returns:

std::vector<register_type> Copy of the register vector.

inline void compactify()

If in Sparse mode, flush the update buffer.

inline void clear()

Remove all state and reset to sparse mode.

inline bool empty() const

Remove all state and reset to sparse mode.

inline constexpr void erase(const std::uint64_t index)

Trigger the underlying container to erase an index.

Parameters:

index – The index to erase.

inline constexpr auto begin()

Mutable begin iterator.

inline constexpr auto begin() const

Const begin iterator.

inline constexpr auto cbegin() const

Const begin iterator.

inline constexpr auto end()

Mutable end iterator.

inline constexpr auto end() const

Const end iterator.

inline constexpr auto cend() const

Const end iterator.

inline register_type &operator[](const std::uint64_t index)

Access reference to the specified element.

Parameters:

index – The index to access.

Returns:

register_type& The accessed register.

inline self_type &operator+=(const self_type &rhs)

Merge other Promotable into this.

Parameters:

rhs – The other promotable. Must have the same parameters.

Returns:

self_type& this after merging rhs.

inline void promote()

Promote sparse container into a dense container.

Promote sparse container into a dense container.

Initializes dense pointer while releasing sparse pointer.

Initializes dense pointer while releasing sparse pointer.

Throws:

  • std::logic_error – if the container is not in sparse mode.

  • std::logic_error – if the sparse container is not compacted.

  • std::logic_error – if the container is not in sparse mode.

  • std::logic_error – if the sparse container is not compacted.

inline void merge_from_sparse(const self_type &rhs)

Incorporate the information in a sparse container into a dense container.

Initializes dense pointer while releasing sparse pointer.

Parameters:

rhs – The sparse container.

Throws:

std::logic_error – if the rhs container is not in sparse mode.

Public Static Functions

static inline constexpr std::string name()

Returns a description of the type of container.

Returns:

std::string “Promotable”

static inline constexpr std::string full_name()

Returns a description of the fully-qualified type of container.

Returns:

std::string “Promotable” plus the full name of the fully-templated compacting_map type.

static inline constexpr std::size_t max_size()

The maximum possible size of the sketch, disregarding mode.

static inline constexpr std::size_t embedding_size()

The size of the embedding. Equal to max_size()

static inline constexpr std::size_t reg_size()

The number of bytes used by each register.

static inline constexpr std::size_t promotion_threshold()

The size at which we switch from Sparse mode to Dense mode.

static inline constexpr std::size_t compaction_threshold()

The size at which the compaction buffer will flush.

Friends

inline friend void swap(self_type &lhs, self_type &rhs)

Swap two Promotable objects.

Parameters:

  • lhs – The left-hand container.

  • rhs – The right-hand containr.

inline friend constexpr bool operator==(const self_type &lhs, const self_type &rhs)

Checks equality between two Promotable containers.

Note

[bwp] do we want to be able to compare sparse to dense containers directly? no for now but will want to revisit.

Parameters:

  • lhs – The left-hand container.

  • rhs – The right-hand container.

Returns:

true The registers agree and promotion thresholds are the same.

Returns:

false At least one register disagrees or the promotion thresholds disagree.

inline friend constexpr bool operator!=(const self_type &lhs, const self_type &rhs)

Checks inequality between two Promotable containers.

Parameters:

  • lhs – The left-hand container.

  • rhs – The right-hand container.

Returns:

true At least one register disagrees or the promotion thresholds disagree.

Returns:

false The registers agree and promotion thresholds are the same.

inline friend constexpr friend self_type operator+ (const self_type &lhs, const self_type &rhs)

Merget two Promotable objects together.

lhs and rhs must have the same parameters.

Parameters:

  • lhs – The left-hand container.

  • rhs – The right-hand container.

Returns:

self_type The merge of the two containers.

inline friend std::ostream &operator<<(std::ostream &os, const self_type &con)

Serialize a Sparse container to human-readable output stream.

Output format is a list of (key, value) pairs, skipping empty registers if in Sparse mode.

Note

Intended for debugging only.

Parameters:

  • os – The output stream.

  • con – The Promotable to print.

Throws:

std::logic_error – if invoked on uncompacted sketch.

Returns:

std::ostream& The new stream state.

template<typename RetType>
inline friend RetType accumulate(const self_type &con, const RetType init)

Accumulate sum of register values.

Template Parameters:

RetType – The value type to return.

Parameters:

  • con – The Promotable to accumulate.

  • init – Initial value of return.

Returns:

RetType The sum over all register values + init.