无法理解方法

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）;