/gocontainer

Implements some containers (stack, queue, priorityQueue, arrayList, linkedList, map) in golang

Primary LanguageGoMIT LicenseMIT

gocontainer (中文版)

gocontainer implements some containers which exist in Java, but are missing in golang. This library is zero dependency, which means it does NOT depend on any 3rd party packages. Currently the containers are not thread-safe.

Table of Contents

How to use this repo

It's very straightforward, just imports the containers you need and then use them directly. The following is an example for ArrayList,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/list"
)

func main() {
	al := list.NewArrayList()
	al.Add(5, 6, 7)

	// Iterate all the elements 
	fmt.Println("Iterate (method 1): ")
	for i := 0; i < al.Len(); i++ {
		v, _ := al.Get(i)
		fmt.Printf("    Index: %d, value: %v\n", i, v)
	}
}

Please find more examples here.

Common Interface

All containers in this repository implement interface collection.Interface,

// Interface is a type of collection, all containers should implement this interface.
type Interface interface {
	// Size returns the number of elements in the collection.
	Size() int
	// IsEmpty returns true if this container contains no elements.
	IsEmpty() bool
	// Clear removes all of the elements from this container.
	Clear()
}

Containers

Currently this library implements the following containers:

  • Stack
  • Queue
  • Set
  • List (ArrayList, LinkedList)
  • PriorityQueue
  • LinkedMap

Stack

Stack is a LIFO(last-in-first-out) container. It implements the following interface. Click here to find examples on how to use a stack.

// Interface is a stack, which is LIFO (last-in-first-out).
type Interface interface {
	collection.Interface

	// Push pushes an element into this stack.
	Push(val interface{})
	// Pop pops the element on the top of this stack.
	Pop() interface{}
}

Please import the following package in order to use stack,

import (
	"github.com/ahrtr/gocontainer/stack"
)

Call stack.New() to create a stack,

New() Interface

The following is a simple example for stack,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/stack"
)

func main() {
	s := stack.New()

	values := []int{5, 6, 7}
	for _, v := range values {
		s.Push(v)
	}

	for s.Size() > 0 {
		fmt.Printf("s.Pop() = %v\n", s.Pop())
	}
}

Queue

Queue is a FIFO(first-in-first-out) container. It implements the following interface. Click here to find examples on how to use a queue.

// Interface is a type of queue, which is FIFO(first-in-first-out).
type Interface interface {
	collection.Interface

	// Add inserts an element into the tail of this queue.
	Add(vals ...interface{})
	// Peek retrieves, but does not remove, the head of this queue, or return nil if this queue is empty.
	Peek() interface{}
	// Poll retrieves and removes the head of the this queue, or return nil if this queue is empty.
	Poll() interface{}
}

Please import the following package in order to use queue,

import (
	"github.com/ahrtr/gocontainer/queue"
)

Call queue.New() to create a queue,

New() Interface

The following is a simple example for queue,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/queue"
)

func main() {
	q := queue.New()

	values := []string{"benjamin", "alice", "john", "tom", "bill"}

	for _, v := range values {
		q.Add(v)
	}

	for q.Peek() != nil {
		fmt.Printf("q.Peek() = %v\n", q.Peek())
		fmt.Printf("q.Poll() = %v\n", q.Poll())
	}
}

Set

A set contains no duplicate elements. The values contained in a set may be any type that is comparable, please refer to the golang language spec to get more detailed info on comparison operators.

Set implements the following interface. Click here to find examples on how to use a set.

// Interface is a type of set, which contains no duplicate elements.
type Interface interface {
	collection.Interface

	// Add adds the specified values to this set if they are not already present.
	// It returns false if any value is already present.
	Add(vals ...interface{}) bool
	// Contains returns true if this set contains the specified element.
	Contains(val interface{}) bool
	// Remove removes the specified element from this set if it is present.
	// It returns false if the target value isn't present, otherwise returns true.
	Remove(val interface{}) bool
	// Iterate iterates all the elements in this set.
	Iterate(cb IterateCallback)
}

Please import the following package in order to use set,

import (
	"github.com/ahrtr/gocontainer/set"
)

Call set.New() to create a set,

New() Interface

The following is a simple example for set,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/set"
)

