Priority queue in J

pq.ijs

NB. priority queue

coclass 'PQ'

load '~Projects/u.ijs'

create=: verb define
vals=: $ 0
size=: 0
)

destroy=: codestroy

top=: 3 : 'boxFirst vals'

getWeight=: boxFirst@boxGet

push=: monad define

if. (#vals) <: size do.
  vals=: vals , <y
else.
  vals=: (<y) size} vals
end.

size=: size + 1

promote (size - 1)
''
)

promote=: monad define
if. 0 = y do. '' return. end.

powers=. 2&^ i. <. 2 + 2&^. y

permuted=. <. y % powers

w=. vals getWeight y

permuted=. /:~ (#~ (w&[ <: (vals&getWeight "1))) permuted

NB.filtered=. ''
NB.for_i. permuted
NB.do.
NB.  if. w > (vals getWeight i)
NB.  do. break.
NB.  end.
NB.  filtered=. filtered , i
NB.end.
NB.permuted=. \:~ filtered

if. 1 >: #permuted do. '' return. end.

pairs=. box sliding&2 }: permuted

vals=: ((({: , {.) permuted) ; pairs) C. vals
)

pop=: monad define
if. 0 = size do. '' return.
else.
  t=. top''
  
  size=: <: size
  vals=: (size { vals) 0 } vals
  vals=: (<'';'') size } vals
  
  demote 0
  
  t
end.
)

demote=: monad define
index=. y
value=. vals boxGet y
weight=. boxFirst value

while. size > >: +: index
do.
  l=. >: +: index
  
  child=. l
  r=. +: >: index
  
  if. r < size
  do.
    if. (vals getWeight l) >: (vals getWeight r)
    do. child=. r
    end.
  end.
  
  if. weight < (vals getWeight child)
  do. break.
  else.
    vals=: (child { vals) index } vals
    vals=: (<value) child } vals
    index=. child
  end.
end.
)

u.ijs

box=: monad define
if. 0 = #y
do. <''
else. if. 1 = #y
  do. <y
  else. ;/ y
  end.
end.
)

boxGet=: > : (>@{~)
boxFirst=: boxGet&0
boxSecond=: boxGet&1
boxLast=: boxGet <:&#

pr=: smoutput

substr=: (];.0~ ,.)~"1
sliding=: [ substr~/ ([: |: [ ,:~ (i. @ >: @ -~ #))~