Roll Your Own
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 InsertItemThe 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!
Copyright © 2003 Charles Ross,
cross@atpm.com. Charles Ross is an independent developer and author. He’s written articles for ISO FileMaker Magazine and is currently writing a book on creating applications with AppleScript Studio.
Also in This Series
- Getting the List of It—Part 2 · July 2003
- Getting the List of It · June 2003
- The Object of Programming—Part 2 · March 2003
- The Object of Programming · February 2003
- How to Handle Anything · January 2003
- Try to Handle This · December 2002
- Charting Your Success · September 2002
- Go with the Flow · August 2002
- Variables and Data · June 2002
- The Ultimate Customization · May 2002
- Complete Archive
Reader Comments (1)
--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 --endIs a fully functioning linked list script object feasible in AppleScript? If so, could that be a future subject for your series? Thanks again. AntonAdd A Comment