6.3 Использование jsoup

jsoup легко скачать и разобрать веб-страницу и получить доступ к дереву DOM. Вот пример:

String url = "http://en.wikipedia.org/wiki/Java_(programming_language)";

// download and parse the document
Connection conn = Jsoup.connect(url);
Document doc = conn.get();

// select the content text and pull out the paragraphs.
Element content = doc.getElementById("mw-content-text");
Elements paragraphs = content.select("p");

Jsoup.connect принимает строку URL и подключается к веб-серверу. Метод get загружает HTML, анализирует его и возвращает объект Document, представляющий дерево DOM.

Документ предоставляет методы для навигации по дереву и выбора узлов. На самом деле он предоставляет множество методов, которые могут сбить вас с толку. Этот пример демонстрирует два способа выбора узла:

• getElementById принимает строку и ищет в дереве элемент, соответствующий полю id. Здесь он выбирает узел
  , который появляется на каждой странице Википедии для определения элемента

  , содержащего текст статьи, а не навигационную панель и другие элементы. Возвращаемое значение getElementById — это объект Element, представляющий этот

  и содержащий элементы внутри

  в качестве последующих узлов.
• select принимает строку и проходит по дереву, возвращая все элементы, соответствующие тегу элемента. В этом примере он возвращает все абзацы в содержимом. Возвращаемым значением является объект Elements.

Прежде чем продолжить, вы должны внимательно прочитать документацию по этим классам, чтобы понять, что они могут делать. Наиболее важными классами являются Element, Elements и Node, которые вы можете прочитать на http://thinkdast.com/jsoupelt, http://thinkdast.com/jsoupelts и http://thinkdast.com/jsoupnode.

Node представляет узел в дереве DOM; существует несколько расширенных классов Node, включая Element, TextNode, DataNode и Comment. Элементы — это коллекция объектов Element.

Рисунок 6.3 представляет собой диаграмму UML, показывающую отношения между этими классами. В диаграмме классов UML линия с пустым стрелкой указывает, что класс наследуется от другого класса. Например, эта диаграмма показывает, что Elements наследует ArrayList. Мы вернёмся к диаграммам UML в разделе 11.6.

6.4 Обход DOM

Чтобы облегчить вам задачу, я предоставил класс WikiNodeIterable, который позволяет вам проходить по дереву DOM. Ниже приведён пример того, как его использовать:

Elements paragraphs = content.select("p");
Element firstPara = paragraphs.get(0);

Iterable<Node> iter = new WikiNodeIterable(firstPara);
for (Node node: iter) {
    if (node instanceof TextNode) {
        System.out.print(node);
    }
}
``` Этот пример следует сразу за предыдущим. Он выбирает `paragraphs`, содержащий первый абзац, а затем создаёт `WikiNodeIterable`, который реализует `Iterable<Node>`. `WikiNodeIterable` выполняет «глубинный поиск в ширину», он генерирует узлы в том порядке, в котором они будут появляться на странице.

В этом примере мы печатаем только `TextNode`, игнорируя другие типы `Node`, особенно представляющие теги `Element` объекты. Результатом является текст абзаца без каких-либо отметок HTML. Вывод:

Java — это универсальный язык программирования для компьютеров, который является параллельным, основанным на классах, объектно-ориентированным и специально разработанным...

> Java — это универсальный компьютерный язык программирования, который является параллельным, основан на классах, ориентирован на объекты и специально разработан...

## 6.5 Глубинный поиск

Существует несколько способов разумно пройти по дереву, каждый из которых имеет своё применение. Мы начинаем с «глубинного поиска в ширину» (DFS). DFS начинается с корневого узла дерева и выбирает первый дочерний узел. Если у дочернего узла есть дочерние узлы, то выбирается первый из них. Когда он достигает узла без дочерних узлов, он возвращается назад, перемещается вверх по дереву к родительскому узлу, где он выбирает следующий дочерний узел, если таковой имеется; в противном случае он снова возвращается назад. Когда он исследует последний дочерний узел корневого узла, процесс завершается.

Есть два распространённых способа реализации DFS: рекурсивный и итеративный. Рекурсивная реализация проста и элегантна:

```java
private static void recursiveDFS(Node node) {
    if (node instanceof TextNode) {
        System.out.print(node);
    }
    for (Node child: node.childNodes()) {
        recursiveDFS(child);
    }
}

Этот метод вызывает себя для каждого Node в дереве, начиная с корневого. Если Node является TextNode, он печатает его содержимое. Если у Node есть какие-либо дочерние узлы, он вызывает recursiveDFS для каждого из них по очереди.

В данном примере мы печатаем содержимое каждого TextNode перед обходом дочерних узлов, поэтому это пример «обхода в прямом порядке». Вы можете узнать о «прямом», «обратном» и «симметричном» обходе на сайте http://thinkdast.com/treetrav. Для этого приложения порядок обхода не имеет значения.

