q

package module
v0.0.0-...-c033019 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 27, 2024 License: MIT Imports: 1 Imported by: 0

README

Go Reference Go

q

This repository contains implementations of various data structures in Go, including:

  • List
  • Heap
  • Set
import "github.com/campbel/q"

func main() {
	list := q.NewList(1, 2, 3)
	fmt.Println(list)

	heap := q.NewHeap(func(a, b int) bool {
		return a < b
	}, 1, 2, 3)
	fmt.Println(heap)

	set := q.NewSet(1, 2, 3)
	fmt.Println(set)
}

Documentation

Overview

Example 
package main

import (
	"fmt"

	"github.com/campbel/q"
)

func main() {
	list := q.NewList(1, 2, 3)
	fmt.Println(list)

	heap := q.NewHeap(func(a, b int) bool {
		return a < b
	}, 1, 2, 3)
	fmt.Println(heap)

	set := q.NewSet(1, 2, 3)
	fmt.Println(set)
}

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Equal 

func Equal[M comparable](a, b *List[M]) bool

Equal returns true if the two lists are equal, false otherwise. Time complexity: O(n), where n is the number of elements in the list.

func IndexOf 

func IndexOf[M comparable](list *List[M], value M) int

IndexOf returns the index of the first occurrence of the value in the list, or -1 if not found. Time complexity: O(n), where n is the number of elements in the list.

func Reduce 

func Reduce[M any, N any](l *List[M], callback func(N, M) N, initial N) N

Reduce applies a callback function to each value in the list and returns a single accumulated value. Time complexity: O(n), where n is the number of elements in the list.

func Remove 

func Remove[M comparable](list *List[M], value M)

Remove removes all occurrences of the value from the list. Time complexity: O(n), where n is the number of elements in the list.

Types

type Counter 

type Counter[T comparable] struct {
	// contains filtered or unexported fields
}

Counter is a generic counter data structure that stores unique elements of type T and counts occurences.

func NewCounter 

func NewCounter[T comparable](elements ...T) *Counter[T]

NewCounter creates a new Counter and returns a pointer to it. Time complexity: O(1).

func (*Counter[T]) Add 

func (c *Counter[T]) Add(elements ...T)

Add adds one or more elements to the counter. Time complexity: O(n), where n is the number of elements being added.

func (*Counter[T]) Clear 

func (c *Counter[T]) Clear()

Clear removes all elements from the counter. Time complexity: O(1).

func (*Counter[T]) Contains 

func (c *Counter[T]) Contains(element T) bool

Contains checks if an element is present in the counter. Time complexity: O(1).

func (*Counter[T]) Count 

func (c *Counter[T]) Count(element T) int

Count returns the number of occurences of an element in the counter. Time complexity: O(1).

func (*Counter[T]) Elements 

func (c *Counter[T]) Elements() []T

Elements returns a slice containing all the elements in the counter. Time complexity: O(n), where n is the number of elements in the counter.

func (*Counter[T]) Equal 

func (c *Counter[T]) Equal(other *Counter[T]) bool

Equal checks if the counter is equal to another counter. Time complexity: O(n), where n is the number of elements in the counter.

func (*Counter[T]) IsEmpty 

func (c *Counter[T]) IsEmpty() bool

IsEmpty checks if the counter is empty. Time complexity: O(1).

func (*Counter[T]) Len 

func (c *Counter[T]) Len() int

Len returns the number of elements in the counter. Time complexity: O(1).

func (*Counter[T]) Remove 

func (c *Counter[T]) Remove(elements ...T) bool

Remove removes an element from the counter. If the element is not present it returns false. Time complexity: O(1).

func (*Counter[T]) String 

func (c *Counter[T]) String() string

String returns a string representation of the counter. Time complexity: O(n), where n is the number of elements in the counter.

type Heap 

type Heap[M any] struct {
	// contains filtered or unexported fields
}

Heap is a generic implementation of a heap data structure.

func NewHeap 

func NewHeap[M any](less func(a, b M) bool, elements ...M) *Heap[M]

NewHeap creates a new instance of Heap with the specified less function. Time complexity: O(1).

func (*Heap[M]) Empty 

func (h *Heap[M]) Empty() bool

Empty returns true if the heap is empty, false otherwise. Time complexity: O(1).

Example

ExampleHeap_Empty demonstrates how to check if the heap is empty. 

h := NewHeap(func(a, b int) bool {
	return a < b
})
fmt.Println(h.Empty())
h.Push(1, 2, 3)
fmt.Println(h.Empty())

Output:
true
false

func (*Heap[M]) Len 

func (h *Heap[M]) Len() int

Len returns the number of elements in the heap. Time complexity: O(1).

Example

ExampleHeap_Len demonstrates how to get the number of elements in the heap. 

h := NewHeap(func(a, b int) bool {
	return a < b
})
h.Push(5, 2, 7, 1, 9)
fmt.Println(h.Len())

Output:
5

func (*Heap[M]) Pop 

func (h *Heap[M]) Pop() M

Pop removes and returns the top element from the heap. Time complexity: O(log n), where n is the number of elements in the heap.

