Difference between revisions of "LGenerics"
From Free Pascal wiki
Jump to navigationJump to searchLine 58: | Line 58: | ||
* timsort (unit LGMiscUtils) | * timsort (unit LGMiscUtils) | ||
* counting sort | * counting sort | ||
+ | * radix sort | ||
* translation of Orson Peters' PDQSort algorithm | * translation of Orson Peters' PDQSort algorithm | ||
* static segment tree | * static segment tree | ||
Line 70: | Line 71: | ||
* brief implementation of thread pool (unit LGAsync) | * brief implementation of thread pool (unit LGAsync) | ||
* 128-bit integers (unit LGInt128) | * 128-bit integers (unit LGInt128) | ||
+ | * JSON validator/parser/generator(unit lgJson) | ||
=Download= | =Download= | ||
GitHub: https://github.com/avk959/LGenerics | GitHub: https://github.com/avk959/LGenerics |
Revision as of 15:13, 30 December 2020
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
- radix 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)
- JSON validator/parser/generator(unit lgJson)