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