# LGenerics

From Lazarus 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 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.

# 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)