Блог

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

Упрощенно: LinkedNode Каждый LinkedNode имеет значение и хэш-карту следующих возможных узлов для перехода. (Я назвал это «пошаговым»)

Это один из способов, которым структура может выглядеть следующим образом. Узлы с ключами BEGIN, START, ALOITA являются начальными узлами маршрута, в то время как в других узлах их ключ не показан на рисунке. Могут быть узлы с одинаковым ключом, но узел a не может указывать на два узла с одинаковыми ключами (то же самое с начальными узлами)

Маршрут: Маршрут имеет хэш-карту LinkedNodes, с которой можно начать, и два стека, которые можно использовать для отмены и повторного выполнения ваших шагов в маршруте. Маршрут может содержать циклы и узлы с одинаковыми значениями ключей, но один LinkedNode может указывать только на узлы с разными ключами (например, узел A может указывать на узлы, у которых есть ключи a, b, c, d, но он не может указывать на узлы a, a, b, c, поскольку есть похожие ключи). Первый стек, который отслеживает ваше продвижение по маршруту, также используется для определения вашего текущего положения в маршруте (поверх стека). Возможно, вы никогда не выйдете из стека (если A указывает на a, b, c, он не сможет попытаться перейти к узлу с ключом d).

Поскольку несколько узлов могут иметь один и тот же ключ, невозможно просто «сохранить их в map», и из-за структуры генерировать UUID очень сложно, поскольку я уже некоторое время пытаюсь заставить это работать. Использование общего алгоритма, подобного DFS, также проблематично, поскольку это приведет к бесконечному циклу, если не будет проверено, что один ключ не повторяется дважды. Я безуспешно пытался собрать все узлы маршрута в список и был бы признателен за любую помощь.

LinkedNode:

 import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * A node that is linked forward to next nodes. Used for example by
 * Web data structure
 * @author Nuubles
 *
 * @param <K> Key
 * @param <V> Value
 */
public class LinkedNode <K extends Comparable<K>,V> implements Comparable<LinkedNode<K,V>>, Iterable<LinkedNode<K,V>>{
    private K key;
    private V value;
    private Map<K,LinkedNode<K,V>> nextNodes = new HashMap<K,LinkedNode<K,V>>();

    /**
     * Initializes a new linkedNode with a key and a value
     * @param key Key of this node
     * @param value Value of this node
     */
    public LinkedNode(final K key, final V value) throws IllegalArgumentException
    {
        if(key == null)
            throw new IllegalArgumentException("Given key was null!");

        this.key = key;
        this.value = value;
    }

    /**
     * Returns the next node using a key 
     * @param key Key which the next node needs to have
     * @return Next node after this or null if there's no next node
     */
    public LinkedNode<K,V> getNextNode(final K key)
    { return nextNodes.get(key); }

    /**
     * Returns the all the next nodes after this node
     * @return Collection of next nodes after this
     */
    public Collection<LinkedNode<K,V>> getNextNodes()
    { return nextNodes.values(); }

    /**
     * Returns the next possible routes after this node
     * @return Routes after this node
     */
    public Collection<K> getNextKeys()
    { return nextNodes.keySet(); }

    /**
     * Return the next node which was removed or null
     * if no node was found
     * @param key Key of the node to be removed
     * @return The removed node
     */
    public LinkedNode<K,V> removeNextNode(final K key)
    { return this.nextNodes.remove(key); }

    /**
     * Adds a next node to this node and overrides old if there
     * is some node with same key
     * @param key Key of the next node to add
     * @param value Value of the next node to add
     */
    public void putNextNode(final K key, final V value)
    {
        LinkedNode<K,V> node = new LinkedNode<K,V>(key,value);
        this.nextNodes.put(key, node);
    }

    /**
     * Adds a next node to this node and overrides old if there
     * is some node with same key
     * @param node Node to add
     */
    public void putNextNode(LinkedNode<K,V> node)
    { this.nextNodes.put(node.key, node); }

    /**
     * Like putNextNode, but if key already exists,
     * does not add.
     * @param key Key of the node
     * @param value Value of the node
     * @return Was the addition successful
     */
    public boolean addNextNode(final K key, final V value)
    {
        if(this.nextNodes.containsKey(key))
            return false;
        LinkedNode<K,V> node = new LinkedNode<K,V>(key,value);
        this.nextNodes.put(key, node);
        return true;
    }

