last edited by usericon

admin on 25-Apr-2010

Iterator

Important note about Java iterators

Iterator

One of the fundamental aspects of our daily work involves using data structures that contain many items. These include lists, arrays, structs and queries, and perhaps more sophisticated data structures such as trees. Each of these data structures requires a different approach to loop through their elements. For example, an array uses a numeric index, a struct uses a named key index, list items are accessed sequentially without any kind of index, etc.

In object oriented CFML these data structures are typically created and used within components. When we need to use these data structures we can just create a function on the component that returns the required data.

For example, if you were writing a shopping cart you might store your items in an array, then have a function items() which simply returns your array of items.

Shopping cart UML diagram

Your application may need to access the set of items from many places throughout your code:

Shopping cart used on many pages UML diagram

If your cart code is unlikely to change much then this is a clean and simple approach, however if you needed to change the data type of the items from an array to a struct then you would need to update every place in your application where the items were referenced and change the loop from an array loop to a struct loop.

Whenever you have an object returning one of it's internal data structures you may be revealing details about how your object was implemented. As a general design guideline we want to minimise exposing how our objects are implemented internally. In the case of our shopping cart it would be nice if we could hide the fact that we are actually using an array to internally store the items.

An Iterator provides a generalised technique for sequentially accessing elements from a group and allows you to hide the real data structure of your items.

Structure of an Iterator

An Iterator is an object that is wrapped around your data structure and simply keeps track of the next item that should be made available. There are a number of approaches to designing Iterators but a common approach requires that every Iterator implement two functions: hasNext() and next().

Iterator structure UML diagram

The hasNext() function returns either true or false indicating if another item available from the set.

The next() function returns the next element from the set.

So to use an Iterator in code, you may write:

<cfset iterator = ...>
<cfloop condition="iterator.hasNext()">
    <cfset element = iterator.next()>
    ... do something with element ...
</cfloop>

You will notice that when using an Iterator we have no knowledge of how the data was originally stored. It may have been an array, a struct, a list, etc. but this information is now hidden. And as a user of the iterator we are not concerned with whatever the original data structure was, we only need a technique for accessing all elements of the set.

Example: Iterating over elements of an array

Let's create an generic ArrayIterator that allows us to iterate over array elements. We know that we need to implement the two functions hasNext() and next(), so our ArrayIterator will look something like this:

Array Iterator UML diagram

We will provide the array as a parameter to the ArrayIterators init() function.

<cfcomponent output="false">

    <cfset variables.array = 0>

    <cffunction name="init" output="false">
        <cfargument name="array" required="true">
        <cfset variables.array = arguments.array>
    </cffunction>

</cfcomponent>

Now let's implement the hasNext() function. To implement this we need to keep track of the index to the next element of our array. We know that we have a next element available if this index is less than or equal to the length of our array.

<cfcomponent output="false">

    <cfset variables.array = 0>
    <cfset variables.next = 0>

    <cffunction name="init" output="false">
        <cfargument name="array" required="true">
        <cfset variables.array = arguments.array>
        <cfset variables.next = 1>
    </cffunction>

    <cffunction name="hasNext" output="false">
        <cfreturn variables.next le arrayLen(variables.array)>
    </cffunction>

</cfcomponent>

Lastly, let's add our next() function. This fetches the next element of the array, then increments the index by one ready for the next element.

<cfcomponent output="false">

    <cfset variables.array = 0>
    <cfset variables.next = 0>

    <cffunction name="init" output="false">
        <cfargument name="array" required="true">
        <cfset variables.array = arguments.array>
        <cfset variables.next = 1>
    </cffunction>

    <cffunction name="hasNext" output="false">
        <cfreturn variables.next le arrayLen(variables.array)>
    </cffunction>

    <cffunction name="next" output="false">
        <cfset element = variables.array[variables.next]>
        <cfset variables.next = variables.next + 1>
        <cfreturn element>
    </cffunction>

</cfcomponent>

To use our Array Iterator we may write:

