Почему Java Collection Framework не содержит Tree и Graph

Ответ 1

Мне интересно, почему Framework не содержит структуры как Tree и Graph, которые являются базовыми коллекциями. Оба они могут рассматриваться как подтипы Collection.

Это хороший вопрос. Я думаю, что это просто сводится к определению. Основными функциями, которые предоставляет API коллекций, являются:

• порядок итерации. Списки и отсортированные карты задали порядок итераций, большинство наборов не имеют.

• дубликаты: списки позволяют дублировать, наборы не

• index: значения списка индексируются целыми числами, значения карт индексируются другими объектами.

Это очень далеко, и я полагаю, что Джошуа Блох и др. утверждали, что более богатые богатыми коллекциями (графики и деревья, которые требуют внутренней взаимосвязи между элементами, множествами с множественностью, двунаправленными картами...) могут быть реализованы сверху этих трех основных функций и, следовательно, лучше в библиотеках.

Ответ 2

Пакет java.util содержит структуры данных для организации данных любого типа. В основном это относится к абстрактным структурам данных (например, List, Set, Map)), которые определяются с помощью их методов и поведения (например, набор не содержит элементов в два раза, список поддерживает порядок и позволяет дублировать и т.д.).

Вы, как разработчик, можете свободно выбирать, какая реализация этих структур данных лучше всего подходит для данных, с которыми вы имеете дело (HashSet против TreeSet/LinkedList против ArrayList/и т.д.). Например, для Sets and Maps вы можете выбирать между реализациями на основе хэшей и реализацией на основе дерева, что может быть или не подходит для того, что вы хотите сделать (в большинстве случаев реализация на основе хэшей будет лучшим выбором, а иногда, когда порядок важен, дерево может быть лучше подходит для ваших нужд. См. также fooobar.com/questions/16422/...).

Если вы думаете о дереве как о специальном виде Графа (который он есть), то вас интересуют конкретные свойства, которые относятся к графикам, а не к коллекциям вообще (которые, по сути, являются списками и, в свою очередь, используется для реализации таких вещей, как графики).

Как уже упоминалось в этом потоке, если вы заинтересованы в моделировании графиков, для библиотек Graph существует множество вариантов. Лично я могу рекомендовать JGraphT.

Я не знаю, почему в JDK нет библиотеки графов (и я не знаю, хорошо ли это спросить?), но я предполагаю, что Sun решила оставить это разработчикам, поскольку большинство приложений, требующих графики, также требуют очень уникальные реализации.

Ответ 3

Я подозреваю, что ответ заключается в том, что это комбинация двух вещей:

• Общий древовидный или графический интерфейс будет "плохой функцией".
• Легче и эффективнее реализовать дерево или график, используя поля для представления дочерних и (если они вам нужны) родительских указателей.

Обратите внимание, что ни у людей, ни в Aparth, ни в общих интересах Google нет общей поддержки графиков или деревьев. Однако я встретил пару общих древовидных/графических иерархий:

• Проект jsfcompounds на JavaNet имеет "com.truchsess.util" график и структуру дерева.
• Проект OpenJGraph (неактивный) на SourceForge включает библиотеки дерева и графа.

Ответ 4

Я боюсь, что ответ: слишком сложно создавать и поддерживать общую древовидную структуру и интерфейсы (см. ответ на этот пост). Большинству пользователей потребуется производительность древовидных реализаций списков и наборов, но они не будут касаться внутренних элементов, поэтому большинство из них скрыты.

Ответ 5

Существует интерфейс для деревьев - javax.swing.tree.TreeModel, который фактически работает для произвольных направленных графов (с выделенным "корнем" node). Однако он не реализует интерфейс Collection (поскольку Swing немного старше рамки коллекции, и не совсем ясно, что сборка действительно будет уместна здесь). (Одна реализация TreeModel - это DefaultTreeModel, которая использует конструкцию дерева из объектов TreeNode, которая сама по себе является интерфейсом, реализуемым пользователями.)

Другие типы деревьев задаются структурами XML-DOM. Некоторые конкретные деревья использования (или, главным образом, "узлы дерева" ) определяются java.io.File, java.awt.Component (и подклассами), API дерева компилятора (com.sun.source.tree.*), Doclet API (com.sun.javadoc.*), Reflection API (java.lang.Class), API-интерфейс языковой модели (javax.lang.**).

Если вы сравниваете эти API

Проблема в том, что для деревьев нет четкого универсального полезного интерфейса - что должно делать такое дерево? Является ли дерево просто набором других деревьев (на одном уровне ниже) или просто указателем на корень node, где каждый node сам содержит больше узлов? Или дерево является совокупностью всех узлов? Или набор всего содержимого всех узлов? У всех узлов должно быть "содержание" или только листовые узлы? Если дерево было набором некоторых элементов контента (а не самих узлов), как должен вести себя итератор? Каким будет размер дерева?

Вот предложение для дерева node (или на самом деле это может быть общий ориентированный граф node, если не для родительского указателя):

/**
 * A general interface for a tree node.
 * @param <N> the concrete node type.
 */
public interface Node<N extends Node<N>> {

   /**
    * equivalent to {@link #children children()}.{@link Collection#isEmpty isEmpty()}.
    * @returns true, if this is a leaf node, else false.
    */
   public boolean isLeaf();

   /**
    * returns a collection of all children of this node.
    * This collection can be changed, if this node is mutable.
    */
   public Collection<N> children();
   /**
    * returns the parent of this node.
    * @return null, if this is the root node, or the node does not know its parent, or has multiple parents.
    */
   public N parent();
}

/**
 * a tree node with content objects.
 * @param <N> the concrete node type
 * @param <C> the type of the content of this node.
 */
public interface ContentNode<C,N extends ContentNode<C,N>>
          extends Node<N>
{
   /**
    * returns the content of this node, if any.
    */
   public C content();
}

Будет ли этого достаточно для всех типов деревьев, например, перечисленных выше? Я так не думаю.

Ответ 6

Оригинальный ответ

Основная проблема с графами (и более конкретно деревья, как вы знаете, особый случай, когда есть только один корень, не может быть никаких циклов и все узлы связаны) заключается в том, что каждый элемент в этой предполагаемой коллекции должен быть удержанием в другой структуре: node. Трудно сделать стандартное такое лечение, поскольку для этого требуется двойной слой "контейнеров".

Если кто-нибудь когда-либо срабатывает с TreeModel для JTree, заметил бы, что почти невозможно избежать того факта, что за ним (внутри?) есть TreeNode, и вам нужно манипулировать как узлами, так и деревьями.

В любом случае, я согласен с тем, что структура была бы полезна, но очень сложно сделать ее стандартной, просто обратите внимание, что, например, ни Apache Commons Collections , ни Google Guava, два больших расширения коллекции для API, также не имеют их.

Обновление

В соответствии с обзор API:

Основной целью проекта было создание API, который был достаточно мал, как в размерах, так и, что более важно, в "концептуальном весе". это было что новые функции не кажутся чужды текущей Java программисты; он должен был увеличить нынешние заменяя их. В то же время новый API должен был быть мощным достаточно, чтобы обеспечить все преимущества, описанные выше.

Итак, в то время как графики являются правильными коллекциями, и, возможно, возможно сделать это стандартным, размер и сложность реализации будут слишком большой, чтобы соответствовать этой цели дизайна, из-за ранее объясненной потребности в двойном слое контейнеров.

Кроме того, Google Guava добавил поддержку графиков. Apache имел песочницу (незавершенная разработка) для графиков, но кажется спящей с 2011 года.