[ In Action ] The collective Groovy datatypes - Working with lists

Preface: 
Java arrays cannot be changed in length, so you cannot add elements easily. One way is to convert the array to a java.util.List , add the element, and convert back. A second way is to construct a new array of size+1, copy the old values over, and set the new element to the last index position. Either takes some lines of code. 

But Java arrays also have their benefits in terms of language support. They work with the subscript operator to easily retrieve elements of an array by index likemyarray[index] , or to store elements at an index position with myarray [index] = newElement . 

We will demonstrate how Groovy lists give you the best of both approaches, extending the features for smart operator implementations, method overloading, and using lists as Booleans. With Groovy lists, you will also discover new ways of leveraging the power of the Java Collections API. 

Specifying lists: 
Listing 4.4 shows various ways of specifying lists. The primary way is with square brackets around a sequence of items, delimited with commas: 

view plaincopy to clipboardprint?

1. def list = [item, item, item]  

The sequence can be empty to declare an empty list. Lists are by default of type java.util.ArrayList and can also be declared explicitly by calling the respective constructor. The resulting list can still be used with the subscript operator. In fact, this works with any type of list, as we show here with type java.util.LinkedList. 

Lists can be created and initialized at the same time by calling toList on ranges. 
- Listing 4.4 Specifying lists 

view plaincopy to clipboardprint?

1. myList = [1,2,3]  
2. assert myList.size() == 3  
3. assert myList[0]     == 1  
4. assert myList instanceof ArrayList  
5.   
6. emptyList = []  
7. assert emptyList.size() == 0  
8. longList = (0..1000).toList()  
9. assert longList[555] == 555  
10. explicitList = new ArrayList()  
11. explicitList.addAll(myList)  
12. assert explicitList.size() == 3  
13. explicitList[0] = 10  
14. assert explicitList[0] == 10  
15.   
16. explicitList = new LinkedList(myList) // 1) Fill from myList  
17. assert explicitList.size() == 3  
18. explicitList[0] = 10  
19. assert explicitList[0] == 10  

The GDK extends all arrays, collection objects, and strings with a toList method that returns a newly generated list of the contained elements. Strings are handled like lists of characters. 

Using list operators: 
Lists implement some of the operators that you saw in section 3.3. Listing 4.4 contained two of them: the getAt and putAt methods to implement the subscript operator. But this was a simple use that works with a mere index argument. There’s much more to the list operators than that. 

The subscript operator 
The GDK overloads the getAt method with range and collection arguments to access a range or a collection of indexes. This is demonstrated in Listing 4.5. 
- Listing 4.5 Accessing parts of a list with the overloaded subscript operator 

view plaincopy to clipboardprint?

1. myList = ['a','b','c','d','e','f']     
2.                                          
3. assert myList[0..2]  == ['a','b','c']       // getAt(Range)  
4. assert myList[0,2,4] == ['a','c','e']       // getAt(collection of indexes)  
5.                                               
6. myList[0..2] = ['x','y','z']                // putAt(Range)  
7. assert myList == ['x','y','z','d','e','f']    
8.                                               
9. myList[3..5] = []                           // 1) Removing elements  
10. assert myList == ['x','y','z']                
11.                                               
12. myList[1..1] = ['1','2']                    // 2) Adding elements  
13. assert myList == ['x','1','2','z']  

In addition to positive index values, lists can also be subscripted with negative indexes that count from the end of the list backward. Figure 4.1 show how positive and negative indexes map to an example list [0,1,2,3,4] . 
 

Consequently, you get the last entry of a non-empty list with list[-1] and the next-to-last with list[-2]. Negative indexes can also be used in ranges, so list[-3..-1] gives you the last three entries. When using a reversed range, the resulting list is reversed as well, so list[4..0] is [4,3,2,1,0] . In this case, the result is a new list object rather than a sublist in the sense of the JDK. Even mixtures of positive and negative indexes are possible, such as list[1..-2] to cut away the first entry and the last entry. 

