Skip to Content
Skip to Table of Contents

← Previous Article Next Article →

ATPM 9.07
July 2003

Columns

How To

Extras

Reviews

Download ATPM 9.07

Choose a format:

Roll Your Own

by Charles Ross, cross@atpm.com

Getting the List of It—Part 2

Welcome back to Roll Your Own, the column where we learn how to create software with AppleScript.

The last few columns have been spent learning about object-oriented programming, and last month we began creating a complex list object. This time we’re going to take our list object a bit further, adding functionality that isn’t available with AppleScript’s built-in list data type.

Here’s the programming behind our list object from last month.

on MakeList(newList)
    script ListObject
        property theList : newList
        to Normalize()
            if class of theList is record then
                set theList to theList as list
            end if
            try
                repeat with i from 1 to count of theList
                    set item i of theList to ¬
                        ((item i of theList) as string)
                end repeat
            on error errMsg number errNum
                if errNum is -1700 then
                    error "List cannot be normalized to list" & ¬
                        " of strings." number 501
                else
                    error errMsg number errNum
                end if
            end try
        end Normalize
        to SetList given listToSet:newList
            set tempList to theList
            try
                set theList to newList
                Normalize()
            on error errMsg number errNum
                set theList to tempList
                if errNum is 501 then
                    error "List canot be normalized to list" & ¬
                        " of strings." number 501
                else
                    error errMsg number errNum
                end if
            end try
        end SetList
        to GetList()
            return theList
        end GetList
        to MemberCount()
            return count of theList
        end MemberCount
        on ItemX given theIndex:x
            if x is greater than MemberCount() or ¬
                (x * -1) is greater than MemberCount() or ¬
                x is 0 then
                error "Invalid index passed to ItemX()" number 502
            else
                return item x of theList
            end if
        end ItemX
    end script
    tell ListObject to Normalize()
    return ListObject
end MakeList

We left the list in this form, which pretty much duplicates what AppleScript’s built-in list does. AppleScript’s list however does not support sorting, or the ability to insert an element at an arbitrary point. We’ll expand our ListObject to include these two features this month.

First we’ll add the ability for the list to return a sorted version of itself. There are numerous algorithms available for sorting data. Each of them has tradeoffs and advantages. If you’re interested in a thorough discussion of sorting algorithms, you may want to check out a computer science textbook, or perhaps visit one of the many Web sites dedicated to the topic, such as Wikipedia and notes from the University of Hawaii.

Sorting

Sort algorithms have different names, and the one we’ll be using is called Selection Sort, which is actually taken from Apple’s Web site. It loops through the values to be sorted, extracting the lowest member of the list and inserting it at the end of a new list. Perhaps an example will help make this clear. Remember, computers are stupid, and every task given to a computer must be minutely directed.

Let’s begin with a list of four numbers, {3, 1, 4, 2}. We want to sort this in ascending order, so that the lowest number comes first and the highest number comes last.

We initialize two new lists, one to store our sorted version and one to store the indices of members that have already been sorted. We’ll call these two new lists sortedList and indexList, and both are empty to begin with. We need a variable to store our current lowest value, and we’ll call this lowItem, which begins as a blank string to indicate that it hasn’t been set yet.

We now loop through the list. The first item in the list is 3. Since our lowItem is currently blank, we store this number in lowItem. Moving to the next number in the list, we find a 1. This is lower than our lowItem, so we set lowItem to 1. Next we come to the 4. This is greater than our lowItem, so we leave it alone. Similarly, when we come to 2, our lowItem variable is lower.

So, with our first pass through the list, the lowest value is 1. We add this to our sortedList, which now has a value of {1}. We also record the index we found that value in, so our indexList has a value of {2}.

Now we initialize lowItem to a blank string again, and loop through the list again. First, we again come to the 3. Since lowItem is blank, we store the 3 in it. Then we come to the 1. But this has an index of 2, which is in our indexList variable, so we ignore it. Next we come to the 4, which is greater than our lowItem, so we ignore it too. Finally, we come to the 2, which is less than our lowItem. We set lowItem to 2, and since we’ve finished looping through our list, we’ve found the next lowest value we need. We add 2 to the end of our sortedList so it has a value of {1, 2} now, and we store the index of the lowest value we found, so indexList has a value of {2, 4}.

Rinse and repeat. Set lowItem to a blank string. Loop through again. First, since lowItem is blank, record the 3. Since the index of 1 is in our indexList, ignore it. Since 4 is greater than 3, ignore it. Since 2’s index has been sorted, ignore it. We’re done looping through the list, so record the index of the current lowest item and add the item to the end of the sortedList. sortedList now has a value of {1, 2, 3} and indexList has a value of {2, 4, 1}.

