deque

README

deque

Deque is deque container using Go generics.

Wikipedia says:

In computer science, a double-ended queue (abbreviated to deque, pronounced deck, like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Usage

// Make a new deque of ints
d := deque.Of(9, 8, 7, 6)

// Sort it
sort.Sort(deque.Sortable[int]{d})
// d is 6, 7, 8, 9

// Add 5, 4, 3, 2, 1 to the front
for i := 5; i > 0; i-- {
    d.PushFront(i)
}

// Deque{ len: 9, cap: 16, items: [1, 2, 3, 4, 5, 6, 7, 8, 9]}
fmt.Println(d)

// Now pop items off the tail
// Prints 9 8 7 6 5 4 3 2 1
for {
    n, ok := d.RemoveBack()
    if !ok {
        break
    }
    fmt.Print(n, " ")
}
fmt.Println()

Documentation

Overview

Package deque provides a type-safe, slice-backed, double-ended queue.

See https://en.wikipedia.org/wiki/Double-ended_queue

Index

• type Deque
  • func Make[T any](cap int) *Deque[T]
  • func Of[T any](items ...T) *Deque[T]
  • func (d *Deque[T]) Append(ts ...T)
  • func (d *Deque[T]) At(n int) (t T, ok bool)
  • func (d *Deque[T]) Back() (t T, ok bool)
  • func (d *Deque[T]) Cap() int
  • func (d *Deque[T]) Clip()
  • func (d *Deque[T]) Front() (v T, ok bool)
  • func (d *Deque[T]) Grow(n int)
  • func (d *Deque[T]) Head() (t T, ok bool)
  • func (d *Deque[T]) Len() int
  • func (d *Deque[T]) PopHead() (t T, ok bool)
  • func (d *Deque[T]) PopTail() (t T, ok bool)
  • func (d *Deque[T]) PushBack(v T)
  • func (d *Deque[T]) PushBackSlice(s []T)
  • func (d *Deque[T]) PushFront(v T)
  • func (d *Deque[T]) PushHead(t T)
  • func (d *Deque[T]) PushTail(t T)
  • func (d *Deque[T]) RemoveBack() (t T, ok bool)
  • func (d *Deque[T]) RemoveFront() (t T, ok bool)
  • func (d *Deque[T]) Slice() []T
  • func (d *Deque[T]) String() string
  • func (d *Deque[T]) Swap(i, j int)
  • func (d *Deque[T]) Tail() (t T, ok bool)
• type Sortable
  • func (sd Sortable[T]) Less(i, j int) bool

Examples

• Deque

Types

type Deque

type Deque[T any] struct {
	// contains filtered or unexported fields
}

Deque is a double-ended queue. It is not concurrency safe.

Example

package main

import (
	"fmt"
	"sort"

	"github.com/carlmjohnson/deque"
)

func main() {
	// Make a new deque
	d := deque.Of(9, 8, 7, 6)
	// Sort it
	sort.Sort(deque.Sortable[int]{d})
	// Add 5, 4, 3, 2, 1 to the front
	for i := 5; i > 0; i-- {
		d.PushFront(i)
	}
	fmt.Println(d)
	// Now pop items off the tail
	for {
		n, ok := d.RemoveBack()
		if !ok {
			break
		}
		fmt.Print(n, " ")
	}
	fmt.Println()
}

Output:

Deque{ len: 9, cap: 16, items: [1, 2, 3, 4, 5, 6, 7, 8, 9]}
9 8 7 6 5 4 3 2 1

func Make

func Make[T any](cap int) *Deque[T]

Make creates a deque with a prereserved capacity.

func Of

func Of[T any](items ...T) *Deque[T]

Of constructs a new Deque.

func (*Deque[T]) Append

func (d *Deque[T]) Append(ts ...T)

Append pushes all items to the tail of the deque.

Deprecated: Use d.PushBackSlice(ts) instead.

func (*Deque[T]) At

func (d *Deque[T]) At(n int) (t T, ok bool)

At returns the zero indexed nth item of the deque, if any.

func (*Deque[T]) Back

func (d *Deque[T]) Back() (t T, ok bool)

Back returns the last value of the deque, if any.

func (*Deque[T]) Cap

func (d *Deque[T]) Cap() int

Cap returns the unused capacity of the deque.

func (*Deque[T]) Clip

func (d *Deque[T]) Clip()

Clip removes unused capacity from the deque.

func (*Deque[T]) Front

func (d *Deque[T]) Front() (v T, ok bool)

Front returns the first value of the deque, if any.

func (*Deque[T]) Grow

func (d *Deque[T]) Grow(n int)

Grow increases the deque's capacity, if necessary, to guarantee space for another n elements. After Grow(n), at least n elements can be appended to the deque without another allocation. If n is negative, Grow panics.

func (*Deque[T]) Head

func (d *Deque[T]) Head() (t T, ok bool)

Head returns the head of the deque, if any.

Deprecated: Use d.Front() instead.

func (*Deque[T]) Len

func (d *Deque[T]) Len() int

Len returns the current length of the deque.

func (*Deque[T]) PopHead

func (d *Deque[T]) PopHead() (t T, ok bool)

PopHead returns and removes the head of the deque, if any.

Deprecated: Use d.RemoveFront() instead.

func (*Deque[T]) PopTail

func (d *Deque[T]) PopTail() (t T, ok bool)

PopTail returns and removes the tail of the deque, if any.

Deprecated: Use d.RemoveBack() instead

func (*Deque[T]) PushBack

func (d *Deque[T]) PushBack(v T)

PushBack adds new value v to the end of the deque.

func (*Deque[T]) PushBackSlice

func (d *Deque[T]) PushBackSlice(s []T)

PushBackSlice adds all items in s to the back of the deque.

func (*Deque[T]) PushFront

func (d *Deque[T]) PushFront(v T)

PushFront adds a new value v to the front of the deque.

func (*Deque[T]) PushHead

func (d *Deque[T]) PushHead(t T)

PushHead adds t to the head of the deque.

Deprecated: Use d.PushFront(t) instead.

func (*Deque[T]) PushTail

func (d *Deque[T]) PushTail(t T)

PushTail adds t to the tail of the deque.

Deprecated: Use d.PushBack(t) instead.

func (*Deque[T]) RemoveBack

func (d *Deque[T]) RemoveBack() (t T, ok bool)

RemoveBack removes and returns the back of the deque, if any.

func (*Deque[T]) RemoveFront

func (d *Deque[T]) RemoveFront() (t T, ok bool)

RemoveFront removes and returns the front of the deque, if any.

func (*Deque[T]) Slice

func (d *Deque[T]) Slice() []T

Slice returns a slice with a copy of the deque.

func (*Deque[T]) String

func (d *Deque[T]) String() string

String implements fmt.Stringer.

func (*Deque[T]) Swap

func (d *Deque[T]) Swap(i, j int)

Swap swaps the elements with indexes i and j.

func (*Deque[T]) Tail

func (d *Deque[T]) Tail() (t T, ok bool)

Tail returns the tail of the deque, if any.

Deprecated: Use d.Back() instead.

type Sortable

type Sortable[T cmp.Ordered] struct {
	*Deque[T]
}

Sortable is a deque that can be sorted with sort.Sort.

func (Sortable[T]) Less

func (sd Sortable[T]) Less(i, j int) bool

Less implements sort.Interface.