Documentation ¶
Overview ¶
Package queue provides various thread-safe queue implementations: an unbounded queue, a bounded queue implemented as a circular queue, and a heap based priority queue.
Index ¶
- type Circular
- func (c *Circular) Cap() int
- func (c *Circular) Dequeue() (interface{}, bool)
- func (c *Circular) Enqueue(item interface{}) error
- func (c *Circular) IsEmpty() bool
- func (c *Circular) IsFull() bool
- func (c *Circular) Len() int
- func (c *Circular) Peek() (interface{}, bool)
- func (c *Circular) Reset()
- func (c *Circular) Resize(size int) int
- type HeapPriority
- type Item
- type PQueue
- type Queue
- func (q *Queue) Cap() int
- func (q *Queue) Dequeue() (interface{}, bool)
- func (q *Queue) Enqueue(item interface{}) error
- func (q *Queue) IsEmpty() bool
- func (q *Queue) IsFull() bool
- func (q *Queue) Len() int
- func (q *Queue) Peek() (interface{}, bool)
- func (q *Queue) Reset()
- func (q *Queue) Resize(size int) int
- func (q *Queue) SetShiftPercent(i int)
- type Queuer
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Circular ¶
Circular is a bounded queue implemented as a circular queue. Even though Items, Head, and Tail are exported, in most cases, they should not be directly. Doing so may lead to outcomes less than desirable. Use the exported methods to interact with the Circular queue.
func NewCircular ¶
NewCircular returns an initialized circular queue. Even though creating the slice with an initial length is much slower than creating one without the initial length, cap only, this is done to simplify the actual queue management. Don't need to worry about appending vs adding via index and don't need to check to see if an append will cause the slice to grow.
The slice is 1 slot larger than the requested size for empty/full detection.
func (*Circular) Dequeue ¶
Dequeue will remove an item from the queue and return it. If the queue is empty, a false will be returned.
func (*Circular) Peek ¶
Peek will return the next item in the queue without removing it from the queue. If the queue is empty, a false will be returned.
type HeapPriority ¶
type HeapPriority struct {
// contains filtered or unexported fields
}
A HeapPriority implements heap.Interface and holds Items.
func NewHeapPriority ¶
func NewHeapPriority(l int) *HeapPriority
NewHeapPriority returns a new priority queue with the item's cap set at l; if l > 0.
func (HeapPriority) Len ¶
func (pq HeapPriority) Len() int
func (HeapPriority) Less ¶
func (pq HeapPriority) Less(i, j int) bool
func (*HeapPriority) Pop ¶
func (pq *HeapPriority) Pop() interface{}
Pop pops the next item from the priority queue.
func (*HeapPriority) Push ¶
func (pq *HeapPriority) Push(x interface{})
Push pushes an item onto the priority queue.
func (HeapPriority) Swap ¶
func (pq HeapPriority) Swap(i, j int)
type Item ¶
type Item struct {
// contains filtered or unexported fields
}
An Item is something we manage in a priority queue.
type PQueue ¶
type PQueue []*Item
PQueue represents a priority queue
func (*PQueue) Pop ¶
func (pq *PQueue) Pop() interface{}
Pop pops the next itme from the priority queue.
type Queue ¶
type Queue struct { sync.Mutex InitCap int Items []interface{} Head int // current item in queue // contains filtered or unexported fields }
Queue represents an unbounded queue and everything needed to manage it. The preferred method for creating a new Queue is to use either NewQ() or its alias, NewQueue().
func NewQueue ¶
NewQueue returns an empty queue with an initial capacity equal to the recieved size.
func (*Queue) Dequeue ¶
Dequeue removes an item from the queue. If the removal of the item empties the queue, the head and tail will be set to 0. If the queue is empty, a false will be returned, else true.
func (*Queue) Enqueue ¶
Enqueue adds an item to the queue. If adding the item requires growing the queue, the queue will either be shifted, to make room at the end of the queue, or it will grow.
func (*Queue) IsFull ¶
IsFull returns false; this is implemented to fulfill Queuer but a dynamic queue will never be full.
func (*Queue) Peek ¶
Peek returns the next item in the queue. Post-peek, the queue remains the same.
func (*Queue) Reset ¶
func (q *Queue) Reset()
Reset resets the queue; Head and tail point to element 0. This does not shrink the queue; for that use Resize(). Any items in the queue will be lost.
func (*Queue) Resize ¶
Resize resizes the queue to the received size, or, either its original capacity or to 1,25 * the number of items in the queue, whichever is larger. When a size of 0 is received, the queue will be set to either 1.25 * the number of items in the queue or its initial capacity, whichever is larger. Queues with space at the front are shifted to the front.
func (*Queue) SetShiftPercent ¶
SetShiftPercent sets the queue's shiftPercent: the percentage of the queue that must be empty before the remaining items will be shifted to the the beginning of the slice. This occurs when the slice is set to grow.
Valid range of values are 0-100, inclusive. Vaues < 0 are set to 0 and values > 100 are set to 100.