ID:1606593
 
This little beauty is a wrapper for a list, which allows you to keep the list in order at all times. When you add an element to a prioritylist, also specify a priority number to go with it, and the datum will automatically sort the object into the list according to its priority.

var/prioritylist/p = new()
p.Add(new/obj(),5,new/obj(),7,new/obj(),3,new/obj(),1,new/obj(),-1000)


This interface supports almost all the functions that regular lists do, except it doesn't support operator overloads.

Do not manipulate values yourself. Only access values directly yourself if you need to perform a for(x in p.value) loop.

By default, the following functions are supported:

Add
Remove
Cut
Copy
Swap
Find


Lastly, the search algorithm for finding the position of the required insertion is pretty fast. It assumes that the values list is always going to be in sequential order, and as such, it only has to search every len/2 position. For large lists, very few nodes will be examined, for smaller lists, a larger portion of the nodes will be examined.

This search algorithm is as close to ideal as is possible.

//utility functions
proc
ceil(val)
. = round(val)
return .==val ? . : . + 1

#define floor(X) round((X))


prioritylist
var
list/values = list()
len = 0
proc
//add one or more elements to the list
Add()
if(args.len % 2 != 0)
CRASH("Add() requires an object and a priority value for every supplied entry.")
var/count=1
//add all elements to the value array
while(count<=args.len)
if(!.)
. = __Add(args[count++],args[count++])
else
__Add(args[count++],args[count++])
//update the len variable
len = values.len

//do not call. Internal function
__Add(datum/d,priority)
//don't do anything if d is already in the list
if(d in values)
return 0
//if priority is less than the first element, add to beginning
if(values.len)
if(priority<=values[values[1]])
values.Insert(1,d)
values[d] = priority
return 1
//if the last element is less or equal to new priority, add to end
if(priority>=values[values[values.len]])
values.Add(d)
values[d] = priority
return 1
//prepeare a search for the index by priority
var/i = floor(values.len/2)
var/vpos = i
//divide and conquer algorithm
while(i>1)
//halve i
i = floor(i/2)
//check if left or right
if(priority>=values[vpos])
vpos += i
else
vpos -= i
//after search has reached final index, insert the element
values.Insert(vpos + 1,d)
values[d] = priority
else
values.Add(d)
values[d] = priority
return 1

//remove one or more elements from the list
Remove()
var/count=1
while(count<=args.len)
if(!.)
. = values.Remove(args[count++])
else
values.Remove(args[count++])
//update the len variable
len = values.len

Change(value,priority)
if(Remove(value))
return Add(value,priority)
return 0

//cut part of the list
Cut(start,end)
. = values.Cut(start,end)
len = values.len

//copy part of the list
Copy(start,end,aspriority=0)
//if aspriority is specified, we return a new prioritylist instead of a list segment.
if(aspriority)
. = new/prioritylist(values.Copy(start,end))
else
. = values.Copy(start,end)

//swap two values by index
Swap(index1,index2)
values.Swap(index1,index2)

//get the index of a
Find(a)
return values.Find(a)

Get(index)
return values[index]

New(list/nlist=null)
if(nlist)
values = nlist
len = values.len
Nice! I didn't know that Swap() preserved associated values, but it's darn handy that it does.

I'll have to remember this is here, I'm sure I'll need it at some point :)
Very nice! Excellent work as always, Ter.
Fixed a trivial case with this one during adding to an empty priority list.
I used this guy in a pathfinding algorithm today. The uses for this are pretty amazing, if you haven't tried it yet.