deque

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:

1. Pluggable deque backends;
2. 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

MIT License

Documentation

Overview

Package deque provides a flexible implementation of the deque ADT.

Index

• type Deque
  • func New(opt ...Option) Deque
  • func NewLD() Deque
  • func NewRD() Deque
  • func NewSD() Deque
• type Option
  • func Backend(d Deque) Option
  • func Safe() Option

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.

func New

func New(opt ...Option) Deque

New creates a new deque.

func NewLD

func NewLD() Deque

NewLD creates a new doubly-linked list based deque.

func NewRD

func NewRD() Deque

NewRD creates a new ring-buffer based deque.

func NewSD

func NewSD() Deque

NewSD creates a new slice based deque.

type Option

type Option func(*options)

Option configures aspects of the deque.

func Backend

func Backend(d Deque) Option

Backend returns an Option that sets the deque backend.

func Safe

func Safe() Option

Safe returns an Option that synchronizes access to the underlying deque implementation.