Go 实现常见数据结构

binary-search-tree.go

// Package binarysearchtree creates a ItemBinarySearchTree data structure for the Item type
package binarysearchtree

import (
    "fmt"
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Item the type of the binary search tree
type Item generic.Type

// Node a single node that composes the tree
type Node struct {
    key   int
    value Item
    left  *Node //left
    right *Node //right
}

// ItemBinarySearchTree the binary search tree of Items
type ItemBinarySearchTree struct {
    root *Node
    lock sync.RWMutex
}

// Insert inserts the Item t in the tree
func (bst *ItemBinarySearchTree) Insert(key int, value Item) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    n := &Node{key, value, nil, nil}
    if bst.root == nil {
        bst.root = n
    } else {
        insertNode(bst.root, n)
    }
}

// internal function to find the correct place for a node in a tree
func insertNode(node, newNode *Node) {
    if newNode.key < node.key {
        if node.left == nil {
            node.left = newNode
        } else {
            insertNode(node.left, newNode)
        }
    } else {
        if node.right == nil {
            node.right = newNode
        } else {
            insertNode(node.right, newNode)
        }
    }
}

// InOrderTraverse visits all nodes with in-order traversing
func (bst *ItemBinarySearchTree) InOrderTraverse(f func(Item)) {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    inOrderTraverse(bst.root, f)
}

// internal recursive function to traverse in order
func inOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        inOrderTraverse(n.left, f)
        f(n.value)
        inOrderTraverse(n.right, f)
    }
}

// PreOrderTraverse visits all nodes with pre-order traversing
func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(Item)) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    preOrderTraverse(bst.root, f)
}

// internal recursive function to traverse pre order
func preOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        f(n.value)
        preOrderTraverse(n.left, f)
        preOrderTraverse(n.right, f)
    }
}

// PostOrderTraverse visits all nodes with post-order traversing
func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(Item)) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    postOrderTraverse(bst.root, f)
}

// internal recursive function to traverse post order
func postOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        postOrderTraverse(n.left, f)
        postOrderTraverse(n.right, f)
        f(n.value)
    }
}

// Min returns the Item with min value stored in the tree
func (bst *ItemBinarySearchTree) Min() *Item {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    n := bst.root
    if n == nil {
        return nil
    }
    for {
        if n.left == nil {
            return &n.value
        }
        n = n.left
    }
}

// Max returns the Item with max value stored in the tree
func (bst *ItemBinarySearchTree) Max() *Item {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    n := bst.root
    if n == nil {
        return nil
    }
    for {
        if n.right == nil {
            return &n.value
        }
        n = n.right
    }
}

// Search returns true if the Item t exists in the tree
func (bst *ItemBinarySearchTree) Search(key int) bool {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    return search(bst.root, key)
}

// internal recursive function to search an item in the tree
func search(n *Node, key int) bool {
    if n == nil {
        return false
    }
    if key < n.key {
        return search(n.left, key)
    }
    if key > n.key {
        return search(n.right, key)
    }
    return true
}

// Remove removes the Item with key `key` from the tree
func (bst *ItemBinarySearchTree) Remove(key int) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    remove(bst.root, key)
}

// internal recursive function to remove an item
func remove(node *Node, key int) *Node {
    if node == nil {
        return nil
    }
    if key < node.key {
        node.left = remove(node.left, key)
        return node
    }
    if key > node.key {
        node.right = remove(node.right, key)
        return node
    }
    // key == node.key
    if node.left == nil && node.right == nil {
        node = nil
        return nil
    }
    if node.left == nil {
        node = node.right
        return node
    }
    if node.right == nil {
        node = node.left
        return node
    }
    leftmostrightside := node.right
    for {
        //find smallest value on the right side
        if leftmostrightside != nil && leftmostrightside.left != nil {
            leftmostrightside = leftmostrightside.left
        } else {
            break
        }
    }
    node.key, node.value = leftmostrightside.key, leftmostrightside.value
    node.right = remove(node.right, node.key)
    return node
}

// String prints a visual representation of the tree
func (bst *ItemBinarySearchTree) String() {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    fmt.Println("------------------------------------------------")
    stringify(bst.root, 0)
    fmt.Println("------------------------------------------------")
}

