DOORS DXL Skip List Advanced

What is DXL Skip List?

IBM Rational DOORS is a requirements management tool that allows you to capture, trace, analyze, and manage requirements for complex systems. DOORS eXtension Language (DXL) is a programming language used in DOORS to automate tasks and extend the functionality of the tool.

DOORS DXL SKIP LIST is a built-in data structure in IBM Rational DOORS that allows you to store a collection of values in a specific order. It is called a “skip list” because it uses a skip-list algorithm to provide efficient search and insertion operations, even for very large lists.

In DOORS DXL (DOORS eXtension Language), you can use the skip list data structure to store and manipulate sets of objects, such as DOORS modules or objects within a module. For example, you might use a skip list to keep track of a set of objects that meet certain criteria or to store a list of objects in a specific order.

How can I remove all elements from a DXL Skip List?

There are two ways to delete all elements from a skip list in DXL.

1. Manually delete all elements from the skip list one by one
2. Use setempty() function. However, this is an undocumented function.

Method-1

Here is a DOORS DXL Skip List example code that deletes all the elements from the skip list manually one by one –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk7.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

void emptySkip(Skip sk) {
	string s = null
	for s in sk do { 
		int k = (int key sk)
		delete (sk, k)
	}
}

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
string each_val = null
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Empty Skip List
emptySkip(sk)
print "All entries from the skip list has been deleted \n"
	
// Print Skip List after deleting entries
print "Skip List after deleting entries - \n" 
each_val = null
each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}
	
// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output –

Method-2

In the following example, we are using setempty() function (which is undocumented) to remove all elements from Skip List.

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk7.2dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
string each_val = null
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Empty Skip List
setempty(sk)
print "All entries from the skip list has been deleted \n"
	
// Print Skip List after deleting entries
print "Skip List after deleting entries - \n" 
each_val = null
each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}
	
// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output –

How can I count all elements in a Skip list without knowing the data type?

You can count the number of elements in a skip list without knowing the data type of the Skip list –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk8.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// KEY: INT; DATA: INT
Skip sk_1 = create()   

// Insert data into Skip List
put(sk_1, 1, 100)
put(sk_1, 2, 200)
put(sk_1, 3, 300)


// KEY: INT; DATA: REAL
Skip sk_2 = create()   

// Insert data into Skip List
put(sk_2, 1, 100.1)
put(sk_2, 2, 200.2)
put(sk_2, 3, 300.3)
put(sk_2, 4, 400.4)


// KEY: INT; DATA: STRING
Skip sk_3 = create()   

// Insert data into Skip List
put(sk_3, 1, "New York")
put(sk_3, 2, "London")
put(sk_3, 3, "Los Angeles")
put(sk_3, 4, "Paris")
put(sk_3, 5, "Houston")


// KEY: STRING; DATA: INT
Skip sk_4 = create()   

// Insert data into Skip List
put(sk_4, "A", 100)
put(sk_4, "B", 200)
put(sk_4, "C", 300)
put(sk_4, "D", 400)
put(sk_4, "E", 500)
put(sk_4, "F", 600)


// KEY: STRING; DATA: REAL
Skip sk_5 = create()   

// Insert data into Skip List
put(sk_5, "A", 100.1)
put(sk_5, "B", 200.2)
put(sk_5, "C", 300.3)
put(sk_5, "D", 400.4)
put(sk_5, "E", 500.5)
put(sk_5, "F", 600.6)
put(sk_5, "G", 700.6)


// KEY: INT; DATA: STRING
Skip sk_6 = create()   

// Insert data into Skip List
put(sk_6, "A", "New York")
put(sk_6, "B", "London")
put(sk_6, "C", "Los Angeles")
put(sk_6, "D", "Paris")
put(sk_6, "E", "Houston")
put(sk_6, "F", "Tokyo")
put(sk_6, "G", "Delhi")
put(sk_6, "H", "Geneva")


// Generic count function for Skip List
int countSkip(Skip sk)  {
	if (null sk)	return 0
	
	int i = 0 
	string str = null
	for str in sk do { 
		i++
	}
	return i
}

