A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.



Task

Create a priority queue.   The queue must support at least two operations:

   Insertion.   An element is added to the queue with a priority (a numeric value).
   Top item removal.   Deletes the element or one of the elements with the current top priority and return it.


Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.



To test your implementation, insert a number of elements into the queue, each with some random priority.

Then dequeue them sequentially; now the elements should be sorted by priority.

You can use the following task/priority items as input data:

        Priority         Task
       ══════════   ════════════════
           3         Clear drains
           4         Feed cat
           5         Make tea
           1         Solve RC tasks
           2         Tax return



The implementation should try to be efficient.   A typical implementation has   O(log n)   insertion and extraction time,   where   n   is the number of items in the queue.

You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc.   If so, discuss the reasons behind it.




 
/* ARM assembly Raspberry PI  */
/*  program priorqueue.s   */
 
/* Constantes    */
.equ STDOUT, 1     @ Linux output console
.equ EXIT,   1     @ Linux syscall
.equ WRITE,  4     @ Linux syscall
 
.equ  NBMAXIELEMENTS,    100
 
/*******************************************/
/* Structures                               */
/********************************************/
/* example structure  item  */
    .struct  0
item_priority:                     @ priority
    .struct  item_priority + 4 
item_address:                      @ string address
    .struct  item_address + 4 
item_fin:
/* example structure heap  */
    .struct  0
heap_size:                         @ heap size
    .struct  heap_size + 4 
heap_items:                        @ structure of items
    .struct  heap_items + (item_fin * NBMAXIELEMENTS)
heap_fin:
 
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessEmpty:       .asciz "Empty queue. \n"
szMessNotEmpty:    .asciz "Not empty queue. \n"
szMessError:       .asciz "Error detected !!!!. \n"
szMessResult:      .ascii "Priority : "                    @ message result
sMessPriority:        .fill 11, 1, ' '
                   .asciz " : "
 
szString1:         .asciz "Clear drains"
szString2:         .asciz "Feed cat"
szString3:         .asciz "Make tea"
szString4:         .asciz "Solve RC tasks"
szString5:         .asciz "Tax return"
szCarriageReturn:  .asciz "\n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss 
.align 4
Queue1:                .skip heap_fin      @ queue memory place 
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                       @ entry of program 
    ldr r0,iAdrQueue1                       @ queue structure address
    bl isEmpty
    cmp r0,#0
    beq 1f
    ldr r0,iAdrszMessEmpty
    bl affichageMess                        @ display message empty
    b 2f
1:
    ldr r0,iAdrszMessNotEmpty
    bl affichageMess                        @ display message not empty
2:
    @ init item 1
    ldr r0,iAdrQueue1                       @ queue structure address
    mov r1,#3                               @ priority
    ldr r2,iAdrszString1
    bl pushQueue                            @ add item in queue
    cmp r0,#-1                              @ error ?
    beq 99f
 
    ldr r0,iAdrQueue1                       @ queue structure address
    bl isEmpty
    cmp r0,#0                               @ not empty
    beq 3f
    ldr r0,iAdrszMessEmpty
    bl affichageMess                        @ display message empty
    b 4f
3:
    ldr r0,iAdrszMessNotEmpty
    bl affichageMess                        @ display message not empty
 
4:
    @ init item 2
    ldr r0,iAdrQueue1                       @ queue structure address
    mov r1,#4                               @ priority
    ldr r2,iAdrszString2
    bl pushQueue                            @ add item in queue
    cmp r0,#-1                              @ error ?
    beq 99f
    @ init item 3
    ldr r0,iAdrQueue1                       @ queue structure address
    mov r1,#5                               @ priority
    ldr r2,iAdrszString3
    bl pushQueue                            @ add item in queue
    cmp r0,#-1                              @ error ?
    beq 99f
    @ init item 4
    ldr r0,iAdrQueue1                       @ queue structure address
    mov r1,#1                               @ priority
    ldr r2,iAdrszString4
    bl pushQueue                            @ add item in queue
    cmp r0,#-1                              @ error ?
    beq 99f
    @ init item 5
    ldr r0,iAdrQueue1                       @ queue structure address
    mov r1,#2                               @ priority
    ldr r2,iAdrszString5
    bl pushQueue                            @ add item in queue
    cmp r0,#-1                              @ error ?
    beq 99f
