Я создал структуру данных, которую раньше нигде не видел.Структура похожа на график, но вместо графика она имеет одну или несколько начальных точек, из которых вы можете перейти к следующим точкам маршрута с помощью клавиш.В приложении (плагине), который я разрабатываю, я столкнулся с необходимостью итерировать все значения в маршруте, чтобы сгенерировать конфигурацию перевода для каждой точки в маршруте.
Упрощенный: LinkedNode Каждый LinkedNode имеет значение и хэш-картуиз следующих возможных узлов для продвижения.(Я назвал это «степпингом»)
Это один из способов, которым структура может выглядеть.Узлы с ключами BEGIN, START, ALOITA являются начальными узлами маршрута, в то время как в других узлах их ключ не показан на рисунке.Могут быть узлы с одинаковым ключом, но узел не может указывать на два узла с одинаковыми ключами (одинаковыми с начальными узлами)
Маршрут: Маршрут имеет хэш-карту узлов LinkedNode, с которых можноНачните с двух стеков, которые можно использовать для отмены (отмены) и повторного (повторения) шагов в маршруте.Маршрут может содержать петли и узлы с одинаковыми значениями ключа, но один LinkedNode может указывать только на узлы с разными ключами (например, узел A может указывать на узлы, которые имеют ключи a, b, c, d, но не может указывать на узлы a,a, b, c, так как есть похожие ключи).Первый стек, который отслеживает ваше продвижение по маршруту, также используется для определения вашей текущей позиции на маршруте (на вершине стека).Вы никогда не сможете выйти из стека (если A указывает на a, b, c, он не может попытаться перейти на узел с ключом d).
Поскольку несколько узлов могут иметь один и тот же ключ, это невозможнопросто «сохранить их на карте», и из-за структуры, генерирующей 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) && 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;
}*/
}