## Data Structure And Algorithms

# Algorithms
## Sorting
### Bubble Sort

func BubbleSort(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}

	return arr
}

### Selection Sort

func SelectionSort(arr []int) []int {
	for i := 0; i < len(arr)-1; i++ {
		minIndex := i
		for j := i; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}

		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}

	return arr
}

### Merge Sort

func MergeSort(arr []int) []int {
	if len(arr) == 1 {
		return arr
	}

	mid := len(arr) / 2

	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])
    
	return Merge(left, right)
}

func Merge(arr1, arr2 []int) []int {
	var arr []int

	i := 0
	j := 0

	for i < len(arr1) && j < len(arr2) {
		if arr1[i] < arr2[j] {
			arr = append(arr, arr1[i])
			i++
		} else {
			arr = append(arr, arr2[j])
			j++
		}
	}

	for ; i < len(arr1); i++ {
		arr = append(arr, arr1[i])
	}

	for ; j < len(arr2); j++ {
		arr = append(arr, arr2[j])
	}

	return arr
}

## Searching

### Linear Search

func LinearSearch(arr []int, n int) int {
	for i := 0; i < len(arr); i++ {
		if arr[i] == n {
			return i
		}
	}

	return -1
}

### Binary Search

func BinarySearch(arr []int, n int) int {
	left := 0
	right := len(arr) - 1
	for left <= right {
		mid := (left + right) / 2
		if arr[mid] == n {
			return mid
		}
		if n > arr[mid] {
			left = mid + 1
		}
		if n < arr[mid] {
			right = mid - 1
		}
	}

	return -1
}

### Binary Search With Recursion

func BinarySearch(arr []int, n int, left int, right int) int {
	if right < left {
		return -1
	}

	mid := (left + right) / 2

	if arr[mid] == n {
		return mid
	}

	if n > arr[mid] {
		return BinarySearch(arr, n, mid+1, right)
	}

	return BinarySearch(arr, n, left, mid-1)
}

# Data Structure
### Queue

package main

import (
	"fmt"
)

type Queue struct {
	Items  []int
	length int
}

func NewQueue() *Queue {
	return &Queue{
		Items: make([]int, 0),
	}
}

func (q *Queue) Enqueue(n int) {
	q.Items = append(q.Items, n)
	q.length++
}

func (q *Queue) Dequeue() int {
	if q.length == 0 {
		fmt.Println("empty queue")
		return 0
	}

	first := q.Items[0]
	q.Items = q.Items[1:]
	q.length--
	return first
}

func (q *Queue) Length() int {
	return q.length
}

func main() {
	q := NewQueue()
	q.Enqueue(5)
	q.Enqueue(6)
	q.Enqueue(8)
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	q.Enqueue(8)
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
}

### Queue with Nodes

package main

import (
	"errors"
	"fmt"
)

func main() {
	fmt.Println("Hello World")
	q := NewQueue()
	q.Enqueue(1)
	q.Enqueue(2)
	q.Enqueue(3)
	q.Enqueue(4)

	fmt.Println(q.Dequeue())
	fmt.Println(q.Dequeue())
	fmt.Println(q.Dequeue())
	fmt.Println(q.Dequeue())
	fmt.Println(q.Dequeue())
}

type Node struct {
	Data int
	Next *Node
}

func (n *Node) HasNext() bool {
	return n.Next != nil
}

type Queue struct {
	Head *Node
}

func (q *Queue) Enqueue(val int) {
	n := &Node{Data: val}
	if q.Head == nil {
		q.Head = n
		return
	}

	cur := q.Head
	for cur.HasNext() {
		cur = cur.Next
	}

	cur.Next = n
}

func (q *Queue) Dequeue() (int, error) {
	if q.Head == nil {
		return 0, errors.New("empty queue")
	}

	val := q.Head.Data
	q.Head = q.Head.Next

	return val, nil
}

func NewQueue() *Queue {
	return &Queue{}
}

### Priority Queue

package main

import (
	"fmt"
)

type QueueItem struct {
	Data     int
	Priority int
}

type Queue struct {
	Items  []QueueItem
	length int
}

func NewQueue() *Queue {
	return &Queue{
		Items: make([]QueueItem, 0),
	}
}

func (q *Queue) Enqueue(n, priority int) {
	qItem := QueueItem{
		Data:     n,
		Priority: priority,
	}

	q.Items = append(q.Items, qItem)
	q.length++
	q.sort()
}

func (q *Queue) sort() {
	for i := 0; i < q.length; i++ {
		for j := 0; j < q.length-1; j++ {
			if q.Items[j].Priority < q.Items[j+1].Priority {
				q.Items[j].Data, q.Items[j+1].Data = q.Items[j+1].Data, q.Items[j].Data
			}
		}
	}
}

func (q *Queue) Dequeue() int {
	if q.length == 0 {
		fmt.Println("empty queue")
		return 0
	}

	first := q.Items[0]
	q.Items = q.Items[1:]
	q.length--
	return first.Data
}

func (q *Queue) Length() int {
	return q.length
}

func main() {
	q := NewQueue()
	q.Enqueue(5, 10)
	q.Enqueue(6, 29)
	q.Enqueue(8, 3)
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
	q.Enqueue(8, 2)
	fmt.Println("Length :", q.Length())
	fmt.Println(q.Dequeue())
}

## Round Robin With Queue

import (
	"fmt"
)

func main() {
	fmt.Println("Hello, 世界")

	q := NewQ()
	r := &RR{q}
	r.Add(func() { fmt.Println("1") })
	r.Add(func() { fmt.Println("2") })
	r.Add(func() { fmt.Println("3") })

	r.Run()
}

type RR struct {
	q *Q
}

