1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
Name: psqueues
Version: 0.2.8.0
License: BSD3
License-file: LICENSE
Maintainer: Jasper Van der Jeugt <jaspervdj@gmail.com>
Bug-reports: https://github.com/jaspervdj/psqueues/issues
Synopsis: Pure priority search queues
Category: Data Structures
Build-type: Simple
Cabal-version: >=1.10
Tested-with: GHC==9.6.1, GHC==9.4.2, GHC==9.2.2, GHC==9.0.2, GHC==8.10.7, GHC==8.8.4, GHC==8.6.5, GHC==8.4.4, GHC==8.2.2, GHC==8.0.2
Description:
The psqueues package provides
<http://en.wikipedia.org/wiki/Priority_queue Priority Search Queues> in
three different flavors.
.
* @OrdPSQ k p v@, which uses the @Ord k@ instance to provide fast insertion,
deletion and lookup. This implementation is based on Ralf Hinze's
<http://citeseer.ist.psu.edu/hinze01simple.html A Simple Implementation Technique for Priority Search Queues>.
Hence, it is similar to the
<http://hackage.haskell.org/package/PSQueue PSQueue> library, although it is
considerably faster and provides a slightly different API.
.
* @IntPSQ p v@ is a far more efficient implementation. It fixes the key type
to @Int@ and uses a <http://en.wikipedia.org/wiki/Radix_tree radix tree>
(like @IntMap@) with an additional min-heap property.
.
* @HashPSQ k p v@ is a fairly straightforward extension of @IntPSQ@: it
simply uses the keys' hashes as indices in the @IntPSQ@. If there are any
hash collisions, it uses an @OrdPSQ@ to resolve those. The performance of
this implementation is comparable to that of @IntPSQ@, but it is more widely
applicable since the keys are not restricted to @Int@, but rather to any
@Hashable@ datatype.
.
Each of the three implementations provides the same API, so they can be used
interchangeably. The benchmarks show how they perform relative to one
another, and also compared to the other Priority Search Queue
implementations on Hackage:
<http://hackage.haskell.org/package/PSQueue PSQueue>
and
<http://hackage.haskell.org/package/fingertree-psqueue fingertree-psqueue>.
.
<<http://i.imgur.com/KmbDKR6.png>>
.
<<http://i.imgur.com/ClT181D.png>>
.
Typical applications of Priority Search Queues include:
.
* Caches, and more specifically LRU Caches;
.
* Schedulers;
.
* Pathfinding algorithms, such as Dijkstra's and A*.
Extra-source-files:
CHANGELOG
Source-repository head
type: git
location: http://github.com/jaspervdj/psqueues.git
Library
Default-language: Haskell2010
Ghc-options: -O2 -Wall
Hs-source-dirs: src
Build-depends:
base >= 4.2 && < 5
, deepseq >= 1.2 && < 1.6
, hashable >= 1.1.2.3 && < 1.5
if impl(ghc>=6.10)
Build-depends: ghc-prim
Exposed-modules:
Data.HashPSQ
Data.IntPSQ
Data.OrdPSQ
Other-modules:
Data.BitUtil
Data.HashPSQ.Internal
Data.IntPSQ.Internal
Data.OrdPSQ.Internal
Benchmark psqueues-benchmarks
Default-language: Haskell2010
Ghc-options: -Wall
Hs-source-dirs: src benchmarks
Main-is: Main.hs
Type: exitcode-stdio-1.0
Other-modules:
BenchmarkTypes
Data.BitUtil
Data.HashPSQ
Data.HashPSQ.Benchmark
Data.HashPSQ.Internal
Data.IntPSQ
Data.IntPSQ.Benchmark
Data.IntPSQ.Internal
Data.OrdPSQ
Data.OrdPSQ.Benchmark
Data.OrdPSQ.Internal
Data.PSQueue.Benchmark
Build-depends:
containers >= 0.5
, unordered-containers >= 0.2.4
, criterion >= 0.8
, mtl >= 2.1
, PSQueue >= 1.1
, random >= 1.0
, base
, deepseq
, ghc-prim
, hashable
, psqueues
Test-suite psqueues-tests
Cpp-options: -DTESTING -DSTRICT
Default-language: Haskell2010
Ghc-options: -Wall
Hs-source-dirs: src tests
Main-is: Main.hs
Type: exitcode-stdio-1.0
Other-modules:
Data.BitUtil
Data.HashPSQ
Data.HashPSQ.Internal
Data.HashPSQ.Tests
Data.IntPSQ
Data.IntPSQ.Internal
Data.IntPSQ.Tests
Data.OrdPSQ
Data.OrdPSQ.Internal
Data.OrdPSQ.Tests
Data.PSQ.Class
Data.PSQ.Class.Gen
Data.PSQ.Class.Tests
Data.PSQ.Class.Util
Build-depends:
HUnit >= 1.2 && < 1.7
, QuickCheck >= 2.7 && < 2.15
, tasty >= 1.2 && < 1.6
, tasty-hunit >= 0.9 && < 0.11
, tasty-quickcheck >= 0.8 && < 0.11
, base
, array
, deepseq
, ghc-prim
, hashable
, psqueues
, tagged
|
