Skip list ordering

I am writing a script that requires multiple passes through a list of items. A skip list looked to be an ideal way to work with the data, however I've discovered that skip lists sort the entries based on the key value, and I need to be able to access the items in the order they were inserted (in my case, I'm using the absolute number of the associated object as the key, iterating from the top of the module to the bottom).

I've experimented a little, and it appears that it is simply a numerical sort (integer keys are sorted as numbers, and I suspect that string keys are sorted based on their ASCII value, although I didn't dig that deep). If this property of skip lists is documented, I failed to see it in the help. I am now starting down the path of using arrays instead of skip lists, I believe this should work for my purposes but I haven't progressed far enough to know for sure.

However, I'm curious to know if there is way to prevent skip lists from sorting, or if there is an access method other than a for loop that would preserve the order.

Thanks!
SystemAdmin - Tue Mar 09 12:04:24 EST 2010

Re: Skip list ordering
SystemAdmin - Tue Mar 09 12:24:23 EST 2010

I'm not going to claim this the best way(s) of doing this... but I've used two methods in the past:

1. Keep two skip lists. The first is your skip list of key=integer absno of object and data=object. The second is a skip list of key=integer place and data=integer absno of object. You for-loop through the second list, using 'find' to get the object from the first list.

2. Make your skip list of key=integer absno of object and data=object. Then for-loop through the objects in the module (if that is the order you want) and use 'find' to see if the object is in your list.

Re: Skip list ordering
SystemAdmin - Tue Mar 09 14:52:03 EST 2010

Do not really get what you are doing, but a question, would the following do:
  

Object o = null
int NumO = 1
Module m = current
Skip Objects = create
 
for o in m do
  {
    put(Objects, NumO, o)
    NumO++
  }

 


i.e use the integer count as key and the object itself as data. You can get the Absolute Number from object as needed.

Off-topic note: if you create the Skip as createString, the data will be automatically sorted as text by key value.

 

Re: Skip list ordering
SystemAdmin - Tue Mar 09 19:39:50 EST 2010

SystemAdmin - Tue Mar 09 14:52:03 EST 2010

Do not really get what you are doing, but a question, would the following do:
  

Object o = null
int NumO = 1
Module m = current
Skip Objects = create
 
for o in m do
  {
    put(Objects, NumO, o)
    NumO++
  }

 


i.e use the integer count as key and the object itself as data. You can get the Absolute Number from object as needed.

Off-topic note: if you create the Skip as createString, the data will be automatically sorted as text by key value.

 

@Pekka:
I had hoped to used the find function to quickly lookup data entries by the absnum, so a non-correlated key doesn't serve me well in this instance.

@oaklodge:
Your first suggestion is a reasonable workaround, although I would be using nested skip lists (all of which I need to preserve the order), so it becomes quite cumbersome to use this method down the chain. I'll keep this in my back pocket for the future.

I've got the functionality I desired working now, using Array objects. It isn't as elegant as skip lists would have allowed, but it gets the job done. Essentially, it emulates ordered skip lists by using the first dimension as the key.

Personally, I would find it nice if the language let the user decide if lists should be ordered. At the least, it would help for this to be documented. I understand that in pure lookup uses, the order shouldn't matter, but it was a pain to get everything in place and then have to track down why items weren't coming out as expected.

Thanks both for responding.