tchap / Go Patricia
Licence: mit
A generic patricia trie (also called radix tree) implemented in Go (Golang)
Stars: ✭ 243
Labels
Projects that are alternatives of or similar to Go Patricia
Tastylib
C++ implementations of data structures, algorithms, and system designs.
Stars: ✭ 101 (-58.44%)
Mutual labels: data-structure
Ordereddictionary
Ordered dictionary data structure implementation in Swift
Stars: ✭ 176 (-27.57%)
Mutual labels: data-structure
Gods
GoDS (Go Data Structures). Containers (Sets, Lists, Stacks, Maps, Trees), Sets (HashSet, TreeSet, LinkedHashSet), Lists (ArrayList, SinglyLinkedList, DoublyLinkedList), Stacks (LinkedListStack, ArrayStack), Maps (HashMap, TreeMap, HashBidiMap, TreeBidiMap, LinkedHashMap), Trees (RedBlackTree, AVLTree, BTree, BinaryHeap), Comparators, Iterators, …
Stars: ✭ 10,883 (+4378.6%)
Mutual labels: data-structure
Cs61a
Structure and Interpretation of Computer Programs
Stars: ✭ 123 (-49.38%)
Mutual labels: data-structure
Skiplist
skip list with rank, code less than z_set in redis
Stars: ✭ 136 (-44.03%)
Mutual labels: data-structure
Denormalizr
Denormalize data normalized with normalizr
Stars: ✭ 231 (-4.94%)
Mutual labels: data-structure
Mnemonist
Curated collection of data structures for the JavaScript/TypeScript language.
Stars: ✭ 1,752 (+620.99%)
Mutual labels: data-structure
Leetcode Solutions
🏋️ Python / Modern C++ Solutions of All 2111 LeetCode Problems (Weekly Update)
Stars: ✭ 2,787 (+1046.91%)
Mutual labels: data-structure
Algorithm
The challenges for algorithm contests, and summary the implementation.
Stars: ✭ 115 (-52.67%)
Mutual labels: data-structure
Data structures and algorithms in python
📖 Worked Solutions of "Data Structures & Algorithms in Python", written by Michael T. Goodrich, Roberto Tamassia and Michael H. Goldwasser. ✏️
Stars: ✭ 147 (-39.51%)
Mutual labels: data-structure
Algorithm templates
algorithm templates and leetcode examples in Python3, you can learn many python tricks too.
Stars: ✭ 107 (-55.97%)
Mutual labels: data-structure
Brein Time Utilities
Library which contains several time-dependent data and index structures (e.g., IntervalTree, BucketTimeSeries), as well as algorithms.
Stars: ✭ 94 (-61.32%)
Mutual labels: data-structure
Binarytree
Python Library for Studying Binary Trees
Stars: ✭ 1,694 (+597.12%)
Mutual labels: data-structure
Staticvec
Implements a fixed-capacity stack-allocated Vec alternative backed by an array, using const generics.
Stars: ✭ 236 (-2.88%)
Mutual labels: data-structure
C Macro Collections
Easy to use, header only, macro generated, generic and type-safe Data Structures in C
Stars: ✭ 192 (-20.99%)
Mutual labels: data-structure
go-patricia
Documentation: GoDoc
Test Coverage:
About
A generic patricia trie (also called radix tree) implemented in Go (Golang).
The patricia trie as implemented in this library enables fast visiting of items in some particular ways:
- visit all items saved in the tree,
- visit all items matching particular prefix (visit subtree), or
- given a string, visit all items matching some prefix of that string.
[]byte
type is used for keys, interface{}
for values.
Trie
is not thread safe. Synchronize the access yourself.
State of the Project
Apparently some people are using this, so the API should not change often. Any ideas on how to make the library better are still welcome.
More (unit) testing would be cool as well...
Usage
Import the package from GitHub first.
import "github.com/tchap/go-patricia/patricia"
You can as well use gopkg.in thingie:
import "gopkg.in/tchap/go-patricia.v2/patricia"
Then you can start having fun.
printItem := func(prefix patricia.Prefix, item patricia.Item) error {
fmt.Printf("%q: %v\n", prefix, item)
return nil
}
// Create a new default trie (using the default parameter values).
trie := NewTrie()
// Create a new custom trie.
trie := NewTrie(MaxPrefixPerNode(16), MaxChildrenPerSparseNode(10))
// Insert some items.
trie.Insert(Prefix("Pepa Novak"), 1)
trie.Insert(Prefix("Pepa Sindelar"), 2)
trie.Insert(Prefix("Karel Macha"), 3)
trie.Insert(Prefix("Karel Hynek Macha"), 4)
// Just check if some things are present in the tree.
key := Prefix("Pepa Novak")
fmt.Printf("%q present? %v\n", key, trie.Match(key))
// "Pepa Novak" present? true
key = Prefix("Karel")
fmt.Printf("Anybody called %q here? %v\n", key, trie.MatchSubtree(key))
// Anybody called "Karel" here? true
// Walk the tree in alphabetical order.
trie.Visit(printItem)
// "Karel Hynek Macha": 4
// "Karel Macha": 3
// "Pepa Novak": 1
// "Pepa Sindelar": 2
// Walk a subtree.
trie.VisitSubtree(Prefix("Pepa"), printItem)
// "Pepa Novak": 1
// "Pepa Sindelar": 2
// Modify an item, then fetch it from the tree.
trie.Set(Prefix("Karel Hynek Macha"), 10)
key = Prefix("Karel Hynek Macha")
fmt.Printf("%q: %v\n", key, trie.Get(key))
// "Karel Hynek Macha": 10
// Walk prefixes.
prefix := Prefix("Karel Hynek Macha je kouzelnik")
trie.VisitPrefixes(prefix, printItem)
// "Karel Hynek Macha": 10
// Delete some items.
trie.Delete(Prefix("Pepa Novak"))
trie.Delete(Prefix("Karel Macha"))
// Walk again.
trie.Visit(printItem)
// "Karel Hynek Macha": 10
// "Pepa Sindelar": 2
// Delete a subtree.
trie.DeleteSubtree(Prefix("Pepa"))
// Print what is left.
trie.Visit(printItem)
// "Karel Hynek Macha": 10
License
MIT, check the LICENSE
file.
Note that the project description data, including the texts, logos, images, and/or trademarks,
for each open source project belongs to its rightful owner.
If you wish to add or remove any projects, please contact us at [email protected].