# π Data Structures and Algorithms in Julia

Contents

General algorithms, data structures and data types for Julia

^{1}

## See also

- Awesome algorithms, a curated list of awesome places to learn and/or practice algorithms.
- algo-book-julia :: Snippets from Problem Solving with Algorithms and Data Structures in Julia.
- study :: A study of interesting algorithms in Python.

- ποΈ means the package may not support current versions of Julia.
- ποΈ means the package may be a WIP.

## General Algorithms and DataStrcutures

- CRC.jl :: a Julia module for calculating Cyclic Redundancy Checksums (CRCs).

WIP or may not work

- ποΈ ARules.jl :: Julia package for Association Rule Learning algorithms.
- ποΈ CRC32.jl :: 32-bit cyclic redundancy check (CRC-32) checksum implementation.
- ποΈ HClust.jl :: Hierarchical Clustering for Julia, similar to R’s hclust(), has now been merged into Clustering.jl
- ποΈ LabelPropagation.jl :: A fast, nearly linear time algorithm for detecting communtiy structure in networks.
- ποΈ RecSys.jl :: An implementation of the ALS-WR algorithm.

## Pattern Matching

- BlossomV.jl :: An interface for the Blossom V perfect matching algorithm.
- Loess.jl :: is a loess implementation based on the fast kd-tree based approximation algorithm, a space-partitioning data structure for organizing points in a k-dimensional space.
- Match.jl :: Advanced Pattern Matching for Julia.

WIP or may not work

- ποΈ AhoCorasick.jl :: Julia implementation of the Aho-Corasick algorithm for fast string searching.
- ποΈ JellyFish.jl :: Port of the jellyfish string comparison library.
- ποΈ NearestNeighbors.jl :: Data structures for nearest neighbor search.
- ποΈ PatternDispatch.jl :: Method dispatch based on pattern matching for Julia.
- ποΈ ReverseRegexes.jl :: Adds functionality to reverse-search strings with regexes

## Sorting

- NaturalSort.jl :: Natural sort order.
- SortingAlgorithms.jl :: extra sorting algorithms extending Julia’s sorting API.
- SortingLab.jl :: Experimental implementations of sorting algorithms.

WIP or may not work

- ποΈ SearchSortAlgos.jl :: An API for common search and sort algorithms.

## NP-complete Problems

π NP-complete problems cannot be solved in polynomial time complexity and often have to be inexactly solved using heuristics.

- TravelingSalesmanHeuristics.jl :: Julia package for simple traveling salesman problem heuristics.

### Boolean satisfiability problem (SAT)

π SAT is a kind of NP-complete (NPC) problems.

- PicoSAT.jl :: Provides Julia bindings to the popular SAT solver picosat by Armin Biere. It is based off the Python pycosat and Go pigosat bindings written by Ilan Schnell and Willam Schwartz.

WIP or may not work

## Data strctures and data types

- DataStructures.jl :: Julia implementation of Data structures
- CBOR.jl :: A Concise Binary Object Representation (RFC 7049) Julia package for working with the CBOR data format, providing straightforward encoding and decoding for Julia types.
- DataStructures.jl :: This package implements a variety of data structures.
- FreeType.jl :: Font FreeType 2 bindings API wrapper.
- FreeTypeAbstraction.jl :: A Julian abstraction layer over FreeType.jl.
- FunctionalCollections.jl :: Functional and and persistent data structures for Julia.
- FunctionalData.jl :: Functional, efficient data manipulation framework.
- ImagineFormat.jl :: Read .imagine light sheet microscopy file formats in Julia.
- MUtils.jl ::
`channels()`

,`tspaces(`

)`,`

