철학으로 가는 길

재귀적 DFS와 비교하였을 때 반복적 DFS의 이점은 Iterator 객체로 래핑하기가 좀 더 쉽다는 것입니다. 

 

1. 생성자는 루트 노드에 대한 참조를 인자로 받아 저장합니다.

2. iterator 메서드는 Iterator 객체를 생성하여 반환합니다. 

 

private class WikiNodeIterator implements Iterator<Node> {

   // this stack keeps track of the Nodes waiting to be visited
   Deque<Node> stack;

   /**
    * Initializes the Iterator with the root Node on the stack.
    *
    * @param node
    */
   public WikiNodeIterator(Node node) {
      stack = new ArrayDeque<Node>();
       stack.push(root);
   }

   @Override
   public boolean hasNext() {
      return !stack.isEmpty();
   }

   @Override
   public Node next() {
      // if the stack is empty, we're done
      if (stack.isEmpty()) {
         throw new NoSuchElementException();
      }

      // otherwise pop the next Node off the stack
      Node node = stack.pop();
      //System.out.println(node);

      // push the children onto the stack in reverse order
      List<Node> nodes = new ArrayList<Node>(node.childNodes());
      Collections.reverse(nodes);
      for (Node child: nodes) {
         stack.push(child);
      }
      return node;
   }

반복적 DFS와 거의 동일하지만, 메서드 세 개로 나뉩니다.

1. 생성자는 스택(ArrayDeque 클래스로 구현)을 초기화하고 그 안에 루트 노드를 push합니다.

2. isEmpty 메서드는 스택이 비었는지 확인합니다.

3. next 메서드는 스택에서 다음 Node를 pop하고 그 자식 노드들은 역순으로 push한 후 pop한 Node를 반환합니다. 누군가 빈 Iterator에서 next 메서드를 호출하면 예외를 던집니다. 

 

package com.allendowney.thinkdast;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import org.jsoup.nodes.Element;
import org.jsoup.select.Elements;

public class WikiPhilosophy {

    final static List<String> visited = new ArrayList<String>();
    final static WikiFetcher wf = new WikiFetcher();

    /**
     * Tests a conjecture about Wikipedia and Philosophy.
     *
     * https://en.wikipedia.org/wiki/Wikipedia:Getting_to_Philosophy
     *
     * 1. Clicking on the first non-parenthesized, non-italicized link
     * 2. Ignoring external links, links to the current page, or red links
     * 3. Stopping when reaching "Philosophy", a page with no links or a page
     *    that does not exist, or when a loop occurs
    *
    * @param args
    * @throws IOException
    */
   public static void main(String[] args) throws IOException {
      
      String destination = "https://en.wikipedia.org/wiki/Philosophy";
      String source = "https://en.wikipedia.org/wiki/Java_(programming_language)";
      
      testConjecture(destination, source, 10);      
   }

   /**
    * Starts from given URL and follows first link until it finds the destination or exceeds the limit.
    * 
    * @param destination
    * @param source
    * @throws IOException
    */
   public static void testConjecture(String destination, String source, int limit) throws IOException {
      String url = source;
      for (int i=0; i<limit; i++) {
         if (visited.contains(url)) {
            System.err.println("We're in a loop, exiting.");
            return;
         } else {
            visited.add(url);
         }
         Element elt = getFirstValidLink(url);
         if (elt == null) {
            System.err.println("Got to a page with no valid links.");
            return;
         }
         
         System.out.println("**" + elt.text() + "**");
         url = elt.attr("abs:href");
         
         if (url.equals(destination)) {
            System.out.println("Eureka!");
            break;
         }
      }
   }

   /**
    * Loads and parses a URL, then extracts the first link.
    * 
    * @param url
    * @return the Element of the first link, or null.
    * @throws IOException
    */
   public static Element getFirstValidLink(String url) throws IOException {
      print("Fetching %s...", url);
      Elements paragraphs = wf.fetchWikipedia(url);
      WikiParser wp = new WikiParser(paragraphs);
      Element elt = wp.findFirstLink();
      return elt;
   }

   /**
    * Formats and print the arguments.
    * 
    * @param msg
    * @param args
    */
   private static void print(String msg, Object... args) {
      System.out.println(String.format(msg, args));
   }
}