Skip to content
View wilderfield's full-sized avatar

Block or report wilderfield

Block user

Prevent this user from interacting with your repositories and sending you notifications. Learn more about blocking users.

You must be logged in to block users.

Please don't include any personal information such as legal names or email addresses. Maximum 100 characters, markdown supported. This note will be visible to only you.
Report abuse

Contact GitHub support about this user’s behavior. Learn more about reporting abuse.

Report abuse
wilderfield/README.md

\mainpage

wilderfield

The wilderfield library is a collection of header only libraries I've developed over time for various purposes.

wilderfield::PriorityMap

The PriorityMap class is designed to manage a set of elements, each with a priority,
allowing for efficient retrieval, updating, and tracking of elements based on their priority.

It is designed to provide constant time access to the element with the highest priority,
as well as constant time priority increment and decrement.

Setting priority for a given element directly is O(n).

The underlying implementation is a doubly linked list backed by a hashmap.

The source code for this project is available on GitHub: wilderfield/wilderfield

usage

Here is a basic example of how to use the PriorityMap class:

#include "wilderfield/PriorityMap.hpp"
#include <iostream>

int main() {

  // Define a PriorityMap instance
  wilderfield::PriorityMap<int, int> pmap;

  // Increment priority of key 7
  ++pmap[7];

  // Retrieve and check the top element
  auto [key, value] = pmap.Top();
  std::cout << "Top element key: " << key << " with priority: " << value << std::endl;

  return 0;
}

example application

Below is an example application illustrating topological sort with Khan's algorithm and a priority map:

#include "wilderfield/PriorityMap.hpp"
#include <vector>
#include <cassert>

std::vector<int> TopSort(std::vector<std::vector<int>>& graph) {
 
   std::vector<int> result;
 
   // Construct priority map with lower values as highest priority
   wilderfield::PriorityMap<int, int, std::less<int>> pmap;
 
   // Initialize pmap to have all nodes with indegree 0
   for (int u = 0; u < graph.size(); u++) {
     pmap[u] = 0;
   }
 
   // Calculate indegrees for each node
   for (int u = 0; u < graph.size(); u++) {
     for (auto v : graph[u]) {
         ++pmap[v];
     }
   }
 
   // Iterate over nodes by smallest indegree
   while (!pmap.Empty()) {
     auto [u, min_val] = pmap.Top(); pmap.Pop();
     assert(min_val == 0); // If not the graph has a cycle
     result.push_back(u);
     for (auto v : graph[u]) { // Decrease indegrees after removing node u
       --pmap[v];
     }
   }
 
   return result;
}

build, test, benchmark, install

Typical CMake build, tune commands to your platform/generator

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake —-build build
build/tests/priority_map_test -s
build/benchmark/run_benchmarking
cmake --install build

documentation

For more information and advanced usage, refer to the respective class and method documentation.

The documentation for this project is available on GitHub: [wilderfield/wilderfield documentation/(https://wilderfield.github.io/wilderfield)

Pinned Loading

  1. data-structures-algorithms data-structures-algorithms Public

    Learning, and implementing computer science fundamentals in C, CPP, and Python

    C++

  2. webcam-client webcam-client Public

    Javascript magic to capture webcam frames from your PC, and send to the cloud

    JavaScript 1 1

  3. Xilinx/ml-suite Xilinx/ml-suite Public archive

    Getting Started with Xilinx ML Suite

    Jupyter Notebook 335 152

  4. CVPR2019-DEVLAB CVPR2019-DEVLAB Public

    3 1