depq

package module
v0.0.0-...-c9a81ca Latest Latest
Warning

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

 Go to latest Published: Aug 18, 2014 License: BSD-3-Clause Imports: 0 Imported by: 0

README

Package Implements DEPQ ( Double Ended Priority Queue ) with Golang ( google go )

GoDoc Go Walker

Priority Queue uses struct comparison methods instead of package ones. Thus gives the ability to build custom Priority Queue, while "container/heap" is array ( slice ) based only.

PQ and DEPQ are array ( slice ) based structures, which implement the corresponding interfaces. One can build tree based PQ with the ability to merge any struct which implements the interface.

Docs: GoWalker or GoDoc

To install / update

version control : git ( git --version )

go get -u -v bitbucket.org/sjbog/depq

To test

100% test coverage

go test -v -parallel=4 -cover bitbucket.org/sjbog/depq
> ok    bitbucket.org/sjbog/depq    0.028s  coverage: 100.0% of statements

####Benchmarks

go test -v -parallel=4 -bench . bitbucket.org/sjbog/depq

####Code coverage html view ( will write a coverage_profile file )

go test -parallel=4 -coverprofile="coverage_profile.out" bitbucket.org/sjbog/depq
go tool cover -html="coverage_profile.out"
License : BSD 3-Clause, see LICENSE file

Tags: golang depq implementation, go depq, golang double ended priority queue

Documentation

Overview

Double Ended Priority Queue ( https://en.wikipedia.org/wiki/Double-ended_priority_queue )

Priority Queue uses struct comparison methods instead of package ones. Thus gives the ability to build custom Priority Queue, while "container/heap" is array ( slice ) based only.

PQ and DEPQ are array ( slice ) based structures, which implement the corresponding interfaces. One can build tree based PQ with the ability to merge any struct which implements the interface. PQ and DEPQ are not thread safe. 

type PQ struct implements Min priority queue.

Notes: go slices don't shrink back, consider this when using huge amounts of data

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type DEPQ 

type DEPQ []Item_Interface

Array ( slice ) based implementation of double ended priority queue. Implements DEPQ_Interface.

Example usage:

1) Create a struct which implements Item_Interface 

type My_Item struct {
	Value	int
}

func ( self  My_Item )	Is_Less ( other  Item_Interface )	bool	{
	return	self.Value < other.( My_Item ).Value
}

// implement Is_More and Copy

  1. Create a new ( array based ) PQ var pq = depq.New_DEPQ ( My_Item { 15 }, My_Item { 11 }, My_Item { 2 }, My_Item { 4 }, My_Item { 8 } )

    pq.Peek () // == 2 <= shows Min value, but doesn't pop pq.Peek_Max () // == 15 <= shows Max value, but doesn't pop

    pq.Push ( My_Item { -1 } )

    pq.Pop () // == -1 <= pops Min value pq.Pop_Max () // == 15 <= pops Max value

func New_DEPQ 

func New_DEPQ(items ...Item_Interface) *DEPQ

Creates and fills a new Double Ended Priority Queue

func (*DEPQ) Copy 

func (self *DEPQ) Copy() PQ_Interface

Makes a deep copy of current values. Calls Item_Interface.Copy () on every item

func (*DEPQ) Heapify 

func (self *DEPQ) Heapify(offset uint)

In-place restructure. Is used to sort raw slice into a Double Ended Priority Queue ordered slice

func (*DEPQ) Len 

func (self *DEPQ) Len() uint

Returns number of items in the underlying array ( length of slice, not capacity )

func (*DEPQ) Merge 

func (self *DEPQ) Merge(other PQ_Interface)

Pushes values of `other` PQ into self. Copy by reference on pointer values ( shallow copy ) 

Warning : this operation will purge `other` ( it will be empty ).

To make a merge with deep copy use 

pq1.Merge ( pq2.Copy () )
Example (ByReferenceCompatibility)

Same as ExamplePQ_Merge_byReference example, but merges PQ and DEPQ 

var (
	pq1 = *New_PQ(&My_Item_Ref{-1}, &My_Item_Ref{2}, &My_Item_Ref{4}, &My_Item_Ref{8})
	pq2 = *New_DEPQ(&My_Item_Ref{-1}, &My_Item_Ref{2}, &My_Item_Ref{4}, &My_Item_Ref{8})

	pq1_backup = make([]Item_Interface, pq1.Len())
	pq2_backup = make([]Item_Interface, pq2.Len())
	tmp        string

	fnCmp = func(pq1, pq2 []Item_Interface) {
		fmt.Print("Do PQ1 & PQ2 reference same item ? : [ ")

		for _, pq1_value := range pq1 {
			tmp = "no "

			for _, pq2_value := range pq2 {
				if pq1_value == pq2_value {
					tmp = "yes "
					break
				}
			}

			fmt.Print(tmp)
		}

		fmt.Println("]")
	}
)
//	fmt.Println ( fmt.Sprintf ( "Initially PQ1 : %v", pq1 ) )
//	fmt.Println ( fmt.Sprintf ( "Initially PQ2 : %v", pq2 ) )

