algorithm

Documentation

Overview

Package algorithm contain some basic algorithm functions. eg. sort, search, list, linklist, stack, queue, tree, graph.

Index

• func BinaryIterativeSearch[T any](sortedSlice []T, target T, lowIndex, highIndex int, ...) int
• func BinarySearch[T any](sortedSlice []T, target T, lowIndex, highIndex int, ...) int
• func BubbleSort[T any](slice []T, comparator constraints.Comparator)
• func CountSort[T any](slice []T, comparator constraints.Comparator) []T
• func HeapSort[T any](slice []T, comparator constraints.Comparator)
• func InsertionSort[T any](slice []T, comparator constraints.Comparator)
• func LinearSearch[T any](slice []T, target T, equal func(a, b T) bool) int
• func MergeSort[T any](slice []T, comparator constraints.Comparator)
• func QuickSort[T any](slice []T, comparator constraints.Comparator)
• func SelectionSort[T any](slice []T, comparator constraints.Comparator)
• func ShellSort[T any](slice []T, comparator constraints.Comparator)
• type LRUCache
  • func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V]
  • func (l *LRUCache[K, V]) Delete(key K) bool
  • func (l *LRUCache[K, V]) Get(key K) (V, bool)
  • func (l *LRUCache[K, V]) Len() int
  • func (l *LRUCache[K, V]) Put(key K, value V)

Examples

• BinaryIterativeSearch
• BinarySearch
• BubbleSort
• CountSort
• HeapSort
• InsertionSort
• LRUCache.Delete
• LRUCache.Get
• LRUCache.Len
• LRUCache.Put
• LinearSearch
• MergeSort
• QuickSort
• SelectionSort
• ShellSort

Functions

func BinaryIterativeSearch

func BinaryIterativeSearch[T any](sortedSlice []T, target T, lowIndex, highIndex int, comparator constraints.Comparator) int

BinaryIterativeSearch return the index of target within a sorted slice, use binary search (no recursive). If not found return -1. Play: https://go.dev/play/p/Anozfr8ZLH3

Example

numbers := []int{1, 2, 3, 4, 5, 6, 7, 8}
comparator := &intComparator{}

result1 := BinaryIterativeSearch(numbers, 5, 0, len(numbers)-1, comparator)
result2 := BinaryIterativeSearch(numbers, 9, 0, len(numbers)-1, comparator)

fmt.Println(result1)
fmt.Println(result2)

Output:

4
-1

func BinarySearch

func BinarySearch[T any](sortedSlice []T, target T, lowIndex, highIndex int, comparator constraints.Comparator) int

BinarySearch return the index of target within a sorted slice, use binary search (recursive call itself). If not found return -1. Play: https://go.dev/play/p/t6MeGiUSN47

Example

numbers := []int{1, 2, 3, 4, 5, 6, 7, 8}
comparator := &intComparator{}

result1 := BinarySearch(numbers, 5, 0, len(numbers)-1, comparator)
result2 := BinarySearch(numbers, 9, 0, len(numbers)-1, comparator)

fmt.Println(result1)
fmt.Println(result2)

Output:

4
-1

func BubbleSort

func BubbleSort[T any](slice []T, comparator constraints.Comparator)

BubbleSort applys the bubble sort algorithm to sort the collection, will change the original collection data. Play: https://go.dev/play/p/GNdv7Jg2Taj

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

BubbleSort(numbers, comparator)

fmt.Println(numbers)

Output:

[1 2 3 4 5 6]

func CountSort

func CountSort[T any](slice []T, comparator constraints.Comparator) []T

CountSort applys the count sort algorithm to sort the collection, don't change the original collection data. Play: https://go.dev/play/p/tB-Umgm0DrP

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

sortedNumber := CountSort(numbers, comparator)

fmt.Println(numbers)
fmt.Println(sortedNumber)

Output:

[2 1 5 3 6 4]
[1 2 3 4 5 6]

func HeapSort

func HeapSort[T any](slice []T, comparator constraints.Comparator)

HeapSort applys the heap sort algorithm to sort the collection, will change the original collection data. Play: https://go.dev/play/p/u6Iwa1VZS_f

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

HeapSort(numbers, comparator)

fmt.Println(numbers)

Output:

[1 2 3 4 5 6]

func InsertionSort

func InsertionSort[T any](slice []T, comparator constraints.Comparator)

InsertionSort applys the insertion sort algorithm to sort the collection, will change the original collection data. Play: https://go.dev/play/p/G5LJiWgJJW6

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