Используя рекурсивные вызовы, recursiveDFS использует стек вызовов (<http://thinkdast.com/callstack>) для отслеживания дочерних узлов и обработки их в правильном порядке. В качестве альтернативы мы можем использовать структуру данных стека для самостоятельного отслеживания узлов; если мы сделаем это, мы сможем избежать рекурсии и выполнить итерационный обход дерева.

6.6 Стек в Java

Прежде чем объяснить итерационную версию DFS, я объясню структуру данных стека. Мы начнём со стека в общем смысле, и я буду использовать строчную букву s для обозначения «стека». Затем мы обсудим два интерфейса Java, которые определяют методы стека: Stack и Deque.

Стек похож на список: это упорядоченная коллекция элементов. Основное различие между стеком и списком заключается в том, что стек предоставляет меньше методов. Обычно он предоставляет:

• push: добавляет элемент в верхнюю часть стека.
• pop: удаляет и возвращает верхний элемент стека.
• peek: возвращает верхний элемент без изменения стека.
• isEmpty: указывает, пуст ли стек. Поскольку pop всегда возвращает верхний элемент, стек также называется LIFO (последним пришёл — первым ушёл). Альтернативой стеку является «очередь», которая возвращает элементы в порядке добавления («первым пришёл — первым ушёл»).

Может быть не совсем понятно, почему стек и очередь полезны. Они не предоставляют никаких функций, которых нет в списке; фактически, они предоставляют меньше функций. Зачем использовать что-то меньшее? Есть две причины:

1. Если вы ограничиваете себя небольшим набором методов — то есть небольшим API — ваш код будет легче читать и с меньшей вероятностью приведёт к ошибкам. Например, использование списка для представления стека может привести к удалению элементов в неправильном порядке. Используя API стека, такая ошибка невозможна буквально. Лучший способ избежать ошибок — сделать их невозможными.
2. Структуру данных, предоставляющую небольшой API, легче реализовать. Например, простой способ реализовать стек — использовать односвязный список. При добавлении элемента мы добавляем его в начало списка; при удалении элемента мы удаляем его из начала. Для связанного списка добавление и удаление в начале — это операции с постоянным временем, поэтому эта реализация эффективна. Напротив, большой API сложнее реализовать эффективно.

Чтобы реализовать стек в Java, у вас есть три варианта:

• Продолжайте использовать ArrayList или LinkedList. Если вы используете ArrayList, обязательно добавляйте и удаляйте элементы с конца, что является операцией с постоянным временем. И будьте осторожны, чтобы не добавлять элементы в неправильные места или удалять их в неправильном порядке.
• Java предоставляет класс Stack, который предоставляет набор стандартных методов стека. Однако этот класс является частью старой части Java: он несовместим с более поздним Java Collection Framework.
• Возможно, лучшим выбором будет использование реализации интерфейса Deque, такого как ArrayDeque.

Deque означает «двусторонняя очередь»; его следует произносить как «дек», но некоторые люди называют его «дик». В Java интерфейс Deque предоставляет методы push, pop, peek и isEmpty, поэтому вы можете использовать Deque в качестве стека. Он предоставляет другие методы, о которых вы можете прочитать на http://thinkdast.com/deque, но сейчас мы их не используем.

6.7 Итерационная версия DFS

Вот итерационная версия DFS, использующая ArrayDeque для представления стека объектов Node.

private static void iterativeDFS(Node root) {
    Deque<Node> stack = new ArrayDeque<Node>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        if (node instanceof TextNode) {
            System.out.print(node);
        }

        List<Node> nodes = new ArrayList<Node>(node.childNodes());
        Collections.reverse(nodes);

        for (Node child : nodes) {
            stack.push(child);
        }
    }
}

Параметр root — это корневой узел дерева, которое мы хотим пройти, поэтому мы сначала создаём стек и помещаем в него корневой узел.

Цикл продолжается до тех пор, пока стек не станет пустым. На каждой итерации мы извлекаем Node из стека. Если мы получаем TextNode, мы печатаем его содержимое. Затем мы помещаем дочерние узлы обратно в стек. Чтобы обработать дочерние узлы в правильном порядке, нам нужно поместить их обратно в обратном порядке; мы делаем это, копируя дочерние узлы в ArrayList, меняя их порядок на месте, а затем перебирая изменённый ArrayList.

Преимущество итерационной версии DFS заключается в том, что её легче реализовать как Java Iterator; вы увидите, как это сделать, в следующей главе.

Но сначала есть ещё одно замечание о Deque интерфейсе: помимо ArrayDeque, Java предоставляет другую реализацию Deque, нашего старого друга LinkedList. LinkedList реализует два интерфейса: List и Deque (а также Queue). Вы получаете тот интерфейс, который используете. Например, если вы присвоите объект LinkedList переменной Deque:

Deqeue<Node> deque = new LinkedList<Node>();

Вы можете использовать методы интерфейса Deque, но не все методы List. Если вы назначите его переменной List:

List<Node> deque = new LinkedList<Node>();

Вы можете использовать методы List, но не методы Deque. И если вы сделаете такое назначение:

LinkedList<Node> deque = new LinkedList<Node>();

Вы можете использовать все методы, но смешиваете методы из разных интерфейсов. Ваш код будет менее читаемым и более подверженным ошибкам.