<cfset arr = []>
<cfset arr[1] = "Red">
<cfset arr[2] = "Green">
<cfset arr[3] = "Blue">

<cfset iterator = createObject("component","ArrayIterator").init(arr)>

<cfloop condition="iterator.hasNext()">
    <cfset colour = iterator.next()>
    <!--- Do something with the colour variable--->
</cfloop>

This is a simple example only and does not include any error or multiple thread handling.

Example: Using an ArrayIterator in a Shopping Cart

Let's write a simple example of a shopping cart that makes use of our ArrayIterator.

Shopping cart UML diagram

addItem(item) adds an item to our cart.

items() returns an iterator of all shopping cart items.

This may be implemented as follows:

<component output="false">

    <!--- Array to hold our shopping cart items --->
    <cfset variables.instance = {}>
    <cfset variables.instance.items = []>

    <!--- Initialisation --->
    <cffunction name="init" output="false">
        <cfreturn this>
    </cffunction>

    <!--- Add an item to the cart --->
    <cffunction name="addItem" output="false">
        <cfargument name="item" required="true">
        <cfset arrayAppend(variables.instance.items,arguments.item)>
    </cffunction>

    <!--- Return the items as an iterator --->
    <cffunction name="items" output="false">
        <cfset var items = createObject("component","ArrayIterator").init(variables.instance.items)>
        <cfreturn items>
    </cffunction>

</cfcomponent>

Then using our shopping cart we may have:

<cfset cart.addItem(item1)>
<cfset cart.addItem(item2)>
<cfset cart.addItem(item3)>

<cfset items = cart.items()>
<cfloop condition="items.hasNext()">
    <cfset item = items.next()>
    <!--- Do something with item --->
</cfloop>

Iterating Business Objects

Within CFML there is a performance penalty associated with creating objects, and this becomes more apparent when dealing with many objects. For example, if you perform a query that returns one hundred or so records, then converting each record to an object will have a noticeable performance impact on your application.

An Iterating Business Object (IBO) is a pattern made popular by Peter Bell that is specific to the CFML language. It allows the benefits of objects without the performance problems of object creation. An IBO appears as though it were a regular object, but at the same time is also an Iterator that contains a set of many data items.

Let's consider a User object with the functions name(), dateOfBirth() and age().

User UML diagram

Objects of this kind only contain the data for a single user.

Now, let's create a User IBO, which has the same set of functions, plus an additional next() function. Notice that we are using a different name for this object to distinguish it from a conventional business object.

Iterating User UML diagram

Objects of this kind wraps the data for many users, but the IBO behaves as though it was only one of those users. Internally it is keeping track of which users' data is the "current" data.

The next() function tells the IBO to change itself internally so it should start behaving like the next User in the set. Unlike the next() function in the Iterator pattern described above which returns the next element from the set, this function returns either true or false to indicate if it has current valid data.

Let's take a look at how an IBO might be used.

<cfset userIBO = ...>
<cfloop condition="userIBO.next()">
    <cfoutput>
        #userIBO.name()#, #userIBO.age()#<br/>
    </cfoutput>
</cfloop>

We can see that the IBO is behaving like both an iterator and a regular business object.

Example: Iterating Business Object for a query

Query data is perhaps the most common scenario where an IBO may be useful, so let's develop an IBO to iterate over a query of users.

First, we need to provide our query data to the IBO's init() function:

<component name="UserIBO" output="false">

    <cfset variables.userQuery = 0>

    <cffunction name="init" output="false">
        <cfargument name="userQuery" required="true">
        <cfset variables.userQuery = arguments.userQuery>
        <cfreturn this>
    </cffunction>

</cfcomponent>

To implement our next() function we will need to keep track of which record from the query data we are up to. When our "currentRow" pointer has a higher value than the number or records in the query then we know that there is no more data available.