kvspaces()` and more. - ResultTypes.jl :: A Result type for Juliaβit’s like Nullables for Exceptions.
- TypeSortedCollections.jl :: It provides the TypeSortedCollection type, which can be used to store type-heterogeneous data in a way that allows operations on the data to be performed in a type-stable manner.

WIP or may not work

- ποΈ ASCIIByte.jl :: Julia package to deal with Characters of 8 bits.
- ποΈ Codecs.jl :: Common data encoding algorithms.
- ποΈ DanaTypes.jl :: Types for continuous variables or parameters.
- ποΈ DictViews.jl :: KeysView and ValuesView types for dynamic low-overhead views into the entries of dictionaries.
- ποΈ DotPlusInheritance.jl :: Expression parser that simulates type inheritance.
- ποΈ jenks.jl
- ποΈ julia-prettyshow :: A module to provide simple pretty printing facilities with base functionality for indentation etc, and a
`pshow`

(pretty show) implementation for julia ASTs. - ποΈ LHEF.jl :: Quick and dirty implementation of the Les Houches Event Format, for particle Physics, in terms of Fortran commonblocks where the information is embedded in a minimal XML-style structure.
- ποΈ MPFI.jl :: A MPFI wrapper for Julia.
- ποΈ RDF.jl :: RDF package for working with RDF Graphs in Julia. Supports serialization as RDF N-Triples, RDF N-Quads and Turtle. Julia package mirror
- ποΈ ReTerms.jl :: Package providing abstract random-effects terms and specific types.
- ποΈ Sexpr.jl :: A program to port clojure-like s-expression syntax to and from Julia.
- ποΈ TexExtensions.jl :: Tex Pretty printing of Julia Base types.
- ποΈ RingBuffer.jl :: Julia ring buffer implementation for buffered IO.

## Text / string data type

- FixedSizeStrings.jl :: A type for efficiently storing short strings of known size.
- Format.jl :: This Julia package provides C and Python-style types and functions formatting support.
- Formatting.jl :: A Julia package to provide Python-like formatting support.
- LaTeXStrings.jl :: This is a small package to make it easier to type LaTeX equations in string literals in the Julia language.
- ShortStrings.jl :: A fast and efficient string format implementation for storing strings of size less than 15 bytes.
- StringDistances.jl :: String Distances in Julia.
- StringLiterals.jl :: Implement improved string literals with Swift-style syntax for interpolation, hex, & unicode characters, plus C & Python style formatting and Unicode, HTML, LaTeX, and Emoji entities.
- VersionParsing.jl :: flexible VersionNumber parsing in Julia.
- WeakRefStrings.jl :: a minimal String type for Julia that allows for efficient string representation and transfer.

WIP or may not work

- ποΈ AutoFormat.jl
- ποΈ MonkeyString.jl :: Fast string implementation inspired by SpiderMonkey.
- ποΈ MutableStrings.jl :: Mutable string types for Julia.
- ποΈ StringInterpolation.jl :: String interpolation for non-standard string literals.
- ποΈ Strings.jl :: Testing out a new String representation.
- ποΈ StringUtils.jl :: String utilities for Julia, Swift-like interpolation/quoting, better performing versions of string functions, etc.
- ποΈ TypeCheck.jl :: a type checker for Julia.
- ποΈ Typeclass.jl :: Prototype typeclasses for Julia.
- ποΈ TypeGraph.jl :: Visualize the Julia type system.

## Graph data types

- AbstractTrees.jl :: Abstract julia interfaces for working with trees.
- Arrowhead.jl :: Arrowhead and Diagonal-plus-rank-one Eigenvalue Solvers.
- LightGraphs.jl :: An optimized simple graphs package designed for fast analysis using standard functions that seeks to mimic the functionality of established packages like NetworkX, but with better performance.
- Seep.jl :: It builds and evaluates computational flow graphs in julia. A computational flow graph (CFG) is a directed acyclic graph where nodes represent values and edges represent data dependencies.
- SimpleGraphs.jl :: A module for working with simple graphs (no loops, no multiple edges, no directed edges).

WIP or may not work

- ποΈ BGraph.jl :: An adjacency list that uses typed properties for vertices, edges, and graphs.
- ποΈ CompressedStacks.jl
- ποΈ DeepReshapes.jl :: Reshape arbitrarily nested structures of Tuples and Arrays in Julia.
- ποΈ EvolvingGraphs.jl :: Working with time-dependent networks in Julia.
- ποΈ FingerTrees.jl :: A Finger Tree is a functional data structure that can give an amortized constant time access to the fingers (leaves) of the tree where the data is stored, while the internal nodes are labeled in some way as to provide the functionality of the particular data structure being implemented.
- ποΈ Graft.jl :: Graft stores vertex and edge metadata in separate dataframes.
- ποΈ Lists.jl :: Singly linked list and doubly linked list for Julia.
- ποΈ PropertyGraph.jl :: A Julia package for constructing, creating and querying graph data structures.
- ποΈ PropertyGraphMongo.jl :: A Mongo storage provider for the
`PropertyGraph.jl`

package. - ποΈ RedBlackTrees.jl :: A redβblack self-balancing binary search tree in Julia. REF: http://en.wikipedia.org/wiki/Red_black_trees
- ποΈ SpatialGraphs.jl
- ποΈ SumTrees.jl :: Binary tree where the nodes contain the sum of the left and right children.
- ποΈ Trie.jl :: Implementation of the trie data structure.

## Numeric data types

- ArbFloats.jl :: extended precision
*values*for arithmetic, elementary, and some special functions (25..500 digits). - ArbNumerics.jl :: extended precision math, accurate and performant
- BFloat16s.jl :: This package defines the BFloat16 data type. The only currently available hardware implementation of this datatype are Google’s Cloud TPUs. As such, this package is suitable to evaluate whether using TPUs would cause precision problems for any particular algorithm, even without access to TPU hardware. Note that this package is designed for functionality, not performance, so this package should be used for precision experiments only, not performance experiments.
- BitIntegers.jl :: This package implements fixed-width integer types similar to standard builtin-ones like Int or UInt128.
- ClosedIntervals.jl :: Closed intervals of the form [a,b].
- CustomUnitRanges.jl :: Package-specific AbstractUnitRange types for julia.
- DecFP.jl :: The package provides 32-bit, 64-bit, and 128-bit binary-encoded decimal floating-point types following the IEEE 754-2008, implemented as a wrapper around the (BSD-licensed) Intel Decimal Floating-Point Math Library.
- Decimals.jl :: Pure Julia decimal arithmetic library.
- DoubleFloats.jl :: Math with 85+ accurate bits.
- FixedPointNumbers.jl :: This library exports fixed-point number types. A fixed-point number represents a fractional, or non-integral, number. In contrast with the more widely known floating-point numbers, fixed-point numbers have a fixed number of digits (bits) after the decimal (radix) point. They are effectively integers scaled by a constant factor.
- Infinity.jl :: Representation of infinity in Julia.
- Measurements.jl :: Error propagation calculator and library. It supports real and complex numbers with uncertainty, arbitrary precision calculations, and operations with arrays.
- MonteCarloMeasurements.jl :: Error propagation using Monte-Carlo simulation. Similar to Measurements.jl, but more accurate for highly nonlinear functions at the expense of longer execution time.
- Measures.jl :: Unified measure and coordinates types.
- Quaternions.jl :: Quaternions, octonions and dual-quaternions.
- Quaternions.jl :: by @peakbook. Quaternion for Julia Language.
- Ratios.jl :: Faster Rational-like types for Julia.
- Unitful.jl :: A Julia package for physical units.

WIP or may not work

- ποΈ ArbDecimals.jl :: reliable and performant extended precision floating point math.
- ποΈ ArbFloats.jl :: Arb available as an extended precision floating point context.
- ποΈ BigRationals.jl :: A BigRational package for Julia using GMP.
- ποΈ ChainedVectors.jl :: Few utility types over Julia Vector type.
- ποΈ DoubleDouble.jl :: A Julia package for performing extended-precision arithmetic using pairs of floating-point numbers.
- ποΈ FlexFloat.jl :: Allows values to stretch in a way that preserves accuracy durring mathematical computations.
- ποΈ FloatFloats.jl.
- ποΈ FloatHigher.jl :: accurate floating point math at extended precisions.
- ποΈ HigherPrecision.jl :: HigherPrecision defines the subtypes of
`AbstractFloat`

,`DoubleFloat64`

, a 128 bit number type with around 30 bits of precision, intended as a drop-in replacement for Float64 and BigFloat. - ποΈ IEEEFloat16.jl
- ποΈ Intervals.jl :: A pure Julia reimplementation of MPFI, a multiple precision interval arithmetic library.
- ποΈ IntModN.jl :: Ring(s) of Integers Modulo-N.
- ποΈ IntsWithInfinty.jl :: Ints augmented with Infinity.
- ποΈ Scalar.jl :: Scalar Types.
- ποΈ Units.jl :: Infrastructure for handling physical units for the Julia programming language. Use
`Unitful.jl`

instead.

### Array types

- AbstractTensors.jl :: Tensor algebra abstract type interoperability with vector bundle parameter.
- ArrayInterface.jl :: Designs for new Base array interface primitives, used widely through scientific machine learning (SciML) and other organizations.
- AxisArrays.jl :: Performant arrays where each dimension can have a named axis with values.
- BandedMatrices.jl :: A Julia package for representing banded matrices.
- BlockArrays.jl :: BlockArrays for Julia.
- CategoricalArrays.jl :: Arrays for working with categorical data (both nominal and ordinal) in Julia.
- ChunkedArrays.jl :: A package for increasing the performance of arrays generated iteratively.
- ContinuumArrays.jl :: A package for representing quasi arrays with continuous indices.
- FastArrays.jl :: Multi-dimensional arrays with arbitrary upper and lower bounds that can be fixed at compile time.
- IndirectArrays.jl :: Julia implementation of indexed or “lookup” arrays.
- InfiniteArrays.jl :: A Julia package for representing infinite-dimensional arrays.
- LabelledArrays.jl :: Arrays with a label for each element.
- LazyArrays.jl :: Lazy arrays and linear algebra in Julia.
- MappedArrays.jl :: Lazy in-place transformations of arrays.
- MatrixDepot.jl :: An Extensible Test Matrix Collection for Julia. Documentation: http://matrixdepotjl.readthedocs.org/
- NamedArrays.jl :: Julia type that implements a drop-in replacement of Array with named dimensions and Dict-type indexes.
- NamedAxesArrays.jl :: Performant arrays where each axis can be named.
- OffsetArrays.jl :: Fortran-like arrays with arbitrary, zero or negative starting indices for arrays in Julia. The main purpose of this package is to simplify translation from Fortran codes intensively using Fortran arrays with negative and zero starting indices, such as the codes accompanying the book Numerical Solution of Hyperbolic Partial Differential Equations by prof. John A. Trangenstein.
- Pseudospectra.jl :: a package for computing pseudospectra of non-symmetric matrices, and plotting them along with eigenvalues (“spectral portraits”).
- QuasiArrays.jl :: A package for representing quasi-arrays, viz. arrays with non-classical indexing, including possibly continuous indexing.
- RandomMatrices.jl :: Random Matrices.
- RangeArrays.jl :: Efficient and convenient array data structures where the columns of the arrays are generated (on the fly) by Ranges.
- RecursiveArrayTools.jl :: Tools for easily handling nestings array objects like arrays of arrays.
- Rotations.jl :: Julia implementations for different rotation parameterisations.
- ShiftedArrays.jl :: Lazy shifted arrays implementation for data analysis in Julia.
- SpecialMatrices.jl :: Julia package for working with special matrix types.
- StaticArrays.jl :: Statically sized arrays for Julia.
- StrideArrays.jl :: Library supporting the ArrayInterface.jl strided array interface.
- StructArrays.jl :: Efficient implementation of struct arrays
`StructArray`

. - SuffixArrays.jl :: Native Julia suffix array implementation.
- ToeplitzMatrices.jl :: Fast matrix multiplication and division for Toeplitz matrices in Julia.
- UniqueVectors.jl :: Vectors of unique elements, with quick reverse lookups.
- Vec.jl :: Provides 2D and 3D vector types for vector operations in Julia.
- WoodburyMatrices.jl :: Library support for the Woodbury matrix identity.

WIP or may not work

- ποΈ FlexibleArrays.jl :: Multi-dimensional arrays with arbitrary upper and lower bounds that can be fixed or flexible.
- ποΈ ImmutableArrays.jl :: Statically-sized immutable vectors and matrices.
- ποΈ JudyDicts.jl :: Judy arrays are fast associative arrays with low memory usage.
- ποΈ NonuniformArray.jl :: This library handles the case of
**array of arrays**where each subarray may have different lengths - but enforces contiguity of data for ease of passing to outside linear algebra packages. - ποΈ RandomBandedMatrices.jl.
- ποΈ Ranges.jl :: Array-like objects with compact storage for the Julia language. Merged in Julia
`Base`

. - ποΈ RingArrays.jl :: A sliding window over a huge array.
- ποΈ Series.jl :: Series data structure in Julia.
- ποΈ SparseVectorMatrix.jl :: SparseMatrices as a vector of SparseVectors.
- ποΈ SparseVectors.jl :: A Julia package to support sparse vectors.
- ποΈ StructsOfArrays.jl :: Structures of Arrays that behave like Arrays of Structures.
- ποΈ TimeArrays.jl :: A temporary repo exploring the union of SeriesPair arrays into multicolumn arrays with similar behavior.

## Composite Data Types

Also see `[Base.@kwdef](https://discourse.julialang.org/t/what-does-kwdef-do/51973)`

.

- Bijections.jl :: Bijection datatype for Julia that blocks assigning the same value to two different keys.
- DispatchedTuples.jl::
`Dispatched Tuples`

are like immutable dictionaries (so, they’re technically more like NamedTuples) except that the keys are instances of types. Also, because DispatchedTuples are backed by tuples, they are GPU-friendly. - ExtractMacro.jl :: Provides a convenience
`@extract`

macro to extract fields from composite types. - Parameters.jl :: Types with default field values, keyword constructors and (un-)pack macros.
- Setfield.jl :: Update deeply nested immutable structs.
- SimpleTraits.jl :: Simple Traits for Julia
- SymDict.jl :: Dictionaries with Symbol keys. (No
`Project.toml`

) - TypedDelegation.jl :: Use a Type’s fields as operands for the type’s operations and easily apply functions onto fields' values.
- Unpack.jl ::
`@unpack`

some or all of the fields of a type, and`@pack`

, in the case of mutable datatypes.

WIP or may not work

- ποΈ AutoTypeParameters.jl :: A Julia library to reversibly encode any value so that it can be used as a type parameter.
- ποΈ DictWrappers.jl :: Wrap any Julia composite type in an Associative interface.
- ποΈ EMLTranslator.jl :: Adds Inheritance to julia composite type.
- ποΈ FixedSizeDictionaries.jl :: Library which implements a fixed size variant of Dictionaries.
- ποΈ Modifyfield.jl :: It creates functions to modify immutable fields of a composite type inside a container.
- ποΈ Named.jl :: Julia named index and named vector types.
- ποΈ NamedTuples.jl :: An implementation of named tuples to support both index and property based access, for example in the definition of a method or as the return value of a method. Merged into Base.
- ποΈ SimpleStructs.jl :: Easy to use struct definition with defaults and value constraints, as well as auto-defined user-friendly constructors.
- ποΈ Traits.jl :: Traits package contracts on a type or a tuple of types and allows dispatch to work with them.
- ποΈ TupleTypes.jl :: A testbed for an API to access Tuple parameters.
- ποΈ TypeTree.jl :: source code and the interactive D3 visualization of a Julia type tree.
- OrderedCollections.jl(404) :: OrderedDict and OrderedSet for Julia.
- ποΈ QuickStructs.jl :: Several data structures with goals of O(1) for important operations.

## Resources

- Jeff Bezanson on The State of the Type System at JuliaCon 2017.
- A more thorough look at Julia’s
**double colon**syntax