Konstrukcja drzewa na podstawie listy scieżek

To zasadniczo proste zadanie. Mają listę ścieżek, np. w postaci nazw węzłów oddzielonych separatorem (A;B;C, A;X) należy skonstruować drzewo. Widziałem jednak to proste zadanie realizowane na tak wiele zakręconych, brzydkich, niewydajnych sposobów, że postanowiłem coś z tym zrobić.

Algorytm

Jest bardzo prosty i składa się z dwóch etapów. Pierwszych jest krokiem jest przetworzenie ścieżek na sekwencję węzłów na podstawie których tworzymy drzewo przeglądają każdą ścieżkę od korzenia dodając brakujące w grafie węzły i krawędzie. Jedynym wyzwaniem jest zapewnienie separacji poszczególnych części zadania tak by można było wielokrotnie wykorzystać kod, co udało mi się całkiem nieźle wykorzystując typy uogólnione

Kod

Najważniejsze interfejsy wyglądają następująco

/**
 * Enkapsuluje operacje na węzłach drzewa które budujemy
 */
public interface TreeNodeAccessor<NodeType, NameType> {
	NodeType getOrCreate(NodeType parentNode, NameType childNodeName);
}

/**
 * Zbiór ścieżek na podstawie którego zbudowane zostanie drzewo
 */

public interface PathSet<NameType> extends Iterable<PathIterable<NameType>> {

}

/**
 * Itarator po kolejnych węzłach ścieżki
 */
public interface PathIterable<NameType> extends Iterable<NameType> {

}

Implementacja algorytmu budowy drzewa jest już bardzo prosta

public class TreeBuilder<NodeType, NameType> {
	public <NodeAccessor extends TreeNodeAccessor<NodeType, ? super NameType>> NodeType 
		buildTree(
				PathSet<NameType> paths,
				NodeType root, 
				NodeAccessor nodeAccessor) {
		for (PathIterable<NameType> path : paths) {
			NodeType current = root;
			for (NameType nodeName : path) {
				current = nodeAccessor.getOrCreate(current, nodeName);
			}
		}
		return root;
	}

	public static <NodeType, NameType> TreeBuilder<NodeType, NameType> getNew() {
		return new TreeBuilder<NodeType, NameType>();
	}
}

Przykład

Dla przykładu zbudujmy drzewo swingowe na podstawie ścieżek dostarczonych jako lista ciągów znaków oddzielonych separatorem. W tym celu potrzebny jest akcesor do węzłów drzewa

package utils.impl;

import javax.swing.tree.DefaultMutableTreeNode;

import utils.TreeNodeAccessor;

public class DefaultMutableTreeNodeAccessor implements
		TreeNodeAccessor<DefaultMutableTreeNode, Object> {

	@Override
	public DefaultMutableTreeNode getOrCreate(
			DefaultMutableTreeNode parentNode, Object childNodeName) {
		int childCount = parentNode.getChildCount();
		for (int childIndex = 0; childIndex < childCount; ++childIndex) {
			DefaultMutableTreeNode childNode =
				(DefaultMutableTreeNode) parentNode.getChildAt(childIndex);
			Object userObject = childNode.getUserObject();
			if (eq(userObject, childNodeName)) {
				return childNode;
			}

		}
		DefaultMutableTreeNode childNode = new DefaultMutableTreeNode(childNodeName);
		parentNode.add(childNode);
		return childNode;
	}

	private static boolean eq(Object userObject, Object nodeName) {
		return userObject == null ? nodeName == null : userObject.equals(nodeName);
	}

	public static DefaultMutableTreeNodeAccessor getNew() {
		return new DefaultMutableTreeNodeAccessor();
	}

}

Sam kod budowania drzewa jest bardzo prosty

TreeBuilder<DefaultMutableTreeNode, String>
	defaultMutableTreeNodeBuilder = TreeBuilder.getNew();
String[] paths = { "A;B;C", "X;A", "A;X", "Q", "X;Y;Z;R;Q;Q" };
DefaultMutableTreeNode rootNode = new DefaultMutableTreeNode();
TreeNodeAccessor<DefaultMutableTreeNode, Object>
	nodeAccessor = DefaultMutableTreeNodeAccessor.getNew();
rootNode = defaultMutableTreeNodeBuilder.buildTree(
		PathSetFactory.fromStringPaths(paths, ";"), rootNode,
		nodeAccessor);
DefaultTreeModel treeModel = new DefaultTreeModel(rootNode);
JTree tree = new JTree(treeModel);

W efekcie otrzymamy następujące drzewo
tree-from-paths-demo
Kompletny projekt dostępny jest jako repozytorium jarek-przygodzki/tree-from-paths na GitHub’ie i zawiera między innymi demo prezentujące w postaci drzewiastej zbiór adresów URL
tree-from-urls-demo

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s