<component name="UserIBO" output="false">

    <cfset variables.userQuery = 0>
    <cfset variables.currentRow = 0>

    <cffunction name="init" output="false">
        <cfargument name="userQuery" required="true">
        <cfset variables.userQuery = arguments.userQuery>
        <cfreturn this>
    </cffunction>

    <cffunction name="next" output="false">
        <cfset variables.currentRow = variables.currentRow + 1>
        <cfreturn variables.currentRow le variables.userQuery.recordCount>
    </cffunction>

</cfcomponent>

Now let's implement our name(), dateOfBirth() and age() functions, which makes use of accessing query data as an array.

<component name="UserIBO" output="false">

    <cfset variables.userQuery = 0>
    <cfset variables.currentRow = 0>

    <cffunction name="init" output="false">
        <cfargument name="userQuery" required="true">
        <cfset variables.userQuery = arguments.userQuery>
        <cfreturn this>
    </cffunction>

    <cffunction name="next" output="false">
        <cfset variables.currentRow = variables.currentRow + 1>
        <cfreturn variables.currentRow le variables.userQuery>
    </cffunction>

    <cffunction name="name" output="false">
        <cfreturn variables.userQuery["name"][variables.currentRow]>
    </cffunction>

    <cffunction name="dateOfBirth" output="false">
        <cfreturn variables.userQuery["dob"][variables.currentRow]>
    </cffunction>

    <cffunction name="age" output="false">
        <cfreturn dateDiff("yyyy", dateOfBirth(), now())>
    </cffunction>

</cfcomponent>

To use our UserIBO we may have something like:

<cfset userIBO = userService.findAllUsers()>
<cfloop condition="userIBO.next()">
    <cfoutput>
        #userIBO.name()#, #userIBO.age()#<br/>
    </cfoutput>
</cfloop>

This is only a simple example that does not include error or multiple thread handling.

Advantages and disadvantages of an Iterating Business Object

Let's take a quick review of the advantages and disadvantages for an IBO.

Advantages

Only one object per data set, so little or no performance impact
Hides details of the underlying data structure (query, array, etc)
Makes your data look like a regular object

Disadvantages

The "insides" of your object change on each iteration so you cannot keep references to individual elements in the set (i.e. only one reference exists for all elements in the set)
More care needs to be taken when implementing more advanced functionality within your object.

When to use an Iterating Business Object?

IBOs are most commonly used when we need to work a large number of objects, such as data returned from a database query.

The choice of using an IBO versus using the original data really depends on how much behaviour you would include in your object. For example, if you have a query of users and the only additional behaviour you need is to calculate the age for each record then it may be better to include this as a calculated column and then just use the query data. However if you have a lot of extra functionality in your object that would be messy or complicated to include in the original query then an IBO may be a better option.

Using underlying Java iterators

Within ColdFusion we also have the option of accessing the underlying Java iterators for arrays and structs.

For an array, we can use the following:

<cfset iterator = yourArray.iterator()>
<cfloop condition="iterator.hasNext()">
    <cfset item = iterator.next()>
    ...
</cfoop>

For a struct, we can use:

<cfset iterator = yourStruct.values().iterator()>
<cfloop condition="iterator.hasNext()">
    <cfset item = iterator.next()>
    ...
</cfoop>

Important note about Java iterators

It is important to note that if your original array or struct is modified while you are iterating though their elements then an error will occur. If this is a possible situation then you can copy your array or struct before retrieving it's iterator.

Extending your Iterators

The description of the iterators we have discussed so far include at most a hasNext() function and a next() function.

This very simple interface allows you to easily change the underlying implementation without affecting any client code using the iterators. There may be some situations where some additional functions may be useful to include.

first() - moves the iterator pointer to the first item in the set
last() - moves the iterator pointer to the last item in the set
previous() - moves the iterator to the previous item in the set
hasPrevious() - returns true if a previous item is available
count() - returns a count of the number of items in the set

Keep in mind that by adding any of these functions you may limit your flexibility in changing the underlying implementation in the future. For example if you expose a count() or previous() function, then you would not be able to substitute in a Java iterator as these functions are not supported.