InsertionSort(numbers, comparator)

fmt.Println(numbers)

Output:

[1 2 3 4 5 6]

func LinearSearch

func LinearSearch[T any](slice []T, target T, equal func(a, b T) bool) int

LinearSearch return the index of target in slice base on equal function. If not found return -1 Play: https://go.dev/play/p/IsS7rgn5s3x

Example

numbers := []int{3, 4, 5, 3, 2, 1}

equalFunc := func(a, b int) bool {
	return a == b
}

result1 := LinearSearch(numbers, 3, equalFunc)
result2 := LinearSearch(numbers, 6, equalFunc)

fmt.Println(result1)
fmt.Println(result2)

Output:

0
-1

func MergeSort

func MergeSort[T any](slice []T, comparator constraints.Comparator)

MergeSort applys the merge sort algorithm to sort the collection, will change the original collection data. Play: https://go.dev/play/p/ydinn9YzUJn

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

MergeSort(numbers, comparator)

fmt.Println(numbers)

Output:

[1 2 3 4 5 6]

func QuickSort

func QuickSort[T any](slice []T, comparator constraints.Comparator)

QuickSort quick sorting for slice, lowIndex is 0 and highIndex is len(slice)-1. Play: https://go.dev/play/p/7Y7c1Elk3ax

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

QuickSort(numbers, comparator)

fmt.Println(numbers)

Output:

[1 2 3 4 5 6]

func SelectionSort

func SelectionSort[T any](slice []T, comparator constraints.Comparator)

SelectionSort applys the selection sort algorithm to sort the collection, will change the original collection data. Play: https://go.dev/play/p/oXovbkekayS

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

SelectionSort(numbers, comparator)

fmt.Println(numbers)

Output:

[1 2 3 4 5 6]

func ShellSort

func ShellSort[T any](slice []T, comparator constraints.Comparator)

ShellSort applys the shell sort algorithm to sort the collection, will change the original collection data. Play: https://go.dev/play/p/3ibkszpJEu3

Example

numbers := []int{2, 1, 5, 3, 6, 4}
comparator := &intComparator{}

ShellSort(numbers, comparator)

fmt.Println(numbers)

Output:

[1 2 3 4 5 6]

Types

type LRUCache

type LRUCache[K comparable, V any] struct {
	// contains filtered or unexported fields
}

LRUCache lru cache (thread unsafe)

func NewLRUCache

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V]

NewLRUCache creates a LRUCache pointer instance.

func (*LRUCache[K, V]) Delete

func (l *LRUCache[K, V]) Delete(key K) bool

Delete item from lru cache.

Example

cache := NewLRUCache[int, int](2)

cache.Put(1, 1)
cache.Put(2, 2)

result1, ok1 := cache.Get(1)

ok2 := cache.Delete(2)

_, ok3 := cache.Get(2)

fmt.Println(result1, ok1)
fmt.Println(ok2)
fmt.Println(ok3)

Output:

1 true
true
false

func (*LRUCache[K, V]) Get

func (l *LRUCache[K, V]) Get(key K) (V, bool)

Get value of key from lru cache. Play: https://go.dev/play/p/iUynEfOP8G0

Example

cache := NewLRUCache[int, int](2)

cache.Put(1, 1)
cache.Put(2, 2)

result1, ok1 := cache.Get(1)
result2, ok2 := cache.Get(2)
result3, ok3 := cache.Get(3)

fmt.Println(result1, ok1)
fmt.Println(result2, ok2)
fmt.Println(result3, ok3)

Output:

1 true
2 true
0 false

func (*LRUCache[K, V]) Len

func (l *LRUCache[K, V]) Len() int

Len returns the number of items in the cache.

Example

cache := NewLRUCache[int, int](2)

cache.Put(1, 1)
cache.Put(2, 2)

result := cache.Len()

fmt.Println(result)

Output:

2

func (*LRUCache[K, V]) Put

func (l *LRUCache[K, V]) Put(key K, value V)

Put value of key into lru cache. Play: https://go.dev/play/p/iUynEfOP8G0

Example

cache := NewLRUCache[int, int](2)

cache.Put(1, 1)
cache.Put(2, 2)

result1, ok1 := cache.Get(1)
result2, ok2 := cache.Get(2)
result3, ok3 := cache.Get(3)

fmt.Println(result1, ok1)
fmt.Println(result2, ok2)
fmt.Println(result3, ok3)

Output:

1 true
2 true
0 false