func main() {
	s := set.New()

	values := []int{5, 3, 9, 7, 6}
	for _, v := range values {
		s.Add(v)
	}

	for _, v := range values {
		fmt.Printf("s.Contains(%v) = %t\n", v, s.Contains(v))
	}

	// iterate all the elements, the callback function's signature:
	//   type IterateCallback func(interface{}) bool
	s.Iterate(func(v interface{}) bool {
		fmt.Printf("Iterate callback: %v\n", v)
		return true
	})

	s.Remove(6)
}

Applications are supposed to define a callback function (see below) when iterating a set.

// IterateCallback is the signature of the callback function called by Iterate.
// If the callback function returns false, then the iteration breaks.
type IterateCallback func(interface{}) bool

The following snip shows how to iterate a set. Please see the example to get more detailed info.

// To iterate over a set (where s is an instance of set.Interface):
s.Iterate(func(v interface{}) bool {
	// Do something with v

	// If you want to break the iteration, then return a false
	return true
})

List

This library implements two kinds of list, which are ArrayList and LinkedList, both of which implement the following interface. Click here to find examples on how to use a list.

// Interface is a type of list, both ArrayList and LinkedList implement this interface.
type Interface interface {
	collection.Interface

	// Add appends the specified elements to the end of this list.
	Add(vals ...interface{})
	// AddTo inserts the specified element at the specified position in this list.
	AddTo(index int, val interface{}) error

	// Contains returns true if this list contains the specified element.
	Contains(val interface{}) bool
	// Get returns the element at the specified positon in this list. The index must be in the range of [0, size).
	Get(index int) (interface{}, error)

	// Remove removes the element at the specified position in this list.
	// It returns an error if the index is out of range.
	Remove(index int) (interface{}, error)
	// RemoveByValue removes the first occurence of the specified element from this list, if it is present.
	// It returns false if the target value isn't present, otherwise returns true.
	RemoveByValue(val interface{}) bool

	// Sort sorts the element using default options below. It sorts the elements into ascending sequence according to their natural ordering.
	//     reverse: false
	//     comparator: nil
	Sort()
	// SortWithOptions sorts the elements in the list.
	// Parameters:
	//     reverse: whether sort the data in reverse ordering
	//     c:       sort the data according to the provided comparator
	// If reverse is true, and a comparator is also provided, then the result will be the reverse sequence as the comparator generates.
	SortWithOptions(reverse bool, c utils.Comparator)

	// Iterator returns an iterator over the elements in this list in proper sequence.
	Iterator() (func() (interface{}, bool), bool)
	// ReverseIterator returns an iterator over the elements in this list in reverse sequence as Iterator.
	ReverseIterator() (func() (interface{}, bool), bool)
}

Please import the following package in order to use list (arrayList or linkedList),

import (
	"github.com/ahrtr/gocontainer/list"
)

Call list.NewArrayList() and list.NewLinkedList() to create a ArrayList and a LinkedList respectively,

NewArrayList() Interface
NewLinkedList() Interface

The following is a simple example for arrayList,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/list"
)

func main() {
	al := list.NewArrayList()
	values := []int{5, 7, 12, 9}
	for _, v := range values {
		al.Add(v)
	}

	al.AddTo(2, 18)
	v3, _ := al.Remove(3)
	fmt.Printf("al.Remove(3) = %v\n", v3)

	// Iterate all the elements 
	fmt.Println("Iterate: ")
	for i := 0; i < al.Size(); i++ {
		v, _ := al.Get(i)
		fmt.Printf("    Index: %d, value: %v\n", i, v)
	}
}

The following is a simple example for linkedList,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/list"
)
func main() {
	ll := list.NewLinkedList()
	values := []int{5, 7, 12, 9}
	for _, v := range values {
		ll.Add(v)
	}

	ll.AddTo(2, 18)
	v3, _ := ll.Remove(3)
	fmt.Printf("ll.Remove(3) = %v\n", v3)


	// Iterate all the elements
	fmt.Println("Iterate: ")
	it, hasNext := ll.Iterator()
	var v interface{}
	for hasNext {
		v, hasNext = it()
		fmt.Printf("    Value: %v\n", v)
	}
}

