Difference between revisions of "Iterable Immutable List Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(34 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Code To Investigate=
+
=Exercise To Revisit=
==Iterable==
+
In this studio we will complete the <code>EmptyImmutableList</code> and <code>NonEmptyImmutableList</code> implementations from the [[ImmutableList_Assignment|ImmutableList exercise]].
:[https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html interface java.lang.Iterable<T>]
 
::[https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html#iterator-- Iterator<T> iterator()]
 
  
==Iterator==
+
==ImmutableList==
:[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html interface java.util.Iterator<T>]
+
The [https://www.cse.wustl.edu/~cosgroved/courses/cse425s/spring20/apidocs/immutable/list/core/ImmutableList.html ImmutableList] interface extends [https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html Iterable] which has one method: [https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html#iterator-- iterator()].
::[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html#hasNext-- boolean hasNext()]
 
::[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html#next-- T next()]
 
  
==ImmutableList==
 
 
  <nowiki>public interface ImmutableList<E> extends Iterable<E> {
 
  <nowiki>public interface ImmutableList<E> extends Iterable<E> {
 
E head();
 
E head();
Line 16: Line 11:
 
}</nowiki>
 
}</nowiki>
  
=Code To Implement=
+
==Iterable==
==DefaultImmutableList==
+
[https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html interface java.lang.Iterable<T>]
{{JavaToImplement|DefaultImmutableList|head<br>tail<br>isEmpty<br>iterator|immutable.list.assignment}}
+
#[https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html#iterator-- Iterator<T> iterator()]
===default constructor===
 
constructs a new empty immutable list
 
  
<nowiki>DefaultImmutableList()</nowiki>
+
==Iterator==
 +
[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html interface java.util.Iterator<T>]
 +
#[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html#hasNext-- boolean hasNext()]
 +
#[https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html#next-- T next()]
  
===cons constructor===
+
=Examples=
construct a new immutable list with head and tail
+
==Using Iterable==
 +
<youtube>A-rTJTHq5B4</youtube>
 +
==Implementing Iterable: DOM NodeList==
 +
<youtube>4ycpqdJ4yb4</youtube>
  
<nowiki>DefaultImmutableList(E head, ImmutableList<E> tail)</nowiki>
+
=Example=
 +
{{Example|IterableImmutableListExample|immutable.list.example}}
  
===head===
+
The code:
  <nowiki>public E head()</nowiki>
+
  <nowiki>ImmutableList<Integer> numbers = Lists.brackets(4, 66, 99);
 +
for (Integer i : numbers) {
 +
System.out.println(i);
 +
}</nowiki>
  
Analogous to the [http://sml-family.org/Basis/list.html SML List] [http://sml-family.org/Basis/list.html#SIG:LIST.hd:VAL hd method].
+
produces:
===tail===
+
<nowiki>4
  <nowiki>public ImmutableList<E> tail()</nowiki>
+
66
 +
99</nowiki>
 +
 
 +
=Diagrams=
 +
==ImmutableList==
 +
  <nowiki>ImList<Char> letters = Lists.brackets('A', 'B', 'C'); </nowiki>
  
Analogous to the [http://sml-family.org/Basis/list.html SML List] [http://sml-family.org/Basis/list.html#SIG:LIST.tl:VAL tl method].
+
[[File:ImmutableList_letters.svg|600px]]
===isEmpty===
 
<nowiki>public boolean isEmpty()</nowiki>
 
  
Analogous to the [http://sml-family.org/Basis/list.html SML List] [http://sml-family.org/Basis/list.html#SIG:LIST.null:VAL null method].
+
==Initial Iterator State==
===iterator===
 
<nowiki>public Iterator<E> iterator()</nowiki>
 
  
==Lists==
+
<nowiki>ImList<Char> letters = Lists.brackets('A', 'B', 'C');
<code>Lists</code> is a class which holds a number of static methods.  As we know, in [https://steve-yegge.blogspot.com/2006/03/execution-in-kingdom-of-nouns.html the Kingdom of Nouns], Verbs must always have an escort.
+
Iterator<Char> iter = letters.iterator(); </nowiki>
  
The first two static methods <code>nil</code> and <code>cons</code> will each call a constructor of the <code>DefaultImmutableList</code> class.  The third method <code>brackets</code> will use <code>nil</code> and <code>cons</code> to build up the desired ImmutableList.  
+
[[File:ImmutableList_iterator.svg|600px]]
  
{{JavaToImplement|Lists|nil<br>cons<br>brackets|immutable.list.assignment}}
+
==Iterator State after next()==
===nil===
 
<nowiki>public static <E> ImmutableList<E> nil()</nowiki>
 
  
Analogous to the [http://sml-family.org/Basis/list.html SML List] [http://sml-family.org/Basis/list.html#SIG:LIST.nil:TY nil constructor].
+
<nowiki>ImList<Char> letters = Lists.brackets('A', 'B', 'C');
 +
Iterator<Char> iter = letters.iterator();
 +
if(iter.hasNext()) {
 +
    char a = iter.next();
 +
} </nowiki>
  
Note: often SML programs use empty brackets <code>[]</code> instead of <code>nil</code>.
+
[[File:ImmutableList_iterator_next.svg|600px]]
  
===cons===
+
==Iterator State after next() next()==
  <nowiki>public static <E> ImmutableList<E> cons(E head, ImmutableList<E> tail)</nowiki>
+
  <nowiki>ImList<Char> letters = Lists.brackets('A', 'B', 'C');
 +
Iterator<Char> iter = letters.iterator();
 +
if(iter.hasNext()) {
 +
    char a = iter.next();
 +
    if(iter.hasNext()) {
 +
        char b = iter.next();
 +
    }
 +
} </nowiki>
  
Analogous to the [http://sml-family.org/Basis/list.html SML List] [http://sml-family.org/Basis/list.html#SIG:LIST.:::TY :: constructor].
+
[[File:ImmutableList_iterator_next_next.svg|600px]]
 +
==Iterator State after next() next() next()==
 +
<nowiki>ImList<Char> letters = Lists.brackets('A', 'B', 'C');
 +
Iterator<Char> iter = letters.iterator();
 +
if(iter.hasNext()) {
 +
    char a = iter.next();
 +
    if(iter.hasNext()) {
 +
        char b = iter.next();
 +
        if(iter.hasNext()) {
 +
            char c = iter.next();
 +
        }
 +
    }
 +
} </nowiki>
  
===brackets===
+
[[File:ImmutableList_iterator_next_next_next.svg|600px]]
<nowiki>@SafeVarargs
 
public static <E> ImmutableList<E> brackets(E... elements)</nowiki>
 
  
<code>brackets</code> accepts [https://docs.oracle.com/javase/8/docs/technotes/guides/language/varargs.html variable length arguments] as specified by the <code>...</code> syntax.  When implementing the <code>brackets</code> method you can treat <code>elements</code> as an array.  Combining generics and varargs https://stackoverflow.com/questions/14231037/java-safevarargs-annotation-does-a-standard-or-best-practice-exist can be problematic] if the implementation lets the E[] escape since it will actually be an Object[].  The [https://docs.oracle.com/javase/7/docs/api/java/lang/SafeVarargs.html @SafeVarargs] annotation indicates a promise that you will rely only on the elements of the array being of type E and not the array being of type E[].  This should not be a problem since you should not require any unsafe use of varargs.
+
=Code To Implement=
 +
==enum EmptyImmutableList==
 +
{{JavaToImplement|EmptyImmutableList|iterator|immutable.list.assignment}}
 +
===iterator()===
 +
return an [https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html Iterator] for the EmptyImmutableList.
  
Note: be sure to <code>cons</code> the elements on from the back of the <code>elements</code> array to the front.
+
Question to ask yourself: Does an iterator for an EmptyImmutableList ever have a next?
  
=Example=
+
==class NonEmptyImmutableList==
{{Example|ListsExample|immutable.list.example}}
+
{{JavaToImplement|NonEmptyImmutableList|iterator|immutable.list.assignment}}
 +
===iterator()===
 +
return an [https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html Iterator] for this instance of NonEmptyImmutableList.
  
The code:
+
Note: If you are within an anonymous inner class, the way to get the outer class's this instance is to qualify it with the out class identifier. For example:
<nowiki>ImmutableList<Integer> numbers = Lists.brackets(4, 66, 99);
 
for (int i : numbers) {
 
System.out.println(i);
 
}</nowiki>
 
  
produces:
+
  <nowiki>NonEmptyImmutableList.this</nowiki>
  <nowiki>4
 
66
 
99</nowiki>
 
  
 
=Test=
 
=Test=
{{TestSuite|ListsTestSuite|immutable.list.assignment}}
+
{{TestSuite|IterableAssignmentTestSuite|immutable.list.util.exercise}}
 +
 
 +
:{{TestSuite|ImmutableListIteratorMethodTestSuite|immutable.list.util.exercise}}

Latest revision as of 19:05, 24 April 2022

Exercise To Revisit

In this studio we will complete the EmptyImmutableList and NonEmptyImmutableList implementations from the ImmutableList exercise.

ImmutableList

The ImmutableList interface extends Iterable which has one method: iterator().

public interface ImmutableList<E> extends Iterable<E> {
	E head();
	ImmutableList<E> tail();
	boolean isEmpty();
}

Iterable

interface java.lang.Iterable<T>

  1. Iterator<T> iterator()

Iterator

interface java.util.Iterator<T>

  1. boolean hasNext()
  2. T next()

Examples

Using Iterable

Implementing Iterable: DOM NodeList

Example

class: IterableImmutableListExample.java Presentation icon-72a7cf.svg
package: immutable.list.example
source folder: src/main/java

The code:

ImmutableList<Integer> numbers = Lists.brackets(4, 66, 99);
for (Integer i : numbers) {
	System.out.println(i);
}

produces:

4
66
99

Diagrams

ImmutableList

ImList<Char> letters = Lists.brackets('A', 'B', 'C'); 

ImmutableList letters.svg

Initial Iterator State

ImList<Char> letters = Lists.brackets('A', 'B', 'C');
Iterator<Char> iter = letters.iterator(); 

ImmutableList iterator.svg

Iterator State after next()

ImList<Char> letters = Lists.brackets('A', 'B', 'C');
Iterator<Char> iter = letters.iterator();
if(iter.hasNext()) {
    char a = iter.next();
} 

ImmutableList iterator next.svg

Iterator State after next() next()

ImList<Char> letters = Lists.brackets('A', 'B', 'C');
Iterator<Char> iter = letters.iterator();
if(iter.hasNext()) {
    char a = iter.next();
    if(iter.hasNext()) {
        char b = iter.next();
    }
} 

ImmutableList iterator next next.svg

Iterator State after next() next() next()

ImList<Char> letters = Lists.brackets('A', 'B', 'C');
Iterator<Char> iter = letters.iterator();
if(iter.hasNext()) {
    char a = iter.next();
    if(iter.hasNext()) {
        char b = iter.next();
        if(iter.hasNext()) {
            char c = iter.next();
        }
    }
} 

ImmutableList iterator next next next.svg

Code To Implement

enum EmptyImmutableList

class: EmptyImmutableList.java Java.png
methods: iterator
package: immutable.list.assignment
source folder: src/main/java

iterator()

return an Iterator for the EmptyImmutableList.

Question to ask yourself: Does an iterator for an EmptyImmutableList ever have a next?

class NonEmptyImmutableList

class: NonEmptyImmutableList.java Java.png
methods: iterator
package: immutable.list.assignment
source folder: src/main/java

iterator()

return an Iterator for this instance of NonEmptyImmutableList.

Note: If you are within an anonymous inner class, the way to get the outer class's this instance is to qualify it with the out class identifier. For example:

NonEmptyImmutableList.this

Test

class: IterableAssignmentTestSuite.java Junit.png
package: immutable.list.util.exercise
source folder: src/test/java
class: ImmutableListIteratorMethodTestSuite.java Junit.png
package: immutable.list.util.exercise
source folder: src/test/java