REBOL [
    Library: [
        level: 'beginner
        platform: 'all
        type: [function module]
        domain: [extension x-file]
        tested-under: [
            [View 1.3.2 on WinXP by Gregg]
        ]
        support: none
        license: 'MIT
    ]
    title:   "Priority Queue"
    file:    %priority-queue.r
    author:  "Gregg Irwin"
    email:   greggirwin@acm.org
    date:    30-Apr-2007
    version: 0.0.1
    purpose: {
        Provides functions, and an object def that uses them, to treat
        a series as a priority queue. When you insert items, you give
        them a priority (higher numbers mean a higher priority). In the
        actual series, the priority is stored along with the value, so
        you should always use the pq* functions to access them, to make
        things easier. 
    }
]

pq-insert: func [
    series [any-block!] "Series to insert value into"
    value "The value to insert"
    priority [integer!] "Higher numbers have higher priority"
][
    sort/skip/reverse append series reduce [priority value] 2
]

pq-remove: func [
    "Remove an item from the priority queue"
    series [any-block!] "Series to remove value from"
    /index  "Remove a specific item"
        idx [integer!] "The index of the item to remove"
][
    remove/part either index [at series (idx * 2 - 1)] [head series] 2
]

pq-first: func [
    series [any-block!]
][
    ; skip over the priority value and return the actual value
    ; that was inserted in the queue.
    attempt [first next head series]
]

pq-take: func [
    series [any-block!] 
    /local value
][
    value: pq-first series  pq-remove series  value
]

priority-queue: make object! [
    data: copy []

    insert: func [item priority] [pq-insert data item priority]

    remove: func [/index idx] [
        either index [pq-remove/index data idx][pq-remove data]
    ]

    first: does [pq-first data]

    take: does [pq-take data]
]