OpenASIP  2.0
Public Types | Public Member Functions | Static Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
BitTrie< DataType, ValueType > Class Template Reference

#include <BitTrie.hh>

Collaboration diagram for BitTrie< DataType, ValueType >:
Collaboration graph

Public Types

using WidthType = unsigned
 The type for width of bit vector. More...
 
using BitVector = std::tuple< ValueType, WidthType >
 The bit vector type used to store patterns to tries. Binary value is queried by value() method. Width value is queried by width() method. More...
 
using Frequency = unsigned int
 The type for frequencies of the patterns. More...
 

Public Member Functions

 BitTrie ()
 
 BitTrie (bool bitReadLeftToRight)
 
virtual ~BitTrie ()
 
unsigned frequency (const BitVector &prefixBits) const
 
bool check (const BitVector &exactbits) const
 
bool insert (BitVector bits)
 
bool insert (BitVector bits, const DataType &data)
 
bool erase (BitVector bits)
 
void clear ()
 
unsigned size () const
 
BitVector uniqueUnusedPrefix () const
 
DataType & at (BitVector bits)
 
BitVector longestCompletePattern (const BitVector &bits) const
 
void dump (std::ostream &out) const
 

Static Public Member Functions

static WidthType & width (BitVector &bitVector)
 
static const WidthType & width (const BitVector &bitVector)
 
static ValueType & value (BitVector &bitVector)
 
static const ValueType & value (const BitVector &bitVector)
 

Private Member Functions

 BitTrie (bool bitReadLeftToRight, BitTrie &parent)
 
bool nextBit (const BitVector &bitVector) const
 
BitVector stripBit (BitVector bitVector) const
 
BitTrie * findNode (const BitVector &bits)
 
const BitTrie * findNode (const BitVector &bits) const
 

Static Private Member Functions

static BitVector uniqueUnusedPrefixImpl (const BitTrie &bitTrie)
 
static BitVector uniquePrefixImpl (const BitTrie &bitTrie)
 
static bool nodeTerminatesPattern (const BitTrie &node)
 
static BitVector patternAtNode (const BitTrie &node)
 
static bool nodeBitValue (const BitTrie &node)
 
static bool isRootNode (const BitTrie &node)
 
static unsigned depth (const BitTrie &node)
 

Private Attributes

bool bitReadLeftToRight_ = false
 The configuration how bits are read and stored into the trie. If true, the rightmost (LSB) bit is placed in the leaf node. If false, the leftmost (MSB) bit is placed in the leaf node. More...
 
BitTrie * node_ [2] = {nullptr, nullptr}
 The bits are encoded as indexes where 0: zero node, 1: one node. If node at index is not nullptr, a bit has been stored in the trie. More...
 
BitTrie * parent_ = nullptr
 Parent of the (sub)trie. If the pointer is null, the node is root of the trie. More...
 
Frequency frequency_ = 0
 The frequency. The current occurrence of the bit pattern so far. More...
 
DataType * data_ = nullptr
 The data at this node. More...
 

Detailed Description

template<class DataType, class ValueType = long long unsigned int>
class BitTrie< DataType, ValueType >

Definition at line 59 of file BitTrie.hh.

Member Typedef Documentation

◆ BitVector

template<class DataType , class ValueType = long long unsigned int>
using BitTrie< DataType, ValueType >::BitVector = std::tuple<ValueType, WidthType>

The bit vector type used to store patterns to tries. Binary value is queried by value() method. Width value is queried by width() method.

Definition at line 70 of file BitTrie.hh.

◆ Frequency

template<class DataType , class ValueType = long long unsigned int>
using BitTrie< DataType, ValueType >::Frequency = unsigned int

The type for frequencies of the patterns.

Definition at line 72 of file BitTrie.hh.

◆ WidthType

template<class DataType , class ValueType = long long unsigned int>
using BitTrie< DataType, ValueType >::WidthType = unsigned

The type for width of bit vector.

Definition at line 66 of file BitTrie.hh.

Constructor & Destructor Documentation

◆ BitTrie() [1/3]

template<class DataType , class ValueType = long long unsigned int>
BitTrie< DataType, ValueType >::BitTrie ( )

◆ BitTrie() [2/3]

template<class DataType , class ValueType = long long unsigned int>
BitTrie< DataType, ValueType >::BitTrie ( bool  bitReadLeftToRight)

◆ ~BitTrie()

template<class DataType , class ValueType = long long unsigned int>
virtual BitTrie< DataType, ValueType >::~BitTrie ( )
virtual

◆ BitTrie() [3/3]

template<class DataType , class ValueType = long long unsigned int>
BitTrie< DataType, ValueType >::BitTrie ( bool  bitReadLeftToRight,
BitTrie< DataType, ValueType > &  parent 
)
private

Member Function Documentation

◆ at()

template<class DataType , class ValueType = long long unsigned int>
DataType& BitTrie< DataType, ValueType >::at ( BitVector  bits)

◆ check()

template<class DataType , class ValueType = long long unsigned int>
bool BitTrie< DataType, ValueType >::check ( const BitVector &  exactbits) const

◆ clear()

template<class DataType , class ValueType = long long unsigned int>
void BitTrie< DataType, ValueType >::clear ( )

◆ depth()

template<class DataType , class ValueType = long long unsigned int>
static unsigned BitTrie< DataType, ValueType >::depth ( const BitTrie< DataType, ValueType > &  node)
staticprivate

◆ dump()

template<class DataType , class ValueType = long long unsigned int>
void BitTrie< DataType, ValueType >::dump ( std::ostream &  out) const

◆ erase()