In our final loop through the list, this time we ignore 3 because it’s been sorted. We also ignore the 1, and then store the 4 in lowItem. We ignore the 2 as it has already been sorted, and we’re done. Add the 4 to the end of sortedList so that it now has a value of {1, 2, 3, 4}.

Keep in mind, there are more efficient ways to sort data. However, this one is fairly easy to understand and, therefore, easy to write in AppleScript.

We’re going to add a bit of functionality to this algorithm, so it lets the user specify whether the sort should happen in ascending or descending order. To do this, we will need to add another property to our ListObject. We’ll call this property sortOrder. It will hold one of three strings: "none", "ascending" or "descending", and it will be initialized to a value of "none".

In your ListObject definition, just after the declaration of the theList property, declare a new property with the following line of code:

property sortOrder : "none"

Since we now have a property that stores the sort order of the list, we need a way to set that property. Add the following SetSortOrder() method to your ListObject definition.

on SetSortOrder given theSortOrder:newSortOrder
    if newSortOrder is not in ¬
        {"ascending", "descending", "none"} then
        error "Invalid sort order sent to " & ¬
            "SetSortOrder()" number 503
    else
        set sortOrder to newSortOrder
    end if
end SetSortOrder

If you recall, when we discussed object-oriented programming, we mentioned that methods come in two forms: public and private. Additionally, although AppleScript does not explicitly support private methods, you, as the programmer, can always obey these concepts. This SetSortOrder() method falls under the private category. It is not meant to be called by any code other than that which exists within the ListObject definition.

We now have a handler that will set the sortOrder property. We should also provide one that allows calling code to get this property. Here’s the AppleScript code for such a handler. Go ahead and add it to the ListObject definition.

on ListSortedBy()
    return sortOrder
end ListSortedBy

In keeping with the philosophy that object methods shouldn’t alter internal data unless specifically told to do so, our sort method will generate a new list that contains the current list in the specified sort order. Add the following Sorted() handler to the ListObject definition:

on Sorted given theSortOrder:orderToSort
    if orderToSort is not in {"ascending, descending"} then
        error "Invalid sort order passed to " & ¬
            "Sorted()" number 504
    else
        set indexList to {}
        set sortedList to {}
        repeat MemberCount() times
            set lowItem to ""
            repeat with i from 1 to MemberCount()
                if i is not in indexList then
                    set thisItem to item i of theList as text
                    if lowItem is "" then
                        set lowItem to thisItem
                        set lowItemIndex to i
                    else if thisItem comes before ¬
                        lowItem then
                        set lowItem to thisItem
                        set lowItemIndex to 1
                    end if
                end if
            end repeat
            set end of sortedList to lowItem
            set end of indexList to lowItemIndex
        end repeat
        if orderToSort is "ascending" then
            set newList to MakeList(sortedList)
            tell newList
                SetSortOrder given theSortOrder:"ascending"
            end tell
        else
            set newList to MakeList(reverse of sortedList)
            tell newList
                SetSortOrder given theSortOrder:"descending"
            end tell
        end if
        return newList
    end if
end Sorted

After performing a quick check that the sort order specified is valid, we follow the algorithm discussed above to sort the list in ascending order. Like we did in the last column, we’re using the MemberCount() method to get the number of members in the list. This ensures that if we ever change how we store our list, and therefore change how the number of members would be computed, this handler will still work.

Once we have the list sorted in ascending order, we then cover the two possibilities for the sort order. If the sort order was specified to be ascending, then we use our sortedList as the parameter passed to MakeList() to generate a new ListObject. If the sort order should be ascending, we simply pass the new list as it is. If, however, the sort order is descending, we pass the reverse of the new list. Once we’ve created our new list, we set the sort order property of the new list using the method we wrote above.

Counting Occurrences

Now we will add to ListObject the ability to count how many times a member appears. This will be related to a future method that will return the index of a given item. The following listing should be added to our ListObject definition.

on OccurrenceCount given itemToFind:theItem
    set occurrenceCounter to 0
    repeat with i from 1 to MemberCount()
        if item i of theList is theItem then ¬
            set occurrenceCounter to occurrenceCounter + 1
    end repeat
    return occurrenceCounter
end OccurrenceCount