A list can be sorted using one of the following two methods. The first method Sort() sorts the list into ascending sequence according to the natural ordering of its elements by default; actually it just calls the second method SortWithOptions(false, nil) using the default parameters. SortWithOptions sorts the list according to the provided parameters. Please get more detailed info in Comparator

Sort()
SortWithOptions(reverse bool, c utils.Comparator)

There are multiple ways to iterate a list. The following snips show how to iterate a list (arrayList or linkedList),

// To iterate over a list (where l is an instance of list.Interface):
it, hasNext := l.Iterator()
var v interface{}
for hasNext {
	v, hasNext = it()
	// do something with v
}
// To iterate over a list (where l is an instance of list.Interface):
// This approach isn't efficient for linkedList.
for i:=0; i<l.Len(); i++ {
	v, _ := l.Get(i)
	// Do something with v
}
// To iterate over a list in reverse order (where l is an instance of list.Interface):
it, hasPrev := l.ReverseIterator()
var v interface{}
for hasPrev {
	v, hasPrev = it()
	// do something with v
}
// To iterate over a list in reverse order (where l is an instance of list.Interface):
// This approach isn't efficient for linkedList.
for i:=l.Len()-1; i>=0; i-- {
	v, _ := l.Get(i)
	// Do something with v
}

PriorityQueue

PriorityQueue is an unbounded priority queue based on a priority heap. It implements the following interface. Click here to find examples on how to use a priority queue.

// Interface is a type of priority queue, and priorityQueue implement this interface.
type Interface interface {
	queue.Interface

	// WithComparator sets a utils.Comparator instance for the queue.
	// It's used to imposes a total ordering on the elements in the queue.
	WithComparator(c utils.Comparator) Interface
	// WithMinHeap configures whether or not using min-heap.
	// If not configured, then it's min-heap by default.
	WithMinHeap(isMinHeap bool) Interface

	// Contains returns true if this queue contains the specified element.
	Contains(val interface{}) bool
	// Remove a single instance of the specified element from this queue, if it is present.
	// It returns false if the target value isn't present, otherwise returns true.
	Remove(val interface{}) bool
}

Please import the following package in order to use priorityQueue,

import (
	"github.com/ahrtr/gocontainer/queue/priorityqueue"
)

Call priorityqueue.New() to create a PriorityQueue,

New() Interface

The following is a simple example for priorityQueue,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/queue/priorityqueue"
)

func main() {
	pq := priorityqueue.New()

	values := []string{"benjamin", "alice", "john", "tom", "bill"}

	for _, v := range values {
		pq.Add(v)
	}

	for _, v := range values {
		fmt.Printf("pq.Contains(%v) = %t\n", v, pq.Contains(v))
	}

	fmt.Printf("pq.Remove(john) = %t\n", pq.Remove("john"))

	for pq.Peek() != nil {
		fmt.Printf("pq.Peek() = %v\n", pq.Peek())
		fmt.Printf("pq.Poll() = %v\n", pq.Poll())
	}
}

A utils.Comparator instance can be provided for a priorityQueue by method WithComparator, please get more detailed info in Comparator.

WithComparator(c gsort.Comparator) Interface

A priorityQueue can be configured to use min-heap or max-heap using method WithMinHeap. If the parameter is true, then it's a min-heap, which is the default option as well; otherwise, it's a max-heap.

WithMinHeap(isMinHeap bool) Interface

LinkedMap

LinkedMap is based on a map and a doubly linked list. The iteration ordering is normally the order in which keys were inserted into the map, or the order in which the keys were accessed if the accessOrder flag is set. It implements the following interface. Click here to find examples on how to use a linked map.

