LGenerics

From Lazarus wiki
Revision as of 16:09, 10 August 2020 by Alextp (talk | contribs)
Jump to navigationJump to search

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 and higher and Lazarus 1.9.0 and higher.

In order to use it:

  • open and compile package lgenerics/LGenerics.lpk.
  • add LGenerics package to project dependencies.

Author: A.Koverdyaev (avk)

License: Apache License 2.0

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