    /**
     * Like putNextNode, but if key already exists,
     * does not add.
     * @param node Node to add
     * @return Was the addition successful
     */
    public boolean addNextNode(final LinkedNode<K,V> node)
    {
        if(this.nextNodes.containsKey(node.key))
            return false;
        this.nextNodes.put(key, node);
        return true;
    }

    /**
     * Removes all the nodes after this node
     */
    public void clearNextNodes()
    { this.nextNodes.clear(); }

    /**
     * Compares the values of the nodes, but not the
     * next nodes. If nodes contain null then return false
     */
    @Override
    public boolean equals(Object node)
    {
        if(!(node instanceof LinkedNode<?,?>))
            return false;

        LinkedNode<?,?> converted = (LinkedNode<?,?>)node;

        //Verify there are no null values
        if(this.key == null || this.value == null || converted.key == null || converted.value == null)
            return false;

        return (this.key.equals(converted.key) amp;amp; this.value.equals(converted.value));
    }

    /**
     * Does this node have next nodes to traverse to
     * @return True if can travel further, false otherwise
     */
    public boolean isEmpty()
    { return this.nextNodes.isEmpty(); }

    /**
     * Compare the keys of this and a given node
     */
    @Override
    public int compareTo(LinkedNode<K,V> node)
    { return this.key.compareTo(node.key); }

    /**
     * Checks if there is a next node that has given key
     * @param key Key to look for
     * @return Was there a next node with given key
     */
    public boolean hasNextNode(final K key)
    { return this.nextNodes.containsKey(key); }

    /*==========[ ACCESSORS ]=========*/

    /**
     * Get this nodes key
     * @return The key of this node
     */
    public K getKey()
    { return this.key; }

    /**
     * Set the key of this node
     * @param key the new node for this key
     * @return Old key of this node
     */
    public K setKey(final K key)
    {
        K k = this.key;
        this.key = key;
        return k;
    }

    /**
     * Get the value of this node
     * @return The value of this node
     */
    public V getValue()
    { return this.value; }

    /**
     * Set the value of this node
     * @param value The value of this node
     * @return The old value of this value
     */
    public V setValue(final V value)
    { 
        V v = this.value;
        this.value = value;
        return v;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Iterator<LinkedNode<K, V>> iterator() {
        return this.nextNodes.values().iterator();
    }
}
  

Маршрут:

