LGenerics

From Free Pascal wiki

About

Collection of generic algorithms and data structures entirely written in/for FPC and Lazarus. Started as a self-education project, it now seems quite comfortable and fast.

Requires: FPC 3.2+, Lazarus 1.9+.

Author: A.Koverdyaev (avk)

License: Apache License 2.0

Features

Implemented primitives:

  • stack (unit LGStack)
  • queue (unit LGQueue)
  • deque (unit LGDeque)
  • vector (unit LGVector)
  • vector of bits (unit LGVector)
  • priority queue based on binary heap (unit LGPriorityQueue)
  • priority queue with key update and melding based on pairing heap (unit LGPriorityQueue)
  • sorted list (unit LGList)
  • hashed list - array based list with the ability to fast search by key (unit LGList)
  • hashset (unit LGHashSet)
  • fine-grained concurrent hashset (unit LGHashSet)
  • sorted set (unit LGTreeSet)
  • set of arbitrary size (unit LGUtil, TGSet)
  • hash multiset (unit LGHashMultiSet)
  • fine-grained concurrent hashmultiset (unit LGHashMultiSet)
  • sorted multiset (unit LGTreeMultiSet)
  • hashmap (unit LGHashMap)
  • fine-grained concurrent hashmap (unit LGHashMap)
  • sorted map (unit LGTreeMap)
  • hash multimap (unit LGMultiMap)
  • tree multimap (unit LGMultiMap)
  • list miltimap (unit LGMultiMap)
  • bijective map (unit LGBiMap)
  • sparse 2D table (unit LGTable2D)
  • disjoint set (unit LGHashSet)
  • AVL tree (unit LGAvlTree)
  • red-black tree (unit LGRbTree)
  • some treap variants (unit LGTreap)
  • general rooted tree (unit LGRootTree)
  • sparse labeled undirected graph (unit LGSimpleGraph)
  • sparse labeled directed graph (unit LGSimpleDigraph)

Algorithms on arrays and vectors (mostly unit LGArrayHelpers):

  • reverse, right/left cyclic shifts
  • permutations
  • binary search
  • N-th order statistics
  • inversion counting
  • distinct values selection
  • quicksort
  • introsort
  • dual pivot quicksort
  • mergesort
  • timsort (unit LGMiscUtils)
  • counting sort
  • translation of Orson Peters' PDQSort algorithm
  • static segment tree
  • ...

Other:

  • non-cryptogarphic hashes (unit LGHash):
    • Yann Collet's xxHash32, xxHash64
    • Austin Appleby's MurmurHash2, MurmurHash2A, MurmurHash3_x86_32, MurmurHash64A
  • brief and dirty implementation of futures concept (unit LGAsync)
  • brief channel implementation (unit LGAsync)
  • brief implementation of thread pool (unit LGAsync)
  • 128-bit integers (unit LGInt128)

Download

GitHub: https://github.com/avk959/LGenerics