Heap

The quickselect package provides primitives for finding the smallest k elements in slices and user-defined collections. The primitives used in the package are modeled off of the standard sort library for Go. Quickselect uses Hoare's Selection Algorithm which finds the smallest k elements in expected O(n) time, and is thus an asymptotically optimal algorithm (and is faster than sorting or heap implementations).

Package fibHeap implements the Fibonacci Heap priority queue. This implementation is a bit different from the traditional Fibonacci Heap by having an index map to achieve better encapsulation.

Package fibHeap implements the Fibonacci Heap priority queue. This implementation is a bit different from the traditional Fibonacci Heap by having an index map to achieve better encapsulation.

Package fibHeap implements the Fibonacci Heap priority queue. This implementation is a bit different from the traditional Fibonacci Heap by having an index map to achieve better encapsulation.

Package btree implements in-memory B-Trees of arbitrary degree. btree implements an in-memory B-Tree for use as an ordered data structure. It is not meant for persistent storage solutions. It has a flatter structure than an equivalent red-black or other binary tree, which in some cases yields better memory usage and/or performance. See some discussion on the matter here: Note, though, that this project is in no way related to the C++ B-Tree implementation written about there. Within this tree, each node contains a slice of items and a (possibly nil) slice of children. For basic numeric values or raw structs, this can cause efficiency differences when compared to equivalent C++ template code that stores values in arrays within the node: These issues don't tend to matter, though, when working with strings or other heap-allocated structures, since C++-equivalent structures also must store pointers and also distribute their values across the heap. This implementation is designed to be a drop-in replacement to gollrb.LLRB trees, (http://github.com/petar/gollrb), an excellent and probably the most widely used ordered tree implementation in the Go ecosystem currently. Its functions, therefore, exactly mirror those of llrb.LLRB where possible. Unlike gollrb, though, we currently don't support storing multiple equivalent values.

Package fibheap implements a Fibonacci heap. A Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. The amortized time complexity of Fibonacci heap operations are as follows: fetching the minimum is Θ(1), extracting the minimum is O(log n), inserting is Θ(1), decreasing a key is Θ(1), and merging two heaps is Θ(1). In our implementation, we do not additionally track the key value of each element. Therefore, users should be aware that they should not insert elements with the same key into the Fibonacci heap.

Package heaps implements a generic heap data structure.

Package topk implements the Filtered Space-Saving TopK streaming algorithm The original Space-Saving algorithm: https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf The Filtered Space-Saving enhancement: http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf This implementation follows the algorithm of the FSS paper, but not the suggested implementation. Specifically, we use a heap instead of a sorted list of monitored items, and since we are also using a map to provide O(1) access on update also don't need the c_i counters in the hash table. Licensed under the MIT license.

Package radixtree implements an Adaptive Radix Tree, aka compressed trie or compact prefix tree. It is adaptive in the sense that nodes are not constant size, having as few or many children as needed to branch to all subtrees. This package implements a radix-256 tree where each key symbol (radix) is a byte, allowing up to 256 possible branches to traverse to the next node. The implementation is optimized for read performance and allocates zero bytes of heap memory for read oprations. Once the radix tree is built, it can be repeatedly searched quickly. Concurrent searches are safe since these do not modify the radixtree. Access is not synchronized (not concurrent safe with writes), allowing the caller to synchronize, if needed, in whatever manner works best for the application. The API uses string keys, since strings are immutable and therefore it is not necessary make a copy of the key provided to the radix tree.

Package xmlwriter provides a fast, non-cached, forward-only way to generate XML data. The API is based heavily on libxml's xmlwriter API [1], which is itself based on C#'s XmlWriter [2]. It offers some advantages over Go's default encoding/xml package and some tradeoffs. You can have complete control of the generated documents and it uses very little memory. There are two styles for interacting with the writer: structured and heap-friendly. If you want a visual representation of the hierarchy of some of your writes in your code and you don't care about a few instances of memory escaping to the heap (and most of the time you won't), you can use the structured API. If you are writing a code generator or your interactions with the API are minimal, you should use the direct API. xmlwriter.Writer{} takes any io.Writer, along with a variable list of options. xmlwriter options are based on Dave Cheney's functional options pattern (https://dave.cheney.net/2014/10/17/functional-options-for-friendly-apis): Provided options are: Using the structured API, you might express a small tree of elements like this. These nodes will escape to the heap, but judicious use of this nesting can make certain structures a lot more readable by representing the desired XML hierarchy in the code that produces it: The code can be made even less dense by importing xmlwriter with a prefix: `import xw "github.com/shabbyrobe/xmlwriter"` The same output is possible with the heap-friendy API. This has a lot more stutter and it's harder to tell the hierarchical relationship just by looking at the code, but there are no heap escapes this way: Use whichever API reads best in your code, but favour the latter style in all code generators and performance hotspots. xmlwriter.Writer extends bufio.Writer! Don't forget to flush otherwise you'll lose data. There are two ways to flush: The EndAllFlush form is just a convenience, it calls EndAll() and Flush() for you. Nodes which can have children can be passed to `Writer.Start()`. This adds them to the stack and opens them, allowing children to be added. Becomes: <foo><bar><baz/></bar></foo> Nodes which have no children, or nodes which can be opened and fully closed with only a trivial amount of information, can be passed to `Writer.Write()`. If written nodes are put on to the stack, they will be popped before Write returns. Becomes: <foo/><bar/><baz/> Block takes a Startable and a variable number of Writable nodes. The Startable will be opened, the Writables will be written, then the Startable will be closed: Becomes: There are several ways to end an element. Choose the End that's right for you! Nodes as they are written can be in three states: StateOpen, StateOpened or StateEnd. StateOpen == "<elem". StateOpened == "<elem>". StateEnd == "<elem></elem>". Node structs are available for writing in the following hierarchy. Nodes which are "Startable" (passed to `writer.Start(n)`) are marked with an S. Nodes which are "Writable" (passed to `writer.Write(n)`) are marked with a W. - xmlwriter.Raw* (W) - xmlwriter.Doc (S) * `xmlwriter.Raw` can be written anywhere, at any time. If a node is in the "open" state but not in the "opened" state, for example you have started an element and written an attribute, writing "raw" will add the content to the inside of the element opening tag unless you call `w.Next()`. Every node has a corresponding NodeKind constant, which can be found by affixing "Node" to the struct name, i.e. "xmlwriter.Elem" becomes "xmlwriter.ElemNode". These are used for calls to Writer.End(). xmlwriter.Attr{} values can be assigned from any golang primitive like so: xmlwriter supports encoders from the golang.org/x/text/encoding package. UTF-8 strings written in from golang will be converted on the fly and the document declaration will be written correctly. To write your XML using the windows-1252 encoder: The document line will look like this:

Package profiler is a client for the Stackdriver Profiler service. This package is still experimental and subject to change. Usage example: Calling Start will start a goroutine to collect profiles and upload to the profiler server, at the rhythm specified by the server. The caller must provide the service string in the config, and may provide other information as well. See Config for details. Profiler has CPU, heap and goroutine profiling enabled by default. Mutex profiling can be enabled in the config. Note that goroutine and mutex profiles are shown as "threads" and "contention" profiles in the profiler UI.