Multidimensional List Access Problem

Suppose you wanted to create a 2-dimensional list. This can be easily done with the list constructor. ex:

mylist = list(list(9))

Now suppose we wanted to access the item in the second dimension of the list. Lists are special in that they are objects that contain other objects without themselves containing variables. To access an item in the list, we use the item_at() system function. This returns an object. Performing it once will return the child list. From there, we can call item_at() in succession to access the item of interest:

myitem = item_at(item_at(mylist: 0) 0)

If you must iterate through many items in a list, this is safe but slow. Suppose you wanted to save time by using a pointer to point to the child list:

mysublist ~ item_at(mylist: 0)

This won’t work the way you want. What happens here is that, because lists contain only objects, you cannot point to them with variables. Variables can only store functions or point to functions. So what happens is that mysublist becomes a copy of the child list we accessed.

At first it would seem we are doomed to slow speeds, or at least we would be if we continue to use the built-in list system. If we have a 3-dimensional list, things get even slower because we have 3 calls to item_at(). To get around the problem, we will need to create a linked list using Copper. We can use a singly linked list to avoid the mess of tracking pointers with a doubly-linked list. The list may look like the following:

SLList = [
 item = {}
 next = {}
 append = [item] {
   super.next = [
    item = item
    next = {}
    append = super.append
   ]
 }
]
mylist = SLList # Create a node #

This list will allow us to point to individual nodes, thereby saving a fraction of time accessing them. Bear in mind however that time savings are proportional to list size. In small lists, the time to access nodes is determined primarily by hash-table searches for the variable name “next” in the SLList scope.

Deletion is as easy as assigning empty function to “next”.

There are some limitations of this list. For one, you cannot extract a node nor delete a node surrounded by other nodes without copying all of the subsequent nodes (e.g. via mylist.next = mylist.next.next).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s