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
• Common Interface
• Containers
  • Stack
  • Queue
  • Set
  • List
  • PriorityQueue
  • LinkedMap
  • BTree
  • Others
• Utilities
  • Comparator
  • Sort
  • Heap
• Contribute to this repo
• Support

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
• BTree

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{}
	// Peek retrieves, but does not remove, the element on the top of this stack, or return nil if this stack is empty.
	Peek() 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 position 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 th