//	Shallow copy is NOT ok

copy(pq1_backup, pq1)
copy(pq2_backup, pq2)
pq1.Merge(&pq2)
pq2 = pq2_backup

//	fmt.Println ( fmt.Sprintf ( "PQ1 after Shallow merge : %v", pq1 ) )
//	fmt.Println ( fmt.Sprintf ( "PQ2 after Shallow merge : %v", pq2 ) )

fmt.Println("Shallow copy merge")
fnCmp(pq1, pq2)

pq1 = pq1_backup
//	fmt.Println ( fmt.Sprintf ( "New PQ1 : %v", pq1 ) )

pq1.Merge(pq2.Copy())
//	fmt.Println ( fmt.Sprintf ( "PQ1 after Deep copy merge : %v", pq1 ) )
//	fmt.Println ( fmt.Sprintf ( "PQ2 after Deep copy merge : %v", pq2 ) )
//
fmt.Println("Deep copy merge")
fnCmp(pq1, pq2)
pq1 = pq1_backup

//	Shallow copy is NOT ok
pq2.Merge(&pq1)
pq1 = pq1_backup

fmt.Println("Shallow copy merge")
fnCmp(pq2, pq1)

pq2 = pq2_backup

pq2.Merge(pq1.Copy())
fmt.Println("Deep copy merge")
fnCmp(pq2, pq1)

Output:

Shallow copy merge
Do PQ1 & PQ2 reference same item ? : [ no yes yes no no no yes yes ]
Deep copy merge
Do PQ1 & PQ2 reference same item ? : [ no no no no no no no no ]
Shallow copy merge
Do PQ1 & PQ2 reference same item ? : [ no no no yes yes yes yes no ]
Deep copy merge
Do PQ1 & PQ2 reference same item ? : [ no no no no no no no no ]

func (*DEPQ) Peek 

func (self *DEPQ) Peek() Item_Interface

Shows top Min item but doesn't pop it

func (*DEPQ) Peek_max 

func (self *DEPQ) Peek_max() Item_Interface

Shows top Max item but doesn't pop it

func (*DEPQ) Pop 

func (self *DEPQ) Pop() (item Item_Interface)

Shows and Removes top Min item from the Priority Queue

func (*DEPQ) Pop_max 

func (self *DEPQ) Pop_max() (item Item_Interface)

Shows and Removes top Max item from the Priority Queue

While inserting, the rightmost node might be More or Less than leftmost tree

Consider Pop_Max : 

      0 4
   3 4   2 3
3 4  3 4    2

->
      0 2
   3 4   2 3
3 4  3 4

->
      0 4
   3 2   2 3
3 4  3 4

-> Here Max node ( 2 ) is less than Min node ( 3 ) need to swap them

-> Property of the interval tree : children of the node ( 3, 4 ) have values 3 <= x <= 4
=> Thus substituting ( 3, 4 ) with ( 2, 4 ) doesn't require fixing children

-> Iterating top to bottom & swapping min max guarantees that parents are swapped ( if needed )

=> After swap continue iterating on the same side ( Max in node ( 2, 3 ) )
->
      0 4
   2 3   2 3
3 4  3 4

->
      0 4
   2 4   2 3
3 3  3 4

func (*DEPQ) Push 

func (self *DEPQ) Push(item Item_Interface)

Appends item to the slice and propagates it up

type DEPQ_Interface 

type DEPQ_Interface interface {
	PQ_Interface

	Pop_max() Item_Interface
	Peek_max() Item_Interface
}

Abstract unit ( parent class in OOP ), which DEPQ produce and consume. Can be downgraded to PQ_Interface

Example (Compatibility) 
package main

import (
	"fmt"
	// "bitbucket.org/sjbog/depq"
)

type My_Item struct {
	Value int
}

func (self My_Item) Is_Less(other Item_Interface) bool {

	return self.Value < other.(My_Item).Value
}

func (self My_Item) Is_More(other Item_Interface) bool {

	return self.Value > other.(My_Item).Value
}

func (self My_Item) Copy() Item_Interface {

	return My_Item{self.Value}
}

func pop(pq PQ_Interface) Item_Interface { return pq.Pop() }

