Welcome to Telelogic Product Support
  Home Downloads Knowledgebase Case Tracking Licensing Help Telelogic Passport
Telelogic DOORS (steve huntington)
Decrease font size
Increase font size
Topic Title: Skip List structure
Topic Summary: Is it possible to to have more than one data element per key in a skip list?
Created On: 12-Jun-2006 13:45
Status: Post and Reply
Linear : Threading : Single : Branch
Search Topic Search Topic
Topic Tools Topic Tools
Quick Reply Quick Reply
Subscribe to this topic Subscribe to this topic
E-mail this topic to someone. E-mail this topic
Bookmark this topic Bookmark this topic
View similar topics View similar topics
View topic in raw text format. Print this topic.
Answer This question was answered by Tony Goodman, on Monday, June 12, 2006 3:20 PM

Answer:
// loop through first skip list
for data1 in skip1 do
{
print "data1=" data1 "\n"
// get key - note that you must cast this to the correct type
int k = (int key skip1)

// use key to extract data from second skip list
string data2

//
if (find(skip2, k, data2))
{
print "data2=" data2 "\n"
}
}
 12-Jun-2006 13:45
User is offline View Users Profile Print this message


Heather Linsk

Posts: 50
Joined: 7-Mar-2006

Is it possible to to have more than one data element per key in a skip list?

e.g.

Key    Data1    Data2
0        abc        f45
1        def         f46

TIA!


-------------------------
Heather Linsk
Lead Engineer
General Dynamics AIS
413-494-7095
Report this to a Moderator Report this to a Moderator
 12-Jun-2006 14:10
User is offline View Users Profile Print this message


Tony Goodman

Posts: 1098
Joined: 12-Sep-2002

No, but you can store any data structure in a skip list such as an array or another skip list.
The only trouble with storing dynamic data structures inside another dynamic data structure is that you have to be very careful about how, and in what scope, you create/delete them. Get it wrong and ... bang!

I would recommend using two skip lists, one for data1 and another for data2. They both have the same key. I do this frequently.

-------------------------
Tony Goodman
http://www.smartdxl.com
Report this to a Moderator Report this to a Moderator
 12-Jun-2006 14:31
User is offline View Users Profile Print this message


Heather Linsk

Posts: 50
Joined: 7-Mar-2006

Thanks Tony.

Now that I am using two skip lists and I know the key of the first skip list, how do I get the related item havng the same key from the second skip list?

TIA.

-------------------------
Heather Linsk
Lead Engineer
General Dynamics AIS
413-494-7095
Report this to a Moderator Report this to a Moderator
 12-Jun-2006 14:50
User is offline View Users Profile Print this message


Tony Goodman

Posts: 1098
Joined: 12-Sep-2002

Answer Answer
// loop through first skip list
for data1 in skip1 do
{
print "data1=" data1 "\n"
// get key - note that you must cast this to the correct type
int k = (int key skip1)

// use key to extract data from second skip list
string data2

//
if (find(skip2, k, data2))
{
print "data2=" data2 "\n"
}
}

-------------------------
Tony Goodman
http://www.smartdxl.com

Edited: 12-Jun-2006 at 14:54 by Tony Goodman
Report this to a Moderator Report this to a Moderator
 12-Jun-2006 14:53
User is offline View Users Profile Print this message


ron lewis

Posts: 650
Joined: 20-Sep-2004

If you want you can put two data items in same list.

The trick is to use a delimited list and then parse the data item string out after retrieving the data item

For a comma delimited list example:
Key Data
0 abc,f45
1 def,f46
Report this to a Moderator Report this to a Moderator
 31-Oct-2007 21:23
User is offline View Users Profile Print this message


Pete Kowalski

Posts: 301
Joined: 7-Feb-2003

Ron, what a great, simple and useful idea! Do you have any good practices on parsing the data out?

-------------------------
pete.kowalski(at)motorola.com
Report this to a Moderator Report this to a Moderator
 31-Oct-2007 21:58
User is offline View Users Profile Print this message


Louie Landale

Posts: 2070
Joined: 12-Sep-2002

Sorry for confusion, but are you saying that you can have 2 'Data' items for the same 'Key' this way? In your example, key 0 has 2 data items, 'abc' and 'f45'? That is, the Skip itself only has one data item, but its delimited and the user needs to un-delimit in order to use them.

If that's what you want to do, I think it would be easier to have a Skip list as the 'Data' in the original skip list. To add a new element find the internal Skip and add the Element to that. New entries in the Skip require you to create a new Skip; and when you are done you have to loop through the Skip deleting all the data Skip lists.

- Louie
Report this to a Moderator Report this to a Moderator
 1-Nov-2007 12:25
User is offline View Users Profile Print this message


Heather Linsk

Posts: 50
Joined: 7-Mar-2006

After using Skip lists for awhile now ;) I often add "data" elements as delimited items and use regular expressions to parse the data back out.

For example:

Skip skip1 = create()
string myitem, p1, p2, p3

put(skip1, 0, "abc::123::a23s")

Regexp KeyParse = regexp "(.*)::(.*)::(.*)"

for myitem in skip1 do {
     if(KeyParse myitem) {
            p1 = myitem[match 1]
            p2 = myitem[match 2]
            p3 = myitem[match 3]
            print p1 "\t" p2 "\t" p3 "\n"
     }
}

Hope this helps!

Heather

-------------------------
Heather Linsk
Lead Engineer
General Dynamics AIS
413-494-7095

Edited: 1-Nov-2007 at 12:26 by Heather Linsk
Report this to a Moderator Report this to a Moderator
 1-Nov-2007 13:20
User is offline View Users Profile Print this message


Louie Landale

Posts: 2070
Joined: 12-Sep-2002

It looks as though your 'Data' has a fixed format with exactly 3 fields. I don't see the advantage of that over just having 3 skip parellel skip lists.

- Louie
Report this to a Moderator Report this to a Moderator
 1-Nov-2007 14:42
User is offline View Users Profile Print this message


Heather Linsk

Posts: 50
Joined: 7-Mar-2006

I guess I am not sure what the difference is either.  But appearently at the time I thought there was.... :-)



-------------------------
Heather Linsk
Lead Engineer
General Dynamics AIS
413-494-7095
Report this to a Moderator Report this to a Moderator
 1-Nov-2007 19:45
User is offline View Users Profile Print this message


Pete Kowalski

Posts: 301
Joined: 7-Feb-2003

Louie:

The advantage I see is just using one Skip list. You are not limited to have fixed format with exactly 3 fields at all. You just need to make sure you have a good enough parser to parse the data out.

Heather:

Thanks for the sample code. It sure helps a lot by providing direction on how to approach this.

-------------------------
pete.kowalski(at)motorola.com
Report this to a Moderator Report this to a Moderator
Statistics
20925 users are registered to the Telelogic DOORS forum.
There are currently 1 users logged in.
The most users ever online was 15 on 15-Jan-2009 at 16:36.
There are currently 0 guests browsing this forum, which makes a total of 1 users using this forum.
You have posted 0 messages to this forum. 0 overall.

FuseTalk Standard Edition v3.2 - © 1999-2009 FuseTalk Inc. All rights reserved.