lane

package module
v1.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 29, 2018 License: MIT Imports: 5 Imported by: 8

README

lane

Lane package provides queue, priority queue, stack and deque data structures implementations. Its was designed with simplicity, performance, and concurrent usage in mind.

Installation

$ go get gopkg.in/oleiade/lane.v1

Usage

Import lane using the gopkg url:

import (
    lane "gopkg.in/oleiade/lane.v1"
)
Priority Queue

Pqueue is a heap priority queue data structure implementation. It can be whether max or min ordered, is synchronized and is safe for concurrent operations. It performs insertion and max/min removal in O(log N) time.

Example
	// Let's create a new max ordered priority queue
	var priorityQueue *PQueue = NewPQueue(MINPQ)

	// And push some prioritized content into it
	priorityQueue.Push("easy as", 3)
	priorityQueue.Push("123", 2)
	priorityQueue.Push("do re mi", 4)
	priorityQueue.Push("abc", 1)

	// Now let's take a look at the min element in
	// the priority queue
	headValue, headPriority := priorityQueue.Head()
	fmt.Println(headValue)    // "abc"
	fmt.Println(headPriority) // 1

	// Okay the song order seems to be preserved, let's
	// roll
	var jacksonFive []string = make([]string, priorityQueue.Size())

	for i := 0; i < len(jacksonFive); i++ {
		value, _ := priorityQueue.Pop()

		jacksonFive[i] = value.(string)
	}

	fmt.Println(strings.Join(jacksonFive, " "))
Deque

Deque is a head-tail linked list data structure implementation. It is based on a doubly-linked list container, so that every operations time complexity is O(1). All operations over an instiated Deque are synchronized and safe for concurrent usage.

Deques can optionally be created with a limited capacity, whereby the return value of the Append and Prepend return false if the Deque was full and the item was not added.

Example
	// Let's create a new deque data structure
	var deque *Deque = NewDeque()

	// And push some content into it using the Append
	// and Prepend methods
	deque.Append("easy as")
	deque.Prepend("123")
	deque.Append("do re mi")
	deque.Prepend("abc")

	// Now let's take a look at what are the first and
	// last element stored in the Deque
	firstValue := deque.First()
	lastValue := deque.Last()
	fmt.Println(firstValue) // "abc"
	fmt.Println(lastValue)  // 1

	// Okay now let's play with the Pop and Shift
	// methods to bring the song words together
	var jacksonFive []string = make([]string, deque.Size())

	for i := 0; i < len(jacksonFive); i++ {
		value := deque.Shift()
		jacksonFive[i] = value.(string)
	}

	// abc 123 easy as do re mi
	fmt.Println(strings.Join(jacksonFive, " "))

	// Let's create a new musical quartet
	quartet := NewCappedDeque(4)

	// List of young hopeful musicians
	musicians := []string{"John", "Paul", "George", "Ringo", "Stuart"}

	// Add as many of them to the band as we can.
	for _, name := range musicians {
		if quartet.Append(name) {
			fmt.Printf("%s is in the band!\n", name)
		} else {
			fmt.Printf("Sorry - %s is not in the band.\n", name)
		}
	}

	// Assemble our new rock sensation
	var beatles = make([]string, quartet.Size())

	for i := 0; i < len(beatles); i++ {
		beatles[i] = quartet.Shift().(string)
	}

	fmt.Println("The Beatles are:", strings.Join(beatles, ", "))
Queue

Queue is a FIFO ( First in first out ) data structure implementation. It is based on a deque container and focuses its API on core functionalities: Enqueue, Dequeue, Head, Size, Empty. Every operations time complexity is O(1). As it is implemented using a Deque container, every operations over an instiated Queue are synchronized and safe for concurrent usage.

Example
    import (
        "fmt"
        "github.com/oleiade/lane"
        "sync"
    )

    func worker(item interface{}, wg *sync.WaitGroup) {
        fmt.Println(item)
        wg.Done()
    }


    func main() {

        queue := lane.NewQueue()
        queue.Enqueue("grumpyClient")
        queue.Enqueue("happyClient")
        queue.Enqueue("ecstaticClient")

        var wg sync.WaitGroup

        // Let's handle the clients asynchronously
        for queue.Head() != nil {
            item := queue.Dequeue()

            wg.Add(1)
            go worker(item, &wg)
        }

        // Wait until everything is printed
        wg.Wait()
    }
Stack