// Interface is a type of linked map, and linkedMap implements this interface.
type Interface interface {
	collection.Interface

	// Put associates the specified value with the specified key in this map. If the map previously contained a mapping for the key,
	// the old value is replaced by the specified value.
	// It returns the previous value associated with the specified key, or nil if there was no mapping for the key.
	// A nil return can also indicate that the map previously associated nil with the specified key.
	Put(k, v interface{}) interface{}

	// WithAccessOrder configures the iteration ordering for this linked map,
	// true for access-order, and false for insertion-order.
	WithAccessOrder(accessOrder bool) Interface

	// Get returns the value to which the specified key is mapped, or nil if this map contains no mapping for the key.
	Get(k interface{}) interface{}
	// GetOrDefault returns the value to which the specified key is mapped, or the defaultValue if this map contains no mapping for the key.
	GetOrDefault(k, defaultValue interface{}) interface{}

	// ContainsKey returns true if this map contains a mapping for the specified key.
	ContainsKey(k interface{}) bool
	// ContainsValue returns true if this map maps one or more keys to the specified value.
	ContainsValue(v interface{}) bool

	// Remove removes the mapping for a key from this map if it is present.
	// It returns the value to which this map previously associated the key, and true,
	// or nil and false if the map contained no mapping for the key.
	Remove(k interface{}) (interface{}, bool)
	// RemoveFirstElement removes the first element from this map, which is the head of the list.
	// It returns the (key, value, true) if the map isn't empty, or (nil, nil, false) if the map is empty.
	RemoveFirstElement() (interface{}, interface{}, bool)
	// RemoveLastElement removes the last element from this map, which is the tail of the list.
	// It returns the (key, value, true) if the map isn't empty, or (nil, nil, false) if the map is empty.
	RemoveLastElement() (interface{}, interface{}, bool)

	// Iterator returns an iterator over the elements in this map in proper sequence.
	Iterator() (func() (interface{}, interface{}, bool), bool)
	// ReverseIterator returns an iterator over the elements in this map in reverse sequence as Iterator.
	ReverseIterator() (func() (interface{}, interface{}, bool), bool)
}

Please import the following package in order to use linkedMap,

import (
	"github.com/ahrtr/gocontainer/map/linkedmap"
)

Call linkedmap.New() to create a linked map,

New() Interface

The following is a simple example for linkedMap,

package main

import (
	"fmt"

	"github.com/ahrtr/gocontainer/map/linkedmap"
)

func main() {
	lm := linkedmap.New()

	keys := []interface{}{24, 43, 18, 23, 35}
	values := []interface{}{"benjamin", "alice", "john", "tom", "bill"}
	for i := 0; i < len(keys); i++ {
		lm.Put(keys[i], values[i])
	}

	for _, k := range keys {
		fmt.Printf("Get(%v) = %v\n", k, lm.Get(k))
	}

	v, _ := lm.Remove(18)
	fmt.Printf("The value associated with 18 is %v\n", v)

	k, v, _ := lm.RemoveFirstElement()
	fmt.Printf("The first element removed is (%v, %v)\n", k, v)

	k, v, _ = lm.RemoveLastElement()
	fmt.Printf("The last element removed is (%v, %v)\n", k, v)
}

If the order in which the keys were accessed is expected for the iteration ordering, then the accessOrder flag should be set,

// WithAccessOrder configures the iteration ordering for this linked map,
// true for access-order, and false for insertion-order.
WithAccessOrder(accessOrder bool) Interface

The following snips show how to interate a linkedMap,

// To iterate over an linkedMap (where lm is an instance of linkedmap.Interface):
it, hasNext := lm.Iterator()
var k, v interface{}
for hasNext {
	k, v, hasNext = it()
	// do something with k & v
}
// To iterate over an linkedMap in reverse order (where lm is an instance of linkedmap.Interface):
it, hasPrev := lm.ReverseIterator()
var k, v interface{}
for hasPrev {
	k, v, hasPrev = it()
	// do something with k & v
}

Others

More containers will be added soon. Please also kindly let me know if you need any other kinds of containers. Feel free to raise issues.

Utilities

Comparator

The comparator utility contains a function "Compare" and an interface "Comparator",

// Compare compares its two arguments if they have the same type and are comparable, otherwise returns an error in the second return value.
// It returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
func Compare(v1 interface{}, v2 interface{}) (int, error)

// Comparator imposes a total ordering on some collection of objects, and it allows precise control over the sort order.
type Comparator interface {
	// Compare compares its two arguments for order.
	// It returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
	Compare(v1 interface{}, v2 interface{}) (int, error)
}

