dsa

http://www.apache.org/licenses/LICENSE-2.0

Quick membership checks for large sets
Spam filtering
Distributed cache lookup
Network packet deduplication

:::note False positive rate is configurable at construction ::: :::warning Not suitable for security-critical membership tests ::: :::warning Cannot remove elements (use CountingBloomFilter instead) :::

Example:

[BloomFilter](./resq-dsa-BloomFilter.md#bloomfilter) filter(10000, 0.01); // 10k elements, 1% false positive rate
filter.add("drone_001");
filter.add("drone_002");

if (filter.has("drone_001")) {
    // Likely in set (may be false positive)
}

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Network traffic analysis
Heavy hitter detection
Approximate frequency queries

:::note Guarantees estimate >= true count (upper bound) ::: :::note Actual error is at most eps * N with probability delta ::: :::warning Not suitable for exact counting :::

Example:

// Create sketch with 1% error bound, 99% confidence
[CountMinSketch](./resq-dsa-CountMinSketch.md#countminsketch) sketch(0.01, 0.01);

for (const auto& req : requests) {
    sketch.increment(req.ip_address);
}

// Estimate frequency (may be overestimate)
uint64_t freq = sketch.estimate("192.168.1.1");

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Graph data structures and pathfinding algorithms Provides generic graph representation with common pathfinding algorithms. Supports both unweighted and weighted edges with Dijkstra and A* search. :::note Uses adjacency list representation for memory efficiency ::: :::note Id type must be hashable and equality-comparable :::

Example:

[Graph<std::string>](./resq-dsa-Graph.md#graph) g;
g.[add_edge](./resq-dsa-Graph.md#add_edge)("A", "B", 1.0);
g.[add_edge](./resq-dsa-Graph.md#add_edge)("B", "C", 2.0);

auto result = g.[dijkstra](./resq-dsa-Graph.md#dijkstra)("A", "C");
if (result) {
    std::cout << "Path: ";
    for (const auto& node : result->path) {
        std::cout << node << " ";
    }
}

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Fixed-size priority queue with bounded capacity A bounded min-heap that maintains at most N elements, automatically evicting the element with the highest distance value when full. Useful for K-nearest-neighbors, top-K selection, and beam search. :::note Uses max-heap internally (highest distance at root), but exposes the element with minimum distance value as the “best” ::: :::warning The comparison function must be consistent - if f(a) < f(b) and f(b) < f(c), then f(a) < f(c) :::

Example:

// Keep top 5 closest drones to target
[BoundedHeap<Drone>](./resq-dsa-BoundedHeap.md#boundedheap) closest(5, [](const Drone& d) {
    return distance(d.position, target);
});

for (const auto& drone : all_drones) {
    closest.[insert](./resq-dsa-BoundedHeap.md#insert)(drone);
}

// Get sorted results
auto results = closest.to_sorted();

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Prefix-based autocomplete
String storage and lookup
Pattern matching

:::note Uses case-sensitive ASCII character comparison ::: :::warning Not suitable for Unicode strings without modification :::

Example:

[Trie](./resq-dsa-Trie.md#trie) trie;
trie.[insert](./resq-dsa-Trie.md#insert-1)("drone");
trie.[insert](./resq-dsa-Trie.md#insert-1)("drone_001");
trie.[insert](./resq-dsa-Trie.md#insert-1)("drone_002");

auto suggestions = trie.[starts_with](./resq-dsa-Trie.md#starts_with-1)("drone_");
// suggestions = {"drone_001", "drone_002"}

Classes

Name	Description
`BloomFilter`	Bloom filter for probabilistic set membership.
`BoundedHeap`	Bounded heap for top-K element selection.
`CountMinSketch`	Count-Min sketch for frequency estimation.
`Graph`	Generic directed weighted graph.
`Trie`	Trie (prefix tree) for efficient string prefix operations.

Functions

Return	Name	Description
`std::vector< std::size_t >`	`rabin_karp`	Rabin-Karp string matching algorithm.

rabin_karp

inline

inline std::vector< std::size_t > rabin_karp(const std::string & text, const std::string & pat)

Rabin-Karp string matching algorithm. Uses rolling hash for O(n + m) average-case string matching. Useful for finding all occurrences of a pattern in text.

Parameters

text Text to search in
pat Pattern to search for

Returns

Vector of starting positions where pattern matches :::note Uses base 31 with modulo 1,000,000,007 ::: :::note False matches are possible due to hash collisions :::

Example:

auto matches = [rabin_karp](#rabin_karp)("ABABDABACDABABCABAB", "ABABCABAB");
// matches = {10}

Overview

Languages

Generated Package References

Resq dsa

dsa

Example:

Example:

Example:

Example:

Example:

Classes

Functions

rabin_karp

Parameters

Returns

Example:

​dsa

​Example:

​Example:

​Example:

​Example:

​Example:

​Classes

​Functions

​rabin_karp

​Parameters

​Returns

​Example:

dsa

Example:

Example:

Example:

Example:

Example:

Classes

Functions

rabin_karp

Parameters

Returns

Example: