Aleph::Range_Mode_Policy< T > Struct Template Reference

Policy: range mode (most frequent element). More...

#include <tpl_mo_algorithm.H>

Collaboration diagram for Aleph::Range_Mode_Policy< T >:

Public Types
using	answer_type = std::pair< size_t, T >

Public Member Functions
void	init (const Array< T > &, size_t)
void	add (const Array< T > &data, size_t idx)
void	remove (const Array< T > &data, size_t idx)
answer_type	answer () const

Public Attributes
MapOLhash< T, size_t >	freq
MapOLhash< size_t, size_t >	cnt_of_cnt
size_t	max_freq = 0
T	mode_val = T()

Detailed Description

template<typename T>
struct Aleph::Range_Mode_Policy< T >

Policy: range mode (most frequent element).

Tracks frequencies and uses a "count of counts" trick for O(1) mode maintenance. Returns {frequency, value} of the mode. Ties are broken arbitrarily.

Note

When max_freq decreases after a removal, this implementation linearly scans current distinct values to pick any valid mode representative. Aggregate Mo complexity is preserved, but a single remove may cost O(number of distinct values).

Template Parameters

T	Element type (must be hashable).

Definition at line 498 of file tpl_mo_algorithm.H.

Member Typedef Documentation

answer_type

template<typename T >

using Aleph::Range_Mode_Policy< T >::answer_type = std::pair<size_t, T>

Definition at line 500 of file tpl_mo_algorithm.H.

Member Function Documentation

add()

template<typename T >

void Aleph::Range_Mode_Policy< T >::add ( const Array< T > &  data, size_t  idx  )

inline

Definition at line 517 of file tpl_mo_algorithm.H.

References Aleph::Range_Mode_Policy< T >::cnt_of_cnt, Aleph::divide_and_conquer_partition_dp(), Aleph::Range_Mode_Policy< T >::freq, Aleph::Range_Mode_Policy< T >::max_freq, and Aleph::Range_Mode_Policy< T >::mode_val.

answer()

template<typename T >

answer_type Aleph::Range_Mode_Policy< T >::answer ( ) const

inline

Definition at line 570 of file tpl_mo_algorithm.H.

References Aleph::Range_Mode_Policy< T >::max_freq, and Aleph::Range_Mode_Policy< T >::mode_val.

init()

template<typename T >

void Aleph::Range_Mode_Policy< T >::init ( const Array< T > &  , size_t    )

inline

Definition at line 507 of file tpl_mo_algorithm.H.

References Aleph::Range_Mode_Policy< T >::cnt_of_cnt, Aleph::divide_and_conquer_partition_dp(), Aleph::Range_Mode_Policy< T >::freq, Aleph::Range_Mode_Policy< T >::max_freq, and Aleph::Range_Mode_Policy< T >::mode_val.

remove()

template<typename T >

void Aleph::Range_Mode_Policy< T >::remove ( const Array< T > &  data, size_t  idx  )

inline

Definition at line 532 of file tpl_mo_algorithm.H.

References Aleph::and, Aleph::Range_Mode_Policy< T >::cnt_of_cnt, Aleph::divide_and_conquer_partition_dp(), Aleph::Range_Mode_Policy< T >::freq, Aleph::Range_Mode_Policy< T >::max_freq, and Aleph::Range_Mode_Policy< T >::mode_val.

Member Data Documentation

cnt_of_cnt

template<typename T >

MapOLhash<size_t, size_t> Aleph::Range_Mode_Policy< T >::cnt_of_cnt

Definition at line 503 of file tpl_mo_algorithm.H.

Referenced by Aleph::Range_Mode_Policy< T >::add(), Aleph::Range_Mode_Policy< T >::init(), and Aleph::Range_Mode_Policy< T >::remove().

freq

template<typename T >

MapOLhash<T, size_t> Aleph::Range_Mode_Policy< T >::freq

Definition at line 502 of file tpl_mo_algorithm.H.

Referenced by Aleph::Range_Mode_Policy< T >::add(), Aleph::Range_Mode_Policy< T >::init(), and Aleph::Range_Mode_Policy< T >::remove().

max_freq

template<typename T >

size_t Aleph::Range_Mode_Policy< T >::max_freq = 0

Definition at line 504 of file tpl_mo_algorithm.H.

Referenced by Aleph::Range_Mode_Policy< T >::add(), Aleph::Range_Mode_Policy< T >::answer(), Aleph::Range_Mode_Policy< T >::init(), and Aleph::Range_Mode_Policy< T >::remove().

mode_val

template<typename T >

T Aleph::Range_Mode_Policy< T >::mode_val = T()

Definition at line 505 of file tpl_mo_algorithm.H.

Referenced by Aleph::Range_Mode_Policy< T >::add(), Aleph::Range_Mode_Policy< T >::answer(), Aleph::Range_Mode_Policy< T >::init(), and Aleph::Range_Mode_Policy< T >::remove().

---

The documentation for this struct was generated from the following file:

• tpl_mo_algorithm.H