5:
    ldr r0,iAdrQueue1                       @ queue structure address
    bl popQueue                             @ return item
    cmp r0,#-1                              @ end ?
    beq 100f
    mov r2,r1                               @ save string address
    ldr r1,iAdrsMessPriority                @ conversion priority
    bl conversion10                         @ decimal conversion
    ldr r0,iAdrszMessResult
    bl affichageMess                        @ display message
    mov r0,r2                               @ string address
    bl affichageMess                        @ display message
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
 
    b 5b                                    @ loop
99:
    @ error
    ldr r0,iAdrszMessError
    bl affichageMess       
100:                                        @ standard end of the program 
    mov r0, #0                              @ return code
    mov r7, #EXIT                           @ request to exit program
    svc #0                                  @ perform the system call
 
iAdrQueue1:               .int Queue1
iAdrszString1:            .int szString1
iAdrszString2:            .int szString2
iAdrszString3:            .int szString3
iAdrszString4:            .int szString4
iAdrszString5:            .int szString5
iAdrszMessError:          .int szMessError
iAdrszMessEmpty:          .int szMessEmpty
iAdrszMessNotEmpty:       .int szMessNotEmpty
iAdrszMessResult:         .int szMessResult
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessPriority:        .int sMessPriority
 
/******************************************************************/
/*     test if queue empty                                        */ 
/******************************************************************/
/* r0 contains the address of queue structure */
isEmpty:
    push {r1,lr}                            @ save  registres
    ldr r1,[r0,#heap_size]                  @ heap size
    cmp r1,#0
    moveq r0,#1                             @ empty queue
    movne r0,#0                             @ not empty
    pop {r1,lr}                             @ restaur registers 
    bx lr                                   @ return  
/******************************************************************/
/*     add item  in queue                                         */ 
/******************************************************************/
/* r0 contains the address of queue structure */
/* r1 contains the priority of item           */
/* r2 contains the string address             */
pushQueue:
    push {r1-r9,lr}                         @ save  registres
    ldr r3,[r0,#heap_size]                  @ heap size
    cmp r3,#0                               @ heap empty ?
    bne 1f
    add r4,r0,#heap_items                   @ address of item structure
    str r1,[r4,#item_priority]              @ store in first item
    str r2,[r4,#item_address]
    mov r3,#1                               @ heap size
    str r3,[r0,#heap_size]                  @ new heap size
    b 100f
1:
    mov r4,r3                               @ maxi index
    lsr r5,r4,#1                            @ current index = maxi / 2
    mov r8,r1                               @ save priority
    mov r9,r2                               @ save string address
2:                                          @ insertion loop
    cmp r4,#0                               @ end loop ?
    ble 3f
    mov r6,#item_fin                        @ item size
    mul r6,r5,r6                            @ item shift
    add r6,r0
    add r6,#heap_items                      @ compute address item
    ldr r7,[r6,#item_priority]              @ load priority
    cmp r7,r8                               @ compare priority
    ble 3f                                  @ <=  end loop
    mov r1,r4                               @ last index
    mov r2,r5                               @ current index
    bl exchange
    mov r4,r5                               @ last index = current index
    lsr r5,#1                               @ current index / 2
    b 2b
3:                                          @ store item at last index find
    mov r6,#item_fin                        @ item size
    mul r6,r4,r6                            @ item shift
    add r6,r0
    add r6,#heap_items                      @ item address
    str r8,[r6,#item_priority]
    str r9,[r6,#item_address]
    add r3,#1                               @ increment heap size
    cmp r3,#NBMAXIELEMENTS                  @ maxi ?
    movge r0,#-1                            @ yes -> error
    bge 100f
    str r3,[r0,#heap_size]                  @ store new size
100:
    pop {r1-r9,lr}                          @ restaur registers 
    bx lr                                   @ return 
/******************************************************************/
/*     swap two elements of table                                  */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first index */
/* r2 contains the second index */
exchange:
    push {r3-r6,lr}                         @ save registers
    add r5,r0,#heap_items                   @ address items begin
    mov r3,#item_fin                        @ item size
    mul r4,r1,r3                            @ compute item 1 shift
    add r4,r5                               @ compute item 1 address
    mul r6,r2,r3                            @ compute item 2 shift
    add r6,r5                               @ compute item 2 address
    ldr r5,[r4,#item_priority]              @ exchange
    ldr r3,[r6,#item_priority]
    str r3,[r4,#item_priority]
    str r5,[r6,#item_priority]
    ldr r5,[r4,#item_address]
    ldr r3,[r6,#item_address]
    str r5,[r6,#item_address]
    str r3,[r4,#item_address]
 
100:
    pop {r3-r6,lr}
    bx lr                                              @ return 
/******************************************************************/
/*     move one element of table                                  */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the origin index */
/* r2 contains the destination index */
moveItem:
    push {r3-r6,lr}                         @ save registers
    add r5,r0,#heap_items                   @ address items begin
    mov r3,#item_fin                        @ item size
    mul r4,r1,r3                            @ compute item 1 shift
    add r4,r5                               @ compute item 1 address
    mul r6,r2,r3                            @ compute item 2 shift
    add r6,r5                               @ compute item 2 address
    ldr r5,[r4,#item_priority]              @ exchange
    str r5,[r6,#item_priority]
    ldr r5,[r4,#item_address]
    str r5,[r6,#item_address]
 
100:
    pop {r3-r6,lr}
    bx lr                                   @ return 
 
 
/******************************************************************/
/*     pop queue                                                  */ 
/******************************************************************/
/* r0 contains the address of queue structure */
/* r0 return priority        */
/* r1 return string address   */
popQueue:
    push {r2-r10,lr}                        @ save  registres
    mov r1,r0                               @ save address queue
    bl isEmpty                              @ control if empty queue
    cmp r0,#1                               @ yes -> error
    moveq r0,#-1
    beq 100f
    @ save données à retourner
    mov r0,r1                               @ restaur address queue
    add r4,r0,#heap_items                   @ address of item structure
    ldr r8,[r4,#item_priority]              @ save priority first item
    ldr r9,[r4,#item_address]               @ save address string first item
    ldr r3,[r0,#heap_size]                  @ heap size
    sub r7,r3,#1                            @ last item
    mov r1,r7
    mov r2,#0                               @ first item 
    bl moveItem                             @ move last item in first item
 
    cmp r7,#1                               @ one only item ?
    beq 10f                                 @ yes -> end
    mov r4,#0                               @ first  index
1:
    cmp r4,r7                               @ = last index
    bge 10f                                 @ yes -> end
    mov r5,r7                               @ last index
    cmp r4,#0                               @ init current index
    moveq r6,#1                             @ = 1
    lslne r6,r4,#1                          @ else = first index * 2
    cmp r6,r7                               @ current index > last index
    bgt 2f                                  @ yes
                                            @ no compar priority current item last item
    mov r1,#item_fin            
    mul r1,r6,r1
    add r1,r0
    add r1,#heap_items                      @ address of current item structure
    ldr r1,[r1,#item_priority]
    mov r10,#item_fin 
    mul r10,r5,r10
    add r10,r0
    add r10,#heap_items                     @ address of last item structure
    ldr r10,[r10,#item_priority]
    cmp r1,r10
    movlt r5,r6
2:
    add r10,r6,#1                           @ increment current index
    cmp r10,r7                              @ end ?
    bgt 3f                                  @ yes
    mov r1,#item_fin                        @ no compare priority
    mul r1,r10,r1
    add r1,r0
    add r1,#heap_items                     @ address of item structure
    ldr r1,[r1,#item_priority]
    mov r2,#item_fin 
    mul r2,r5,r2
    add r2,r0
    add r2,#heap_items                     @ address of item structure
    ldr r2,[r2,#item_priority]
    cmp r1,r2
    movlt r5,r10
3:
    mov r1,r5                              @ move item
    mov r2,r4
    bl moveItem
    mov r4,r5
    b 1b                                   @ and loop
10:
    sub r3,#1
    str r3,[r0,#heap_size]                 @ new heap size
    mov r0,r8                              @ return priority
    mov r1,r9                              @ return string address
100:
    pop {r2-r10,lr}                        @ restaur registers 
    bx lr                                  @ return  
/******************************************************************/
/*     display text with size calculation                         */ 
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
    push {r0,r1,r2,r7,lr}                   @ save  registres
    mov r2,#0                               @ counter length 
1:                                          @ loop length calculation 
    ldrb r1,[r0,r2]                         @ read octet start position + index 
    cmp r1,#0                               @ if 0 its over 
    addne r2,r2,#1                          @ else add 1 in the length 
    bne 1b                                  @ and loop 
                                            @ so here r2 contains the length of the message 
    mov r1,r0                               @ address message in r1 
    mov r0,#STDOUT                          @ code to write to the standard output Linux 
    mov r7, #WRITE                          @ code call system "write" 
    svc #0                                  @ call systeme 
    pop {r0,r1,r2,r7,lr}                    @ restaur registers */ 
    bx lr                                   @ return  
/******************************************************************/
/*     Converting a register to a decimal                                 */ 
/******************************************************************/
/* r0 contains value and r1 address area   */
.equ LGZONECAL,   10
conversion10:
    push {r1-r4,lr}                         @ save registers 
    mov r3,r1
    mov r2,#LGZONECAL
1:                                          @ start loop
    bl divisionpar10                        @ r0 <- dividende. quotient ->r0 reste -> r1
    add r1,#48                              @ digit
    strb r1,[r3,r2]                         @ store digit on area
    cmp r0,#0                               @ stop if quotient = 0 
    subne r2,#1                               @ previous position    
    bne 1b                                  @ else loop
                                            @ end replaces digit in front of area
    mov r4,#0
2:
    ldrb r1,[r3,r2] 
    strb r1,[r3,r4]                         @ store in area begin
    add r4,#1
    add r2,#1                               @ previous position
    cmp r2,#LGZONECAL                       @ end
    ble 2b                                  @ loop
    mov r1,#' '
3:
    strb r1,[r3,r4]
    add r4,#1
    cmp r4,#LGZONECAL                       @ end
    ble 3b
100:
    pop {r1-r4,lr}                          @ restaur registres 
    bx lr                                   @return
/***************************************************/
/*   division par 10   signé                       */
/* Thanks to http://thinkingeek.com/arm-assembler-raspberry-pi/*  
/* and   http://www.hackersdelight.org/            */
/***************************************************/
/* r0 dividende   */
/* r0 quotient */	
/* r1 remainder  */
divisionpar10:	
  /* r0 contains the argument to be divided by 10 */
    push {r2-r4}                           @ save registers  */
    mov r4,r0  
    mov r3,#0x6667                         @ r3 <- magic_number  lower
    movt r3,#0x6666                        @ r3 <- magic_number  upper
    smull r1, r2, r3, r0                   @ r1 <- Lower32Bits(r1*r0). r2 <- Upper32Bits(r1*r0) 
    mov r2, r2, ASR #2                     @ r2 <- r2 >> 2
    mov r1, r0, LSR #31                    @ r1 <- r0 >> 31
    add r0, r2, r1                         @ r0 <- r2 + r1 
    add r2,r0,r0, lsl #2                   @ r2 <- r0 * 5 
    sub r1,r4,r2, lsl #1                   @ r1 <- r4 - (r2 * 2)  = r4 - (r0 * 10)
    pop {r2-r4}
    bx lr                                  @ return
 