Example

ExampleHeap_Pop demonstrates how to pop the top element from the heap. 

h := NewHeap(func(a, b int) bool {
	return a < b
})
h.Push(5, 2, 7, 1, 9)
top := h.Pop()
fmt.Println(top)
fmt.Println(h.data)

Output:
1
[2 5 7 9]

func (*Heap[M]) Push 

func (h *Heap[M]) Push(values ...M)

Push adds one or more values to the heap. Time complexity: O(log n) for each value, where n is the number of elements in the heap.

Example

ExampleHeap_Push demonstrates how to push elements onto the heap. 

h := NewHeap(func(a, b int) bool {
	return a < b
})
h.Push(5, 2, 7, 1, 9)
fmt.Println(h.data)

Output:
[1 2 7 5 9]

func (*Heap[M]) String 

func (h *Heap[M]) String() string

String returns a string representation of the heap.

func (*Heap[M]) Top 

func (h *Heap[M]) Top() M

Top returns the top element of the heap without removing it. Time complexity: O(1).

Example

ExampleHeap_Top demonstrates how to retrieve the top element without removing it. 

h := NewHeap(func(a, b string) bool {
	return a < b
})
h.Push("banana", "apple", "orange", "grape")
top := h.Top()
fmt.Println(top)
fmt.Println(h.data)

Output:
apple
[apple banana orange grape]

type List 

type List[M any] struct {
	// contains filtered or unexported fields
}

List represents a generic linked list.

func Join 

func Join[M any](lists ...*List[M]) *List[M]

Join combines multiple lists into a single list. Time complexity: O(m), where m is the total number of elements in all the lists.

func Map 

func Map[M any, N any](l *List[M], callback func(M) N) *List[N]

Map applies a callback function to each value in the list and returns a new list with the results. Time complexity: O(n), where n is the number of elements in the list.

func NewList 

func NewList[M any](elements ...M) *List[M]

NewList creates a new List and initializes it with the given elements. Time complexity: O(n), where n is the number of elements.

func (*List[M]) All 

func (l *List[M]) All(callback func(int, M) bool) bool

All returns true if all values in the list satisfy the callback function, false otherwise. Time complexity: O(n), where n is the number of elements in the list.

func (*List[M]) Any 

func (l *List[M]) Any(callback func(int, M) bool) bool

Any returns true if at least one value in the list satisfies the callback function, false otherwise. Time complexity: O(n), where n is the number of elements in the list.

func (*List[M]) Copy 

func (l *List[M]) Copy() *List[M]

Copy returns a new list with the same values as the original list. Time complexity: O(n), where n is the number of elements in the list.

func (*List[M]) Each 

func (l *List[M]) Each(callback func(int, M))

Each applies a callback function to each value in the list. Time complexity: O(n), where n is the number of elements in the list.

Example

ExampleList_Each demonstrates how to apply a callback function to each element in the list. 

list := NewList[int](1, 2, 3, 4, 5)
list.Each(func(i, value int) {
	fmt.Print(value*2, " ")
})

Output:
2 4 6 8 10

func (*List[M]) Elements 

func (l *List[M]) Elements() []M

Elements returns a slice containing all the values in the list. Time complexity: O(n), where n is the number of elements in the list.

func (*List[M]) Extend 

func (l *List[M]) Extend(lists ...*List[M])

Extend appends other lists to the current list. Time complexity: O(m), where m is the total number of elements in all the lists.

func (*List[M]) Filter 

func (l *List[M]) Filter(callback func(int, M) bool) *List[M]

Filter returns a new list containing only the values that satisfy the callback function. Time complexity: O(n), where n is the number of elements in the list.

func (*List[M]) Find 

func (l *List[M]) Find(callback func(int, M) bool) M

Find returns the first value in the list that satisfies the callback function. Time complexity: O(n), where n is the number of elements in the list.

Example

ExampleList_Find demonstrates how to find the first element that satisfies a condition. 

list := NewList[int](1, 2, 3, 4, 5)
even := list.Find(func(i, value int) bool {
	return value%2 == 0
})
fmt.Println(even)

Output:
2

func (*List[M]) IsSorted 

func (l *List[M]) IsSorted(less func(M, M) bool) bool

IsSorted returns true if the list is sorted in non-decreasing order according to the provided less function, false otherwise. Time complexity: O(n), where n is the number of elements in the list.

func (*List[M]) Len 

func (l *List[M]) Len() int

Len returns the length of the list. Time complexity: O(1).

func (*List[M]) Len64 

func (l *List[M]) Len64() int64

Len64 returns the length of the list as an int64. Time complexity: O(1).

func (*List[M]) Pop 

func (l *List[M]) Pop() M

Pop removes and returns the last value from the list. Time complexity: O(1).

Example

ExampleList_Pop demonstrates how to remove and return the last element from the list. 

list := NewList[int](1, 2, 3)
last := list.Pop()
fmt.Println(last)
fmt.Println(list)

Output:
3
[1 2]

func (*List[M]) PopLeft 

func (l *List[M]) PopLeft() M