view plaincopy to clipboardprint?

1. myList = ['x','1','2','z']  
2. alist = myList[1..-2]  
3. assert alist == ['1','2']  

Tips: 

Ranges in List ’s subscript operator are IntRanges. Exclusive IntRanges are mapped to inclusive ones at construction time, before the subscript operator comes into play and can map negative indexes to positive ones. This can lead to surprises when mixing positive left and negative right bounds with exclusiveness; for example,IntRange (0..<-2) gets mapped to (0..-1) , such that list[0..<-2] is effectively list[0..-1] . 

Although this is stable and works predictably, it may be confusing for the readers of your code, who may expect it to work like list[0..-3] . For this reason, this situation should be avoided for the sake of clarity.

Adding and removing items 
Although the subscript operator can be used to change any individual element of a list, there are also operators available to change the contents of the list in a more drastic way. They are plus(Object) , plus(Collection) , leftShift(Object) , minus(Collection) , and multiply . Listing 4.6 shows them in action. The plus method is overloaded to distinguish between adding an element and adding all elements of a collection. The minus method only works with collection parameters. 
- Listing 4.6 List operators involved in adding and removing items 

view plaincopy to clipboardprint?

1. myList = []            
2.             
3. myList += 'a'                   // plus(Object)  
4. assert myList == ['a']  
5.   
6. myList += ['b','c']             // plus(Collection)  
7. assert myList == ['a','b','c']  
8.   
9. myList = []  
10. myList <<  'a' << 'b'           // leftShift is like append  
11. assert myList == ['a','b']  
12.   
13. assert myList - ['b'] == ['a']  // minus(Collection)  
14.   
15. // Multiply  
16. assert myList * 2 == ['a','b','a','b']  

Control structures 
Groovy lists are more than flexible storage places. They also play a major role in organizing the execution flow of Groovy programs. Listing 4.7 shows the use of lists in Groovy’s if , switch , and for control structures. 
- Listing 4.7 Lists taking part in control structures 

view plaincopy to clipboardprint?

1. myList = ['a', 'b', 'c']  
2. assert myList.isCase('a')  
3.   
4. // 1) Classify by containment  
5. candidate = 'a'  
6. switch(candidate){  
7.     case myList : assert true; break     
8.     default     : assert false  
9. }  
10.   
11. // 2) Intersection filter  
12. assert ['x','a','z'].grep(myList) == ['a']  
13.   
14. // 3) Empty lists are false     
15. myList = []  
16. if (myList) assert false     
17. // Lists can be iterated with a 'for' loop  
18. log = ''  
19. for (i in [1,'x',5]){   // 4) for in Collection  
20.     log += i  
21. }  
22. assert log == '1x5'  

Using list methods: 
There are so many useful methods on the List type that we cannot provide an example for all of them in the language description. The large number of methods comes from the fact that the Java interface java.util.List is already fairly wide (25 methods in JDK 1.4). 

Furthermore, the GDK adds methods to the List interface, to the Collection interface, and to Object . Therefore, many methods are available on the List type, including all methods of Collection and Object. While working with lists in Groovy, there is no need to be aware of whether a method stems from the JDK or the GDK, or whether it is defined in the List or Collection interface. However, for the purpose of describing the Groovy List datatype, we fully cover the GDK methods on lists and collections, but not all combinations from overloaded methods and not what is already covered in the previous examples. We provide only partial examples of the JDK methods that we consider important. 

Manipulating list content 
A first set of methods is presented in Listing 4.8. It deals with changing the content of the list by adding and removing elements; combining lists in various ways; sorting, reversing, and flattening nested lists; and creating new lists from existing ones. 
- Listing 4.8 Methods to manipulate list content 

view plaincopy to clipboardprint?

