Ciao a tutti, sto scrivendo una applicazione Java che permetta di cifrare e decifrare un testo con vari algoritmi di cifratura.
Quando un utente vuole decifrare un testo, propone delle assegnazioni che vengono applicate al testo cifrato.
Una assegnazione è per esempio:
A = d, cioè il carattere A viene mappato con il carattere d.
In altre parole il programma sostituirà (nel testo cifrato) ogni occorrenza del carattere A con il carattere d.
Inoltre l'utente deve avere la possibilità di tornare indietro nelle assegnazioni fatte senza che quest'ultime vengano cancellate.
Il mio problema è l'implementazione di una struttura dati che mi permetta di navigare le assegnazioni fatte.
Per questo motivo ho pensato di usare un albero generico.
Ad esempio ad un certo istante l'utente potrebbe essere in questa situazione.
gXsAm.jpg
Ovvero l'utente
- per prima cosa ha creato la prima assegnazione A = d
- poi ha creato la seconda assegnazione (primo ramo) C = b
- la terza assegnazione è F = i
- poi ha deciso di tornare indietro. Quindi l'assegnazione F = i viene segnata come non valida.
Crea quindi l'assegnazione G = l.
- torna ancora indietro di una posizione e crea la nuova assegnazione T = h
- eccetera...
Inoltre l'utente può modificare ed eliminare una assegnazione a piacere fatta precedentemente quindi
ciò di cui ho bisogno è una struttura dati che permetta di:
1) memorizzare ogni "percorso"
2) tornare indietro senza cancellare le assegnazioni già fatte
3) poter cercare un assegnamento e, se presente nell'albero, di raggiungere quel nodo e modificare il suo valore.
Quindi una specie di funzione "find(Assegnazione assegnazione)".
4) aggiungere ed eliminare nodi senza creare danni.
Cioè se viene eliminato il nodo C = b (con la stella azzurra), i percorsi {A = d, F = i} e {A = d, G = l} devono rimanere distinti.
Per ora ho scritto questo codice.
Class Node<T>:
codice:public class Node<T> { private T data; private Timestamp timestamp; private List<Node<T>> children; private Node<T> parent; public Node(T data) { this.data = data; this.children = new ArrayList<Node<T>>(); long l = 3L; this.timestamp = new Timestamp(l); } public Node(Node<T> node) { this.data = (T) node.getData(); children = new ArrayList<Node<T>>(); long l = 3L; this.timestamp = new Timestamp(l); } public T getData() { return this.data; } public void setData(T data) { this.data = data; } public Timestamp getTimestamp() { return this.timestamp; } public Node<T> getParent() { return this.parent; } public void setParent(Node<T> parent) { this.parent = parent; } public List<Node<T>> getChildren() { return this.children; } public void addChild(Node<T> child) { child.setParent(this); children.add(child); } public void addChildAt(int index, Node<T> child) { child.setParent(this); this.children.add(index, child); } public void setChildren(List<Node<T>> children) { for(Node<T> child : children) child.setParent(this); this.children = children; } public void removeChildren() { this.children.clear(); } public Node<T> removeChildAt(int index) { return children.remove(index); } public void removeThisIfItsAChild(Node<T> childToBeDeleted) { List<Node<T>> list = getChildren(); list.remove(childToBeDeleted); } public Node<T> getChildAt(int index) { return children.get(index); } @Override public boolean equals(Object obj) { if(obj == null) return false; if(obj instanceof Node) { if(((Node<T>) obj).getData().equals(this.data)) return true; } return false; } @Override public String toString() { return this.data.toString(); } }
Classe Tree<T>:
codice:import java.util.ArrayList; public class Tree<T> { private Node<T> root; public Tree(Node<T> root) { this.root = root; } public Node<T> getRoot() { return root; } public void setRoot(Node<T> root) { this.root = root; } public boolean isEmpty() { return (root == null) ? true : false; } public boolean exists(T key) { return find(root, key); } public int getNumberOfNodes() { return getNumberOfDescendants(root) + 1; } public int getNumberOfDescendants(Node<T> node) { int n = node.getChildren().size(); for(Node<T> child : node.getChildren()) n += getNumberOfDescendants(child); return n; } private boolean find(Node<T> node, T keyNode) { boolean res = false; if(node.getData().equals(keyNode)) return true; else { for(Node<T> child : node.getChildren()) if(find(child, keyNode)) res = true; } return res; } private Node<T> findNode(Node<T> node, T keyNode) { if(node == null) return null; if(node.getData().equals(keyNode)) return node; else { Node<T> cnode = null; for(Node<T> child : node.getChildren()) if((cnode = findNode(child, keyNode)) != null) return cnode; } return null; } public ArrayList<Node<T>> getPreOrderTraversal() { ArrayList<Node<T>> preOrder = new ArrayList<Node<T>>(); buildPreOrder(root, preOrder); return preOrder; } public ArrayList<Node<T>> getPostOrderTraversal() { ArrayList<Node<T>> postOrder = new ArrayList<Node<T>>(); buildPostOrder(root, postOrder); return postOrder; } private void buildPreOrder(Node<T> node, ArrayList<Node<T>> preOrder) { preOrder.add(node); for(Node<T> child : node.getChildren()) { buildPreOrder(child, preOrder); } } private void buildPostOrder(Node<T> node, ArrayList<Node<T>> preOrder) { for(Node<T> child : node.getChildren()) { buildPreOrder(child, preOrder); } preOrder.add(node); } public ArrayList<Node<T>> getLongestPathFromRootToAnyLeaf() { ArrayList<Node<T>> longestPath = null; int max = 0; for(ArrayList<Node<T>> path : getPathsFromRootToAnyLeaf()) { if(path.size() > max) { max = path.size(); longestPath = path; } } return longestPath; } public int getMaxDepth() { return getLongestPathFromRootToAnyLeaf().size(); } public ArrayList<ArrayList<Node<T>>> getPathsFromRootToAnyLeaf() { ArrayList<ArrayList<Node<T>>> paths = new ArrayList<ArrayList<Node<T>>>(); ArrayList<Node<T>> currentPath = new ArrayList<Node<T>>(); getPath(root, currentPath, paths); return paths; } private void getPath(Node<T> node, ArrayList<Node<T>> currentPath, ArrayList<ArrayList<Node<T>>> paths) { if(currentPath == null) return; currentPath.add(node); if(node.getChildren().size() == 0) { paths.add(clone(currentPath)); } for(Node<T> child : node.getChildren()) getPath(child, currentPath, paths); int index = currentPath.indexOf(node); for(int i = index; i < currentPath.size(); i++) currentPath.remove(index); } private ArrayList<Node<T>> clone(ArrayList<Node<T>> list) { ArrayList<Node<T>> newList = new ArrayList<Node<T>>(); for(Node<T> node : list) newList.add(new Node<T>(node)); return newList; } /*** TO DO ***/ public void addChild() { //looking for most recent timestamp //add the child } }
Main class:
codice:public class Main { public static void main(String[] args) { Node<Integer> node = new Node<Integer>(5); Tree<Integer> tree = new Tree<Integer>(node); Node<Integer> f1 = new Node<Integer>(1); node.addChild(f1); Node<Integer> f2 = new Node<Integer>(2); node.addChild(f2); Node<Integer> f3 = new Node<Integer>(3); node.addChild(f3); ArrayList<Node<Integer>> preorder = new ArrayList<Node<Integer>>(); preorder = tree.getPreOrderTraversal(); Iterator iterator = preorder.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } } }
Ora vorrei aggiungere 3 metodi che facciano le seguenti cose:
- printTree(): stampa l'albero in modo comprensibile (usando Graphviz come si fa?). Oppure anche a terminale.
- goBack(): torna indietro di un nodo ed aggiorna il timestamp
- addChild(): aggiunge un nodo a quello in cui mi trovo ora, cioè teoricamente quello con timestamp più recente.
- removeNode(Node n): rimuove il nodo n e risistema l'albero (come spiegato sopra)
- find(Assegnazione a): cerca l'assegnazione a
Come si fanno? Sembrano facili ma al momento in cui provo a scrivere codice non ho idee di come farli...
Non so se ho scelto la struttura dati corretta per i miei scopi oppure no. In caso sbagliato, cosa mi consigliate di usare?
Ci sono già implementazioni che fanno quello che mi serve?
Grazie!
Rispondi quotando