Stack is a LIFO ( Last in first out ) data structure implementation. It is based on a deque container and focuses its API on core functionalities: Push, Pop, Head, Size, Empty. Every operations time complexity is O(1). As it is implemented using a Deque container, every operations over an instiated Stack are synchronized and safe for concurrent usage.

Example
	// Create a new stack and put some plates over it
	var stack *Stack = NewStack()

	// Let's put some plates on the stack
	stack.Push("redPlate")
	stack.Push("bluePlate")
	stack.Push("greenPlate")

	fmt.Println(stack.Head) // greenPlate

	// What's on top of the stack?
	value := stack.Pop()
	fmt.Println(value.(string)) // greenPlate

	stack.Push("yellowPlate")
	value = stack.Pop()
	fmt.Println(value.(string)) // yellowPlate

	// What's on top of the stack?
	value = stack.Pop()
	fmt.Println(value.(string)) // bluePlate

	// What's on top of the stack?
	value = stack.Pop()
	fmt.Println(value.(string)) // redPlate

Documentation

For a more detailled overview of lane, please refer to Documentation

Bitdeli Badge

Documentation

Overview

Lane package provides queue, priority queue, stack and deque data structures implementations. Its was designed with simplicity, performance, and concurrent usage in mind.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Deque 

type Deque struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Deque is a head-tail linked list data structure implementation. It is based on a doubly linked list container, so that every operations time complexity is O(1).

every operations over an instiated Deque are synchronized and safe for concurrent usage.

Example 
// Let's create a new deque data structure
var deque *Deque = NewDeque()

// And push some content into it using the Append
// and Prepend methods
deque.Append("easy as")
deque.Prepend("123")
deque.Append("do re mi")
deque.Prepend("abc")

// Now let's take a look at what are the first and
// last element stored in the Deque
firstValue := deque.First()
lastValue := deque.Last()
fmt.Println(firstValue) // "abc"
fmt.Println(lastValue)  // 1

// Okay now let's play with the Pop and Shift
// methods to bring the song words together
var jacksonFive []string = make([]string, deque.Size())

for i := 0; i < len(jacksonFive); i++ {
	value := deque.Shift()
	jacksonFive[i] = value.(string)
}

// abc 123 easy as do re mi
fmt.Println(strings.Join(jacksonFive, " "))

Output:

func NewCappedDeque 

func NewCappedDeque(capacity int) *Deque

NewCappedDeque creates a Deque with the specified capacity limit.

func NewDeque 

func NewDeque() *Deque

NewDeque creates a Deque.

func (*Deque) Append 

func (s *Deque) Append(item interface{}) bool

Append inserts element at the back of the Deque in a O(1) time complexity, returning true if successful or false if the deque is at capacity.

func (*Deque) Capacity 

func (s *Deque) Capacity() int

Capacity returns the capacity of the deque, or -1 if unlimited

func (*Deque) Empty 

func (s *Deque) Empty() bool

Empty checks if the deque is empty

func (*Deque) First 

func (s *Deque) First() interface{}

First returns the first value stored in the deque in a O(1) time complexity

func (*Deque) Full 

func (s *Deque) Full() bool

Full checks if the deque is full

func (*Deque) Last 

func (s *Deque) Last() interface{}

Last returns the last value stored in the deque in a O(1) time complexity

func (*Deque) Pop 

func (s *Deque) Pop() interface{}

Pop removes the last element of the deque in a O(1) time complexity

func (*Deque) Prepend 

func (s *Deque) Prepend(item interface{}) bool

Prepend inserts element at the Deques front in a O(1) time complexity, returning true if successful or false if the deque is at capacity.

func (*Deque) Shift 

func (s *Deque) Shift() interface{}

Shift removes the first element of the deque in a O(1) time complexity

func (*Deque) Size 

func (s *Deque) Size() int

Size returns the actual deque size

type PQType 

type PQType int

PQType represents a priority queue ordering kind (see MAXPQ and MINPQ) 

const (
	MAXPQ PQType = iota
	MINPQ
)

type PQueue 

type PQueue struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

PQueue is a heap priority queue data structure implementation. It can be whether max or min ordered and it is synchronized and is safe for concurrent operations.

Example 
// Let's create a new max ordered priority queue
var priorityQueue *PQueue = NewPQueue(MINPQ)

// And push some prioritized content into it
priorityQueue.Push("easy as", 3)
priorityQueue.Push("123", 2)
priorityQueue.Push("do re mi", 4)
priorityQueue.Push("abc", 1)