This is a fairly simple handler. After initializing a counter variable to 0, we loop through the members of the list. Whenever the current member is equal to the item being searched for, we increment the counter by 1. Once we’re finished looping through the list, we return this counter to the calling code.

Note that this handler can also serve as a way to determine whether an item is in the list at all. By passing a possible member to this handler, we know that if it returns 0, the item is not in the list.

Now that we’ve provided the means for the user to check whether an item is in the list or not, we’ll next provide a way to get the index of an item given the item and which occurrence of the item to find. Add the code for IndexOf() to the ListObject definition.

on IndexOf given itemToFind:theItem, whichOccurrence:occurrence
    if class of occurrence is in {real, integer} then
        try
            set occurrence to occurrence as integer
        on error
            error "Cannot get occurrence of " & occurrence & ¬
                "of an item." number 505
        end try
        if occurrence is less than or equal to 0 then
            error "Cannot get occurrence of " & occurrence & ¬
                "of an item." number 505
        else
            if theItem is not in theList then
                return 0
            else
                set occurrenceCounter to 1
                repeat with i from 1 to MemberCount()
                    if theItem is item i of theList then
                        if occurrence is occurrenceCounter then
                            return i
                        else
                            set occurrenceCounter to ¬
                                occurrenceCounter + 1
                        end if
                    end if
                end repeat
                return 0
            end if
        end if
    else
        error "Invalid parameter passed to IndexOf()" number 506
    end if
end IndexOf

The first thing we need to think of with this handler is what could go wrong. The handler expects two parameters: the item to find and which occurrence of the item to return the index of. We don’t need to worry about theItem. It can be pretty much anything. However, we do need to perform some error checking regarding the occurrence parameter.

First of all, occurrence should be either an integer or a real number that can be converted to an integer (such as 5.0). So the first thing we do is check whether the parameter is one of these two data types. If it is, we attempt to coerce the parameter into an integer. If it either already is an integer or is a real with no fractional part, this will work without a hitch. However, if an error occurs, then it must have been a real with a fractional part (such as 5.1). Since we captured this error within a try block, we can report the error back to the calling code.

If we’ve gotten past the try block in our handler, then the occurrence parameter is now certainly an integer. However, not all integers are useful. Only positive integers make sense as an occurrence of an item. Therefore, we check that occurrence is positive, and if it isn’t return an error to the calling code.

Finally, we’re sure that occurrence makes sense, so we check whether the item is in the list at all. After all, if it isn’t in the list, we don’t need to loop through the list and waste time. If the item isn’t in the list, then we immediately return a 0.

If we’re still in the handler, we know that there is at least one occurrence of the item in the list. So we loop through the list until we find the item. Once we do find it, we check our occurrenceCounter variable against the occurrence parameter. If we’ve found the specified occurrence, we return the index of the current item. If we haven’t yet found the right occurrence, we increment occurrenceCounter and continue looping.

There’s one last scenario we need to account for. Perhaps the item is in the list, and the occurrence is a valid positive integer, but the occurrence parameter is greater than the number of occurrences of the item. For instance, perhaps there are 3 occurrences of the item, but the occurrence parameter was passed a value of 5. We have two choices: we can return an error, or we can return a value of 0. The version of the handler does the later, but a case could be made for generating an error.

Inserting at an Arbitrary Index

As mentioned previously, there is no built-in way of inserting an item into an AppleScript list data type at some arbitrary point. This next handler adds this functionality to our ListObject. Add it to the object definition.

