Transcript A Recursive List Paradigm

A Recursive List Paradigm
Jack Beidler
Yaodong Bi
Bob McCloskey
Computing Sciences
University of Scranton
Scranton, PA 18510
A Recursive List Paradigm
•
•
•
•
•
List Paradigms
A Recursive List Paradigm
Examples
Unfocused vs. focused paradigms
From the recursive paradigm to a positional
paradigm
List Paradigms
• Lists and the Java API
– Interface List and its implementations
• 25 methods
• Swiss Army Knif Approach (multiple paradigms)
• Focused Paradigms - a few well chosen
coordinated methods
–
–
–
–
Array Analogy Paradigm
Positional Paradigm (One-way)
Positional Paradigm (Two-way)
Recursive Paradigm
A Recursive List Paradigm
• McCarthy’s LISP
http://www-formal.stanford.edu/jmc/history/lisp/lisp.html
– No compromise recursive paradigm
– A list:
• isEmpty
• or (head, tail)
– head is an object
– tail is a (possibly empty) sublist
– A Java Implementation
• 3 constructors
• 6 methods
• 2 utility methods
A Recursive List Paradigm
• Constructors
RecursiveList ()
empty list
RecursiveList (Object Head)
non-empty list w empty tail
RecursiveList
(Object Head, RecursiveList Tail)
list with tail
A Recursive List Paradigm
• Methods
boolean
isEmpty()
RecursiveList
tailOf()
Object
getHead()
void
setHead(Object NewHead)
void
insert(RecursiveList List)
RecursiveList
remove()
A Recursive List Paradigm
• Utility Methods
void
String
swap(RecursiveList List)
toString()
A Recursive List Paradigm
• What about iterator support
– Recursion is the traversal method
Examples
• OrderedList Class (composed with RecursiveList)
import java.util.*;
class OrderedList {
private Comparator c;
protected RecursiveList L;
OrderedList (Comparator c){
this.c=c;
L = new RecursiveList();
}
Examples
• OrderedList Class (composed with RecursiveList)
…
private void RecInsert
(Object Obj,
RecursiveList List){
if(List.isEmpty()
|| (c.compare(Obj, List.getHead())<0))
List.insert(new RecursiveList(Obj));
else RecInsert(Obj, List.tailOf());
}
public void insert(Object Obj){
RecInsert(Obj, L);
}
Examples
• OrderedList Class (composed with RecursiveList)
…
private void Recmerge (RecursiveList Source1,
RecursiveList Source2, RecursiveList Merged){
if (Source1.isEmpty()) Merged.swap(Source2);
else if (Source2.isEmpty()) Merged.swap(Source1);
else {
if (c.compare(Source1.getHead()
, Source2.getHead())<0)
Merged.insert(Source1.remove());
else Merged.insert(Source2.remove());
Recmerge(Source1, Source2, Merged.tailOf());
}
}
Examples
• OrderedList Class (composed with RecursiveList)
…
public void merge(OrderedList Source1,
OrderedList Source2){
Recmerge(Source1.L, Source2.L, this.L);
}
public String toString(){
return L.toString();
}
}
Examples
• OrderedList Class (composed with RecursiveList)
– Simplicity of insert
– Simplicity of merge
– But what about iteration?? (be patient)
Examples
• What about iterator support
Unfocused vs. focused paradigms
• G&T
– 1 Constructors
– 13 Methods
– 0 Utility Methods
• RecursiveList
– 3 Constructors
– 6 Methods
– 2 Utility methods
Unfocused vs. focused paradigms
• S
– 2 Constructors
– 14 Methods
– 0 Utility Methods
• RecursiveList
– 3 Constructors
– 6 Methods
– 2 Utility methods
Unfocused vs. focused paradigms
• C&P
– 1 Constructors
– 7 Methods
– 0 Utility Methods
• RecursiveList
– 3 Constructors
– 6 Methods
– 2 Utility methods
From the recursive paradigm to a
positional paradigm
• What about iteration?
• What about the positional paradigm?
• Constructed on top of the recursive
paradigm.
From the recursive paradigm to a
positional paradigm
void front()
boolean offRear()
void rear()
boolean backingUp()
void next()
void prev()
void append(Object O)
void setObject(Object O)
Object getObject()
From the recursive paradigm to a
positional paradigm
RecursiveList Order = new RecursiveList();
…
RecursiveListIterator It = new
RecursiveListIterator(Order);
for (It.front(); !It.offRear(); It.next())
System.out.print(((Integer)It.getObject())+"\t");
System.out.println();
for (It.rear(); It.backingUp(); It.prev())
System.out.print(((Integer)It.getObject())+"\t");
System.out.println();
Conclusions
• Lean, mean, well focused is usually better that the
Swiss Army Knife approach
http://www.cs.scranton.edu/~beidler/java/OneWay/
• It is even nicer with trees
– RecBinTree Class
http://www.cs.scranton.edu/~beidler/java/RecBinTree/