// Main code
print "Size of Skip List 1 = " countSkip(sk_1) "\n" // KEY:INT; DATA:INT
print "Size of Skip List 2 = " countSkip(sk_2) "\n" // KEY:INT; DATA:REAL
print "Size of Skip List 3 = " countSkip(sk_3) "\n" // KEY:INT; DATA:STR
print "Size of Skip List 4 = " countSkip(sk_4) "\n" // KEY:STR; DATA:INT
print "Size of Skip List 5 = " countSkip(sk_5) "\n" // KEY:STR; DATA:REAL
print "Size of Skip List 6 = " countSkip(sk_6) "\n" // KEY:STR; DATA:STR

// Delete Skip List to free dynamically allocated memory
delete(sk_1)
delete(sk_2)
delete(sk_3)
delete(sk_4)
delete(sk_5)
delete(sk_6)

Here is the output –

Understanding sorting order in Skip List

The data value is always sorted in the skip list based on the key. The following example creates two skip list (KEY: INT; DATA:INT). Both of the are sorted based on the key value –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk9.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// KEY: INT; DATA: INT
Skip sk_1 = create()   

// Insert data into Skip List
put(sk_1, 3, 100)
put(sk_1, 2, 200)
put(sk_1, 1, 300)

// KEY: INT; DATA: INT
Skip sk_2 = create()   

// Insert data into Skip List
put(sk_2, 2, 100)
put(sk_2, 3, 200)
put(sk_2, 1, 300)

// Now print both the skip list one by one 
print "Print Skip List-1 - \n" 
int each_val = null
int each_key = null
for each_val in sk_1 do {
    each_key = (int key(sk_1))
    print("{" each_key ": " each_val "}, ")
}

//
print "\nPrint Skip List-2 - \n" 
each_val = null
each_key = null
for each_val in sk_2 do {
    each_key = (int key(sk_2))
    print("{" each_key ": " each_val "}, ")
}

print "\nThis indicates that the Skip list always sorted based on the key\n"

// Free memory
delete sk_1
delete sk_2

Here is the output –

However, for a string-type key skip list, it may not always be sorted the way we want. For example, in the following code, we have inserted the date in the reverse order (Key: H, G, F, E, D, C, B, A) and expect the key to be sorted as A, B, C, D, E, F, G, H. But the output shows that the string type key is sorted based on the address.

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk10.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// KEY: INT; DATA: STRING
Skip sk_1 = create()   

// Insert data into Skip List
put(sk_1, "H", "New York")
put(sk_1, "G", "London")
put(sk_1, "F", "Los Angeles")
put(sk_1, "E", "Paris")
put(sk_1, "D", "Houston")
put(sk_1, "C", "Tokyo")
put(sk_1, "B", "Delhi")
put(sk_1, "A", "Geneva")


// Now print both the skip list one by one 
print "Print Skip List-1 - \n" 
string each_val = null
string each_key = null
for each_val in sk_1 do {
    each_key = (string key(sk_1))
    print("{" each_key ": " each_val "}, ")
}

print "\nThis indicates that the Skip list always sorted based on the key\n"

// Free memory
delete sk_1

Here is the output –

Nested Skip List

For real-world complex DXL tools, you may want to use a nested skip list. In the following example, we will demonstrate how to handle a skip list in DXL –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk11.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Nested Skip List Example 

// KEY: INT; DATA: INT
Skip sk_nested_1 = create()   

// Insert data into Skip List
put(sk_nested_1, 3, 10)
put(sk_nested_1, 2, 20)
put(sk_nested_1, 1, 30)

// KEY: INT; DATA: INT
Skip sk_nested_2 = create()   

// Insert data into Skip List
put(sk_nested_2, 30, 333)
put(sk_nested_2, 20, 222)
put(sk_nested_2, 10, 111)


// KEY: INT; DATA: INT
Skip sk_nested_3 = create()   

// Insert data into Skip List
put(sk_nested_3, 300, 9300)
put(sk_nested_3, 200, 9200)
put(sk_nested_3, 100, 9100)


// Now, create top level Skip List
// KEY: INT; DATA: another Skip List
Skip sk_top_level = create()  

