data_structures Namespace Reference

for IO operations More...

Namespaces
namespace	treap
	Functions for the Treap algorithm implementation.

Classes
class	Bitset
	Simple bitset implementation for bloom filter. More...
class	BloomFilter
	Bloom filter template class. More...
struct	Node
class	SegmentTree
	class representation of the segment tree More...
class	SkipList
class	Stack
	Class representation of a stack. More...
class	trie
	Trie implementation for small-case English alphabets a-z More...

Functions
static std::size_t	hashDJB2 (std::string const &s)
	Function djb2 to get hash for the given string.
static std::size_t	hashStr (std::string const &s)
	Hash function, to get hash for the given string.
std::size_t	hashInt_1 (int x)
	Hash function for test
std::size_t	hashInt_2 (int x)
	Hash function for test

Variables
constexpr int	MAX_LEVEL = 2
	Maximum level of skip list.
constexpr float	PROBABILITY = 0.5
	Current probability for "coin toss".

Detailed Description

for IO operations

for std::vector

Stack Data Structure Using the Queue Data Structure.

For std::out_of_range.

Data-structure algorithms.

For assert.

for managing dynamic storage

Algorithms with data structures.

for assert

Data Structures algorithms.

for assert for list of hash functions for bloom filter constructor for initializer_list for bloom filter constructor for testing on strings for std::vector

Data Structures algorithms

for std::array for io operations

Algorithms with data structures

for assert for I/O operations

Data Structures algorithms

For IO operations For std::vector For std::min and std::max

for std::array for IO operations

Data Structures algorithms

For std::assert For std::cout For std::unique_ptr

data_structures

Using 2 Queues inside the Stack class, we can easily implement Stack data structure with heavy computation in push function.

References used: StudyTonight

Author

tushar2407 for assert for IO operations for queue data structure

Data structures algorithms

For array For IO operations

Data Structures

for std::array for assert for std::ofstream for std::cout for std::unique_ptr for std::queue for std::to_string

for assert for IO operations for std::shared_ptr for std::stack for std::unordered_map

Data structures algorithms

Function Documentation

hashDJB2()

static std::size_t data_structures::hashDJB2 ( std::string const & s )

static

Function djb2 to get hash for the given string.

Parameters

s	string to get hash from

Returns

hash for a string

Definition at line 166 of file bloom_filter.cpp.

                                              {
    std::size_t hash = 5381;
    for (char c : s) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

hashInt_1()

std::size_t data_structures::hashInt_1

(

int

x

)

Hash function for test

Parameters

x	to get hash from

Returns

hash for the x parameter

Definition at line 199 of file bloom_filter.cpp.

                           {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

hashInt_2()

std::size_t data_structures::hashInt_2

(

int

x

)

Hash function for test

Parameters

x	to get hash from

Returns

hash for the x parameter

Definition at line 213 of file bloom_filter.cpp.

                           {
    auto y = static_cast<std::size_t>(x);
    y = (y ^ (y >> 30)) * static_cast<std::size_t>(0xbf58476d1ce4e5b9);
    y = (y ^ (y >> 27)) * static_cast<std::size_t>(0x94d049bb133111eb);
    y = y ^ (y >> 31);
    return y;
}

hashStr()

static std::size_t data_structures::hashStr ( std::string const & s )

static

Hash function, to get hash for the given string.

Parameters

s	string to get hash from

Returns

hash for the given string

Definition at line 182 of file bloom_filter.cpp.

                                             {
    std::size_t hash = 37;
    std::size_t primeNum1 = 54059;
    std::size_t primeNum2 = 76963;
    for (char c : s) {
        hash = (hash * primeNum1) ^ (c * primeNum2);
    }
    return hash;
}

Variable Documentation

MAX_LEVEL

int data_structures::MAX_LEVEL = 2

constexpr

Maximum level of skip list.

Definition at line 27 of file skip_list.cpp.

PROBABILITY

float data_structures::PROBABILITY = 0.5

constexpr

Current probability for "coin toss".

Definition at line 28 of file skip_list.cpp.