// Now let's take a look at the min element in
// the priority queue
headValue, headPriority := priorityQueue.Head()
fmt.Println(headValue)    // "abc"
fmt.Println(headPriority) // 1

// Okay the song order seems to be preserved, let's
// roll
var jacksonFive []string = make([]string, priorityQueue.Size())

for i := 0; i < len(jacksonFive); i++ {
	value, _ := priorityQueue.Pop()

	jacksonFive[i] = value.(string)
}

fmt.Println(strings.Join(jacksonFive, " "))

Output:

func NewPQueue 

func NewPQueue(pqType PQType) *PQueue

NewPQueue creates a new priority queue with the provided pqtype ordering type

func (*PQueue) Empty 

func (pq *PQueue) Empty() bool

Check queue is empty

func (*PQueue) Head 

func (pq *PQueue) Head() (interface{}, int)

Head returns the highest/lowest priority item (depending on whether you're using a MINPQ or MAXPQ) from the priority queue

func (*PQueue) InQueueHash added in v1.0.2 

func (pq *PQueue) InQueueHash(hash string) bool

func (*PQueue) InQueueSession added in v1.0.2 

func (pq *PQueue) InQueueSession(s *melody.Session) bool

func (*PQueue) Pop 

func (pq *PQueue) Pop() (interface{}, int)

Pop and returns the highest/lowest priority item (depending on whether you're using a MINPQ or MAXPQ) from the priority queue

func (*PQueue) Push 

func (pq *PQueue) Push(value interface{}, priority int)

Push the value item into the priority queue with provided priority.

func (*PQueue) RemoveHash added in v1.0.2 

func (pq *PQueue) RemoveHash(hash string)

func (*PQueue) RemoveSession added in v1.0.2 

func (pq *PQueue) RemoveSession(s *melody.Session)

func (*PQueue) Size 

func (pq *PQueue) Size() int

Size returns the elements present in the priority queue count

type Queue 

type Queue struct {
	*Deque
}

Queue is a FIFO (First in first out) data structure implementation. It is based on a deque container and focuses its API on core functionalities: Enqueue, Dequeue, Head, Size, Empty. Every operations time complexity is O(1).

As it is implemented using a Deque container, every operations over an instiated Queue are synchronized and safe for concurrent usage.

Example 
// Create a new queue and pretend we're handling starbucks
// clients
var queue *Queue = NewQueue()

// Let's add the incoming clients to the queue
queue.Enqueue("grumpyClient")
queue.Enqueue("happyClient")
queue.Enqueue("ecstaticClient")

fmt.Println(queue.Head) // grumpyClient

// Let's handle the clients asynchronously
for client := queue.Dequeue(); client != nil; {
	go fmt.Println(client)
}

Output:

func NewQueue 

func NewQueue() *Queue

func (*Queue) Dequeue 

func (q *Queue) Dequeue() interface{}

Dequeue removes and returns the front queue item

func (*Queue) Enqueue 

func (q *Queue) Enqueue(item interface{})

Enqueue adds an item at the back of the queue

func (*Queue) Head 

func (q *Queue) Head() interface{}

Head returns the front queue item

type Stack 

type Stack struct {
	*Deque
}

Stack is a LIFO (Last in first out) data structure implementation. It is based on a deque container and focuses its API on core functionalities: Push, Pop, Head, Size, Empty. Every operations time complexity is O(1).

As it is implemented using a Deque container, every operations over an instiated Stack are synchronized and safe for concurrent usage.

Example 
// Create a new stack and put some plates over it
var stack *Stack = NewStack()

// Let's put some plates on the stack
stack.Push("redPlate")
stack.Push("bluePlate")
stack.Push("greenPlate")

fmt.Println(stack.Head) // greenPlate

// What's on top of the stack?
value := stack.Pop()
fmt.Println(value.(string)) // greenPlate

stack.Push("yellowPlate")
value = stack.Pop()
fmt.Println(value.(string)) // yellowPlate

// What's on top of the stack?
value = stack.Pop()
fmt.Println(value.(string)) // bluePlate

// What's on top of the stack?
value = stack.Pop()
fmt.Println(value.(string)) // redPlate

Output:

func NewStack 

func NewStack() *Stack

func (*Stack) Head 

func (s *Stack) Head() interface{}

Head returns the item on the top of the stack

func (*Stack) Pop 

func (s *Stack) Pop() interface{}

Pop removes and returns the item on the top of the Stack

func (*Stack) Push 

func (s *Stack) Push(item interface{})

Push adds on an item on the top of the Stack

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.