pqs

package
v0.4.146 Latest Latest
Warning

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

 Go to latest Published: Dec 21, 2023 License: ISC Imports: 6 Imported by: 0

Documentation

Overview

pqs provides legacy priority-queue implementation likely to be deprecated

RankingThreadSafe is a thread-safe pointer-identity-to-value map of updatable values traversable by rank. RankingThreadSafe implements parl.Ranking[V comparable, R constraints.Ordered].

Ranking is a pointer-identity-to-value map of updatable values traversable by rank. Ranking implements parl.Ranking[V comparable, R constraints.Ordered].

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func NewAggregatePriority 

func NewAggregatePriority[V any, P constraints.Ordered](
	value *V,
	index int,
	aggregator parl.Aggregator[V, P],
) (aggregatePriority parl.AggregatePriority[V, P])

NewAggregatePriority returns an object providing cached priority values and order function

func NewAggregatingPriorityQueue 

func NewAggregatingPriorityQueue[V any, P constraints.Ordered](
	maxQueueLength ...int,
) (priorityQueue parl.AggregatingPriorityQueue[V, P])

NewAggregatingPriorityQueue returns a map of updatable values traversable by rank

func NewPriorityQueue 

func NewPriorityQueue[V any, P constraints.Ordered](
	priorityFunc func(value *V) (priority P),
) (priorityQueue parl.PriorityQueue[V, P])

NewPriorityQueue returns a map of updatable values traversable by rank

func NewPriorityQueueThreadSafe 

func NewPriorityQueueThreadSafe[V any, P constraints.Ordered](
	ranker func(value *V) (rank P),
) (o1 parl.PriorityQueue[V, P])

NewRanking returns a thread-safe map of updatable values traversable by rank

Types

type AggregatePriority 

type AggregatePriority[V any, P constraints.Ordered] struct {
	// contains filtered or unexported fields
}

AggregatePriority provides cached priority values and order function

func (*AggregatePriority[V, P]) Aggregator 

func (a *AggregatePriority[V, P]) Aggregator() (aggregator parl.Aggregator[V, P])

Aggregator returns the object calculating values

func (*AggregatePriority[V, P]) CachedPriority 

func (a *AggregatePriority[V, P]) CachedPriority() (priority P)

Priority returns the effective cached priority

func (*AggregatePriority[V, P]) Cmp 

func (x *AggregatePriority[V, P]) Cmp(a, b parl.AggregatePriority[V, P]) (result int)

Cmp returns a comparison of two AggregatePriority objects that represents value elements.

  • Cmp is a custom comparison function to be used with pslices and slices packages
  • Cmp makes AggregatePriority ordered
  • the Priority used is uncached value

func (*AggregatePriority[V, P]) Index 

func (a *AggregatePriority[V, P]) Index() (index int)

Priority returns the effective cached priority

func (*AggregatePriority[V, P]) Update 

func (a *AggregatePriority[V, P]) Update()

Update caches the current priority from the aggregator

type AggregatingPriorityQueue 

type AggregatingPriorityQueue[V any, P constraints.Ordered] struct {
	// contains filtered or unexported fields
}

AggregatingPriorityQueue implements a priority queue using cached priority from aggregators

  • item type is parl.AggregatePriority that can cache priorities
  • item identity is the pointer value to each aggregator of type V
  • the queue is periodically cleared, then regenerated by updating all items
  • the return queue length is configurable to be 1 or longer
  • P is the type used for priority, ordered highest first
  • insertion order is used for equal priorities, order lowest/earliest first

func (*AggregatingPriorityQueue[V, P]) Clear 

func (a *AggregatingPriorityQueue[V, P]) Clear()

Clear empties the priority queue. The hashmap is left intact.

func (*AggregatingPriorityQueue[V, P]) Get 

func (a *AggregatingPriorityQueue[V, P]) Get(valuep *V) (aggregator parl.Aggregator[V, P], ok bool)

Get retrieves a the value container with running totals associated with the identity valuep

func (*AggregatingPriorityQueue[V, P]) List 

func (a *AggregatingPriorityQueue[V, P]) List(n ...int) (aggregatorQueue []parl.AggregatePriority[V, P])

