README
¶
Deque
Introduction
Deque is an fast and flexible implementation of the deque ADT in Go. Supporting this claim, the implementation comes with two notable features over simply satisfying the deque method contract:
- Pluggable deque backends;
- Optional (abeit simple) general thread-safety.
Install
go get -v bitbucket.org/jvulic/deque
Usage
Creating a deque; both safe and non-safe varients.
deque.New() // default non-safe deque
deque.New(deque.Backend(deque.NewRD())) // non-safe deque with ring-buffer backend
deque.New(deque.Safe()) // default thread-safe deque
deque.New(deque.Safe(), deque.Backend(deque.NewRD())) // thread-safe deque with ring-buffer backend
Simple usage example.
// Create a deque.
d := deque.New()
// Put some content into the deque using PushBack() and PushFront() methods.
d.PushFront(2)
d.PushBack(3)
d.PushFront(1)
d.PushBack(4)
// Lets see what elements are at the front and back of the deque.
first := d.Front() // 1
last := d.Back() // 4
fmt.Printf("%v is first, and %v is last\n", first, last)
// Lets print out the contents of the deque either front->back or back->front.
if rand.Int() % 2 == 0 {
fmt.Println("Going front->back!")
for d.Length() > 0 {
fmt.Println(d.Front())
d.PopFront()
}
} else {
fmt.Println("Going back->front!")
for d.Length() > 0 {
fmt.Println(d.Back())
d.PopBack()
}
}
Backends
This implementation comes with the ability to select or even integrate your own deque backend seemlessly. This enables easy switching between different implementations to best-fit a use case, or integrating your own inspired deque backend. Generally speaking, most cases where a full deque method set is necessary a backend swap will trade speed for memory efficiency and vise versa. However, significant performance gains can be made when only requiring a subset of deque methods; for example when using a deque to implement another ADT like a stack or queue.
Currently supports the following backends:
Doubly-Linked List
Implements a deque using a doubly-linked list. The doubly-linked list
implementation is provided by the container/list package.
Ring-Buffer
Implements a deque using a slice treated as a ring buffer. Cuts down memory usage and GC pauses by carefully managing the interal buffer.
Slice
Implements a deque using a slice buffer, and slice operations.
Tests
Tests can be run by executing make test.
Benchmarks
Benchmarks can be run by executing make bench.
Below is an example of the benchmarking output:
PASS
BenchmarkList-8 5000000 235 ns/op 41 B/op 1 allocs/op
BenchmarkListSafe-8 3000000 433 ns/op 41 B/op 1 allocs/op
BenchmarkRing-8 10000000 320 ns/op 32 B/op 0 allocs/op
BenchmarkRingSafe-8 3000000 465 ns/op 28 B/op 0 allocs/op
BenchmarkSlice-8 50000 284624 ns/op 102597 B/op 2 allocs/op
BenchmarkSliceSafe-8 50000 285532 ns/op 102597 B/op 2 allocs/op
ok bitbucket.org/jvulic/deque 37.856s
License
Documentation
¶
Overview ¶
Package deque provides a flexible implementation of the deque ADT.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Deque ¶
type Deque interface {
// Returns the current length of the deque.
Length() int
// Returns the current capacity of the deque. Returns -1 for inf capacity.
Capacity() int
// Returns the element at the head of the deque; does NOT remove it. Panics
// if the deque is empty.
Front() interface{}
// Returns the element at the back of the deque; does NOT remove it. Panics
// if the deque is empty.
Back() interface{}
// Adds an element to the head of the deque.
PushFront(elem interface{})
// Adds an element tot he tail of the deque.
PushBack(elem interface{})
// Removes the element at the head of the deque. Panics if the deque is empty.
PopFront()
// Removes the element at the tail of the deque. Panics if the deque is empty.
PopBack()
}
Deque defines the deque ADT.
Source Files