 import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class Route<K extends Comparable<K>,V> implements Iterable<Entry<K,V>>{
    //Path we've made
    private Deque<LinkedNode<K,V>> path = new ArrayDeque<LinkedNode<K,V>>();
    //Path we've made but stepped back from
    private Deque<LinkedNode<K,V>> futurePath = new ArrayDeque<LinkedNode<K,V>>();
    //Nodes in this web
    private Map<K,LinkedNode<K,V>> nodes = new HashMap<K,LinkedNode<K,V>>();

    /**
     * Initializes the route to start with given path startpoints
     * @param startValues Points which from the path can be started
     */
    public Route(Collection<Entry<K,V>> startValues)
    {
        for(Entry<K,V> entry : startValues)
            nodes.put(entry.getKey(), new LinkedNode<K,V>(entry.getKey(),entry.getValue()));
    }

    /**
     * Initializes an empty route with no startpoints
     * to start traversal
     */
    public Route()
    {}

    /**
     * Initializes a route with one startpoint to start
     * traversal from
     * @param key Key of the startpoint
     * @param value Value of the startpoint
     */
    public Route(final K key, final V value)
    { nodes.put(key, new LinkedNode<K,V>(key,value)); }

    /**
     * Traverses a given path starting from current point.
     * Stops traversal if unsuccessful, but stays at endpoint.
     * Cannot perform restep after this action, traversal is stored in unstep.
     * @param points Keys to travel along
     * @return True if traversal was successful to point, False if unsuccessful and
     * stayed at endpoint 
     */
    public boolean traversePoints(List<K> points)
    {
        //Traverse the points
        for(K point : points)
        {
            if(!this.hasNextNode(point))
                return false;
            this.step(point);
        }

        return true;
    }

    /**
     * Connects current node to another node following the
     * given path. Will not replace existing node if there is one
     * with same key as the node being added.
     * Basically creates a bridge from current node to the node
     * in the given path
     * @param points Path to follow to next node FROM START
     * @return Was the route created to the path
     */
    public boolean addCurrentToPath(List<K> points)
    {
        //If empty list is given, return false
        if(points == null || points.size() == 0)
            return false;

        if(this.path.peek().hasNextNode(points.get(points.size()-1)))
            return false;

        return this.putCurrentToPath(points);
    }

    /**
     * Connects current node to another node following the
     * given path and replaces old node with same key if there is one.
     * Basically creates a bridge from current node to the node
     * in the given path
     * @param points Path to follow to next node FROM START
     * @return Was the route created to the path
     */
    public boolean putCurrentToPath(List<K> points)
    {
        //If empty list is given, return false
        if(points == null || points.size() == 0)
            return false;

        if(this.nodes.isEmpty())
            return false;

        boolean firstStep = true;
        LinkedNode<K,V> currentNode = null;

        //Traverse path along points
        for(K point : points)
        {
            if(firstStep)
            {
                //Node to start the traversal from
                currentNode = this.nodes.get(points);
                if(currentNode == null)
                    return false;
                continue;
            }

            currentNode = currentNode.getNextNode(point);

            if(currentNode == null)
                return false;
        }

        //currentNode will be the node to which current node needs to connect
        this.path.peek().putNextNode(currentNode);
        return true;
    }

    /**
     * Traverses a given path starting from current point.
     * Stops traversal if unsuccessful, but stays at endpoint.
     * Cannot perform restep after this action, traversal is stored in unstep.
     * @param points Keys to travel along
     * @return True if traversal was successful to point, False if unsuccessful and
     * stayed at endpoint 
     */
    public boolean traversePoints(@SuppressWarnings("unchecked") K... points)
    {
        if(points == null)
            return false;

        //Traverse the points
        for(K point : points)
        {
            if(!this.hasNextNode(point))
                return false;
            this.step(point);
        }

        return true;
    }

    /**
     * Returns the possible path choices for next key
     * @return
     */
    public Collection<K> getNextKeys()
    { 
        if(path.isEmpty()) //Begin a new path
            return nodes.keySet();
        else //Continue old path
            return path.peek().getNextKeys();
    }


    /**
     * Traverses forward in path to the next object.
     * Cannot restep after this is ran unless unsteps are made
     * @param key Key to which object should we traverse to
     * @return List of keys possible to continue from the next node
     */
    public Collection<K> step(final K key)
    {
        if(path.isEmpty())
        {
            LinkedNode<K,V> node = nodes.get(key);
            if(node == null) //There is no next node after this, return empty list
                return new ArrayDeque<K>();
            path.push(node); //Add new node to the route traversed
            futurePath.clear();
            return node.getNextKeys();
        }

        //We've already traversed some path, continue on
        LinkedNode<K,V> node = path.peek().getNextNode(key);
        if(node == null) //There is no next node after this, return empty list
            return new ArrayDeque<K>();

        path.push(node);
        futurePath.clear();
        return node.getNextKeys();
    }

    /**
     * Removes the next node if it exists
     * @param key Key of the next node to remove
     * @return Value of the node removed
     */
    public V removeNextNode(final K key)
    {
        //We haven't started traversal yet, remove from start nodes
        if(path.isEmpty())
        {
            LinkedNode<K,V> node = nodes.remove(key);
            if(node == null)
                return null;
            return node.getValue();
        }

        LinkedNode<K,V> node = path.peek().removeNextNode(key);
        if(node == null)
            return null;
        return node.getValue();
    }

    /**
     * Removes all the next nodes after this node, or if
     * we've not traversed at all, clear the start nodes.
     */
    public void clearNextNodes()
    {
        if(path.isEmpty())
        {
            this.nodes.clear();
            return;
        }

        path.peek().clearNextNodes();
    }

    /**
     * Steps back one step in the route.
     * Works kinda like UNDO
     * @return Can we step back more
     */
    public boolean unstep()
    {
        if(path.isEmpty())
            return false;

        futurePath.push(path.pop());
        return !path.isEmpty();
    }

    /**
     * Steps forward in path we've already traversed
     * but backstepped.
     * Works kinda like REDO
     * @return Can we restep further
     */
    public boolean restep()
    {
        if(futurePath.isEmpty())
            return false;

        path.push(futurePath.pop());
        return !futurePath.isEmpty();
    }

    /**
     * Checks if this route has no routes
     * @return Is this route empty
     */
    public boolean isEmpty()
    { return this.nodes.isEmpty(); }

    /**
     * Returns the traversed path from start to current node.
     * MAY LOOP LIKE A RING!
     * @return List of key-value pairs in the traversed order
     */
    public ArrayDeque<Entry<K,V>> getCurrentPath()
    {
        ArrayDeque<Entry<K,V>> traversal = new ArrayDeque<Entry<K,V>>();

        for(LinkedNode<K,V> node : this.path)
            traversal.add(new SimpleEntry<K,V>(node.getKey(),node.getValue()));
        return traversal;
    }

    /**
     * Clears the traversed path, returning to start where
     * no moves were made.
     * Restep and unstep cannot be operated after this unless
     * steps are made.
     */
    public void clearPath()
    {
        this.path.clear();
        this.futurePath.clear();
    }

    /**
     * Are there any nodes further where
     * it is possible to traverse to.
     * @return If there are nodes after this node to traverse to
     */
    public boolean hasNextNodes()
    { 
        if(this.path.isEmpty())
            return this.nodes.isEmpty();
        return path.peek().isEmpty(); 
    }

    /**
     * Checks if it is possible to traverse from current position to a node with
     * given key
     * @param key Key to look for
     * @return Is it possible to traverse with given key
     */
    public boolean hasNextNode(final K key)
    {
        if(this.path.isEmpty())
            return this.nodes.containsKey(key);
        if(this.path.peek().isEmpty())
            return false;
        return this.path.peek().hasNextNode(key);
    }

    /**
     * Checks if it is possible to restep (REDO)
     * @return Is it possible to restep unstepped steps
     */
    public boolean canRestep()
    { return !this.futurePath.isEmpty(); }

    /**
     * Checks if it is possible to unstep (UNDO)
     * @return Is it possible to unstep stepped steps
     */
    public boolean canUnstep()
    { return !this.path.isEmpty(); }

    /**
     * Adds a new node after current node or at the start nodes
     * @param key Key for the new node
     * @param value Value for the new node
     * @return True if node was added, False if node already existed
     * and was not added
     */
    public boolean addNextNode(final K key, final V value)
    {
        if(this.hasNextNode(key))
            return false;

        if(this.path.isEmpty())
            this.nodes.put(key, new LinkedNode<K,V>(key, value));
        else
            this.path.peek().addNextNode(new LinkedNode<K,V>(key, value));
        return true;
    }

    /**
     * Puts a new node after current node or start nodes
     * @param key Key for the new node
     * @param value Value for the new node
     */
    public void putNextNode(final K key, final V value)
    {
        if(this.path.isEmpty())
            this.nodes.put(key, new LinkedNode<K,V>(key, value));
        else
            this.path.peek().addNextNode(key, value);
    }

    /*@Override
    public Iterator<Entry<K,V>> iterator() {
        List<Entry<K,V>> allNodes = new ArrayList<Entry<K,V>>();
        Deque<LinkedNode<K,V>> queue = new ArrayDeque<LinkedNode<K,V>>();

        for(Entry<K, LinkedNode<K, V>> entry : this.nodes.entrySet())
        {
            queue.push(entry.getValue()); //Add current start node to queue
            //Add current start node to list of all Nodes
            allNodes.add(new SimpleEntry<K,V>(entry.getValue().getKey(), entry.getValue().getValue()));

            for(LinkedNode<K,V> node : entry.getValue()) //Iterate all children in queue
            {
                Entry<K,V> pair = new SimpleEntry<K,V>(node.getKey(),node.getValue());

                //If we've already counter this node, don't count it
                if(allNodes.contains(pair))
                    continue;
                //queue.push(p);
            }
        }

        return null;
    }*/
}
  

Как сказал @Dylan в комментариях, в LinkedNode был добавлен простой флаг для определения того, был ли узел уже посещен, чтобы предотвратить повторное посещение одного и того же узла. Для получения всех узлов требуется поиск в глубину, после чего флаги в узлах снимаются.