List returns the first n or default all values by pirority

func (*AggregatingPriorityQueue[V, P]) Put 

func (a *AggregatingPriorityQueue[V, P]) Put(valuep *V, aggregator parl.Aggregator[V, P])

Put stores a new value container associated with valuep

  • the valuep is assumed to not have a node in the queue

func (*AggregatingPriorityQueue[V, P]) Update 

func (a *AggregatingPriorityQueue[V, P]) Update(valuep *V)

Update re-prioritizes a value

type AssignedPriority 

type AssignedPriority[V any, P constraints.Ordered] struct {
	Priority P   // the main sort value, ordered high to low
	Index    int // insertion order: lowest/earliest value first: distinguishes between equal priorities
	Value    *V  // the pointer provides identity for this priority
}

AssignedPriority contains the assigned priority for a priority-queue element

  • V is the element value type whose pointer-value provides identity
  • P is the priority, a descending-ordered type
  • SetPriority updates the priority
  • Cmp makes AssignedPriority ordered

func NewAssignedPriority 

func NewAssignedPriority[V any, P constraints.Ordered](priority P, index int, value *V) (assignedPriority *AssignedPriority[V, P])

func (*AssignedPriority[V, P]) Cmp 

func (a *AssignedPriority[V, P]) Cmp(b *AssignedPriority[V, P]) (result int)

Cmp sorts descending: -1 results appears first

func (*AssignedPriority[V, P]) SetPriority 

func (ap *AssignedPriority[V, P]) SetPriority(priority P)

type PriorityQueue 

type PriorityQueue[V any, P constraints.Ordered] struct {
	// contains filtered or unexported fields
}

PriorityQueue is a pointer-identity-to-value map of updatable values traversable by rank. PriorityQueue implements parl.PriorityQueue[V comparable, R constraints.Ordered].

  • V is a value reference composite type that is comparable, ie. not slice map function. Preferrably, V is interface or pointer to struct type.
  • R is an ordered type such as int floating-point string, used to rank the V values
  • values are added or updated using AddOrUpdate method distinguished by (computer science) identity
  • if the same comparable value V is added again, that value is re-ranked
  • rank R is computed from a value V using the ranker function. The ranker function may be examining field values of a struct
  • values can have the same rank. If they do, equal rank is provided in insertion order

func (*PriorityQueue[V, P]) AddOrUpdate 

func (pq *PriorityQueue[V, P]) AddOrUpdate(valuep *V)

AddOrUpdate adds a new value to the ranking or updates the ranking of a value that has changed.

func (*PriorityQueue[V, P]) List 

func (pq *PriorityQueue[V, P]) List(n ...int) (valueQueue []*V)

List returns the first n or default all values by rank

type PriorityQueueThreadSafe 

type PriorityQueueThreadSafe[V any, P constraints.Ordered] struct {
	parl.PriorityQueue[V, P]
	// contains filtered or unexported fields
}

PriorityQueueThreadSafe is a thread-safe pointer-identity-to-value map of updatable values traversable by rank. PriorityQueueThreadSafe implements parl.Ranking[V comparable, R constraints.Ordered].

  • V is a value reference composite type that is comparable, ie. not slice map function. Preferrably, V is interface or pointer to struct type.
  • P is an ordered type such as int floating-point string, used to rank the V values
  • values are added or updated using AddOrUpdate method distinguished by (computer science) identity
  • if the same comparable value V is added again, that value is re-ranked
  • rank R is computed from a value V using the ranker function. The ranker function may be examining field values of a struct
  • values can have the same rank. If they do, equal rank is provided in insertion order

func (*PriorityQueueThreadSafe[V, P]) AddOrUpdate 

func (mp *PriorityQueueThreadSafe[V, P]) AddOrUpdate(value *V)

AddOrUpdate adds a new value to the ranking or updates the ranking of a value that has changed.

func (*PriorityQueueThreadSafe[V, P]) List 

func (mp *PriorityQueueThreadSafe[V, P]) List(n ...int) (list []*V)

List returns the first n or default all values by rank

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.