// Insert data into Skip List
put(sk_top_level, 1, sk_nested_1)	// Data is another Skip List
put(sk_top_level, 2, sk_nested_2)	// Data is another Skip List
put(sk_top_level, 3, sk_nested_3)	// Data is another Skip List


// Main Code
// Print Nested Skip List

print "Print Nested Skip List - \n" 
Skip each_val = null // DATA is Skip Type
int each_key = null
for each_val in sk_top_level do {
    each_key = (int key(sk_top_level))
	print "Top Level Skip Key: " each_key " -  \n"
    
	// for loop for nested skip list
	int each_nested_key, each_nested_data
	for each_nested_data in each_val do {
		each_nested_key = (int key(each_val))
			print("{" each_nested_key ": " each_nested_data "}, ")
	}
	print "\n"
}

// Free memory
delete sk_nested_1
delete sk_nested_2
delete sk_nested_3
delete sk_top_level


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Expected Output in DXL Output Window - 
// Print Nested Skip List - 
// Top Level Skip Key: 1 -  
// {1: 30}, {2: 20}, {3: 10}, 
// Top Level Skip Key: 2 -  
// {10: 111}, {20: 222}, {30: 333}, 
// Top Level Skip Key: 3 -  
// {100: 9100}, {200: 9200}, {300: 9300}, 
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Here is the output –

Advanced Concept of Skip List Deletion

When you delete the skip list it deletes only the skip list itself, it does not delete the referenced object –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk12.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Nested Skip List Example 

// KEY: INT; DATA: INT
Skip sk_nested_1 = create()   

// Insert data into Skip List
put(sk_nested_1, 3, 10)
put(sk_nested_1, 2, 20)
put(sk_nested_1, 1, 30)

// KEY: INT; DATA: INT
Skip sk_nested_2 = create()   

// Insert data into Skip List
put(sk_nested_2, 30, 333)
put(sk_nested_2, 20, 222)
put(sk_nested_2, 10, 111)


// KEY: INT; DATA: INT
Skip sk_nested_3 = create()   

// Insert data into Skip List
put(sk_nested_3, 300, 9300)
put(sk_nested_3, 200, 9200)
put(sk_nested_3, 100, 9100)


// Now, create top level Skip List
// KEY: INT; DATA: another Skip List
Skip sk_top_level = create()  

// Insert data into Skip List
put(sk_top_level, 1, sk_nested_1)	// Data is another Skip List
put(sk_top_level, 2, sk_nested_2)	// Data is another Skip List
put(sk_top_level, 3, sk_nested_3)	// Data is another Skip List


// Main Code
// Print Nested Skip List
print "Print Nested Skip List - \n" 
Skip each_val = null // DATA is Skip Type
int each_key = null
for each_val in sk_top_level do {
    each_key = (int key(sk_top_level))
	print "Top Level Skip Key: " each_key " -  \n"
    
	// for loop for nested skip list
	int each_nested_key, each_nested_data
	for each_nested_data in each_val do {
		each_nested_key = (int key(each_val))
			print("{" each_nested_key ": " each_nested_data "}, ")
	}
	print "\n"
}

// Free memory - delete only top level skip list; Do not delete nested skip list
// delete sk_nested_1
// delete sk_nested_2
// delete sk_nested_3
print "Delete the top level skip list only - sk_top_level \n"
delete sk_top_level


// Now access nested skip list
// Print Skip List
print "Print nested skip list even after deleting top level skip list - "
int i_data = null
int i_key = null
for i_data in sk_nested_1 do {
    i_key = (int key(sk_nested_1))
    print("{" i_key ": " i_data "}; ")
}
print "\n"

Here is the output –

Compare Two Skip Lists

There is no native function to support DOORS Skip list comparison in DXL. Here is a custom example code to demonstrate how you can compare two skip lists –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk14.dxl
* $DESCRIPTION: Skip List example code - compare two skip lists.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Compare Skip Lists

int sizeOfSkip(Skip sk) {
	int i = 0 
	int s = null
	for s in sk do {
		i++
	}
	return i
}

