Iterator'COMP'401,'Spring'2013'Lecture'07'1/31/2013'Design'Situa>on'• Suppose'we'have'an'object'that'encapsulates'some'sort'of'collec>on.'– SongLibrary'• A'collec>on'of'songs'in'an'iTunesKlike'system'– PolygonModel'• A'collec>on'of'polygons'in'a'3D'modeling'system'– Polygon'• A'collec>on'of'points'in'our'Assignment'2'Design'Situa>on'• Now'suppose'we'have'code'outside'of'this'collec>on'object'that'needs'to'examine'each'element'of'the'underlying'collec>on'in'turn.'– SongFilter'• A'object'that'represents'a'set'of'search'criteria'that'is'to'be'applied'to'a'collec>on'of'songs'– An'intersec>on'test'in'which'each'polygon'of'a'PolygonModel'needs'to'be'evaluated'Strategy'1:'Provide'access'to'underlying'collec>on'as'an'array.'• SongLibrary'– public'Song[]'getSongs()'• PolygonModel'– public'Polygon[]'getPolygons()'• Drawbacks?'– May'have'to'do'a'lot'of'work'to'create'the'array'– Collec>on'may'be'result'of'genera>ve'process'Strategy'2:'Provide'index'access'to'each'underlying'item'in'collec>on'• SongLibrary'– public'int'getNumSongs();'– public'Song'getSong(int'song_idx);'• PolygonModel'– public'int'getNumPolygons();'– public'Polygon'getPolygon(int'polygon_idx);'• Drawbacks?'– Doesn’t'help'with'genera>ve'collec>ons'– Imposes'restric>ons'on'how'collec>on'is'represented'and'linearized'– Deteriorates'encapsula>on'Strategy'3:'Internalize'a'“cursor”'• SongLibrary'– public'void'resetSongCursor();'– public'Song'getNextSong();'– public'boolean'isCursorAtEnd();'• Drawbacks?'– Can’t'have'two'traversals'going'at'the'same'>me.'– But,'this'does'come'close.'Iterator'Design'Pa_ern'• “Provide'a'way'to'access'the'elements'of'an'aggregate'object'sequen>ally'without'exposing'its'underlying'representa>on”'– Gang'of'Four,'Design+Pa.erns'• Consider:'for(int i=0; i<slist.size(); i++) {!Song next_song = slist.get(i);!// Do something with next_song.!}!Iterator'Design'Pa_ern'• Iterator'object'encapsulates'details'of'item'traversal.'– Understands'details'of'the'underlying'collec>on.'– Manages'order'of'items'• May'want'a'traversal'that'is'not'just'first'to'last.'• Underlying'collec>on'may'not'be'linear.'– Manages'state'of'traversal'• Allows'traversal'to'be'picked'up'again'later.'• Assump>on:'underlying'collec>on'is'not'changed'or'modified'while'the'traversal'is'occurring.'– Interator'should'be'able'to'detect'this'and'signal'an'error'– Variant'of'pa_ern'will'have'iterator'provide'methods'that'modify'underlying'collec>on'safely'Elements'of'Iterator'Pa_ern'• Collec>on'object'is'“iterable”'– Provides'a'method'that'returns'an'object'that'acts'as'an'iterator.'• Iterator'object'provides'access'to'the'elements'in'turn.'– A'method'to'test'whether'more'items'exist.'– A'method'to'retrieve'the'next'item.'Java'Iterator'Pa_ern'Interfaces'• The'Java'Collec>ons'Framework'defines'two'generic'interfaces'for'suppor>ng'the'interable'design'pa_ern'– Implemented'by'the'various'collec>on'types'such'as'List<E>,'Map<E>,'Set<E>,'etc.'• Iterable<E>'– Interator<E>'iterator()'• Iterator<E>'Iterator<E>'• boolean'hasNext()'– Are'we'at'the'end'of'the'traversal?'• E'next()'– Get'the'next'item'of'the'traversal.'– Throws'a'run>me'excep>on'if'no'next'item.'• void'remove()'– Not'supported'by'all'implementa>ons.'– Safely'removes'last'item'retrieved'by'next()'from'the'underlying'collec>on.'Iterable'examples'• lec7.v1'– Main1'• Simple'use'– Main2'• Parallel'iterators'– Main3'• Simultaneous'iterators'– Main4'• for'–'each'syntac>c'sugar'Main1'Visualized'(1)'ArrayList<Song>'slist'0'Words'and'Guitar'Dig'Me'Out'Jenny'Li_le'Babies'Buy'Her'Candy'1'2'3'4'Main1'Visualized'(2)'ArrayList<Song>'slist'0'Words'and'Guitar'Dig'Me'Out'Jenny'Li_le'Babies'Buy'Her'Candy'1'2'3'4'Iterator<Song>'iter'0'next_idx'list'Main1'Visualized'(3)'ArrayList<Song>'slist'0'Words'and'Guitar'Dig'Me'Out'Jenny'Li_le'Babies'Buy'Her'Candy'1'2'3'4'Iterator<Song>'iter'0'next_idx'list'public'boolean'hasNext()'{''if'(next_idx'<'list.size())'{'''return'true;''}''return'false;'}'NOTE:'This'may'or'may'not'be'how'it'is'actually'implemented,'but'it'is'effec2vely+what'is'going'on.'Main1'Visualized'(4)'ArrayList<Song>'slist'0'Words'and'Guitar'Dig'Me'Out'Jenny'Li_le'Babies'Buy'Her'Candy'1'2'3'4'Iterator<Song>'iter'1'next_idx'list'public'Song'next()'{''Song's'='list.get(next_idx);''next_idx++;''return's;'}'NOTE:'Real'implementa>on'would'first'check'to'see'if'hasNext()'is's>ll'true'and'throw'an'excep>on'otherwise.'lec7.v1.Main2'• Parallel'itera>on'– Processes'two'different'lists'• Iterator'associated'with'each.'• Iterators'advance'unevenly'lec7.v1.Main3'• Simultaneous'itera>on'– 2'Iterators,'1'List'• Insert'your'own'joke'here.'lec7.v1.Main4'• Java'provides'“syntac>c'sugar”'for'common'use'of'iterators.'– Supposing'e_coll'is'Iterable<E>,'then'these'are'equivalent:'Iterator<E> iter = e_coll.iterator();!while (iter.hasNext()) {!!E elem = iter.next();!!// Do something with element!}!!for (E elem : e_coll) {!!// Do something with elem!}!lec7.v2'• A'more'complicated'iterator'– Can'build'iterators'that'do'things'other'than'just'go'through'every'item.'•
View Full Document