func (rr *RR) Add(fn func()) {
	rr.q.En(fn)
}

func (rr *RR) Run() {
	for {
		fn := rr.q.De()
		fn()
		rr.Add(fn)
	}
}

type Q struct {
	items []func()
}

func NewQ() *Q {
	return &Q{
		items: make([]func(), 0, 10),
	}
}

func (q *Q) En(fn func()) {
	q.items = append(q.items, fn)
}

func (q *Q) De() func() {
	fn := q.items[0]
	q.items = q.items[1:]

	return fn
}

### Stack with nodes

package main

import (
	"errors"
	"fmt"
)

func main() {
	fmt.Println("Hello World")
	s := NewStack()
	s.Push(4)
	s.Push(3)
	s.Push(2)
	s.Push(1)
	fmt.Println(s.Pop())
	fmt.Println(s.Pop())
	fmt.Println(s.Pop())
	fmt.Println(s.Pop())
	fmt.Println(s.Pop())
}

type Node struct {
	Data int
	Next *Node
}

func (n *Node) HasNext() bool {
	return n.Next != nil
}

type Stack struct {
	Head *Node
}

func (s *Stack) Push(val int) {
	n := &Node{Data: val}
	if s.Head == nil {
		s.Head = n
		return
	}

	n.Next = s.Head
	s.Head = n
}

func (s *Stack) Pop() (int, error) {
	if s.Head == nil {
		return 0, errors.New("empty stack")
	}

	val := s.Head.Data
	s.Head = s.Head.Next

	return val, nil
}

func NewStack() *Stack {
	return &Stack{}
}

### Binary Searh Tree

package main

import (
	"fmt"
)

func main() {
	fmt.Println("Hello World")
	n := &Node{data: 1}
	bst := &BST{root: n}
	bst.insert(2)
	bst.insert(3)
	bst.insert(4)
	bst.insert(5)
	printOrder(bst.root)
	fmt.Println()
	fmt.Println(bst.find(6))
}

type Node struct {
	data  int
	left  *Node
	right *Node
}

func (n *Node) HasLeft() bool {
	return n.left != nil
}

func (n *Node) HasRight() bool {
	return n.right != nil
}

func (n *Node) Insert(value int) {
	if value < n.data {
		if n.left == nil {
			n.left = &Node{data: value}
		} else {
			n.left.Insert(value)
		}
	}

	if value > n.data {
		if n.right == nil {
			n.right = &Node{data: value}
		} else {
			n.right.Insert(value)
		}
	}
}

func (n *Node) Find(val int) int {
	if n.data == val {
		return n.data
	}

	if val < n.data && n.HasLeft() {
		return n.left.Find(val)
	}

	if val > n.data && n.HasRight() {
		return n.right.Find(val)
	}

	return -1
}

type BST struct {
	root *Node
}

func (bst *BST) insert(value int) {
	if bst.root == nil {
		bst.root = &Node{data: value}
		return
	}

	bst.root.Insert(value)
}

func (bst *BST) find(val int) int {
	if bst.root == nil {
		return -1
	}

	return bst.root.Find(val)
}

func printOrder(root *Node) {
	if root == nil {
		return
	}

	if root.HasLeft() {
		printOrder(root.left)
	}

	fmt.Print(root.data, " ")

	if root.HasRight() {
		printOrder(root.right)
	}
}

### HashTable

package main

import (
	"fmt"
)

func main() {
	fmt.Println("Hello World")
	ht := New()
	ht.Insert("1", 1)
	ht.Insert("22", 2)
	ht.Insert("333", 3)
	ht.Insert("4444", 4)
	ht.Insert("55555", 5)
	ht.Insert("666666", 6)
	ht.Insert("7777777", 7)

	// fmt.Println(ht.Get("1"))
	// fmt.Println(ht.Get("2"))
	// fmt.Println(ht.Get("3"))
	// fmt.Println(ht.Get("4"))
	// fmt.Println(ht.Get("5"))
	// fmt.Println(ht.Get("6"))

	ht.PrintAll()
}

type node struct {
	key   string
	value int
	next  *node
}

type list struct {
	root *node
}

func (l *list) insert(n *node) {
	if l.root == nil {
		l.root = n
		return
	}

	curr := l.root
	for curr.next != nil {
		curr = curr.next
	}

	curr.next = n
}

const size = 3

type HashTable struct {
	arr [size]*list
}

func New() *HashTable {

	var arr [size]*list

	for i := 0; i < size; i++ {
		arr[i] = &list{}
	}

	return &HashTable{
		arr: arr,
	}
}

func (h *HashTable) hash(key string) int {
	return len(key) % 3
}

func (h *HashTable) PrintAll() {
	for i := 0; i < size; i++ {
		fmt.Println("[", i, "]")
		list := h.arr[i]
		curr := list.root
		for curr != nil {
			fmt.Println(fmt.Sprintf("key %s value %d\n", curr.key, curr.value))
			curr = curr.next
		}
	}
}

func (h *HashTable) Insert(key string, value int) {
	index := h.hash(key)
	list := h.arr[index]
	gn := h.getNode(key)

	if gn != nil {
		gn.value = value
		return
	}

	n := node{
		key:   key,
		value: value,
	}

	list.insert(&n)
}

func (h *HashTable) getNode(key string) *node {
	index := h.hash(key)

	list := h.arr[index]

	curr := list.root

	for curr != nil {
		if curr.key == key {
			return curr
		}

		curr = curr.next
	}

	return nil
}

func (h *HashTable) Get(key string) int {
	index := h.hash(key)

	list := h.arr[index]

	curr := list.root

	for curr != nil {
		if curr.key == key {
			return curr.value
		}

		curr = curr.next
	}

	fmt.Println("no value found")

	return -1

}