func is_equal(array []int, pq PQ_Interface) bool {

	switch pq.(type) {

	case *PQ:

		for i, size := uint(0), pq.Len(); i < size; i++ {

			if array[i] !=
				(*pq.(*PQ))[i].(My_Item).Value {

				return false
			}
		}

	case *DEPQ:

		for i, size := uint(0), pq.Len(); i < size; i++ {

			if array[i] !=
				(*pq.(*DEPQ))[i].(My_Item).Value {

				return false
			}
		}
	}
	return true
}

func main() {

	var pq = New_DEPQ(
		My_Item{4}, My_Item{-4}, My_Item{1}, My_Item{3}, My_Item{5}, My_Item{3})

	fmt.Println(is_equal(
		[]int{
			-4, 5,
			1, 3, 3, 4,
		}, pq,
	))

	for pq.Len() > 0 {

		fmt.Println(pop(pq).(My_Item).Value)
	}

}

Output:

true
-4
1
3
3
4
5

type Item_Interface 

type Item_Interface interface {
	Is_Less(Item_Interface) bool
	Is_More(Item_Interface) bool

	// to make full ( deep ) copy, not by reference ( shallow )
	Copy() Item_Interface
}

Abstract unit ( parent class in OOP ), which PQ and DEPQ produce and consume

type PQ 

type PQ []Item_Interface

Array ( slice ) based implementation of Min priority queue. Implements PQ_Interface.

Example (ItemsByReference) 
package main

import (
	"fmt"
	// "bitbucket.org/sjbog/depq"
)

type My_Item_Ref struct {
	Value int
}

func (self *My_Item_Ref) Is_Less(other Item_Interface) bool {

	return self.Value < other.(*My_Item_Ref).Value
}

func (self *My_Item_Ref) Is_More(other Item_Interface) bool {

	return self.Value > other.(*My_Item_Ref).Value
}

func (self *My_Item_Ref) Copy() Item_Interface {

	return &My_Item_Ref{(*self).Value}
}

func main() {

	var pq = New_PQ()

	pq.Push(&My_Item_Ref{4})
	pq.Push(&My_Item_Ref{2})
	pq.Push(&My_Item_Ref{1})

	var pq2 = New_PQ()
	pq2.Push(&My_Item_Ref{3})
	pq2.Push(&My_Item_Ref{-4})

	//	Shallow copy of items ( by reference )
	pq.Merge(pq2)

	for pq.Len() > 0 {
		fmt.Println(pq.Pop().(*My_Item_Ref).Value)
	}

}

Output:

-4
1
2
3
4

func New_PQ 

func New_PQ(items ...Item_Interface) *PQ

Creates and fills a new Priority Queue

func (*PQ) Copy 

func (self *PQ) Copy() PQ_Interface

Makes a deep copy of current values. Calls Item_Interface.Copy () on every item

func (*PQ) Heapify 

func (self *PQ) Heapify(start_offset uint)

In-place restructure. Is used to sort raw slice into a Priority Queue ordered slice

Example 
var (
	arr = []Item_Interface{My_Item{15}, My_Item{-1}, My_Item{2}, My_Item{4}, My_Item{8}}

	pq     = *New_PQ(arr...)
	pq_raw = PQ(arr)
)

fmt.Println(fmt.Sprintf("Raw slice : %v", pq_raw))
fmt.Println(fmt.Sprintf("Priority Queue slice : %v", pq))

pq_raw.Heapify(1) // 0-indexed item will be swapped anyway

fmt.Println(fmt.Sprintf("After heapify / reorder : %v", pq_raw))

fmt.Println(fmt.Sprintf("Are they equal ? : %v", fmt.Sprintf("%v", pq) == fmt.Sprintf("%v", pq_raw)))

Output:

Raw slice : [{15} {-1} {2} {4} {8}]
Priority Queue slice : [{-1} {4} {2} {15} {8}]
After heapify / reorder : [{-1} {4} {2} {15} {8}]
Are they equal ? : true

func (*PQ) Len 

func (self *PQ) Len() uint

Returns number of items in the underlying array ( length of slice, not capacity )

func (*PQ) Merge 

func (self *PQ) Merge(other PQ_Interface)

Pops values of `other` PQ into self. Copy by reference on pointer values ( shallow copy ) 

Warning : this operation will purge `other` ( it will be empty ).

To make a merge with deep copy use 

pq1.Merge ( pq2.Copy () )
Example (ByReference)

My_Item implements Item_Interface by Reference : func ( self * My_Item ) ... 