1. assert [1,[2,3]].flatten() == [1,2,3]         
2.                                                 
3. assert [1,2,3].intersect([4,3,1])== [3,1]     
4. assert [1,2,3].disjoint([4,5,6])              
5.                                                 
6. list = [1,2,3]                                
7. def popped = list.pop()     // 1) Treating a list like a stack  
8. assert popped == 3                            
9. assert list == [1,2]                          
10.                                                 
11. assert [1,2].reverse() == [2,1]               
12.                                                 
13. assert [3,1,2].sort() == [1,2,3]              
14.                                                                    
15. def list = [ [1,0], [0,1,2] ]                  
16. list = list.sort { a,b -> a[0] <=> b[0] }   // 2) Comparing lists by first element  
17. assert list == [ [0,1,2], [1,0] ]      
18. list = list.sort { item -> item.size() }   // 3) Comparing lists by size  
19. assert list == [ [1,0], [0,1,2] ]   
20.                                                 
21. list = ['a','b','c']                            
22. list.remove(2)              // 4) Removing by index  
23. assert list == ['a','b']                        
24. list.remove('b')            // 5) Removing by value  
25. assert list == ['a']  
26.   
27. list = ['a','b','b','c']  
28. list.removeAll(['b','c'])  
29. assert list == ['a']  
30.                           
31. // 6) Transforming one list to another list        
32. def doubled = [1,2,3].collect{ item ->  
33.     item*2  
34. }  
35. assert doubled == [2,4,6]  
36.                                           
37. // 7) Finding any element matching the closure    
38. def odd = [1,2,3].findAll{ item ->  
39.     item % 2 == 1  
40. }  
41. assert odd == [1,3]  

Two issues related to changing an existing list are removing duplicates and removing null values. One way to remove duplicate entries is to convert the list to a datatype that is free of duplicates: a Set . This can be achieved by calling a Set ’s constructor with that list as an argument. 

view plaincopy to clipboardprint?

1. def x = [1,1,1]  
2. assert [1] == new HashSet(x).toList()  
3. assert [1] == x.unique()  

If you don’t want to create a new collection but do want to keep working on your cleaned list, you can use the unique method, which ensures that the sequence of entries is not changed by this operation. Removing null from a list can be done by keeping all non-null s—for example, with the findAll methods that you have seen previously: 

view plaincopy to clipboardprint?

1. def x = [1,null,1]  
2. assert [1,1] == x.findAll{it != null}  
3. assert [1,1] == x.grep{it}  

You can see there’s an even shorter version with grep , but in order to understand its mechanics, you need more knowledge about closures (Chapter 5) and “The Groovy truth” (Chapter 6). Just take it for granted until then. 

Accessing list content 
Lists have methods to query their elements for certain properties, iterate through them, and retrieve accumulated results. Query methods include a count of given elements in the list, min and max , a find method that finds the first element that satisfies a closure, and methods to determine whether any or every element in the list satisfies a closure. Iteration can be achieved as usual, forward with each or backward with eachReverse . 

Cumulative methods come in simple and sophisticated versions. The join method is simple: It returns all elements as a string, concatenated with a given string. The injectmethod is inspired by Smalltalk. It uses a closure to inject new functionality. That functionality operates on an intermediary result and the current element of the iteration. The first parameter of the inject method is the initial value of the intermediary result. In listing 4.9, we use this method to sum up all elements and then use it a second time to multiply them. 
- Listing 4.9 List query, iteration, and accumulation 

view plaincopy to clipboardprint?