// internal recursive function to print a tree
func stringify(n *Node, level int) {
    if n != nil {
        format := ""
        for i := 0; i < level; i++ {
            format += "       "
        }
        format += "---[ "
        level++
        stringify(n.left, level)
        fmt.Printf(format+"%d\n", n.key)
        stringify(n.right, level)
    }
}

dictionary.go

// Package dictionary creates a ValueDictionary data structure for the Item type
package dictionary

import (
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Key the key of the dictionary
type Key generic.Type

// Value the content of the dictionary
type Value generic.Type

// ValueDictionary the set of Items
type ValueDictionary struct {
    items map[Key]Value
    lock  sync.RWMutex
}

// Set adds a new item to the dictionary
func (d *ValueDictionary) Set(k Key, v Value) {
    d.lock.Lock()
    defer d.lock.Unlock()
    if d.items == nil {
        d.items = make(map[Key]Value)
    }
    d.items[k] = v
}

// Delete removes a value from the dictionary, given its key
func (d *ValueDictionary) Delete(k Key) bool {
    d.lock.Lock()
    defer d.lock.Unlock()
    _, ok := d.items[k]
    if ok {
        delete(d.items, k)
    }
    return ok
}

// Has returns true if the key exists in the dictionary
func (d *ValueDictionary) Has(k Key) bool {
    d.lock.RLock()
    defer d.lock.RUnlock()
    _, ok := d.items[k]
    return ok
}

// Get returns the value associated with the key
func (d *ValueDictionary) Get(k Key) Value {
    d.lock.RLock()
    defer d.lock.RUnlock()
    return d.items[k]
}

// Clear removes all the items from the dictionary
func (d *ValueDictionary) Clear() {
    d.lock.Lock()
    defer d.lock.Unlock()
    d.items = make(map[Key]Value)
}

// Size returns the amount of elements in the dictionary
func (d *ValueDictionary) Size() int {
    d.lock.RLock()
    defer d.lock.RUnlock()
    return len(d.items)
}

// Keys returns a slice of all the keys present
func (d *ValueDictionary) Keys() []Key {
    d.lock.RLock()
    defer d.lock.RUnlock()
    keys := []Key{}
    for i := range d.items {
        keys = append(keys, i)
    }
    return keys
}

// Values returns a slice of all the values present
func (d *ValueDictionary) Values() []Value {
    d.lock.RLock()
    defer d.lock.RUnlock()
    values := []Value{}
    for i := range d.items {
        values = append(values, d.items[i])
    }
    return values
}

graph.go

// Package graph creates a ItemGraph data structure for the Item type
package graph

import (
    "fmt"
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Item the type of the binary search tree
type Item generic.Type

// Node a single node that composes the tree
type Node struct {
    value Item
}

func (n *Node) String() string {
    return fmt.Sprintf("%v", n.value)
}

// ItemGraph the Items graph
type ItemGraph struct {
    nodes []*Node
    edges map[Node][]*Node
    lock  sync.RWMutex
}

// AddNode adds a node to the graph
func (g *ItemGraph) AddNode(n *Node) {
    g.lock.Lock()
    g.nodes = append(g.nodes, n)
    g.lock.Unlock()
}

// AddEdge adds an edge to the graph
func (g *ItemGraph) AddEdge(n1, n2 *Node) {
    g.lock.Lock()
    if g.edges == nil {
        g.edges = make(map[Node][]*Node)
    }
    g.edges[*n1] = append(g.edges[*n1], n2)
    g.edges[*n2] = append(g.edges[*n2], n1)
    g.lock.Unlock()
}

// AddEdge adds an edge to the graph
func (g *ItemGraph) String() {
    g.lock.RLock()
    s := ""
    for i := 0; i < len(g.nodes); i++ {
        s += g.nodes[i].String() + " -> "
        near := g.edges[*g.nodes[i]]
        for j := 0; j < len(near); j++ {
            s += near[j].String() + " "
        }
        s += "\n"
    }
    fmt.Println(s)
    g.lock.RUnlock()
}

hashtable.go

// Package hashtable creates a ValueHashtable data structure for the Item type
package hashtable

import (
    "fmt"
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Key the key of the dictionary
type Key generic.Type

// Value the content of the dictionary
type Value generic.Type

// ValueHashtable the set of Items
type ValueHashtable struct {
    items map[int]Value
    lock  sync.RWMutex
}

// the hash() private function uses the famous Horner's method
// to generate a hash of a string with O(n) complexity
func hash(k Key) int {
    key := fmt.Sprintf("%s", k)
    h := 0
    for i := 0; i < len(key); i++ {
        h = 31*h + int(key[i])
    }
    return h
}

// Put item with value v and key k into the hashtable
func (ht *ValueHashtable) Put(k Key, v Value) {
    ht.lock.Lock()
    defer ht.lock.Unlock()
    i := hash(k)
    if ht.items == nil {
        ht.items = make(map[int]Value)
    }
    ht.items[i] = v
}

// Remove item with key k from hashtable
func (ht *ValueHashtable) Remove(k Key) {
    ht.lock.Lock()
    defer ht.lock.Unlock()
    i := hash(k)
    delete(ht.items, i)
}

// Get item with key k from the hashtable
func (ht *ValueHashtable) Get(k Key) Value {
    ht.lock.RLock()
    defer ht.lock.RUnlock()
    i := hash(k)
    return ht.items[i]
}

// Size returns the number of the hashtable elements
func (ht *ValueHashtable) Size() int {
    ht.lock.RLock()
    defer ht.lock.RUnlock()
    return len(ht.items)
}

linked-list.go

// Package linkedlist creates a ItemLinkedList data structure for the Item type
package linkedlist

import (
    "fmt"
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Item the type of the linked list
type Item generic.Type

// Node a single node that composes the list
type Node struct {
    content Item
    next    *Node
}

// ItemLinkedList the linked list of Items
type ItemLinkedList struct {
    head *Node
    size int
    lock sync.RWMutex
}

// Append adds an Item to the end of the linked list
func (ll *ItemLinkedList) Append(t Item) {
    ll.lock.Lock()
    node := Node{t, nil}
    if ll.head == nil {
        ll.head = &node
    } else {
        last := ll.head
        for {
            if last.next == nil {
                break
            }
            last = last.next
        }
        last.next = &node
    }
    ll.size++
    ll.lock.Unlock()
}

// Insert adds an Item at position i
func (ll *ItemLinkedList) Insert(i int, t Item) error {
    ll.lock.Lock()
    defer ll.lock.Unlock()
    if i < 0 || i > ll.size {
        return fmt.Errorf("Index out of bounds")
    }
    addNode := Node{t, nil}
    if i == 0 {
        addNode.next = ll.head
        ll.head = &addNode
        return nil
    }
    node := ll.head
    j := 0
    for j < i-2 {
        j++
        node = node.next
    }
    addNode.next = node.next
    node.next = &addNode
    ll.size++
    return nil
}

// RemoveAt removes a node at position i
func (ll *ItemLinkedList) RemoveAt(i int) (*Item, error) {
    ll.lock.Lock()
    defer ll.lock.Unlock()
    if i < 0 || i > ll.size {
        return nil, fmt.Errorf("Index out of bounds")
    }
    node := ll.head
    j := 0
    for j < i-1 {
        j++
        node = node.next
    }
    remove := node.next
    node.next = remove.next
    ll.size--
    return &remove.content, nil
}

// IndexOf returns the position of the Item t
func (ll *ItemLinkedList) IndexOf(t Item) int {
    ll.lock.RLock()
    defer ll.lock.RUnlock()
    node := ll.head
    j := 0
    for {
        if node.content == t {
            return j
        }
        if node.next == nil {
            return -1
        }
        node = node.next
        j++
    }
}

// IsEmpty returns true if the list is empty
func (ll *ItemLinkedList) IsEmpty() bool {
    ll.lock.RLock()
    defer ll.lock.RUnlock()
    if ll.head == nil {
        return true
    }
    return false
}

// Size returns the linked list size
func (ll *ItemLinkedList) Size() int {
    ll.lock.RLock()
    defer ll.lock.RUnlock()
    size := 1
    last := ll.head
    for {
        if last == nil || last.next == nil {
            break
        }
        last = last.next
        size++
    }
    return size
}

// Insert adds an Item at position i
func (ll *ItemLinkedList) String() {
    ll.lock.RLock()
    defer ll.lock.RUnlock()
    node := ll.head
    j := 0
    for {
        if node == nil {
            break
        }
        j++
        fmt.Print(node.content)
        fmt.Print(" ")
        node = node.next
    }
    fmt.Println()
}

// Head returns a pointer to the first node of the list
func (ll *ItemLinkedList) Head() *Node {
    ll.lock.RLock()
    defer ll.lock.RUnlock()
    return ll.head
}

queue.go

// Package queue creates a ItemQueue data structure for the Item type
package queue

import (
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Item the type of the queue
type Item generic.Type

// ItemQueue the queue of Items
type ItemQueue struct {
    items []Item
    lock  sync.RWMutex
}

// New creates a new ItemQueue
func (s *ItemQueue) New() *ItemQueue {
    s.items = []Item{}
    return s
}

// Enqueue adds an Item to the end of the queue
func (s *ItemQueue) Enqueue(t Item) {
    s.lock.Lock()
    s.items = append(s.items, t)
    s.lock.Unlock()
}

// Dequeue removes an Item from the start of the queue
func (s *ItemQueue) Dequeue() *Item {
    s.lock.Lock()
    item := s.items[0]
    s.items = s.items[1:len(s.items)]
    s.lock.Unlock()
    return &item
}

// Front returns the item next in the queue, without removing it
func (s *ItemQueue) Front() *Item {
    s.lock.RLock()
    item := s.items[0]
    s.lock.RUnlock()
    return &item
}

// IsEmpty returns true if the queue is empty
func (s *ItemQueue) IsEmpty() bool {
    return len(s.items) == 0
}

// Size returns the number of Items in the queue
func (s *ItemQueue) Size() int {
    return len(s.items)
}

set.go

// Package set creates a ItemSet data structure for the Item type
package set

import "github.com/cheekybits/genny/generic"

// Item the type of the Set
type Item generic.Type

// ItemSet the set of Items
type ItemSet struct {
    items map[Item]bool
}

// Add adds a new element to the Set. Returns a pointer to the Set.
func (s *ItemSet) Add(t Item) *ItemSet {
    if s.items == nil {
        s.items = make(map[Item]bool)
    }
    _, ok := s.items[t]
    if !ok {
        s.items[t] = true
    }
    return s
}

// Clear removes all elements from the Set
func (s *ItemSet) Clear() {
    s.items = make(map[Item]bool)
}

// Delete removes the Item from the Set and returns Has(Item)
func (s *ItemSet) Delete(item Item) bool {
    _, ok := s.items[item]
    if ok {
        delete(s.items, item)
    }
    return ok
}

// Has returns true if the Set contains the Item
func (s *ItemSet) Has(item Item) bool {
    _, ok := s.items[item]
    return ok
}

// Items returns the Item(s) stored
func (s *ItemSet) Items() []Item {
    items := []Item{}
    for i := range s.items {
        items = append(items, i)
    }
    return items
}

// Size returns the size of the set
func (s *ItemSet) Size() int {
    return len(s.items)
}

stack.go

// Package stack creates a ItemStack data structure for the Item type
package stack

import (
    "sync"

    "github.com/cheekybits/genny/generic"
)

// Item the type of the stack
type Item generic.Type

// ItemStack the stack of Items
type ItemStack struct {
    items []Item
    lock  sync.RWMutex
}

// New creates a new ItemStack
func (s *ItemStack) New() *ItemStack {
    s.items = []Item{}
    return s
}

// Push adds an Item to the top of the stack
func (s *ItemStack) Push(t Item) {
    s.lock.Lock()
    s.items = append(s.items, t)
    s.lock.Unlock()
}

// Pop removes an Item from the top of the stack
func (s *ItemStack) Pop() *Item {
    s.lock.Lock()
    item := s.items[len(s.items)-1]
    s.items = s.items[0 : len(s.items)-1]
    s.lock.Unlock()
    return &item
}