Revision: 5328
http://sourceforge.net/p/jump-pilot/code/5328
Author: michaudm
Date: 2017-01-20 22:29:48 +0000 (Fri, 20 Jan 2017)
Log Message:
-----------
Add a BeanTool to search for a plugin in the menus
Modified Paths:
--------------
core/trunk/ChangeLog
Added Paths:
-----------
core/trunk/src/com/vividsolutions/jump/util/SuggestTree.java
core/trunk/src/com/vividsolutions/jump/workbench/ui/SuggestTreeComboBox.java
Modified: core/trunk/ChangeLog
===================================================================
--- core/trunk/ChangeLog 2017-01-17 18:11:26 UTC (rev 5327)
+++ core/trunk/ChangeLog 2017-01-20 22:29:48 UTC (rev 5328)
@@ -3,6 +3,9 @@
# 2. make sure that lines break at 80 chars for constricted display situations
#<-------------------------------- 80 chars
---------------------------------->#
+2017-01-20 mmichaud <m.michael.mich...@orange.fr>
+ * Add a BeanTool to search for a plugin in the menus
+
2017-01-17 mmichaud <m.michael.mich...@orange.fr>
* Upgrade GraphToolBox to 0.4.0 for PLUS version
Added: core/trunk/src/com/vividsolutions/jump/util/SuggestTree.java
===================================================================
--- core/trunk/src/com/vividsolutions/jump/util/SuggestTree.java
(rev 0)
+++ core/trunk/src/com/vividsolutions/jump/util/SuggestTree.java
2017-01-20 22:29:48 UTC (rev 5328)
@@ -0,0 +1,683 @@
+/*
+ * Copyright (c) 2008-2014 Nicolai Diethelm
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE
+ * SOFTWARE.
+ *
+ * (MIT License)
+ */
+
+package com.vividsolutions.jump.util;
+
+import java.util.Arrays;
+import java.util.NoSuchElementException;
+import java.util.Random;
+
+/**
+ * An autocomplete data structure that enables you to quickly look up the top k
+ * terms with a given prefix in a set of weighted terms. The structure is based
+ * on a compressed trie of the terms (implemented as a randomized ternary
search
+ * tree) in which each node holds a weight-ordered list of the k
+ * highest-weighted terms in its subtree.
+ *
+ * <p>Note that this implementation is not synchronized. If multiple threads
+ * access a Suggest Tree concurrently, and at least one of the threads modifies
+ * the tree, it must be synchronized externally.
+ */
+public class SuggestTree {
+
+ private final Random random = new Random();
+ private final int k;
+ private Node root;
+ private int size;
+
+ /**
+ * Creates a Suggest Tree with the specified k-value.
+ *
+ * @param k the maximum number of autocomplete suggestions to return for a
+ * given prefix
+ * @throws IllegalArgumentException if the specified k-value is less than 1
+ */
+ public SuggestTree(int k) {
+ if(k < 1)
+ throw new IllegalArgumentException();
+ this.k = k;
+ root = null;
+ size = 0;
+ }
+
+ /**
+ * Returns the k highest-weighted terms in the tree that start with the
+ * specified prefix, or null if there is no such term.
+ *
+ * @param prefix the prefix for which to return autocomplete suggestions
+ * @return the k highest-weighted terms in the tree that start with the
+ * specified prefix, or null if there is no such term
+ * @throws IllegalArgumentException if the specified prefix is an empty
+ * string
+ * @throws NullPointerException if the specified prefix is null
+ */
+ public Node getAutocompleteSuggestions(String prefix) {
+ return search(prefix);
+ }
+
+ /**
+ * Returns the tree entry for the specified term, or null if there is no
+ * such entry.
+ *
+ * @param term the term for which to return the corresponding tree entry
+ * @return the tree entry for the specified term, or null if there is no
+ * such entry
+ * @throws IllegalArgumentException if the specified term is an empty
string
+ * @throws NullPointerException if the specified term is null
+ */
+ public Entry getEntry(String term) {
+ Node n = search(term);
+ if(n == null || n.charEnd > term.length())
+ return null;
+ else
+ return n.entry;
+ }
+
+ /**
+ * Returns an iterator over the terms in the tree.
+ *
+ * @return an iterator over the terms in the tree
+ */
+ public Iterator iterator() {
+ return new Iterator();
+ }
+
+ /**
+ * Returns the number of terms in the tree.
+ *
+ * @return the number of terms in the tree
+ */
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Inserts the specified term with the specified weight into the tree, or
+ * reweights the term if it is already present.
+ *
+ * @param term the term to be inserted or reweighted
+ * @param weight the weight to be assigned to the term
+ * @throws IllegalArgumentException if the specified term is an empty
string
+ * or much too long (longer than 32767 characters)
+ * @throws NullPointerException if the specified term is null
+ */
+ public void put(String term, int weight) {
+ if(term.isEmpty() || term.length() > Short.MAX_VALUE)
+ throw new IllegalArgumentException();
+ if(root == null) {
+ root = new Node(term, weight, 0, null);
+ finishInsertion(root);
+ return;
+ }
+ int i = 0;
+ Node n = root;
+ while(true) {
+ if(term.charAt(i) < n.firstChar) {
+ if(n.left == null) {
+ n.left = new Node(term, weight, i, n);
+ finishInsertion(n.left);
+ return;
+ }else
+ n = n.left;
+ }else if(term.charAt(i) > n.firstChar) {
+ if(n.right == null) {
+ n.right = new Node(term, weight, i, n);
+ finishInsertion(n.right);
+ return;
+ }else
+ n = n.right;
+ }else{
+ while(++i < n.charEnd) {
+ if(i == term.length() || term.charAt(i) != n.charAt(i)) {
+ n = split(n, i);
+ break;
+ }
+ }
+ if(i < term.length()) {
+ if(n.mid == null) {
+ n.mid = new Node(term, weight, i, n);
+ finishInsertion(n.mid);
+ return;
+ }else
+ n = n.mid;
+ }else{
+ if(n.entry == null) {
+ n.entry = new Entry(term, weight);
+ finishInsertion(n);
+ }else if(n.entry.weight < weight)
+ increaseWeight(n, weight);
+ else if(n.entry.weight > weight)
+ reduceWeight(n, weight);
+ return;
+ }
+ }
+ }
+ }
+
+ /**
+ * Removes the specified term from the tree.
+ *
+ * @param term the term to be removed
+ * @throws IllegalArgumentException if the specified term is an empty
string
+ * @throws NullPointerException if the specified term is null
+ */
+ public void remove(String term) {
+ Node n = search(term);
+ if(n == null || n.entry == null || n.charEnd > term.length())
+ return;
+ randomizeDeletion(n);
+ Entry e = n.entry;
+ n.entry = null;
+ if(n.mid == null) {
+ Node p = parent(n);
+ delete(n);
+ n = p;
+ }
+ if(n != null && n.entry == null && n.mid.left == null && n.mid.right
== null) {
+ Node p = parent(n);
+ merge(n, n.mid);
+ n = p;
+ }
+ removeFromLists(e, n);
+ size--;
+ }
+
+ private Node search(String s) {
+ if(s.isEmpty())
+ throw new IllegalArgumentException();
+ int i = 0;
+ Node n = root;
+ while(n != null) {
+ if(s.charAt(i) < n.firstChar)
+ n = n.left;
+ else if(s.charAt(i) > n.firstChar)
+ n = n.right;
+ else{
+ while(++i < n.charEnd) {
+ if(i == s.length())
+ return n;
+ else if(s.charAt(i) != n.charAt(i))
+ return null;
+ }
+ if(i == s.length())
+ return n;
+ else
+ n = n.mid;
+ }
+ }
+ return null;
+ }
+
+ private Node split(Node n, int position) {
+ Node s = new Node(n, position);
+ if(n.list.length == k)
+ s.list = Arrays.copyOf(n.list, k);
+ else // the list is copied in insertIntoLists()
+ s.list = n.list;
+ if(n.left != null)
+ n.left.up = s;
+ if(n.right != null)
+ n.right.up = s;
+ if(n == root)
+ root = s;
+ else if(n == n.up.left)
+ n.up.left = s;
+ else if(n == n.up.right)
+ n.up.right = s;
+ else
+ n.up.mid = s;
+ n.firstChar = n.charAt(position);
+ n.left = n.right = null;
+ n.up = s;
+ return s;
+ }
+
+ private void merge(Node n, Node m) {
+ m.firstChar = n.firstChar;
+ m.left = n.left;
+ m.right = n.right;
+ m.up = n.up;
+ if(n.left != null)
+ n.left.up = m;
+ if(n.right != null)
+ n.right.up = m;
+ if(n == root)
+ root = m;
+ else if(n == n.up.left)
+ n.up.left = m;
+ else if(n == n.up.right)
+ n.up.right = m;
+ else
+ n.up.mid = m;
+ }
+
+ private void delete(Node n) {
+ if(n == root)
+ root = null;
+ else if(n == n.up.left)
+ n.up.left = null;
+ else if(n == n.up.right)
+ n.up.right = null;
+ else
+ n.up.mid = null;
+ }
+
+ private void finishInsertion(Node n) {
+ randomizeInsertion(n);
+ insertIntoLists(n);
+ size++;
+ }
+
+ private void randomizeInsertion(Node n) {
+ n.entry.priority = random.nextInt();
+ n.priority = higherPriority(n.entry, n.mid);
+ while(n != root && n.up.priority < n.priority) {
+ if(n == n.up.left)
+ rotateRight(n.up);
+ else if(n == n.up.right)
+ rotateLeft(n.up);
+ else{
+ n.up.priority = n.priority;
+ n = n.up;
+ }
+ }
+ }
+
+ private void randomizeDeletion(Node n) {
+ int p = n.entry.priority;
+ n.entry.priority = Integer.MIN_VALUE;
+ while(n != null && n.priority == p) {
+ n.priority = higherPriority(n.entry, n.mid);
+ Node h = higherPriorityNode(n.left, n.right);
+ while(h != null && h.priority >= n.priority) {
+ if(h == n.left)
+ rotateRight(n);
+ else
+ rotateLeft(n);
+ h = higherPriorityNode(n.left, n.right);
+ }
+ n = parent(n);
+ }
+ }
+
+ private int higherPriority(Entry e, Node n) {
+ if(e == null)
+ return n.priority;
+ else if(n == null)
+ return e.priority;
+ else if(e.priority < n.priority)
+ return n.priority;
+ else
+ return e.priority;
+ }
+
+ private Node higherPriorityNode(Node n, Node m) {
+ if(n == null)
+ return m;
+ else if(m == null)
+ return n;
+ else if(n.priority < m.priority)
+ return m;
+ else
+ return n;
+ }
+
+ private void rotateLeft(Node n) {
+ Node r = n.right;
+ n.right = r.left;
+ if(r.left != null)
+ r.left.up = n;
+ r.up = n.up;
+ if(n == root)
+ root = r;
+ else if(n == n.up.left)
+ n.up.left = r;
+ else if(n == n.up.right)
+ n.up.right = r;
+ else
+ n.up.mid = r;
+ r.left = n;
+ n.up = r;
+ }
+
+ private void rotateRight(Node n) {
+ Node l = n.left;
+ n.left = l.right;
+ if(l.right != null)
+ l.right.up = n;
+ l.up = n.up;
+ if(n == root)
+ root = l;
+ else if(n == n.up.left)
+ n.up.left = l;
+ else if(n == n.up.right)
+ n.up.right = l;
+ else
+ n.up.mid = l;
+ l.right = n;
+ n.up = l;
+ }
+
+ private void insertIntoLists(Node n) {
+ Entry e = n.entry;
+ for( ; n != null; n = parent(n)) {
+ if(n.mid == null)
+ n.list = new Entry[1];
+ else if(n.list.length < k)
+ n.list = Arrays.copyOf(n.list, n.list.length + 1);
+ else if(e.weight <= n.list[k - 1].weight)
+ return;
+ int i = n.list.length - 1;
+ while(i > 0 && e.weight > n.list[i - 1].weight) {
+ n.list[i] = n.list[i - 1];
+ i--;
+ }
+ n.list[i] = e;
+ }
+ }
+
+ private void increaseWeight(Node n, int newWeight) {
+ Entry e = n.entry;
+ e.weight = newWeight;
+ for( ; n != null; n = parent(n)) {
+ int i = n.listIndexOf(e);
+ if(i == -1) {
+ if(e.weight <= n.list[k - 1].weight)
+ return;
+ else
+ i = k - 1;
+ }
+ while(i > 0 && e.weight > n.list[i - 1].weight) {
+ n.list[i] = n.list[i - 1];
+ i--;
+ }
+ n.list[i] = e;
+ }
+ }
+
+ private void reduceWeight(Node n, int newWeight) {
+ Entry e = n.entry;
+ e.weight = newWeight;
+ for( ; n != null; n = parent(n)) {
+ int i = n.listIndexOf(e);
+ if(i == -1)
+ return;
+ while(i < n.list.length - 1 && e.weight < n.list[i + 1].weight) {
+ n.list[i] = n.list[i + 1];
+ i++;
+ }
+ n.list[i] = e;
+ if(i == k - 1) {
+ Entry t = topUnlistedTerm(n);
+ if(t != null && t.weight > e.weight)
+ n.list[i] = t;
+ }
+ }
+ }
+
+ private void removeFromLists(Entry e, Node n) {
+ for( ; n != null; n = parent(n)) {
+ int i = n.listIndexOf(e);
+ if(i == -1)
+ return;
+ while(i < n.list.length - 1) {
+ n.list[i] = n.list[i + 1];
+ i++;
+ }
+ n.list[i] = e;
+ if(n.list.length < k)
+ n.list = Arrays.copyOf(n.list, n.list.length - 1);
+ else{
+ Entry t = topUnlistedTerm(n);
+ if(t == null)
+ n.list = Arrays.copyOf(n.list, k - 1);
+ else
+ n.list[i] = t;
+ }
+ }
+ }
+
+ private Entry topUnlistedTerm(Node n) {
+ Entry t = null;
+ if(n.entry != null && n.listIndexOf(n.entry) == -1)
+ t = n.entry;
+ for(Node c = leftmostChild(n); c != null; c = rightSibling(c)) {
+ for(Entry e : c.list) {
+ if(n.listIndexOf(e) == -1) {
+ if(t == null || t.weight < e.weight)
+ t = e;
+ break;
+ }
+ }
+ }
+ return t;
+ }
+
+ private Node leftmostChild(Node n) {
+ n = n.mid;
+ if(n != null) {
+ while(n.left != null)
+ n = n.left;
+ }
+ return n;
+ }
+
+ private Node rightSibling(Node n) {
+ if(n.right != null) {
+ n = n.right;
+ while(n.left != null)
+ n = n.left;
+ return n;
+ }else{
+ while(n == n.up.right)
+ n = n.up;
+ if(n == n.up.left)
+ return n.up;
+ else
+ return null;
+ }
+ }
+
+ private Node parent(Node n) {
+ while(n != root && n != n.up.mid)
+ n = n.up;
+ return n.up;
+ }
+
+ /**
+ * An iterator over the terms in the tree. The iterator returns the terms
in
+ * alphabetical order and allows the caller to remove returned terms from
+ * the tree during the iteration.
+ */
+ public class Iterator {
+
+ private Node next;
+
+ private Iterator() {
+ if(root == null)
+ next = null;
+ else
+ next = firstEntry(root);
+ }
+
+ /**
+ * Returns true if the iteration has more terms.
+ *
+ * @return true if the iteration has more terms
+ */
+ public boolean hasNext() {
+ return (next != null);
+ }
+
+ /**
+ * Returns the next term in the iteration.
+ *
+ * @return the next term in the iteration
+ * @throws NoSuchElementException if the iteration has no more terms
+ */
+ public Entry next() {
+ if(next == null)
+ throw new NoSuchElementException();
+ Entry e = next.entry;
+ next = nextEntry(next);
+ return e;
+ }
+
+ private Node firstEntry(Node n) {
+ while(true) {
+ while(n.left != null)
+ n = n.left;
+ if(n.entry == null)
+ n = n.mid;
+ else
+ return n;
+ }
+ }
+
+ private Node nextEntry(Node n) {
+ if(n.mid != null)
+ return firstEntry(n.mid);
+ else if(n.right != null)
+ return firstEntry(n.right);
+ else{
+ while(n.up != null) {
+ if(n == n.up.left) {
+ if(n.up.entry != null)
+ return n.up;
+ else
+ return firstEntry(n.up.mid);
+ }else if(n == n.up.mid && n.up.right != null)
+ return firstEntry(n.up.right);
+ else
+ n = n.up;
+ }
+ return null;
+ }
+ }
+ }
+
+ /**
+ * A list of autocomplete suggestions, ordered from highest weight to
lowest
+ * weight.
+ */
+ public static class Node {
+
+ private Entry[] list;
+ private Entry entry;
+ private char firstChar;
+ private short charEnd;
+ private int priority;
+ private Node left, mid, right;
+ private Node up; // parent in the ternary search tree
+
+ private Node(String term, int weight, int charStart, Node up) {
+ entry = new Entry(term, weight);
+ firstChar = term.charAt(charStart);
+ charEnd = (short) term.length();
+ left = mid = right = null;
+ this.up = up;
+ }
+
+ private Node(Node n, int charEnd) {
+ entry = null;
+ firstChar = n.firstChar;
+ this.charEnd = (short) charEnd;
+ priority = n.priority;
+ left = n.left;
+ mid = n;
+ right = n.right;
+ up = n.up;
+ }
+
+ /**
+ * Returns the suggestion at the specified index in the list. The first
+ * suggestion is at index 0, the second at index 1, and so on.
+ *
+ * @param index the index of the suggestion to return
+ * @return the suggestion at the specified index in the list
+ * @throws ArrayIndexOutOfBoundsException if the specified index is
+ * negative or not less than the list length
+ */
+ public Entry getSuggestion(int index) {
+ return list[index];
+ }
+
+ /**
+ * Returns the number of suggestions in the list.
+ *
+ * @return the number of suggestions in the list
+ */
+ public int listLength() {
+ return list.length;
+ }
+
+ private char charAt(int index) {
+ if(entry != null)
+ return entry.term.charAt(index);
+ else
+ return list[0].term.charAt(index);
+ }
+
+ private int listIndexOf(Entry e) {
+ for(int i = 0; i < list.length; i++) {
+ if(list[i] == e)
+ return i;
+ }
+ return -1;
+ }
+ }
+
+ /**
+ * A weighted term.
+ */
+ public static class Entry {
+
+ private final String term;
+ private int weight;
+ private int priority;
+
+ private Entry(String term, int weight) {
+ this.term = term;
+ this.weight = weight;
+ }
+
+ /**
+ * Returns the term.
+ *
+ * @return the term
+ */
+ public String getTerm() {
+ return term;
+ }
+
+ /**
+ * Returns the weight of the term.
+ *
+ * @return the weight of the term
+ */
+ public int getWeight() {
+ return weight;
+ }
+ }
+}
\ No newline at end of file
Added:
core/trunk/src/com/vividsolutions/jump/workbench/ui/SuggestTreeComboBox.java
===================================================================
---
core/trunk/src/com/vividsolutions/jump/workbench/ui/SuggestTreeComboBox.java
(rev 0)
+++
core/trunk/src/com/vividsolutions/jump/workbench/ui/SuggestTreeComboBox.java
2017-01-20 22:29:48 UTC (rev 5328)
@@ -0,0 +1,100 @@
+package com.vividsolutions.jump.workbench.ui;
+
+import com.vividsolutions.jump.util.SuggestTree;
+
+import javax.swing.*;
+import java.awt.event.KeyAdapter;
+import java.awt.event.KeyEvent;
+import java.util.*;
+
+/**
+ * SuggestTreeComboBox presents a selection of items starting with the
+ * same letters as the one in the editor using a SuggestTree (Trie).
+ * To be more flexible, suggestions are not limited to words starting
+ * with the token typed in the editor but also includes items containing
+ * such tokens.
+ */
+public class SuggestTreeComboBox extends JComboBox<String> {
+
+ private SuggestTree trie;
+ private Map<String,String> map;
+
+ public SuggestTreeComboBox(final String[] array, int size) {
+ super();
+ map = new HashMap<>(array.length);
+ this.trie = initTrie(array, size);
+ this.setEditable(true);
+ this.getEditor().getEditorComponent().addKeyListener(new
MyKeyAdapter(this));
+ }
+
+ public void changeModel(String[] array) {
+ map = new HashMap<>(array.length);
+ this.trie = initTrie(array, trie.size());
+ }
+
+ private SuggestTree initTrie(String[] array, int size) {
+ SuggestTree trie = new SuggestTree(size);
+ for (String s : array) {
+ String sm = s.toLowerCase();
+ map.put(sm, s);
+ trie.put(sm, 2);
+ for (int split : split(sm)) {
+ String permuted = sm.substring(split) + sm.substring(0, split);
+ map.put(permuted, s);
+ trie.put(permuted, 1);
+ }
+ }
+ return trie;
+ }
+
+ private Integer[] split(String s) {
+ List<Integer> list = new ArrayList<>();
+ for (int i = 1 ; i < s.length() ; i++) {
+ if (!Character.isLetter(s.charAt(i-1)) &&
Character.isLetter(s.charAt(i))) list.add(i);
+ if (!Character.isDigit(s.charAt(i-1)) &&
Character.isDigit(s.charAt(i))) list.add(i);
+ }
+ return list.toArray(new Integer[list.size()]);
+ }
+
+ class MyKeyAdapter extends KeyAdapter {
+
+ final SuggestTreeComboBox cb;
+
+ MyKeyAdapter(SuggestTreeComboBox cb) {
+ this.cb = cb;
+ }
+ @Override
+ public void keyReleased(KeyEvent e) {
+ super.keyReleased(e);
+ if (e.getKeyCode() == KeyEvent.VK_DOWN || e.getKeyCode() ==
KeyEvent.VK_UP) {
+ cb.getEditor().setItem(
+ cb.getSelectedItem()
+ );
+ return;
+ }
+ String newValue = ((String)cb.getEditor().getItem());
+ if (newValue.length() == 0) return;
+ SuggestTree.Node node =
cb.trie.getAutocompleteSuggestions(newValue.toLowerCase());
+ if (node == null || node.listLength() == 0) {
+ return;
+ } else if (node.listLength() == 1) {
+ cb.setSelectedItem(map.get(node.getSuggestion(0).getTerm()));
+ cb.hidePopup();
+ } else {
+ Set<String> set = new HashSet<>();
+ for (int i = 0; i < node.listLength(); i++) {
+ set.add(map.get(node.getSuggestion(i).getTerm()));
+ }
+ cb.setModel(new DefaultComboBoxModel<>(set.toArray(new
String[set.size()])));
+ cb.showPopup();
+ cb.getEditor().setItem(newValue);
+ // Very strange : if I start OpenJUMP from my IDE with ant, I
don't need to do that,
+ // but in production, if I don't unselect editor's content,
next key will replace
+ // previous content, and I can't simply add a letter to the
prvious one !
+
((JTextField)cb.editor.getEditorComponent()).select(newValue.length(),newValue.length());
+ }
+ }
+ }
+
+}
+
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
