PEDAC example of sorting the background jobs queue

pedac_sort_queue.txt

***********
**PROBLEM**
***********

**INPUT**
Upon form submission an array like the following is provided as a value to a key in Sinatra's params hash
[{"job_id"=>"43", "new_order"=>""},
 {"job_id"=>"44", "new_order"=>""},
 {"job_id"=>"46", "new_order"=>""},
 {"job_id"=>"47", "new_order"=>""},
 {"job_id"=>"48", "new_order"=>""},
 {"job_id"=>"45", "new_order"=>""},
 {"job_id"=>"39", "new_order"=>""},
 {"job_id"=>"40", "new_order"=>""},
 {"job_id"=>"41", "new_order"=>""},
 {"job_id"=>"42", "new_order"=>""},
 {"job_id"=>"34", "new_order"=>"-10"},
 {"job_id"=>"35", "new_order"=>"1"},
 {"job_id"=>"36", "new_order"=>"1"},
 {"job_id"=>"37", "new_order"=>"-8"},
 {"job_id"=>"38", "new_order"=>""}]

**OUTPUT**
Update the queue_order value for each queued job in the background_jobs table

**REQUIREMENTS**
Create an algorithm to manually sort the jobs that are not completed (queued jobs and running jobs)
Enter values for all jobs or only the jobs you want to update
Enter 1 or a negative value to make a job appear first in the queue
  For example: -100, -50, -1, 1 will become 1, 2, 3, 4
Enter a large positive value (larger than the number of queued jobs) to make a job appear last in the queue
  For example: 10, 100, 200 will become 8, 9, 10 if the number of queued jobs is 10
If you enter the same sort value for more than one job, the job that appears first in the list below that value will be assigned that value and the others will increment by 1 accordingly
  For example: 2, 2, 2 will become 2, 3, 4
Enter fractional numbers, up to two decimal spaces, for more fine-grained control
  For example: 1.1, 1.3, 1.2, 1.15 will become 1, 4, 3, 2 (which will then be rendered by ascending order on the page)
If you enter a number with more than two decimal places it will be truncated to two decimal places

**RULES**
New Queue Order field can be:
empty or not empty
if not empty:
  the value must be a postive or negative number with a decimal or no decimal
    if decimal, a number does not have to follow the decimal point

Valid numbers:
-10
10
10.
10.0
10.00

If a decimal is entered and has more than 2 decimal places, the decimal will be rounded to 2 places

**MENTAL MODEL**
Some jobs will have values, some will not

sort order can have negative values.
the lowest negative value becomes 0, the next becomes 1, etc.

sort order can have values that are greater than the queue count
the greatest value should become queue_count, the next should become queue_count - 1, etc.

Split jobs with new_queue_order values and jobs without new_queue_order values into two arrays:
  new_queue_order
  not_new_queue_order

renumber the queue order for each job:
correct the queue order ascending
correct it descending

ascending:
get number of jobs -- the new queue_orders will be numbered 1 to 'number of jobs'
set current_queue_order to 1
Iterate through new_queue_order array ascending
  if negative value, adjust it to current_queue_order, current_queue_order++
    if another negative value, adjust it to current_queue_order, current_queue_order++
      etc.
  if value is less than current_queue_order, set it to current_queue_order, current_queue_order++
  if value is > than current_queue_order, set current_queue_order to that value

This will correct all queue orders ascending

descending:
Do the reverse to correct all queue orders that are greater than queue_count

What if some jobs have the same updated queue_order?
The problem states that the first job with the queue_order should get that order, then the next job should have that queue_order + 1
How can this be preserved when we're sorting the new_queue_order list ascending and descending?

idea:
upon submission, convert all updated sort_orders to two decimal places
starting at .00001 and incrementing by .00001, add the number to the new sort_order so it will be like this

1.10
1.11 (duplicate) 
1.11 (duplicate)
1.12
2.00

becomes...

1.10001
1.11002 (not duplicate any more, and order is perserved) 
1.11003 (not duplicate any more, and order is perserved)
1.12004
2.00005