The function "Compare" is used to compare two values of golang build-in data types listed below. The two arguments must be the same data type, otherwise an error in the second return value will be returned. It returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second one. Note that for bool, a false is regarded as less than a true.

  • bool
  • int
  • int8
  • int16
  • int32
  • int64
  • uint
  • uint8
  • uint16
  • uint32
  • uint64
  • float32
  • float64
  • string
  • byte
  • rune
  • time.Time

Applications can also provide a utils.Comparators instance to customize the comparing. The following example demonstrates how to compare two students by age.

type student struct {
	name string
	age int
}

type MyComparator struct{}

func (c *MyComparator) Compare(v1, v2 interface{}) (int, error) {
	e1, e2 := v1.(*student), v2.(*student)
	if e1.age < e2.age {
		return -1, nil
	}
	if e1.age > e2.age {
		return 1, nil
	}
	return 0, nil
}

Sort

The sort utility provides the following two functions to sort the values in the provided slice.

// Sort sorts values into ascending sequence according to their natural ordering, or according to the provided comparator.
func Sort(values []interface{}, c Comparator)

// ReverseSort sorts the values into opposite sequence to Sort
func ReverseSort(values []interface{}, c Comparator)

Both of the above functions sort values in-place. The first function "Sort" sorts the values into ascending sequence according to their natural ordering, or according to the provided comparator. The second function "ReverseSort" sorts the values into opposite sequence to the first function "Sort".

Heap

The heap utility provides the following functions. It's useful for containers like priorityQueue. Please read the comment for each function to get more detailed info.

// HeapInit establishes the heap from scratch. The operation is in-place.
// Parameters:
//     values:    the data source of the heap
//     isMinHeap: true for min-hap, false for max-heap
//     c:         an utils.Comparator instance
func HeapInit(values []interface{}, isMinHeap bool, c Comparator) 

// HeapPostPush moves the new element up until it gets to the right place. The operation is in-place.
// Push workflow (this functions takes care of the second step):
//     1.  add a new element to the end of the slice;
//     2*. call this method to move the new element up until it gets to the right place.
// Parameters:
//     values:    the data source of the heap
//     isMinHeap: true for min-hap, false for max-heap
//     c:         an utils.Comparator instance
func HeapPostPush(values []interface{}, isMinHeap bool, c Comparator) 

// HeapPrePop move the top element down until it gets to the right place. The operation is in-place.
// Pop workflow (this function takes care of step 1 and 2):
//    1*. swap the first and the last element;
//    2*. move the first/top element down until it gets to the right place;
//    3.  remove the last element, and return the removed element to users.
// Parameters:
//     values:    the data source of the heap
//     isMinHeap: true for min-hap, false for max-heap
//     c:         an utils.Comparator instance
func HeapPrePop(values []interface{}, isMinHeap bool, c Comparator)

// HeapPreRemove move the element with the specified index down or up until it gets to the right place. The operation is in-place.
// Remove workflow(this function takes care of step 1 and 2):
//    1*. swap the element with the specifed index and the last element;
//    2*. move the element with the specified index down or up until it gets to the right place;
//    3.  remove the last element, and return the removed element to users.
// Parameters:
//     values:    the data source of the heap
//     index:     the element at the specified index will be removed after calling this function
//     isMinHeap: true for min-hap, false for max-heap
//     c:         an utils.Comparator instance
func HeapPreRemove(values []interface{}, index int, isMinHeap bool, c Comparator) 

// HeapPostUpdate re-establishes the heap ordering after the element at the specified index has changed its value. The operation is in-place.
// Update workflow (this function takes care of the second step):
//    1.  update the element's value at the specified index;
//    2*. call this function to move the updated element down or up until it gets to the right place.
// Parameters:
//     values:    the data source of the heap
//     index:     the element at the specified index should have already been updated before calling this function
//     isMinHeap: true for min-hap, false for max-heap
//     c:         an utils.Comparator instance
func HeapPostUpdate(values []interface{}, index int, isMinHeap bool, c Comparator)

Contribute to this repo

Anyone is welcome to contribute to this repo. Please raise an issue firstly, then fork this repo and submit a pull request.

Currently this repo is under heavily development, any helps are appreciated!

Support

If you need any support, please raise issues.

If you have any suggestions or proposals, please also raise issues. Thanks!