PopLeft removes and returns the first value from the list. Time complexity: O(1).

func (*List[M]) PopRight 

func (l *List[M]) PopRight() M

PopRight removes and returns the last value from the list. Time complexity: O(1).

func (*List[M]) Push 

func (l *List[M]) Push(values ...M)

Push adds values to the list. Time complexity: O(n), where n is the number of values.

Example

ExampleList_Push demonstrates how to add elements to the list. 

list := NewList[int]()
list.Push(1, 2, 3)
fmt.Println(list)

Output:
[1 2 3]

func (*List[M]) PushLeft 

func (l *List[M]) PushLeft(values ...M)

PushLeft adds values to the beginning of the list. Time complexity: O(n), where n is the number of values.

func (*List[M]) PushRight 

func (l *List[M]) PushRight(values ...M)

PushRight adds values to the end of the list. Time complexity: O(n), where n is the number of values.

func (*List[M]) Reverse 

func (l *List[M]) Reverse()

Reverse reverses the order of the list. Time complexity: O(n), where n is the number of elements in the list.

Example

ExampleList_Reverse demonstrates how to reverse the order of elements in the list. 

list := NewList[string]("apple", "banana", "orange")
list.Reverse()
fmt.Println(list)

Output:
[orange banana apple]

func (*List[M]) Slice 

func (l *List[M]) Slice(start, stop int) *List[M]

Slice returns a new list containing the elements from the start index to the stop index. Time complexity: O(n), where n is the number of elements in the list.

func (*List[M]) Sort 

func (l *List[M]) Sort(less func(M, M) bool) *List[M]

Sort returns a new sorted list using the provided less function. Time complexity: O(n log n), where n is the number of elements in the list.

Example

ExampleList_Sort demonstrates how to sort the list using a custom less function. 

list := NewList[int](5, 2, 4, 1, 3)
sorted := list.Sort(func(a, b int) bool {
	return a < b
})
fmt.Println(sorted)

Output:
[1 2 3 4 5]

func (*List[M]) String 

func (l *List[M]) String() string

String returns a string representation of the list. Time complexity: O(n), where n is the number of elements in the list.

type Node 

type Node[M any] struct {
	// contains filtered or unexported fields
}

Node represents a node in the linked list.

type Set 

type Set[T comparable] struct {
	// contains filtered or unexported fields
}

Set is a generic set data structure that stores unique elements of type T.

func NewSet 

func NewSet[T comparable](elements ...T) *Set[T]

NewSet creates a new Set and returns a pointer to it. Time complexity: O(1).

func (*Set[T]) Add 

func (s *Set[T]) Add(elements ...T)

Add adds one or more elements to the set. Time complexity: O(n), where n is the number of elements being added.

Example

Example_Set_Add demonstrates how to add elements to a set. 

set := NewSet[int]()
set.Add(1, 2, 3)
elements := set.Elements()
slices.Sort(elements)
fmt.Println(elements)

Output:
[1 2 3]

func (*Set[T]) Clear 

func (s *Set[T]) Clear()

Clear removes all elements from the set. Time complexity: O(1).

func (*Set[T]) Contains 

func (s *Set[T]) Contains(element T) bool

Contains checks if an element is present in the set. Time complexity: O(1).

Example

Example_Set_Contains demonstrates how to check if an element exists in a set. 

set := NewSet[string]()
set.Add("apple", "banana", "orange")
fmt.Println(set.Contains("banana"))
fmt.Println(set.Contains("grape"))

Output:
true
false

func (*Set[T]) Difference 

func (s *Set[T]) Difference(other *Set[T]) *Set[T]

Difference returns a new set that contains the elements present in the current set but not in another set. Time complexity: O(n), where n is the number of elements in the current set.

func (*Set[T]) Elements 

func (s *Set[T]) Elements() []T

Elements returns a slice containing all the elements in the set. Time complexity: O(n), where n is the number of elements in the set.

func (*Set[T]) Intersection 

func (s *Set[T]) Intersection(other *Set[T]) *Set[T]

Intersection returns a new set that is the intersection of the current set and another set. Time complexity: O(n), where n is the number of elements in the smaller set.

func (*Set[T]) Len 

func (s *Set[T]) Len() int

Len returns the number of elements in the set. Time complexity: O(1).

func (*Set[T]) Remove 

func (s *Set[T]) Remove(element T)

Remove removes an element from the set. Time complexity: O(1).

func (*Set[T]) String 

func (s *Set[T]) String() string

func (*Set[T]) Union 

func (s *Set[T]) Union(other *Set[T]) *Set[T]

Union returns a new set that is the union of the current set and another set. Time complexity: O(n), where n is the total number of elements in both sets.

Example

Example_Set_Union demonstrates how to find the union of two sets. 

set1 := NewSet[int]()
set1.Add(1, 2, 3)
set2 := NewSet[int]()
set2.Add(3, 4, 5)
unionSet := set1.Union(set2)
sorted := sort.IntSlice(unionSet.Elements())
sorted.Sort()
fmt.Println(sorted)

Output:
[1 2 3 4 5]

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.