README
¶
Datastructures for Go
-
ordered array is to solve "get M smallest ones among N(N>M) items".
-
priority queue is rewrite of github.com/Workiva/go-datastructures/queue/priority_queue.go.
Documentation
¶
Index ¶
Constants ¶
const MaxInt = int(MaxUint >> 1)
const MaxUint = ^uint(0)
https://stackoverflow.com/questions/6878590/the-maximum-value-for-an-int-type-in-go
const MinInt = -MaxInt - 1
const MinUint = 0
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Comparable ¶
type Comparable interface {
// Compare returns a int that can be used to determine
// ordering in the priority queue. Assuming the queue
// is in ascending order, this should return > logic.
// Return 1 to indicate this object is greater than the
// the other logic, 0 to indicate equality, and -1 to indicate
// less than other.
Compare(other Comparable) int
}
Comparable is an item that can be added to the priority queue.
type OrderedArray ¶
type OrderedArray struct {
// contains filtered or unexported fields
}
OrderedArray is similar to size limited array except that it's to solve "get M smallest ones among N(N>M) items".
func NewOrderedArray ¶
func NewOrderedArray(capacity int) (oa *OrderedArray)
NewOrderedArray is the constructor for an ordered array. capacity is size limit of queue. <=0 means no limit.
func (*OrderedArray) Finalize ¶
func (oa *OrderedArray) Finalize() (items []Comparable)
Finalize retrieves all items from and clear the array. items is sorted in ascending order.
func (*OrderedArray) Len ¶
func (oa *OrderedArray) Len() int
Len returns a number indicating how many items are in the array.
func (*OrderedArray) Merge ¶
func (oa *OrderedArray) Merge(other *OrderedArray)
Merge merges other (keep unchanged) into oa
func (*OrderedArray) Put ¶
func (oa *OrderedArray) Put(items ...Comparable)
Put adds items to the queue.
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
PriorityQueue is similar to queue except that it takes items that implement the Item interface and adds them to the queue in priority order.
func NewPriorityQueue ¶
func NewPriorityQueue(capHint int) *PriorityQueue
NewPriorityQueue is the constructor for a priority queue.
func (*PriorityQueue) BulkGet ¶
func (pq *PriorityQueue) BulkGet(number int) (items []Comparable)
BulkGet retrieves items from the queue. len(items) will be max(0, min(number, len(pq.items))) items is sorted in ascending order.
func (*PriorityQueue) Empty ¶
func (pq *PriorityQueue) Empty() bool
Empty returns a bool indicating if there are any items left in the queue.
func (*PriorityQueue) Get ¶
func (pq *PriorityQueue) Get() (item Comparable)
Get retrieves an item from the queue if non-empty, othewise returns nil
func (*PriorityQueue) Len ¶
func (pq *PriorityQueue) Len() int
Len returns a number indicating how many items are in the queue.
func (*PriorityQueue) Peek ¶
func (pq *PriorityQueue) Peek() Comparable
Peek will look at the next item without removing it from the queue.
func (*PriorityQueue) Put ¶
func (pq *PriorityQueue) Put(items ...Comparable)
Put adds items to the queue.
Source Files