Skip Lists

when you store an element into a skip list:

Skip skiplist = createString();
string key, element;
put(skiplist, key, element)

when you want to retrieve the elements in the Skip list:

for element in skiplist do
{
//do something with element
//Question: Is there a way to obtain the associated key value of this element?
}
lsand - Wed Jun 29 17:04:35 EDT 2011

Re: Skip Lists
SystemAdmin - Wed Jun 29 18:49:31 EDT 2011

The following code gives an example of using the "key" function to get the value of the key associated with a skip list element - it's just a variation of some example code from the Skip Lists section of the DXL Reference manual - the DXL Reference manual is included under the Help menu in the DOORS client.
  

Skip numberCache = create 
Object o 
int keyValue = 0
int absno = 0
 
for o in current Module do { 
    absno = o."Absolute Number" 
        put(numberCache, absno, o) // Absolute number is the skip list key, object is the skip list element
        }
 
for absno in numberCache do { //This prints out the absno key in ascending order
        keyValue  =  (int key numberCache)
        print keyValue  
        }
 
delete numberCache

Paul Miller
Melbourne, Australia

Re: Skip Lists
llandale - Thu Jun 30 13:03:49 EDT 2011

SystemAdmin - Wed Jun 29 18:49:31 EDT 2011

The following code gives an example of using the "key" function to get the value of the key associated with a skip list element - it's just a variation of some example code from the Skip Lists section of the DXL Reference manual - the DXL Reference manual is included under the Help menu in the DOORS client.
  

Skip numberCache = create 
Object o 
int keyValue = 0
int absno = 0
 
for o in current Module do { 
    absno = o."Absolute Number" 
        put(numberCache, absno, o) // Absolute number is the skip list key, object is the skip list element
        }
 
for absno in numberCache do { //This prints out the absno key in ascending order
        keyValue  =  (int key numberCache)
        print keyValue  
        }
 
delete numberCache

Paul Miller
Melbourne, Australia

Yes. The "key" command MUST be cast and with parenthesis.
keyValue = (int key numberCache)
keyValue = (string key numberCache)

That command is routine as the first line of the <for data in Skip do> loop; unless of course you don't care about the Key. The key command must be inside a for data in Skip loop.

Notice that the Skip list itself does NOT know the Type of Key and Data it contains. It is your responsibility to insure they are consistent.

Looking at Paul's code I see he has cleverly added a feature to demonstrate the fact that the Skip list doesn't care about the type of its contents. In the 2nd loop <for absno in numberCache do> he is using a "string" variable "absno" as the Data loop, whereas the Data for this skip is clearly of type "Object", as seen in the previous loop's <put> statement. So long as the 2nd loop doesn't actually USE "absno", all is well. But try <print keyValue "\t" absNo "\n"> ... you end up with egg on your face.

Make SURE you always put the same Key and Data in the skip and make sure you retrieve them the same way. I routinely announce very loudly the casting of the KEY and DATA for all my skip lists:

Skip numberCache = create // KEY: 'int' AbsNo; DATA: 'Object' handle

But that's mainly because I cannot possibly remember them.

  • Louie

Re: Skip Lists
lsand - Thu Jun 30 13:11:12 EDT 2011

Thank you!