Package mafsa implements Minimal Acyclic Finite State Automata (MA-FSA) in a space-optimized way as described by Dacuik, Mihov, Watson, and Watson in their paper, "Incremental Construction of Minimal Acyclic Finite-State Automata" (2000). It also implements Minimal Perfect Hashing (MPH) as described by Lucceshi and Kowaltowski in their paper, "Applications of Finite Automata Representing Large Vocabularies" (1992). Unscientifically speaking, this package lets you store large amounts of strings (with Unicode) in memory so that membership queries, prefix lookups, and fuzzy searches are fast. And because minimal perfect hashing is included, you can associate each entry in the tree with more data used by your application. See the README or the end of this documentation for a brief tutorial. MA-FSA structures are a specific type of Deterministic Acyclic Finite State Automaton (DAFSA) which fold equivalent state transitions into each other starting from the suffix of each entry. Typical construction algorithms involve building out the entire tree first, then minimizing the completed tree. However, the method described in the paper above allows the tree to be minimized after every word insertion, provided the insertions are performed in lexicographical order, which drastically reduces memory usage compared to regular prefix trees ("tries"). The goal of this package is to provide a simple, useful, and correct implementation of MA-FSA. Though more complex algorithms exist for removal of items and unordered insertion, these features may be outside the scope of this package. Membership queries are on the order of O(n), where n is the length of the input string, so basically O(1). It is advisable to keep n small since long entries without much in common, especially in the beginning or end of the string, will quickly overrun the optimizations that are available. In those cases, n-gram implementations might be preferable, though these will use more CPU. This package provides two kinds of MA-FSA implementations. One, the BuildTree, facilitates the construction of an optimized tree and allows ordered insertions. The other, MinTree, is effectively read-only but uses significantly less memory and is ideal for production environments where only reads will be occurring. Usually your build process will be separate from your production application, which will make heavy use of reading the structure. To use this package, create a BuildTree and insert your items in lexicographical order: The tree is now compressed to a minimum number of nodes and is ready to be saved. In your production application, then, you can read the file into a MinTree directly: The mt variable is a *MinTree which has the same data as the original BuildTree, but without all the extra "scaffolding" that was required for adding new elements. The package provides some basic read mechanisms.
Package toml is a TOML parser and manipulation library. This version supports the specification as described in https://github.com/toml-lang/toml/blob/master/versions/en/toml-v0.4.0.md Go-toml can marshal and unmarshal TOML documents from and to data structures. Go-toml can operate on a TOML document as a tree. Use one of the Load* functions to parse TOML data and obtain a Tree instance, then one of its methods to manipulate the tree. The package github.com/pelletier/go-toml/query implements a system similar to JSONPath to quickly retrieve elements of a TOML document using a single expression. See the package documentation for more information.
Package toml is a TOML parser and manipulation library. This version supports the specification as described in https://github.com/toml-lang/toml/blob/master/versions/en/toml-v0.5.0.md Go-toml can marshal and unmarshal TOML documents from and to data structures. Go-toml can operate on a TOML document as a tree. Use one of the Load* functions to parse TOML data and obtain a Tree instance, then one of its methods to manipulate the tree. The package github.com/pelletier/go-toml/query implements a system similar to JSONPath to quickly retrieve elements of a TOML document using a single expression. See the package documentation for more information. Package civil implements types for civil time, a time-zone-independent representation of time that follows the rules of the proleptic Gregorian calendar with exactly 24-hour days, 60-minute hours, and 60-second minutes. Because they lack location information, these types do not represent unique moments or intervals of time. Use time.Time for that purpose.
Package balloon implements Balloon, an authenticated data structure that is based on a hash treap and a history tree.
Package suture provides Erlang-like supervisor trees. This implements Erlang-esque supervisor trees, as adapted for Go. This is an industrial-strength, tested library deployed into hostile environments, not just a proof of concept or a toy. If you are reading this, you are reading the documentation for the v3 version, which is not the latest. If you want the latest v4, be sure to be using gitee.com/pengdacn/suture/v4. This rewrites the API to be in terms of contexts. Supervisor Tree -> SuTree -> suture -> holds your code together when it's trying to fall apart. Why use Suture? Suture has 100% test coverage, and is golint clean. This doesn't prove it free of bugs, but it shows I care. A blog post describing the design decisions is available at http://www.jerf.org/iri/post/2930 . To idiomatically use Suture, create a Supervisor which is your top level "application" supervisor. This will often occur in your program's "main" function. Create "Service"s, which implement the Service interface. .Add() them to your Supervisor. Supervisors are also services, so you can create a tree structure here, depending on the exact combination of restarts you want to create. As a special case, when adding Supervisors to Supervisors, the "sub" supervisor will have the "super" supervisor's Log function copied. This allows you to set one log function on the "top" supervisor, and have it propagate down to all the sub-supervisors. This also allows libraries or modules to provide Supervisors without having to commit their users to a particular logging method. Finally, as what is probably the last line of your main() function, call .Serve() on your top level supervisor. This will start all the services you've defined. See the Example for an example, using a simple service that serves out incrementing integers.
The trie package implements a trie (prefix tree) data structure over byte slices.
Package errortree provides multiple-error matching considering the tree structure of errors in Go1.20 and later. This package uses generics to keep the type info from the caller, and returns the search result with an arbitrary concrete type.
Package kdtree implements a k-d tree data structure.
Package merkletree implements a Merkle Tree capable of storing arbitrary content. A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with. At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items is inserted into a leaf node and a tree of hashes is constructed bottom up using a hash of the nodes left and right children's hashes. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case. Creating a new merkletree requires that the type that the tree will be constructed from implements the Content interface. A slice of the Content items should be created and then passed to the NewTree method. t represents the Merkle Tree and can be verified and manipulated with the API methods described below.
Package trie is an implementation of a trie (prefix tree) data structure over byte slices. It provides a small and simple API for usage as a set as well as a 'Node' API for walking the trie.
Package balloon implements Balloon, an authenticated data structure that is based on a hash treap and a history tree.
Package fstree creates or check filesystem tree structure driven by yaml.
Package Ki provides the base element of GoKi Trees: Ki = Tree in Japanese, and "Key" in English -- powerful tree structures supporting scenegraphs, programs, parsing, etc.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package gtrie is an implementation of an R-Way Trie value structure. This package supports more useful functions based on derekparker/trie (https://godoc.org/github.com/derekparker/trie). A Trie has a root trieNode which is the base of the tree. Each subsequent trieNode has a letter and children, which are nodes that have letter values associated with them.
This package is the root package of the govmomi library. The library is structured as follows: The minimal usable functionality is available through the vim25 package. It contains subpackages that contain generated types, managed objects, and all available methods. The vim25 package is entirely independent of the other packages in the govmomi tree -- it has no dependencies on its peers. The vim25 package itself contains a client structure that is passed around throughout the entire library. It abstracts a session and its immutable state. See the vim25 package for more information. The session package contains an abstraction for the session manager that allows a user to login and logout. It also provides access to the current session (i.e. to determine if the user is in fact logged in) The object package contains wrappers for a selection of managed objects. The constructors of these objects all take a *vim25.Client, which they pass along to derived objects, if applicable. The govc package contains the govc CLI. The code in this tree is not intended to be used as a library. Any functionality that govc contains that _could_ be used as a library function but isn't, _should_ live in a root level package. Other packages, such as "event", "guest", or "license", provide wrappers for the respective subsystems. They are typically not needed in normal workflows so are kept outside the object package.
Package flattenhtml provides a way to flatten the HTML tree structure and then use the flattened data to do different kinds of lookups.
this pattern is only useful if the code can be structured as a tree
Package trie is an implementation of a trie (prefix tree) data structure over byte slices.
Package bitcask is a high performance embedded key value store that uses an on-disk LSM and WAL data structures and in-memory radix tree of key/value pairs as per the bitcask paper and seen in the Riak database.
Package bitcask is a high performance embedded key value store that uses an on-disk LSM and WAL data structures and in-memory radix tree of key/value pairs as per the bitcask paper and seen in the Riak database. Package bitcask implements a high-performance key-value store based on a WAL and LSM.
Package tree provides a simple structure for dealing with dynamic or unknown JSON/YAML structures.
Package skiplist implements a probabilistic list-based data structure that are a simple and efficient substitute for balanced trees.
Package asciitree pretty-prints hierarchical node data structures as ASCII trees.
Original package by Scott Pakin, available under https://github.com/spakin/disjoint. This fork introduces one new method to allow for re-using the same objects, in an attempt to allow an application using this data structure to reduce memory overhead Original description below: Package disjoint implements a disjoint-set data structure. A disjoint-set—also called union-find—data structure keeps track of nonoverlapping partitions of a collection of data elements. Initially, each data element belongs to its own, singleton, set. The following operations can then be performed on these sets: • Union merges two sets into a single set containing the union of their elements. • Find returns an arbitrary element from a set. The critical feature is that Find returns the same element when given any element in a set. The implication is that two elements A and B belong to the same set if and only if A.Find() == B.Find(). Both Union and Find take as arguments elements of sets, not the sets themselves. Because sets are mutually disjoint, an element uniquely identifies a set. Ergo, there is no need to pass sets to those functions. Disjoint sets are more limited in functionality than conventional sets. They support only set union, not set intersection, set difference, or any other set operation. They don't allow an element to reside in more than one set. They don't even provide a way to enumerate the elements in a given set. What makes them useful, though, is that they're extremely fast, especially for large sets; both Union and Find run in amortized near-constant time. See http://en.wikipedia.org/wiki/Disjoint-set_data_structure for more information. Disjoint sets are often used in graph algorithms, for example to find a minimal spanning tree for a graph or to determine if adding a given edge to a graph would create a cycle. Draw a maze. This is my favorite use of disjoint-set forests. The algorithm works by repeatedly knocking down walls between two sets of rooms that are not part of the same union and merging those rooms into a single union. A union represents connected components—rooms in the maze that are mutually reachable. A single union implies that every room is reachable from every other room. This is a fairly long example, but note that only half of it relates to generating the maze. The other half renders the maze using Unicode box-drawing characters.
Package rbtree implements Red-Black tree data structure (RB-Tree).
The drill package contains primitives for implementing tree structures that can be drilled into.
Implementation of an R-Way Trie data structure. A Trie has a root Node which is the base of the tree. Each subsequent Node has a letter and children, which are nodes that have letter values associated with them.
Package tea provides a tree structure for writing stateful tests, such that child tests may utilize the side-effects of their ancestors.
Package splaytree implements the splay tree data structure, which is a self-balancing binary search tree, that is, it adapts its internal tree structure to how it is being used in order to optimize future operations.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package treeindex materializes and caches hierarchy-shaped lookup paths over an assembled IRAC reasoning tree (packages/irac), stored in a packages/graph GraphStore, for fast structured retrieval.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package antlr implements the Go version of the ANTLR 4 runtime. ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. It's widely used to build languages, tools, and frameworks. From a grammar, ANTLR generates a parser that can build parse trees and also generates a listener interface (or visitor) that makes it easy to respond to the recognition of phrases of interest. ANTLR supports the generation of code in a number of target languages, and the generated code is supported by a runtime library, written specifically to support the generated code in the target language. This library is the runtime for the Go target. To generate code for the go target, it is generally recommended to place the source grammar files in a package of their own, and use the `.sh` script method of generating code, using the go generate directive. In that same directory it is usual, though not required, to place the antlr tool that should be used to generate the code. That does mean that the antlr tool JAR file will be checked in to your source code control though, so you are free to use any other way of specifying the version of the ANTLR tool to use, such as aliasing in `.zshrc` or equivalent, or a profile in your IDE, or configuration in your CI system. Here is a general template for an ANTLR based recognizer in Go: Make sure that the package statement in your grammar file(s) reflects the go package they exist in. The generate.go file then looks like this: And the generate.sh file will look similar to this: depending on whether you want visitors or listeners or any other ANTLR options. From the command line at the root of your package “myproject” you can then simply issue the command: Copyright (c) 2012-2022 The ANTLR Project. All rights reserved. Use of this file is governed by the BSD 3-clause license, which can be found in the LICENSE.txt file in the project root.
Package bitreevis implements tool whichs help visualize binary tree structure in golang.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package ki creates tree structures from lists of file paths.