bool compareSkip(Skip sk1, Skip sk2){
	// Compare two Skip Lists - both of KEY: INT; DATA: INT
	// Returns True - if both are same
	// Returns False - if they are different
	int iSkSize1 = null
	int iSkSize2 = null
	int val1 = null
	int val2 = null
	int sData = null
	int sKey = null
	bool cmpResult = false
	iSkSize1 = sizeOfSkip(sk1)
	iSkSize2 = sizeOfSkip(sk2)
	
	if((iSkSize1 == 0) && (iSkSize2 == 0))
		return true
	if(iSkSize1 != iSkSize2){
		return false
	}
	for sData in sk1 do {
		val1 = null
		val2 = null
		sKey = (int key(sk1))
		val1 = sData
		if(find(sk2, sKey, val2)){
			if(val1 == val2){
				cmpResult = true
			}
			else{
				cmpResult = false
				break
			}	
		}
		else{
			cmpResult = false
			break
		}	
	}
	return cmpResult
}

// Skip List Initialisation

Skip sk_1 = create()   // KEY: INT; DATA: INT
put(sk_1, 1, 100)		// Insert data into Skip List
put(sk_1, 2, 200)
put(sk_1, 3, 300)

Skip sk_2 = create()   // KEY: INT; DATA: INT
put(sk_2, 1, 100)		// Insert data into Skip List
put(sk_2, 2, 200)
put(sk_2, 3, 300)

Skip sk_3 = create()   // KEY: INT; DATA: INT
put(sk_3, 1, 100)		// Insert data into Skip List
put(sk_3, 2, 200)
put(sk_3, 3, 300)
put(sk_3, 4, 400)

// Main Code
// Compare sk_1 and sk_2
bool b = compareSkip(sk_1, sk_2)
if (b)	print "Both sk_1 and sk_2 Skip Lists are identical\n"
else 	print "Both sk_1 and sk_2 Skip Lists are NOT identical\n"

// Compare sk_1 and sk_3
b = compareSkip(sk_1, sk_3)
if (b)	print "Both sk_1 and sk_3 Skip Lists are identical\n"
else 	print "Both sk_1 and sk_3 Skip Lists are NOT identical\n"


// Free memory
delete sk_1
delete sk_2
delete sk_3

Here is the output –

DXL Skip List Error

You may encounter a DXL error when the data type mismatch happens in the for loop. Here is an example code and the sample error output –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk13.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, "1", "New York")
put(sk, "2", "London")
put(sk, "3", "Los Angeles")
put(sk, "4", "Paris")
put(sk, "5", "Houston")
put(sk, "6", "Tokyo")
put(sk, "7", "Delhi")
put(sk, "8", "Geneva")

// Print Skip List
int each_val = null	// ERROR - should be 'string each_val = null'
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Empty Skip List
setempty(sk)
print "All entries from the skip list has been deleted... \n"
	
// Print Skip List after deleting entries
print "Skip List after deleting entries - \n" 
each_val = null
each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}
	
// Delete Skip List to free dynamically allocated memory
delete(sk)

The Skip List i.e. sk is of {STRING:STRING} type, which means, the key is of STRING type and the data value is of INT type. But, at Line No: 31 we are iterating over the skip list by using the for loop with ‘each_val’ which is of type INT. Clearly, there is a data type mismatch (STRING vs INT). To correct this error, you need to change the code in Line No: 29 and update the line of code as – ‘string each_val = null’.

Here is the error in the output window –

Memory vs Speed

There are two important concepts of the DXL skip list. The first is, if you create a skip list you should delete it when it is no longer required in the program to free up the memory. For example, if you create a skip list in a local function’s for loop and never delete them, each one of them is sitting in the memory until you close the DOORS.

The second is that creating and deleting the skip lists is expensive in terms of speed/time. Creating a skip list and deleting it in a for loop or while loop will dramatically reduce the performance. For large complex DXL tools, it is an expensive item you may not want to afford.

Conclusion

In this article, we have discussed various advanced concepts of DOORS DXL Skip List. However, if you have any questions about DOORS DXL Skip List, please feel free to comment below.