無法理解方法

Question

上的Java調用方法所以我正在閱讀Java，並且遇到了一個示例。我不知道它是如何工作的。以下您將在ConsLoRunner類中看到方法sortByTime()。我的問題是它如何能夠輸出一些東西，難道它只是一遍又一遍地重複這種方法，並且永遠不會達到insertByTime(this.first)方法？

邊注意：這個例子是馬拉松跑步者的例子，並根據他們的時間（從最快到最慢）對他們進行排序。

class Runner { 
    String name; 
    int age; 
    int bib; 
    boolean isMale; 
    int pos; 
    int time; 

    Runner(String name, int age, int bib, boolean isMale, int pos, int time) { 
     this.name = name; 
     this.age = age; 
     this.bib = bib; 
     this.isMale = isMale; 
     this.pos = pos; 
     this.time = time; 
    } 

    public boolean finishesBefore(Runner r) { 
     return this.time < r.time; 
    } 
} 

interface ILoRunner { 
    ILoRunner sortByTime(); 
    ILoRunner insertByTime(Runner r); 
} 

class MtLoRunner implements ILoRunner { 

    public ILoRunner sortByTime() { 
     return this; 
    } 

    public ILoRunner insertByTime(Runner r) { 
     return new ConsLoRunner(r, this); 
    } 

} 

class ConsLoRunner implements ILoRunner { 
    Runner first; 
    ILoRunner rest; 

    ConsLoRunner(Runner first, ILoRunner rest) { 
     this.first = first; 
     this.rest = rest; 
    } 
    /*******HOW DOES IT DO THIS?????**********/ 
    public ILoRunner sortByTime() { 
     return this.rest.sortByTime().insertByTime(this.first); 
    } 

    public ILoRunner insertByTime(Runner r) { 
     if (this.first.finishesBefore(r)) { 
      return new ConsLoRunner(this.first, this.rest.insertByTime(r)); 
     } 
     else { 
      return new ConsLoRunner(r, this); 
     } 
    } 
} 

class ExamplesRunners { 
    MtLoRunner empty = new MtLoRunner(); 
    Runner tim = new Runner ("Tim", 1, 2, true, 5, 6); 
    Runner bob = new Runner ("Bob", 5, 6, true, 9, 50); 
    Runner jim = new Runner ("Jim", 5, 6, true, 10, 40); 

    ILoRunner list1 = new ConsLoRunner(this.tim, new ConsLoRunner(this.bob, new ConsLoRunner(this.jim, this.empty))); 

    boolean testSort(Tester t) { 
     return t.checkExpect(this.list1.sortByTime(), new ConsLoRunner(this.tim, new ConsLoRunner(this.jim, new ConsLoRunner(this.bob, this.empty)))); 
    } 
} 

Answer 1

我不知道它是如何工作的。

我會盡量回答這個問題。

您正在查看List Data Structure的（非常容易混淆的）Java版本，它通常在LISP等語言中找到。

我們的例子中的「list」可以遞歸地定義。它可以是：

• 甲空列表，通過()或nil，或
• 第一元件，接着另一列表（元素的其餘部分）表示爲：(first, rest)

正如你可以看到，還有你的Java類的明確映射到這些概念：

ILoRunner -> An abstract List, the root type 
MtLoRunner -> An empty list:() or nil 
ConsLoRunner -> A non-empty list: (first, rest) 

的線索是在世紀初e名稱ConsLoRunner。在LISP中，cons是一個「構造函數」，它創建一個擁有另外兩個對象的對象。 cons通常用於創建列表。但它也可以用來創建非列表結構。對不起，我離題了。

重寫你的榜樣成一個列表表示，運動員list1名單看​​起來大致是這樣的（省略等領域爲簡單起見）：

(Tim <-- first: Tim, rest: (Bob ...) 
    (Bob <-- first: Bob, rest: (Jim()) 
     (Jim()))) <-- first: Jim, rest:() // rest of the list is empty, no more elements. 

究竟是什麼ExamplesRunners在做什麼。

現在是令人困惑的部分。該代碼正在按照結束時間排序跑步者。這個想法非常簡單，有點像這樣的列表，我們

1. 第一排序列表的其餘部分
2. 然後插入第一個元素到排序列表中的第一步

這是ConsLoRunner.sortByTime正在做什麼。但請注意，它正在返回一個新的排序列表。 所以原始列表從不改變。

插入元素x到排序列表也很簡單：

1. 比較x與列表
2. 如果x較小的第一個元素，整個列表
3. 前插入x否則，將x插入列表的其餘部分

請記住，插入是通過創建新的cons對象並使用適當的元素順序完成的。再次保留原始列表。

IMO，如果它是針對實際的列表界面編寫的，代碼會更容易閱讀，而不是與內部表示和新列表的構建混合在一起。

// The list interface 
interface List<T extends Comparable<T>> { 

    boolean isEmpty(); 

    T first(); 

    List<T> rest(); 
} 

// Instances of this class represents an empty list:() 
class Empty<T extends Comparable<T>> implements List<T> { 

    @Override 
    public boolean isEmpty() { 
     return true; 
    } 

    @Override 
    public T first() { 
     return null; 
    } 

    @Override 
    public List<T> rest() { 
     return null; 
    } 

    @Override 
    public String toString() { 
     return "()"; 
    } 
} 

// A non-empty list, composed of the first element and the rest. 
class Cons<T extends Comparable<T>> implements List<T> { 

    private final T first; 
    private final List<T> rest; 

    public Cons(T first, List<T> rest) { 
     this.first = first; 
     this.rest = rest; 
    } 

    @Override 
    public boolean isEmpty() { 
     return false; 
    } 

    @Override 
    public T first() { 
     return first; 
    } 

    @Override 
    public List<T> rest() { 
     return rest; 
    } 

    @Override 
    public String toString() { 
     return "(" + first +", " + rest + ")"; 
    } 
} 

public class Lisp { 

    // Creates and returns a sorted list from the given list 
    // The original list is never changed. 
    public static <T extends Comparable<T>> List<T> sort(List<T> list) { 
     if (list.isEmpty()) { 
      // Empty lists are already sorted. 
      return list; 
     } else { 
      // We first sort the rest of the list 
      List<T> sortedRest = sort(list.rest()); 
      // Then insert the first element into the sorted list 
      return insert(list.first(), sortedRest); 
     } 
    } 

    // Creates and returns a sorted list with x inserted into a proper position in the already sorted list 
    private static <T extends Comparable<T>> List<T> insert(T x, List<T> list) { 
     if (list.isEmpty() || x.compareTo(list.first()) < 0) { 
      return new Cons<>(x, list); 
     } else { 
      // Recursive call return a sorted list containing x 
      return new Cons<>(list.first(), 
           insert(x, list.rest())); 
     } 
    } 

    public static void main(String [] args) { 
     List<Integer> alist = new Cons<>(7, new Cons<>(1, new Cons<>(4, new Empty<>()))); 
     System.out.println("Sorted: " + sort(alist)); 
     System.out.println("Original: " + alist); 
    } 
} 

輸出

Sorted: (1, (4, (7,()))) 
Original: (7, (1, (4,()))) 

Answer 2

不會只是遞歸該方法一遍遍

不，它不使用遞歸的一切，因爲它調用的類成員rest上的方法：

返回這個。 rest .sortByTime（）。insertByTime（this.first）;