on InsertItem given itemToInsert:theItem, atPosition:thePosition
    if class of thePosition is not in {real, integer} then ¬
        error "Invalid position passed to InsertItem()" number 507
    if thePosition is 0 then
        error "Can't set item 0 of list" number 508
    else if thePosition is less than 0 then
        if (thePosition * -1) is greater than ¬
            MemberCount() + 1 then ¬
            set thePosition to (MemberCount() + 1) * -1
    else
        if thePosition is greater than MemberCount() + 1 then ¬
            set thePosition to MemberCount() + 1
    end if
    set newList to theList
    if thePosition is less than 0 then
        if (thePosition * -1) is MemberCount() + 1 then
            set beginning of newList to theItem
        else
            set newList to reverse of newList
            set thePosition to (thePosition * -1)
            set newList to (items 1 thru ¬
                (thePosition - 1) of newLIst) & ¬
                theItem & (items thePosition thru -1 of newList)
            set newList to reverse of newList
        end if
    else
        if thePosition is 1 then
            set beginning of newList to theItem
        else if thePosition is (MemberCount() + 1) then
            set end of newList to theItem
        else
            set newList to (items 1 thru ¬
                (thePosition - 1) of newList & ¬
                theItem & (items thePosition thru -1 of newList)
        end if
    endif
    return MakeList(newList)
end InsertItem
The first thing our handler does is make sure that thePosition is an integer (or can be coerced into an integer). If it isn’t, an error is generated, since only integers are valid for thePosition.

Then our InsertItem() handler checks that the thePosition parameter makes sense. If thePosition is zero, an error is generated, since we can’t set the 0th item of a list. If thePosition is greater than 0, we check to see if the absolute value of thePosition is also greater than the number of items in the list plus one. If it is, we have two options. We can either generate an error as we did when thePosition was zero, or we can reset thePosition so that it makes sense. This handler does the latter, so that if theList contains 5 members, and this handler is told to insert an item at position 10, it will instead insert an item at position 6, since that is the largest position it can set.

Notice that we allow negative indices of AppleScript lists, which indicate that counting should start from the end of the list, rather than the beginning. It makes the code more complex, but keeps the base functionality of the AppleScript list while still providing our additional features.

Now that we know that the thePosition variable is within the required range, we create a new variable, newList, that is set to our theList property. If a negative number was passed for thePosition, we reverse this list and multiply thePostion by -1, and then insert the item into the indicated place within the list. If the thePosition is positive, then we simply insert the item into the place indicated.

Let’s go through an example of using the handler to clarify how it is working. We’ll assume that theList has a value of {"Apple", "Script", "Programming"} and that InsertItem() is called with InsertItem given itemToInsert:"Language" atPosition:2.

Since thePosition has a value of 2, which is an integer, the first error checking is successful. Since it is not 0, the second error check is also successful.

2 is not less than 0, nor is it greater than the number of items plus one, so the value of thePosition doesn’t change. newList is now set to the value of theList, so newList also has a value of {"Apple", "Script", "Programming"}.

Since 2 is greater than 0, the else block is executed that checks if thePosition is 1, followed by a check that thePosition is equal to 1 plus the number of members in the list. Neither of these tests is true, so the final else block is executed. The line that does the actual job reads:

set newList to (items 1 thru ¬
    (thePosition - 1) of newList) & ¬
    theItem & (items thePosition thru -1 of newList)

Replacing all of the variables in the expression with their values and doing a bit of math brings the code fragment to:

set newList to (items 1 thru ¬
    1 of {"Apple", "Script", "Programming") & ¬
    "Language" & (items 2 thru -1 of {"Apple", "Script", "Programming"})

Evaluating the items x thru y portions of the code fragment results in:

set newList to {"Apple"} & "Language" & {"Script", "Programming"}

Finally, applying the ampersand operator to the expression results in:

set newList to {"Apple", "Langauge", "Script", "Programming"}

This would then be passed to MakeList() and the new ListObject returned by that handler would be returned the original calling code.

Try working through the handler with InsertItem given itemToInsert:"Language", atPosition:-3. (Hint: the final result will be the same as what we just got with thePosition being passed a value of 2.)

• • •

As you can see, our object is becoming more complicated yet more useful each time we add functionality to it. I hope you’ll join me next time when we continue to improve our ListObject. Until then, happy programming!

Also in This Series

Reader Comments (1)

Anton Wilson · July 16, 2003 - 21:37 EST #1
Your series has greatly increased my grasp of the utility of the "script object." Thanks. Also, the exposure to the use of labeled parameters is helpful. I recently read about linked lists in a novice programming book. I played around with this code:
--make a linked list
set oneList to {"one", "two", "three", 0, a reference to twoList}
set twoList to {"four", "five", "six", a reference to oneList, a reference to threeList}
set threeList to {"seven", "eight", "nine", a reference to twoList, 0}
set linkedList to {oneList, twoList, threeList}
--append linkedList
set fourList to {1, 2, 3}
appendLinkedList(a reference to fourList, linkedList)
set fiveList to {4, 5, 6}
appendLinkedList(a reference to fiveList, linkedList)
set sixList to {7, 8, 9}
appendLinkedList(a reference to sixList, linkedList)
return linkedList

on appendLinkedList(newList, linked_List)
	set item -1 of (item -1 of linked_List) to newList
	set end of newList to item -1 of (item -2 of linked_List)
	set end of newList to 0
	set end of linked_List to contents of newList
end appendLinkedList
--end
Is a fully functioning linked list script object feasible in AppleScript? If so, could that be a future subject for your series? Thanks again. Anton

Add A Comment





 E-mail me new comments on this article