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

Question

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

Кстати, я знаю, что TreeSet реализован в Red-Black Tree.Однако TreeSet - это не дерево, а Set, поэтому в структуре нет настоящего дерева.

Answer 1

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

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

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

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

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

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

Answer 2

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

Вы, как разработчик, можете сами выбирать, какая реализация этих структур данных лучше всего подходит для того типа данных, с которым вы имеете дело ( HashSet против TreeSet / LinkedList противArrayList / и т.д. ).Например, для Наборов и Карт вы можете выбрать между реализациями на основе хеша и реализациями на основе дерева, которые могут подходить или не подходить для того, что вы хотите сделать (в большинстве случаев реализация на основе хеша будет лучшим выбором, хотя иногдакогда порядок важен, дерево может лучше подходить для ваших нужд - см. также HashSet против TreeSet (здесь, в Stackoverflow) ).

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

Обновление

Согласно обзору API :

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

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

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

Answer 5

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

Answer 6

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

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

Если сравнить эти API

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

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

/**
 * 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();
}

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