var (
	pq1        = *New_PQ(&My_Item_Ref{-1}, &My_Item_Ref{2}, &My_Item_Ref{4}, &My_Item_Ref{8})
	pq2        = PQ{&My_Item_Ref{-1}, &My_Item_Ref{2}, &My_Item_Ref{4}, &My_Item_Ref{8}}
	pq2_backup = make([]Item_Interface, pq2.Len())
	tmp        string

	fnCmp = func(pq1, pq2 []Item_Interface) {
		fmt.Print("Do PQ1 & PQ2 reference same item ? : [ ")

		for _, pq1_value := range pq1 {
			tmp = "no "

			for _, pq2_value := range pq2 {
				if pq1_value == pq2_value {
					tmp = "yes "
					break
				}
			}

			fmt.Print(tmp)
		}

		fmt.Println("]")
	}
)
//	fmt.Println ( fmt.Sprintf ( "Initially PQ1 : %v", pq1 ) )
//	fmt.Println ( fmt.Sprintf ( "Initially PQ2 : %v", pq2 ) )

//	Shallow copy is NOT ok
copy(pq2_backup, pq2)
pq1.Merge(&pq2)
pq2 = pq2_backup

//	fmt.Println ( fmt.Sprintf ( "PQ1 after Shallow merge : %v", pq1 ) )

fmt.Println("Shallow copy merge")
fnCmp(pq1, pq2)

pq1 = *New_PQ(&My_Item_Ref{-1}, &My_Item_Ref{2}, &My_Item_Ref{4}, &My_Item_Ref{8})
//	fmt.Println ( fmt.Sprintf ( "New PQ1 : %v", pq1 ) )

pq1.Merge(pq2.Copy())
//	fmt.Println ( fmt.Sprintf ( "PQ1 after Deep copy merge : %v", pq1 ) )

fmt.Println("Deep copy merge")
fnCmp(pq1, pq2)

//	Initially PQ1 : [0xc082000480 0xc082000488 0xc082000490 0xc082000498]
//	Initially PQ2 : [0xc0820004a0 0xc0820004a8 0xc0820004b0 0xc0820004b8]

//	PQ1 after Shallow merge : [0xc082000480 0xc0820004a0 0xc0820004a8 0xc082000498 0xc082000488 0xc082000490 0xc0820004b0 0xc0820004b8]

//	New PQ1 : [0xc0820004f0 0xc0820004f8 0xc082000500 0xc082000508]
//	PQ1 after Deep copy merge : [0xc0820004f0 0xc082000520 0xc082000528 0xc082000508 0xc0820004f8 0xc082000500 0xc082000530 0xc082000538]

Output:

Shallow copy merge
Do PQ1 & PQ2 reference same item ? : [ no yes yes no no no yes yes ]
Deep copy merge
Do PQ1 & PQ2 reference same item ? : [ no no no no no no no no ]
Example (ByValue)

My_Item implements Item_Interface by Value : func ( self My_Item ) ... 

var (
	arr = []Item_Interface{My_Item{15}, My_Item{-1}, My_Item{2}, My_Item{4}, My_Item{8}}

	pq1 = *New_PQ(arr...)
	pq2 = PQ(arr)
)

fmt.Println(fmt.Sprintf("Initially Priority Queue 1 : %v", pq1))
fmt.Println(fmt.Sprintf("Initially Priority Queue 2 : %v", pq2))

//	Shallow copy is OK
pq1.Merge(&pq2)

fmt.Println(fmt.Sprintf("Shallow merge : %v", pq1))
fmt.Println(fmt.Sprintf("After Merge Priority Queue 2 : %v", pq2))

Output:

Initially Priority Queue 1 : [{-1} {4} {2} {15} {8}]
Initially Priority Queue 2 : [{15} {-1} {2} {4} {8}]
Shallow merge : [{-1} {2} {-1} {4} {8} {15} {2} {15} {4} {8}]
After Merge Priority Queue 2 : []

func (*PQ) Peek 

func (self *PQ) Peek() Item_Interface

Shows top Min item but doesn't pop it

func (*PQ) Pop 

func (self *PQ) Pop() (item Item_Interface)

Shows and Removes top Min item from the Priority Queue

func (*PQ) Push 

func (self *PQ) Push(item Item_Interface)

Appends item to the slice and propagates it up

type PQ_Interface 

type PQ_Interface interface {
	Len() uint
	Push(Item_Interface)
	Pop() Item_Interface
	Peek() Item_Interface

	//	In-place restructure
	Heapify(offset uint)

	//	Copy by reference on pointer values
	Merge(other PQ_Interface)

	//	Makes deep copy, calls Item_Interface.Copy ()
	Copy() PQ_Interface
}

Abstract unit ( abstract class in OOP ), which defines the behaviour ( methods )

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.