template<class DataType , class ValueType = long long unsigned int>
bool BitTrie< DataType, ValueType >::erase ( BitVector  bits)

◆ findNode() [1/2]

template<class DataType , class ValueType = long long unsigned int>
BitTrie* BitTrie< DataType, ValueType >::findNode ( const BitVector &  bits)
private

◆ findNode() [2/2]

template<class DataType , class ValueType = long long unsigned int>
const BitTrie* BitTrie< DataType, ValueType >::findNode ( const BitVector &  bits) const
private

◆ frequency()

template<class DataType , class ValueType = long long unsigned int>
unsigned BitTrie< DataType, ValueType >::frequency ( const BitVector &  prefixBits) const

◆ insert() [1/2]

template<class DataType , class ValueType = long long unsigned int>
bool BitTrie< DataType, ValueType >::insert ( BitVector  bits)

◆ insert() [2/2]

template<class DataType , class ValueType = long long unsigned int>
bool BitTrie< DataType, ValueType >::insert ( BitVector  bits,
const DataType &  data 
)

◆ isRootNode()

template<class DataType , class ValueType = long long unsigned int>
static bool BitTrie< DataType, ValueType >::isRootNode ( const BitTrie< DataType, ValueType > &  node)
staticprivate

◆ longestCompletePattern()

template<class DataType , class ValueType = long long unsigned int>
BitVector BitTrie< DataType, ValueType >::longestCompletePattern ( const BitVector &  bits) const

◆ nextBit()

template<class DataType , class ValueType = long long unsigned int>
bool BitTrie< DataType, ValueType >::nextBit ( const BitVector &  bitVector) const
private

◆ nodeBitValue()

template<class DataType , class ValueType = long long unsigned int>
static bool BitTrie< DataType, ValueType >::nodeBitValue ( const BitTrie< DataType, ValueType > &  node)
staticprivate

◆ nodeTerminatesPattern()

template<class DataType , class ValueType = long long unsigned int>
static bool BitTrie< DataType, ValueType >::nodeTerminatesPattern ( const BitTrie< DataType, ValueType > &  node)
staticprivate

◆ patternAtNode()

template<class DataType , class ValueType = long long unsigned int>
static BitVector BitTrie< DataType, ValueType >::patternAtNode ( const BitTrie< DataType, ValueType > &  node)
staticprivate

◆ size()

template<class DataType , class ValueType = long long unsigned int>
unsigned BitTrie< DataType, ValueType >::size ( ) const

◆ stripBit()

template<class DataType , class ValueType = long long unsigned int>
BitVector BitTrie< DataType, ValueType >::stripBit ( BitVector  bitVector) const
private

◆ uniquePrefixImpl()

template<class DataType , class ValueType = long long unsigned int>
static BitVector BitTrie< DataType, ValueType >::uniquePrefixImpl ( const BitTrie< DataType, ValueType > &  bitTrie)
staticprivate

◆ uniqueUnusedPrefix()

template<class DataType , class ValueType = long long unsigned int>
BitVector BitTrie< DataType, ValueType >::uniqueUnusedPrefix ( ) const

◆ uniqueUnusedPrefixImpl()

template<class DataType , class ValueType = long long unsigned int>
static BitVector BitTrie< DataType, ValueType >::uniqueUnusedPrefixImpl ( const BitTrie< DataType, ValueType > &  bitTrie)
staticprivate

◆ value() [1/2]

template<class DataType , class ValueType = long long unsigned int>
static ValueType& BitTrie< DataType, ValueType >::value ( BitVector &  bitVector)
static

◆ value() [2/2]

template<class DataType , class ValueType = long long unsigned int>
static const ValueType& BitTrie< DataType, ValueType >::value ( const BitVector &  bitVector)
static

◆ width() [1/2]

template<class DataType , class ValueType = long long unsigned int>
static WidthType& BitTrie< DataType, ValueType >::width ( BitVector &  bitVector)
static

◆ width() [2/2]

template<class DataType , class ValueType = long long unsigned int>
static const WidthType& BitTrie< DataType, ValueType >::width ( const BitVector &  bitVector)
static

Member Data Documentation

◆ bitReadLeftToRight_

template<class DataType , class ValueType = long long unsigned int>
bool BitTrie< DataType, ValueType >::bitReadLeftToRight_ = false
private

The configuration how bits are read and stored into the trie. If true, the rightmost (LSB) bit is placed in the leaf node. If false, the leftmost (MSB) bit is placed in the leaf node.

Definition at line 110 of file BitTrie.hh.

◆ data_

template<class DataType , class ValueType = long long unsigned int>
DataType* BitTrie< DataType, ValueType >::data_ = nullptr
private

The data at this node.

Definition at line 120 of file BitTrie.hh.

◆ frequency_

template<class DataType , class ValueType = long long unsigned int>
Frequency BitTrie< DataType, ValueType >::frequency_ = 0
private

The frequency. The current occurrence of the bit pattern so far.

Definition at line 118 of file BitTrie.hh.

◆ node_

template<class DataType , class ValueType = long long unsigned int>
BitTrie* BitTrie< DataType, ValueType >::node_[2] = {nullptr, nullptr}
private

The bits are encoded as indexes where 0: zero node, 1: one node. If node at index is not nullptr, a bit has been stored in the trie.

Definition at line 113 of file BitTrie.hh.

◆ parent_

template<class DataType , class ValueType = long long unsigned int>
BitTrie* BitTrie< DataType, ValueType >::parent_ = nullptr
private

Parent of the (sub)trie. If the pointer is null, the node is root of the trie.

Definition at line 116 of file BitTrie.hh.

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.17