.00001 will allow for 999 submitted sort orders, which is way more than will ever be requested

.00001 can be easily adjusted

adding this to each new_sort_order will preserve the order in which they were submitted, if any were duplicates

******************
**DATA STRUCTURE**
******************

Array of hashes
  hashes have two keys: job_id and new_order
  job_id values are integers represented as strings (from hidden fields in the html form)
  new_order is an empty string if a new_order was not entered for the job,
    otherwise the value is a positive or negative integer or float represented as a string

*************
**ALGORITHM**
*************

Check if all updated new_order values (not '') are valid

if yes continue...

- -

ending_number = 0.00001
select all jobs with updated new_order (new_order != '')
convert the value to a float and round 2 places
add ending_number to value
ending_number += 0.00001

- -

Adjust the new_order values ascending:

METHOD: adjust ascending
sort new_sort_orders ASC.
sort_order = 0
iterate through new_sort_orders

if new_sort_order <= queue_count && new_sort_order > sort_order
  sort_order = new_sort_order + 1
  next
else if new_sort_order < sort_order
  new_sort_order = sort_order (WE NEED TO PRESERVE FLOATS)
end 

if new_sort_order <= sort_order # this will always be new_sort_order == sort_order because new_sort_order is set to sort_order
  sort_order += 1
end

queue_count = 10
-5
-1
0
1
3
11
12
14
14
15

iteration 1
queue_count = 10
=> -5 becomes 1
-1
0
1
3
11
12
14
14
15

iteration 2
queue_count = 10
=> -5 becomes 1
=> -1 becomes 2
0
1
3
11
12
14
14
15

iteration 3
queue_count = 10
=> -5 becomes 1
=> -1 becomes 2
=> 0 becomes 3
1
3
11
12
14
14
15

iteration 4
queue_count = 10
=> -5 becomes 1
=> -1 becomes 2
=> 0 becomes 3
=> 1 becomes 4
3
11
12
14
14
15

iteration 5
queue_count = 10
=> -5 becomes 1
=> -1 becomes 2
=> 0 becomes 3
=> 1 becomes 4
=> 3 becomes 5
11
12
14
14
15

- -

adjust the new_orders descending

METHOD: adjust descending
sort new_sort_orders DESC
sort_order = queue_count

iterate through new_sort_orders
if new_sort_order < sort_order
  sort_order = new_sort_order - 1
  next
else if new_sort_order > sort_order 
    new_sort_order = sort_order (WE NEED TO PRESERVE FLOATS)
end

if new_sort_order >= sort_order # this will always be new_sort_order == sort_order because new_sort_order is set to sort_order
  sort_order -=1
end

queue_count = 10
15
14
14
12
11
5
4
3
2
1

iteration 1
queue_count = 10
=> 15 becomes 10
14
14
12
11
5
4
3
2
1

iteration 2
queue_count = 10
=> 15 becomes 10
=> 14 becomes 9
14
12
11
5
4
3
2
1

iteration 3
queue_count = 10
=> 15 becomes 10
=> 14 becomes 9
=> 14 becomes 8
12
11
5
4
3
2
1

iteration 4
queue_count = 10
=> 15 becomes 10
=> 14 becomes 9
=> 14 becomes 8
=> 12 becomes 7
11
5
4
3
2
1

iteration 5
queue_count = 10
=> 15 becomes 10
=> 14 becomes 9
=> 14 becomes 8
=> 12 becomes 7
=> 11 becomes 6
5
4
3
2
1

... the rest of the sort orders are preserved on the next 5 iterations

- -

using the job ids, update the jobs queue_order database values with the new values

- -

not_new_queue_order = select the jobs that were not updated
  select jobs with sort_order == ''
  sort ascending

count from 1 up to queue_count, set block parameter to 'number'
  if new_queue_order array has job with new_order value of number
    next
  else
    instantiate the job from the job_id
    update that job's queue_order database value with number
    shift the job off the not_new_queue_order array