Commits

Anonymous committed 377d171 Draft

first

  • Participants

Comments (0)

Files changed (7)

+.DS_Store
+package bst
+
+import (
+    "fmt"
+)
+
+type Node struct {
+    data int
+    left *Node
+    right *Node
+}
+
+type Tree struct {
+    root *Node
+}
+
+func initialize() (self *Tree) {
+    tree := &Tree{nil}
+    return tree
+}
+
+func new_node(data int) (node *Node) {
+    newNode := &Node{data, nil, nil}
+    return newNode
+}
+
+func _insert_inner(self *Tree, node *Node, data int) (n *Node) {
+    if node == nil {
+        return new_node(data)
+    }
+    if(data < node.data) {
+        node.left = _insert_inner(self, node.left, data)
+    } else {
+        node.right = _insert_inner(self, node.right, data)
+    }
+    return node
+}
+
+func insert(self *Tree, data int) {
+    self.root = _insert_inner(self, self.root, data)
+}
+
+func find_max(self *Tree) (data int) {
+    node := self.root
+    for ; node.right != nil; {
+        node = node.right
+    }
+    return node.data
+}
+
+func find_min(self *Tree) (data int) {
+    node := self.root
+    for ; node.left != nil; {
+        node = node.left
+    }
+    return node.data
+}
+
+func inorder(node *Node) {
+    if node != nil {
+        inorder(node.left)
+        fmt.Println(node.data)
+        inorder(node.right)
+    }
+}
+
+func display(self *Tree) {
+    inorder(self.root)
+}
+/*
+    Elf and FNV hashing algorithms in Go.
+*/
+
+package main
+
+
+func elf(s string, size uint64) (uint64) {
+    hash := uint64(0)
+    for i := 0; i < len(s); i++ {
+        hash = (hash << 4) + uint64(s[i])
+        t := hash & 0xF0000000
+        if t != 0 {
+            hash ^= t >> 24
+        }
+        hash &= ^t
+    }
+    return hash % size
+}
+
+func fnv(s string, fold uint32, mask uint32) (uint32) {
+    const FNV_PRIME_32_BIT := 16777619
+    const OFFSET_BASIS_32_BIT := 2166136261
+    hash := OFFSET_BASIS_32_BIT
+    for i = 0; i < len(s); i++ {
+        hash = (hash * FNV_PRIME_32_BIT) ^ s[i]
+    }
+    if fold == 0 {
+        return hash
+    }
+    return (hash ^ (hash >> fold)) & mask
+}
+/*
+    Heapsort example in Go.
+*/
+
+package heapsort
+
+func LeftChild(val int) (int) {
+    return (val << 1) + 1
+}
+
+func Parent(val int) (int) {
+    return val >> 1
+}
+
+func MoveDown(a []int, i int, n int) {
+    child := 0
+    temp := 0
+    for temp = a[i]; LeftChild(i) < n; i = child {
+        child = LeftChild(i)
+        if child != n - 1 && a[child] < a[child + 1] {
+            child++
+        }
+        if temp < a[child] {
+            a[i] = a[child]
+        } else {
+            break
+        }
+    }
+    a[i] = temp
+}
+
+func HeapSort(a []int) ([]int) {
+    for i := Parent(len(a)); i >= 0; i-- {
+        MoveDown(a, i, len(a))
+    }
+    for i := len(a) - 1; i > 0; i-- {
+        a[0] ^= a[i]
+        a[i] ^= a[0]
+        a[0] ^= a[i]
+        MoveDown(a, 0, i)
+    }
+    return a
+}
+/*
+    Knuth-Morris-Pratt string search algorithm in Go.
+*/
+
+package kmp
+
+
+func _compute_prefix(pattern string) ([]int) {
+    pi := make([] int, len(pattern))
+    k := 0
+    for q := 1; q < len(pattern); q++ {
+        for ; k > 0 && pattern[k] != pattern[q]; {
+            k = pi[k]
+        }
+        if pattern[k] == pattern[q] {
+            k++
+        }
+        pi[q] = k
+    }
+    return pi
+}
+
+func KMP(text string, pattern string) (int) {
+    m := len(pattern)
+    pi := _compute_prefix(pattern)
+    q := 0
+    for i := 0; i < len(text); i++ {
+        for ; q > 0 && pattern[q] != text[i]; {
+            q = pi[q]
+        }
+        if pattern[q] == text[i] {
+            q++
+        }
+        if q == m {
+            return i - m + 1
+        }
+    }
+    return -1
+}
+/*
+    Basic Linked List example in Go.
+*/
+
+package linkedlist
+
+import (
+    "fmt"
+)
+
+type Node struct {
+    data int
+    next *Node
+    prev *Node
+}
+
+type LinkedList struct {
+    head *Node
+    tail *Node
+    size int
+}
+
+func Initialize() (self *LinkedList) {
+    list := &LinkedList{nil, nil, 0}
+    return list
+}
+
+func Append(self *LinkedList, data int) {
+    node := &Node{data, nil, nil}
+    if self.tail != nil {
+        self.tail.next = node
+    } else {
+        self.head = node
+    }
+    self.tail = node
+    node.next = nil
+    self.size += 1
+}
+
+func Insert(self *LinkedList, data int) {
+    node := &Node{data, self.head, nil}
+    node.data = data
+    self.head = node
+    if self.tail == nil {
+        self.tail = node
+    }
+    self.size += 1
+}
+
+func Search(self *LinkedList, data int) (bool) {
+    for node := self.head; node != nil; node = node.next {
+        if node.data == data {
+            return true
+        }
+    }
+    return false
+}
+
+func Nth(self *LinkedList, index int) (*Node) {
+    counter := 0
+    for cur := self.head; cur != nil; cur = cur.next {
+        if counter == index {
+            return cur
+        }
+        counter++
+    }
+    return nil
+}
+
+func InsertNth(self *LinkedList, index int, data int) {
+    if self.size < index || index < 0 {
+        panic("IndexOutOfBoundsException")
+    }
+    if index == 0 {
+        insert(self, data)
+    } else {
+        before := self.head
+        after := self.head.next
+        for i := 0; i < index - 1 && after != nil; i++ {
+            before = after
+            after = after.next
+        }
+        node := &Node{data, after, before}
+        before.next = node
+    }
+}
+
+func Remove(self *LinkedList, data int) {
+    node := &Node{0, nil, nil}
+    prev := &Node{0, nil, nil}
+    for node = self.head; node != nil; node = node.next {
+        if node.data == data {
+            break
+        }
+        prev = node
+    }
+    if node != nil {
+        if prev == nil {
+            self.head = node.next
+        } else {
+            prev.next = node.next
+        }
+        if node.next == nil {
+            self.tail = prev
+        }
+        self.size -= 1
+    }
+}
+
+func Display(self *LinkedList) {
+    for node := self.head; node != nil; node = node.next {
+        fmt.Println(node.data)
+    }
+}
+/*
+    Mergesort in Go.
+*/
+
+package main
+
+
+func merge(a []int, temp []int, left, m, right int) {
+    i := 0
+    j := 0
+    for i = m + 1; i > left; i-- {
+        temp[i - 1] = a[i - 1]
+    }
+    for j = m; j < right; j++ {
+        temp[right + m - j] = a[j + 1]
+    }
+    for k := left; k <= right; k++ {
+        if temp[j] < temp[i] {
+            a[k] = temp[j]
+            j--
+        } else {
+            a[k] = temp[i]
+            i++
+        }
+    }
+}
+
+func min(a int, b int) (int) {
+    if a < b {
+        return a
+    }
+    return b
+}
+
+func mergesort(a []int, left, right int) ([] int) {
+    if left < right {
+        temp := make([] int, len(a))
+        for m := 1; m <= right - left; m += m {
+            for i := left; i <= right - m; i += m + m {
+                merge(a, temp, i, i + m - 1, min(i + m + m - 1, right))
+            }
+        }
+    }
+    return a
+}