1. // Querying  
2. def list = [1,2,2,3,3,3]  
3. assert list.count(2) == 2                 
4. assert list.max() == 3                    
5. assert list.min() == 1                    
6.                                           
7. def even = list.find { item ->            
8.     item % 2 == 0                         
9. }                                         
10. assert even == 2                          
11.                                 
12. assert list.every { item -> item < 5}     
13. assert list.any   { item -> item < 2}  
14.   
15. // Iteration  
16. def store = ''  
17. list.each { item ->  
18.     store += item  
19. }  
20. assert store == '122333'  
21.                               
22. store = ''  
23. list.reverseEach{ item ->  
24.     store += item  
25. }  
26. assert store == '333221'  
27.   
28. // Accumulation  
29. assert list.join('-') == '1-2-2-3-3-3'  
30.   
31. def result = list.inject(0){ clinks, guests ->  
32. clinks += guests  
33. }  
34. assert result     == 0+1+2+2+3+3+3  
35. assert list.sum() == 14  
36.   
37. def factorial = list.inject(1){ fac, item ->  
38. fac *= item  
39. }  
40. assert factorial == 1*1*2*2*3*3*3  

Understanding and using the inject method can be a bit challenging if you’re new to the concept. Note that it is exactly parallel to the iteration examples, with store playing the role of the intermediary result. The benefit is that you do not need to introduce that extra variable to the outer scope of your accumulation, and your closure has no side effects on that scope. 

The GDK introduces two more convenience methods for lists: asImmutable and asSynchronized . These methods use Collections.unmodifiableList andCollections.synchronizedList to protect the list from unintended content changes and concurrent access. See these methods’ Javadocs for more details on the topic. 

Lists in action: 
After all the artificial examples, you deserve to see a real one. Here it is: We will implement Tony Hoare’s Quicksort 1 algorithm in listing 4.10. To make things more interesting, we will do so in a generic way; we will not demand any particular datatype for sorting. We rely on duck typing—as long as something walks like a duck and talks like a duck, we happily treat it as a duck. For our use, this means that as long as we can use the < , = , and > operators with our list items, we treat them as if they were comparable. 

The goal of Quicksort is to be sparse with comparisons. The strategy relies on finding a good pivot element in the list that serves to split the list into two sublists: one with all elements smaller than the pivot, the second with all elements bigger than the pivot. Quicksort is then called recursively on the sublists. The rationale behind this is that you never need to compare elements from one list with elements from the other list. If you always find the perfect pivot, which exactly splits your list in half, the algorithm runs with a complexity of n*log(n). In the worst case, you choose a border element every time, and you end up with a complexity of n^2 . In listing 4.10, we choose the middle element of the list, which is a good choice for the frequent case of preordered sublists. 
- Listing 4.10 Quicksort with lists 

view plaincopy to clipboardprint?

1. def quickSort(list) {  
2.     if (list.size() < 2) return list  
3.     def pivot  = list[list.size().intdiv(2)]  
4.     // 1) Classify by pivot  
5.     def left   = list.findAll {item -> item <  pivot }     
6.     def middle = list.findAll {item -> item == pivot }     
7.     def right  = list.findAll {item -> item >  pivot }     
8.     return (quickSort(left) + middle + quickSort(right))     
9. }  
10. assert quickSort([])                == []  
11. assert quickSort([1])               == [1]  
12. assert quickSort([1,2])             == [1,2]  
13.   
14. assert quickSort([2,1])             == [1,2]  
15. assert quickSort([3,1,2])           == [1,2,3]  
16. assert quickSort([3,1,2,2])         == [1,2,2,3]  
17. // 2) Duck-typed items  
18. assert quickSort([1.0f,'a',10,null])== [null, 1.0f, 10, 'a']  
19. // 3) Duck-typed structure  
20. assert quickSort('Karin and Dierk') == '  DKaadeiiknnrr'.toList()  

BY THE WAY 

The sort method that comes with Groovy uses Java’s sorting implementation that beats our example in terms of worst-case performance. It guarantees a complexity of n*log(n). However, we win on a different front.

If we had to explain the Quicksort algorithm without the help of Groovy, we would sketch it in pseudocode that looks exactly like listing 4.10. In other words, the Groovy code itself is the best description of what it does! 

Supplement: 
* Groovy > Document > Collections