Index: trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionItem.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionItem.java	(revision 12859)
+++ trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionItem.java	(revision 12859)
@@ -0,0 +1,140 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.tagging.ac;
+
+import org.openstreetmap.josm.tools.CheckParameterUtil;
+
+/**
+ * Represents an entry in the set of auto completion values.
+ *
+ *  An AutoCompletionItem has a <em>priority</em> and a <em>value</em>.
+ *
+ *  The priority helps to sort the auto completion items according to their importance. For instance,
+ *  in an auto completion set for tag names, standard tag names would be assigned a higher
+ *  priority than arbitrary tag names present in the current data set. There are three priority levels,
+ *  {@link AutoCompletionPriority}.
+ *
+ * The value is a string which will be displayed in the auto completion list.
+ * @since 12859 (copied from {@code gui.tagging.ac.AutoCompletionListItem})
+ */
+public class AutoCompletionItem implements Comparable<AutoCompletionItem> {
+
+    /** the priority of this item */
+    private AutoCompletionPriority priority;
+    /** the value of this item */
+    private String value;
+
+    /**
+     * Constructs a new {@code AutoCompletionItem} with the given value and priority.
+     * @param value The value
+     * @param priority The priority
+     */
+    public AutoCompletionItem(String value, AutoCompletionPriority priority) {
+        this.value = value;
+        this.priority = priority;
+    }
+
+    /**
+     * Constructs a new {@code AutoCompletionItem} with the given value and unknown priority.
+     * @param value The value
+     */
+    public AutoCompletionItem(String value) {
+        this.value = value;
+        priority = AutoCompletionPriority.UNKNOWN;
+    }
+
+    /**
+     * Constructs a new {@code AutoCompletionItem}.
+     */
+    public AutoCompletionItem() {
+        value = "";
+        priority = AutoCompletionPriority.UNKNOWN;
+    }
+
+    /**
+     * Returns the priority.
+     * @return the priority
+     */
+    public AutoCompletionPriority getPriority() {
+        return priority;
+    }
+
+    /**
+     * Sets the priority.
+     * @param priority  the priority
+     */
+    public void setPriority(AutoCompletionPriority priority) {
+        this.priority = priority;
+    }
+
+    /**
+     * Returns the value.
+     * @return the value
+     */
+    public String getValue() {
+        return value;
+    }
+
+    /**
+     * sets the value
+     * @param value the value; must not be null
+     * @throws IllegalArgumentException if value if null
+     */
+    public void setValue(String value) {
+        CheckParameterUtil.ensureParameterNotNull(value, "value");
+        this.value = value;
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder sb = new StringBuilder();
+        sb.append("<val='")
+          .append(value)
+          .append("',")
+          .append(priority)
+          .append('>');
+        return sb.toString();
+    }
+
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime * result
+                + ((priority == null) ? 0 : priority.hashCode());
+        result = prime * result + ((value == null) ? 0 : value.hashCode());
+        return result;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null)
+            return false;
+        if (obj instanceof String)
+            return obj.equals(value);
+        if (getClass() != obj.getClass())
+            return false;
+        final AutoCompletionItem other = (AutoCompletionItem) obj;
+        if (priority == null) {
+            if (other.priority != null)
+                return false;
+        } else if (!priority.equals(other.priority))
+            return false;
+        if (value == null) {
+            if (other.value != null)
+                return false;
+        } else if (!value.equals(other.value))
+            return false;
+        return true;
+    }
+
+    @Override
+    public int compareTo(AutoCompletionItem other) {
+        int ret = other.priority.compareTo(priority); // higher priority items come first in the list
+        if (ret != 0)
+            return ret;
+        else
+            return this.value.compareTo(other.value);
+    }
+}
Index: trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionPriority.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionPriority.java	(revision 12859)
+++ trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionPriority.java	(revision 12859)
@@ -0,0 +1,173 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.tagging.ac;
+
+import java.util.Objects;
+
+/**
+ * Describes the priority of an item in an autocompletion set.
+ * The selected flag is currently only used in plugins.
+ *
+ * Instances of this class are not modifiable.
+ * @since 12859 (copied from {@code gui.tagging.ac.AutoCompletionItemPriority})
+ */
+public class AutoCompletionPriority implements Comparable<AutoCompletionPriority> {
+
+    /**
+     * Indicates, that the value is standard and it is found in the data.
+     * This has higher priority than some arbitrary standard value that is
+     * usually not used by the user.
+     */
+    public static final AutoCompletionPriority IS_IN_STANDARD_AND_IN_DATASET = new AutoCompletionPriority(true, true, false);
+
+    /**
+     * Indicates that this is an arbitrary value from the data set, i.e.
+     * the value of a tag name=*.
+     */
+    public static final AutoCompletionPriority IS_IN_DATASET = new AutoCompletionPriority(true, false, false);
+
+    /**
+     * Indicates that this is a standard value, i.e. a standard tag name
+     * or a standard value for a given tag name (from the presets).
+     */
+    public static final AutoCompletionPriority IS_IN_STANDARD = new AutoCompletionPriority(false, true, false);
+
+    /**
+     * Indicates that this is a value from a selected object.
+     */
+    public static final AutoCompletionPriority IS_IN_SELECTION = new AutoCompletionPriority(false, false, true);
+
+    /** Unknown priority. This is the lowest priority. */
+    public static final AutoCompletionPriority UNKNOWN = new AutoCompletionPriority(false, false, false);
+
+    private static final int NO_USER_INPUT = Integer.MAX_VALUE;
+
+    private final int userInput;
+    private final boolean inDataSet;
+    private final boolean inStandard;
+    private final boolean selected;
+
+    /**
+     * Constructs a new {@code AutoCompletionItemPriority}.
+     *
+     * @param inDataSet true, if the item is found in the currently active data layer
+     * @param inStandard true, if the item is a standard tag, e.g. from the presets
+     * @param selected true, if it is found on an object that is currently selected
+     * @param userInput null, if the user hasn't entered this tag so far. A number when
+     * the tag key / value has been entered by the user before. A lower number means
+     * this happened more recently and beats a higher number in priority.
+     */
+    public AutoCompletionPriority(boolean inDataSet, boolean inStandard, boolean selected, Integer userInput) {
+        this.inDataSet = inDataSet;
+        this.inStandard = inStandard;
+        this.selected = selected;
+        this.userInput = userInput == null ? NO_USER_INPUT : userInput;
+    }
+
+    /**
+     * Constructs a new {@code AutoCompletionItemPriority}.
+     *
+     * @param inDataSet true, if the item is found in the currently active data layer
+     * @param inStandard true, if the item is a standard tag, e.g. from the presets
+     * @param selected true, if it is found on an object that is currently selected
+     */
+    public AutoCompletionPriority(boolean inDataSet, boolean inStandard, boolean selected) {
+        this(inDataSet, inStandard, selected, NO_USER_INPUT);
+    }
+
+    /**
+     * Determines if the item is found in the currently active data layer.
+     * @return {@code true} if the item is found in the currently active data layer
+     */
+    public boolean isInDataSet() {
+        return inDataSet;
+    }
+
+    /**
+     * Determines if the item is a standard tag, e.g. from the presets.
+     * @return {@code true} if the item is a standard tag, e.g. from the presets
+     */
+    public boolean isInStandard() {
+        return inStandard;
+    }
+
+    /**
+     * Determines if it is found on an object that is currently selected.
+     * @return {@code true} if it is found on an object that is currently selected
+     */
+    public boolean isSelected() {
+        return selected;
+    }
+
+    /**
+     * Returns a number when the tag key / value has been entered by the user before.
+     * A lower number means this happened more recently and beats a higher number in priority.
+     * @return a number when the tag key / value has been entered by the user before.
+     *         {@code null}, if the user hasn't entered this tag so far.
+     */
+    public Integer getUserInput() {
+        return userInput == NO_USER_INPUT ? null : userInput;
+    }
+
+    /**
+     * Imposes an ordering on the priorities.
+     * Currently, being in the current DataSet is worth more than being in the Presets.
+     */
+    @Override
+    public int compareTo(AutoCompletionPriority other) {
+        int ui = Integer.compare(other.userInput, userInput);
+        if (ui != 0)
+            return ui;
+
+        int sel = Boolean.compare(selected, other.selected);
+        if (sel != 0)
+            return sel;
+
+        int ds = Boolean.compare(inDataSet, other.inDataSet);
+        if (ds != 0)
+            return ds;
+
+        int std = Boolean.compare(inStandard, other.inStandard);
+        if (std != 0)
+            return std;
+
+        return 0;
+    }
+
+    /**
+     * Merges two priorities.
+     * The resulting priority is always &gt;= the original ones.
+     * @param other other priority
+     * @return the merged priority
+     */
+    public AutoCompletionPriority mergeWith(AutoCompletionPriority other) {
+        return new AutoCompletionPriority(
+                inDataSet || other.inDataSet,
+                inStandard || other.inStandard,
+                selected || other.selected,
+                Math.min(userInput, other.userInput));
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(inDataSet, inStandard, selected, userInput);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj)
+            return true;
+        if (obj == null || getClass() != obj.getClass())
+            return false;
+        AutoCompletionPriority other = (AutoCompletionPriority) obj;
+        return inDataSet == other.inDataSet &&
+               inStandard == other.inStandard &&
+               selected == other.selected &&
+               userInput == other.userInput;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("<Priority; userInput: %s, inDataSet: %b, inStandard: %b, selected: %b>",
+                userInput == NO_USER_INPUT ? "no" : Integer.toString(userInput), inDataSet, inStandard, selected);
+    }
+}
Index: trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionSet.java	(revision 12859)
+++ trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionSet.java	(revision 12859)
@@ -0,0 +1,86 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.tagging.ac;
+
+import java.util.Collection;
+import java.util.Optional;
+import java.util.TreeSet;
+import java.util.stream.Collectors;
+
+/**
+ * A sorted set of {@link AutoCompletionItem}s.
+ *
+ * Items are sorted with higher priority first, then according to lexicographic order
+ * on the value of the {@code AutoCompletionListItem}.
+ *
+ * @since 12859 (extracted from {@code gui.tagging.ac.AutoCompletionList})
+ */
+public class AutoCompletionSet extends TreeSet<AutoCompletionItem> {
+
+    @Override
+    public boolean add(AutoCompletionItem e) {
+        // Is there already an item for the value?
+        Optional<AutoCompletionItem> result = stream().filter(i -> i.getValue().equals(e.getValue())).findFirst();
+        if (result.isPresent()) {
+            AutoCompletionItem item = result.get();
+            // yes: merge priorities
+            AutoCompletionPriority newPriority = item.getPriority().mergeWith(e.getPriority());
+            // if needed, remove/re-add the updated item to maintain set ordering
+            if (!item.getPriority().equals(newPriority)) {
+                remove(item);
+                item.setPriority(newPriority);
+                return add(item);
+            } else {
+                return false;
+            }
+        } else {
+            return super.add(e);
+        }
+    }
+
+    /**
+     * Adds a list of strings to this list. Only strings which
+     * are not null and which do not exist yet in the list are added.
+     *
+     * @param values a list of strings to add
+     * @param priority the priority to use
+     * @return {@code true} if this set changed as a result of the call
+     */
+    public boolean addAll(Collection<String> values, AutoCompletionPriority priority) {
+        return addAll(values.stream().filter(v -> v != null).map(v -> new AutoCompletionItem(v, priority)).collect(Collectors.toList()));
+    }
+
+    /**
+     * Adds values that have been entered by the user.
+     * @param values values that have been entered by the user
+     * @return {@code true} if this set changed as a result of the call
+     */
+    public boolean addUserInput(Collection<String> values) {
+        int i = 0;
+        boolean modified = false;
+        for (String value : values) {
+            if (value != null && add(new AutoCompletionItem(value, new AutoCompletionPriority(false, false, false, i++)))) {
+                modified = true;
+            }
+        }
+        return modified;
+    }
+
+    /**
+     * Checks whether an item with the given value is already in the list. Ignores priority of the items.
+     *
+     * @param value the value of an auto completion item
+     * @return true, if value is in the list; false, otherwise
+     */
+    public boolean contains(String value) {
+        return stream().anyMatch(i -> i.getValue().equals(value));
+    }
+
+    /**
+     * Removes the auto completion item with key <code>key</code>
+     * @param key the key
+     * @return {@code true} if an element was removed
+     */
+    public boolean remove(String key) {
+        return removeIf(i -> i.getValue().equals(key));
+    }
+}
Index: trunk/src/org/openstreetmap/josm/data/tagging/ac/package-info.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/tagging/ac/package-info.java	(revision 12859)
+++ trunk/src/org/openstreetmap/josm/data/tagging/ac/package-info.java	(revision 12859)
@@ -0,0 +1,6 @@
+// License: GPL. For details, see LICENSE file.
+
+/**
+ * Provides classes for handling autocompletion of tags.
+ */
+package org.openstreetmap.josm.data.tagging.ac;
Index: trunk/src/org/openstreetmap/josm/gui/dialogs/properties/TagEditHelper.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/dialogs/properties/TagEditHelper.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/dialogs/properties/TagEditHelper.java	(revision 12859)
@@ -77,4 +77,5 @@
 import org.openstreetmap.josm.data.preferences.ListProperty;
 import org.openstreetmap.josm.data.preferences.StringProperty;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
 import org.openstreetmap.josm.gui.ExtendedDialog;
 import org.openstreetmap.josm.gui.IExtendedDialog;
@@ -83,5 +84,4 @@
 import org.openstreetmap.josm.gui.mappaint.MapPaintStyles;
 import org.openstreetmap.josm.gui.tagging.ac.AutoCompletingComboBox;
-import org.openstreetmap.josm.gui.tagging.ac.AutoCompletionListItem;
 import org.openstreetmap.josm.gui.tagging.ac.AutoCompletionManager;
 import org.openstreetmap.josm.gui.tagging.presets.TaggingPreset;
@@ -112,5 +112,5 @@
     private String objKey;
 
-    static final Comparator<AutoCompletionListItem> DEFAULT_AC_ITEM_COMPARATOR =
+    static final Comparator<AutoCompletionItem> DEFAULT_AC_ITEM_COMPARATOR =
             (o1, o2) -> String.CASE_INSENSITIVE_ORDER.compare(o1.getValue(), o2.getValue());
 
@@ -393,11 +393,11 @@
         private final String key;
         private final transient Map<String, Integer> m;
-        private final transient Comparator<AutoCompletionListItem> usedValuesAwareComparator;
-
-        private final transient ListCellRenderer<AutoCompletionListItem> cellRenderer = new ListCellRenderer<AutoCompletionListItem>() {
+        private final transient Comparator<AutoCompletionItem> usedValuesAwareComparator;
+
+        private final transient ListCellRenderer<AutoCompletionItem> cellRenderer = new ListCellRenderer<AutoCompletionItem>() {
             private final DefaultListCellRenderer def = new DefaultListCellRenderer();
             @Override
-            public Component getListCellRendererComponent(JList<? extends AutoCompletionListItem> list,
-                    AutoCompletionListItem value, int index, boolean isSelected, boolean cellHasFocus) {
+            public Component getListCellRendererComponent(JList<? extends AutoCompletionItem> list,
+                    AutoCompletionItem value, int index, boolean isSelected, boolean cellHasFocus) {
                 Component c = def.getListCellRendererComponent(list, value, index, isSelected, cellHasFocus);
                 if (c instanceof JLabel) {
@@ -447,9 +447,8 @@
 
             AutoCompletionManager autocomplete = AutoCompletionManager.of(MainApplication.getLayerManager().getEditLayer().data);
-            List<AutoCompletionListItem> keyList = autocomplete.getKeys();
-            keyList.sort(DEFAULT_AC_ITEM_COMPARATOR);
+            List<AutoCompletionItem> keyList = autocomplete.getTagKeys(DEFAULT_AC_ITEM_COMPARATOR);
 
             keys = new AutoCompletingComboBox(key);
-            keys.setPossibleACItems(keyList);
+            keys.setPossibleAcItems(keyList);
             keys.setEditable(true);
             keys.setSelectedItem(key);
@@ -460,6 +459,5 @@
             p.add(keys, GBC.eol().fill(GBC.HORIZONTAL));
 
-            List<AutoCompletionListItem> valueList = autocomplete.getValues(getAutocompletionKeys(key));
-            valueList.sort(usedValuesAwareComparator);
+            List<AutoCompletionItem> valueList = autocomplete.getTagValues(getAutocompletionKeys(key), usedValuesAwareComparator);
 
             final String selection = m.size() != 1 ? tr("<different>") : m.entrySet().iterator().next().getKey();
@@ -469,5 +467,5 @@
 
             values.setEditable(true);
-            values.setPossibleACItems(valueList);
+            values.setPossibleAcItems(valueList);
             values.setSelectedItem(selection);
             values.getEditor().setItem(selection);
@@ -630,5 +628,5 @@
         * @return The created adapter
         */
-        protected FocusAdapter addFocusAdapter(final AutoCompletionManager autocomplete, final Comparator<AutoCompletionListItem> comparator) {
+        protected FocusAdapter addFocusAdapter(final AutoCompletionManager autocomplete, final Comparator<AutoCompletionItem> comparator) {
            // get the combo box' editor component
            final JTextComponent editor = values.getEditorComponent();
@@ -639,8 +637,7 @@
                    String key = keys.getEditor().getItem().toString();
 
-                   List<AutoCompletionListItem> valueList = autocomplete.getValues(getAutocompletionKeys(key));
-                   valueList.sort(comparator);
+                   List<AutoCompletionItem> valueList = autocomplete.getTagValues(getAutocompletionKeys(key), comparator);
                    Logging.trace("Focus gained by {0}, e={1}", values, e);
-                   values.setPossibleACItems(valueList);
+                   values.setPossibleAcItems(valueList);
                    values.getEditor().selectAll();
                    objKey = key;
@@ -692,12 +689,11 @@
 
             cacheRecentTags();
-            AutoCompletionManager autocomplete = AutoCompletionManager.of(MainApplication.getLayerManager().getEditLayer().data);
-            List<AutoCompletionListItem> keyList = autocomplete.getKeys();
+            AutoCompletionManager autocomplete = AutoCompletionManager.of(Main.main.getEditDataSet());
+            List<AutoCompletionItem> keyList = autocomplete.getTagKeys(DEFAULT_AC_ITEM_COMPARATOR);
 
             // remove the object's tag keys from the list
             keyList.removeIf(item -> containsDataKey(item.getValue()));
 
-            keyList.sort(DEFAULT_AC_ITEM_COMPARATOR);
-            keys.setPossibleACItems(keyList);
+            keys.setPossibleAcItems(keyList);
             keys.setEditable(true);
 
Index: trunk/src/org/openstreetmap/josm/gui/preferences/projection/CustomProjectionChoice.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/preferences/projection/CustomProjectionChoice.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/preferences/projection/CustomProjectionChoice.java	(revision 12859)
@@ -24,6 +24,6 @@
 import org.openstreetmap.josm.data.projection.ProjectionConfigurationException;
 import org.openstreetmap.josm.data.projection.Projections;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
 import org.openstreetmap.josm.gui.ExtendedDialog;
-import org.openstreetmap.josm.gui.tagging.ac.AutoCompletionListItem;
 import org.openstreetmap.josm.gui.widgets.AbstractTextComponentValidator;
 import org.openstreetmap.josm.gui.widgets.HistoryComboBox;
@@ -65,5 +65,5 @@
             input = new JosmTextField(30);
             cbInput = new HistoryComboBox();
-            cbInput.setPrototypeDisplayValue(new AutoCompletionListItem("xxxx"));
+            cbInput.setPrototypeDisplayValue(new AutoCompletionItem("xxxx"));
             cbInput.setEditor(new BasicComboBoxEditor() {
                 @Override
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletingComboBox.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletingComboBox.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletingComboBox.java	(revision 12859)
@@ -10,4 +10,5 @@
 import java.util.Collection;
 import java.util.Locale;
+import java.util.stream.Collectors;
 
 import javax.swing.ComboBoxEditor;
@@ -23,4 +24,6 @@
 import javax.swing.text.StyleConstants;
 
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionPriority;
 import org.openstreetmap.josm.gui.MainApplication;
 import org.openstreetmap.josm.gui.MapFrame;
@@ -35,5 +38,5 @@
  * @since 272
  */
-public class AutoCompletingComboBox extends JosmComboBox<AutoCompletionListItem> {
+public class AutoCompletingComboBox extends JosmComboBox<AutoCompletionItem> {
 
     private boolean autocompleteEnabled = true;
@@ -85,5 +88,5 @@
      */
     class AutoCompletingComboBoxDocument extends PlainDocument {
-        private final JosmComboBox<AutoCompletionListItem> comboBox;
+        private final JosmComboBox<AutoCompletionItem> comboBox;
         private boolean selecting;
 
@@ -92,5 +95,5 @@
          * @param comboBox the combobox
          */
-        AutoCompletingComboBoxDocument(final JosmComboBox<AutoCompletionListItem> comboBox) {
+        AutoCompletingComboBoxDocument(final JosmComboBox<AutoCompletionItem> comboBox) {
             this.comboBox = comboBox;
         }
@@ -159,5 +162,5 @@
             }
             if (item != null) {
-                String newText = ((AutoCompletionListItem) item).getValue();
+                String newText = ((AutoCompletionItem) item).getValue();
                 if (!newText.equals(curText)) {
                     selecting = true;
@@ -190,8 +193,8 @@
 
         private Object lookupItem(String pattern, boolean match) {
-            ComboBoxModel<AutoCompletionListItem> model = comboBox.getModel();
-            AutoCompletionListItem bestItem = null;
+            ComboBoxModel<AutoCompletionItem> model = comboBox.getModel();
+            AutoCompletionItem bestItem = null;
             for (int i = 0, n = model.getSize(); i < n; i++) {
-                AutoCompletionListItem currentItem = model.getElementAt(i);
+                AutoCompletionItem currentItem = model.getElementAt(i);
                 if (currentItem.getValue().equals(pattern))
                     return currentItem;
@@ -219,5 +222,5 @@
      */
     public AutoCompletingComboBox(String prototype) {
-        super(new AutoCompletionListItem(prototype));
+        super(new AutoCompletionItem(prototype));
         setRenderer(new AutoCompleteListCellRenderer());
         final JTextComponent editorComponent = this.getEditorComponent();
@@ -241,4 +244,5 @@
      */
     @Override
+    @SuppressWarnings("deprecation")
     public void configureEditor(ComboBoxEditor cbEditor, Object item) {
         if (item == null) {
@@ -246,6 +250,8 @@
         } else if (item instanceof String) {
             cbEditor.setItem(item);
+        } else if (item instanceof AutoCompletionItem) {
+            cbEditor.setItem(((AutoCompletionItem) item).getValue());
         } else if (item instanceof AutoCompletionListItem) {
-            cbEditor.setItem(((AutoCompletionListItem) item).getValue());
+            cbEditor.setItem(((AutoCompletionListItem) item).getItem().getValue());
         } else
             throw new IllegalArgumentException("Unsupported item: "+item);
@@ -254,17 +260,20 @@
     /**
      * Selects a given item in the ComboBox model
-     * @param item      excepts AutoCompletionListItem, String and null
+     * @param item      excepts AutoCompletionItem, String and null
      */
     @Override
+    @SuppressWarnings("deprecation")
     public void setSelectedItem(Object item) {
         if (item == null) {
             super.setSelectedItem(null);
+        } else if (item instanceof AutoCompletionItem) {
+            super.setSelectedItem(item);
         } else if (item instanceof AutoCompletionListItem) {
-            super.setSelectedItem(item);
+            super.setSelectedItem(((AutoCompletionListItem) item).getItem());
         } else if (item instanceof String) {
             String s = (String) item;
             // find the string in the model or create a new item
             for (int i = 0; i < getModel().getSize(); i++) {
-                AutoCompletionListItem acItem = getModel().getElementAt(i);
+                AutoCompletionItem acItem = getModel().getElementAt(i);
                 if (s.equals(acItem.getValue())) {
                     super.setSelectedItem(acItem);
@@ -272,5 +281,5 @@
                 }
             }
-            super.setSelectedItem(new AutoCompletionListItem(s, AutoCompletionItemPriority.UNKNOWN));
+            super.setSelectedItem(new AutoCompletionItem(s, AutoCompletionPriority.UNKNOWN));
         } else {
             throw new IllegalArgumentException("Unsupported item: "+item);
@@ -283,9 +292,9 @@
      */
     public void setPossibleItems(Collection<String> elems) {
-        DefaultComboBoxModel<AutoCompletionListItem> model = (DefaultComboBoxModel<AutoCompletionListItem>) this.getModel();
+        DefaultComboBoxModel<AutoCompletionItem> model = (DefaultComboBoxModel<AutoCompletionItem>) this.getModel();
         Object oldValue = this.getEditor().getItem(); // Do not use getSelectedItem(); (fix #8013)
         model.removeAllElements();
         for (String elem : elems) {
-            model.addElement(new AutoCompletionListItem(elem, AutoCompletionItemPriority.UNKNOWN));
+            model.addElement(new AutoCompletionItem(elem, AutoCompletionPriority.UNKNOWN));
         }
         // disable autocomplete to prevent unnecessary actions in AutoCompletingComboBoxDocument#insertString
@@ -298,11 +307,22 @@
      * Sets the items of the combobox to the given {@code AutoCompletionListItem}s.
      * @param elems AutoCompletionListItem items
-     */
+     * @deprecated to be removed end of 2017. Use {@link #setPossibleAcItems(Collection)} instead
+     */
+    @Deprecated
     public void setPossibleACItems(Collection<AutoCompletionListItem> elems) {
-        DefaultComboBoxModel<AutoCompletionListItem> model = (DefaultComboBoxModel<AutoCompletionListItem>) this.getModel();
+        setPossibleAcItems(elems.stream().map(AutoCompletionListItem::getItem).collect(Collectors.toList()));
+    }
+
+    /**
+     * Sets the items of the combobox to the given {@code AutoCompletionItem}s.
+     * @param elems AutoCompletionItem items
+     * @since 12859
+     */
+    public void setPossibleAcItems(Collection<AutoCompletionItem> elems) {
+        DefaultComboBoxModel<AutoCompletionItem> model = (DefaultComboBoxModel<AutoCompletionItem>) this.getModel();
         Object oldValue = getSelectedItem();
         Object editorOldValue = this.getEditor().getItem();
         model.removeAllElements();
-        for (AutoCompletionListItem elem : elems) {
+        for (AutoCompletionItem elem : elems) {
             model.addElement(elem);
         }
@@ -359,5 +379,5 @@
      * renders an AutoCompletionListItem by showing only the string value part
      */
-    public static class AutoCompleteListCellRenderer extends JLabel implements ListCellRenderer<AutoCompletionListItem> {
+    public static class AutoCompleteListCellRenderer extends JLabel implements ListCellRenderer<AutoCompletionItem> {
 
         /**
@@ -370,6 +390,6 @@
         @Override
         public Component getListCellRendererComponent(
-                JList<? extends AutoCompletionListItem> list,
-                AutoCompletionListItem item,
+                JList<? extends AutoCompletionItem> list,
+                AutoCompletionItem item,
                 int index,
                 boolean isSelected,
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletingTextField.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletingTextField.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletingTextField.java	(revision 12859)
@@ -99,5 +99,5 @@
             if (autoCompletionList.getFilteredSize() > 0 && !Objects.equals(str, noAutoCompletionString)) {
                 // there are matches. Insert the new text and highlight the auto completed suffix
-                String matchingString = autoCompletionList.getFilteredItem(0).getValue();
+                String matchingString = autoCompletionList.getFilteredItemAt(0).getValue();
                 remove(0, getLength());
                 super.insertString(0, matchingString, a);
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionItemPriority.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionItemPriority.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionItemPriority.java	(revision 12859)
@@ -1,4 +1,6 @@
 // License: GPL. For details, see LICENSE file.
 package org.openstreetmap.josm.gui.tagging.ac;
+
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionPriority;
 
 /**
@@ -8,5 +10,7 @@
  * Instances of this class are not modifiable.
  * @since 1762
+ * @deprecated to be removed end of 2017. Use {@link AutoCompletionPriority} instead
  */
+@Deprecated
 public class AutoCompletionItemPriority implements Comparable<AutoCompletionItemPriority> {
 
@@ -16,5 +20,6 @@
      * usually not used by the user.
      */
-    public static final AutoCompletionItemPriority IS_IN_STANDARD_AND_IN_DATASET = new AutoCompletionItemPriority(true, true, false);
+    public static final AutoCompletionItemPriority IS_IN_STANDARD_AND_IN_DATASET = new AutoCompletionItemPriority(
+            AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET);
 
     /**
@@ -22,5 +27,5 @@
      * the value of a tag name=*.
      */
-    public static final AutoCompletionItemPriority IS_IN_DATASET = new AutoCompletionItemPriority(true, false, false);
+    public static final AutoCompletionItemPriority IS_IN_DATASET = new AutoCompletionItemPriority(AutoCompletionPriority.IS_IN_DATASET);
 
     /**
@@ -28,20 +33,17 @@
      * or a standard value for a given tag name (from the presets).
      */
-    public static final AutoCompletionItemPriority IS_IN_STANDARD = new AutoCompletionItemPriority(false, true, false);
+    public static final AutoCompletionItemPriority IS_IN_STANDARD = new AutoCompletionItemPriority(AutoCompletionPriority.IS_IN_STANDARD);
 
     /**
      * Indicates that this is a value from a selected object.
      */
-    public static final AutoCompletionItemPriority IS_IN_SELECTION = new AutoCompletionItemPriority(false, false, true);
+    public static final AutoCompletionItemPriority IS_IN_SELECTION = new AutoCompletionItemPriority(AutoCompletionPriority.IS_IN_SELECTION);
 
     /** Unknown priority. This is the lowest priority. */
-    public static final AutoCompletionItemPriority UNKNOWN = new AutoCompletionItemPriority(false, false, false);
+    public static final AutoCompletionItemPriority UNKNOWN = new AutoCompletionItemPriority(AutoCompletionPriority.UNKNOWN);
 
     private static final int NO_USER_INPUT = Integer.MAX_VALUE;
 
-    private final int userInput;
-    private final boolean inDataSet;
-    private final boolean inStandard;
-    private final boolean selected;
+    private final AutoCompletionPriority priority;
 
     /**
@@ -56,8 +58,5 @@
      */
     public AutoCompletionItemPriority(boolean inDataSet, boolean inStandard, boolean selected, Integer userInput) {
-        this.inDataSet = inDataSet;
-        this.inStandard = inStandard;
-        this.selected = selected;
-        this.userInput = userInput == null ? NO_USER_INPUT : userInput;
+        this(new AutoCompletionPriority(inDataSet, inStandard, selected, userInput));
     }
 
@@ -74,9 +73,18 @@
 
     /**
+     * Constructs a new {@code AutoCompletionItemPriority} from an existing {@link AutoCompletionPriority}.
+     * @param other {@code AutoCompletionPriority} to convert
+     * @since 12859
+     */
+    public AutoCompletionItemPriority(AutoCompletionPriority other) {
+        this.priority = other;
+    }
+
+    /**
      * Determines if the item is found in the currently active data layer.
      * @return {@code true} if the item is found in the currently active data layer
      */
     public boolean isInDataSet() {
-        return inDataSet;
+        return priority.isInDataSet();
     }
 
@@ -86,5 +94,5 @@
      */
     public boolean isInStandard() {
-        return inStandard;
+        return priority.isInStandard();
     }
 
@@ -94,5 +102,5 @@
      */
     public boolean isSelected() {
-        return selected;
+        return priority.isSelected();
     }
 
@@ -104,5 +112,5 @@
      */
     public Integer getUserInput() {
-        return userInput == NO_USER_INPUT ? null : userInput;
+        return priority.getUserInput();
     }
 
@@ -113,21 +121,5 @@
     @Override
     public int compareTo(AutoCompletionItemPriority other) {
-        int ui = Integer.compare(other.userInput, userInput);
-        if (ui != 0)
-            return ui;
-
-        int sel = Boolean.compare(selected, other.selected);
-        if (sel != 0)
-            return sel;
-
-        int ds = Boolean.compare(inDataSet, other.inDataSet);
-        if (ds != 0)
-            return ds;
-
-        int std = Boolean.compare(inStandard, other.inStandard);
-        if (std != 0)
-            return std;
-
-        return 0;
+        return priority.compareTo(other.priority);
     }
 
@@ -139,15 +131,19 @@
      */
     public AutoCompletionItemPriority mergeWith(AutoCompletionItemPriority other) {
-        return new AutoCompletionItemPriority(
-                inDataSet || other.inDataSet,
-                inStandard || other.inStandard,
-                selected || other.selected,
-                Math.min(userInput, other.userInput));
+        return new AutoCompletionItemPriority(priority.mergeWith(other.priority));
     }
 
     @Override
     public String toString() {
-        return String.format("<Priority; userInput: %s, inDataSet: %b, inStandard: %b, selected: %b>",
-                userInput == NO_USER_INPUT ? "no" : Integer.toString(userInput), inDataSet, inStandard, selected);
+        return priority.toString();
+    }
+
+    /**
+     * Returns the underlying priority.
+     * @return the underlying priority
+     * @since 12859
+     */
+    public AutoCompletionPriority getPriority() {
+        return priority;
     }
 }
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionList.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionList.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionList.java	(revision 12859)
@@ -5,20 +5,23 @@
 import java.util.Collection;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.List;
-import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
 
 import javax.swing.JTable;
 import javax.swing.table.AbstractTableModel;
 
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionPriority;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionSet;
 import org.openstreetmap.josm.tools.CheckParameterUtil;
 
 /**
- * AutoCompletionList manages a list of {@link AutoCompletionListItem}s.
+ * AutoCompletionList manages a graphical list of {@link AutoCompletionItem}s.
  *
  * The list is sorted, items with higher priority first, then according to lexicographic order
- * on the value of the {@link AutoCompletionListItem}.
+ * on the value of the {@link AutoCompletionItem}.
  *
- * AutoCompletionList maintains two views on the list of {@link AutoCompletionListItem}s.
+ * AutoCompletionList maintains two views on the list of {@link AutoCompletionItem}s.
  * <ol>
  *   <li>the bare, unfiltered view which includes all items</li>
@@ -33,11 +36,9 @@
 
     /** the bare list of AutoCompletionItems */
-    private final transient List<AutoCompletionListItem> list;
+    private final transient AutoCompletionSet list;
     /**  the filtered list of AutoCompletionItems */
-    private final transient ArrayList<AutoCompletionListItem> filtered;
+    private final transient ArrayList<AutoCompletionItem> filtered;
     /** the filter expression */
     private String filter;
-    /** map from value to priority */
-    private final transient Map<String, AutoCompletionListItem> valutToItemMap;
 
     /**
@@ -45,7 +46,6 @@
      */
     public AutoCompletionList() {
-        list = new ArrayList<>();
+        list = new AutoCompletionSet();
         filtered = new ArrayList<>();
-        valutToItemMap = new HashMap<>();
     }
 
@@ -81,19 +81,32 @@
 
     /**
-     * adds an AutoCompletionListItem to the list. Only adds the item if it
+     * adds an {@link AutoCompletionListItem} to the list. Only adds the item if it
      * is not null and if not in the list yet.
      *
      * @param item the item
-     */
+     * @deprecated To be removed end of 2017. Use {@link #add(AutoCompletionItem)} instead
+     */
+    @Deprecated
     public void add(AutoCompletionListItem item) {
         if (item == null)
             return;
-        appendOrUpdatePriority(item);
-        sort();
-        filter();
-    }
-
-    /**
-     * adds another AutoCompletionList to this list. An item is only
+        add(item.getItem());
+    }
+
+    /**
+     * adds an {@link AutoCompletionItem} to the list. Only adds the item if it
+     * is not null and if not in the list yet.
+     *
+     * @param item the item
+     * @since 12859
+     */
+    public void add(AutoCompletionItem item) {
+        if (item != null && list.add(item)) {
+            filter();
+        }
+    }
+
+    /**
+     * adds another {@link AutoCompletionList} to this list. An item is only
      * added it is not null and if it does not exist in the list yet.
      *
@@ -103,25 +116,34 @@
     public void add(AutoCompletionList other) {
         CheckParameterUtil.ensureParameterNotNull(other, "other");
-        for (AutoCompletionListItem item : other.list) {
-            appendOrUpdatePriority(item);
-        }
-        sort();
-        filter();
-    }
-
-    /**
-     * adds a list of AutoCompletionListItem to this list. Only items which
+        add(other.list);
+    }
+
+    /**
+     * adds a colleciton of {@link AutoCompletionItem} to this list. An item is only
+     * added it is not null and if it does not exist in the list yet.
+     *
+     * @param collection auto completion collection; must not be null
+     * @throws IllegalArgumentException if other is null
+     * @since 12859
+     */
+    public void add(Collection<AutoCompletionItem> collection) {
+        CheckParameterUtil.ensureParameterNotNull(collection, "collection");
+        if (list.addAll(collection)) {
+            filter();
+        }
+    }
+
+    /**
+     * adds a list of {@link AutoCompletionListItem} to this list. Only items which
      * are not null and which do not exist yet in the list are added.
      *
      * @param other a list of AutoCompletionListItem; must not be null
      * @throws IllegalArgumentException if other is null
-     */
+     * @deprecated to be removed end of 2017. Use {@link #add(Collection)} instead
+     */
+    @Deprecated
     public void add(List<AutoCompletionListItem> other) {
         CheckParameterUtil.ensureParameterNotNull(other, "other");
-        for (AutoCompletionListItem toadd : other) {
-            appendOrUpdatePriority(toadd);
-        }
-        sort();
-        filter();
+        add(other.stream().map(AutoCompletionListItem::getItem).collect(Collectors.toList()));
     }
 
@@ -132,18 +154,23 @@
      * @param values a list of strings to add
      * @param priority the priority to use
-     */
+     * @deprecated to be removed end of 2017. Use {@link #add(Collection, AutoCompletionPriority)} instead
+     */
+    @Deprecated
     public void add(Collection<String> values, AutoCompletionItemPriority priority) {
-        if (values == null)
-            return;
-        for (String value : values) {
-            if (value == null) {
-                continue;
-            }
-            AutoCompletionListItem item = new AutoCompletionListItem(value, priority);
-            appendOrUpdatePriority(item);
-
-        }
-        sort();
-        filter();
+        add(values, priority.getPriority());
+    }
+
+    /**
+     * adds a list of strings to this list. Only strings which
+     * are not null and which do not exist yet in the list are added.
+     *
+     * @param values a list of strings to add
+     * @param priority the priority to use
+     * @since 12859
+     */
+    public void add(Collection<String> values, AutoCompletionPriority priority) {
+        if (values != null && list.addAll(values, priority)) {
+            filter();
+        }
     }
 
@@ -153,25 +180,6 @@
      */
     public void addUserInput(Collection<String> values) {
-        if (values == null)
-            return;
-        int i = 0;
-        for (String value : values) {
-            if (value != null) {
-                appendOrUpdatePriority(
-                        new AutoCompletionListItem(value, new AutoCompletionItemPriority(false, false, false, i++)));
-            }
-        }
-        sort();
-        filter();
-    }
-
-    protected void appendOrUpdatePriority(AutoCompletionListItem toAdd) {
-        AutoCompletionListItem item = valutToItemMap.get(toAdd.getValue());
-        if (item == null) {
-            // new item does not exist yet. Add it to the list
-            list.add(toAdd);
-            valutToItemMap.put(toAdd.getValue(), toAdd);
-        } else {
-            item.setPriority(item.getPriority().mergeWith(toAdd.getPriority()));
+        if (values != null && list.addUserInput(values)) {
+            filter();
         }
     }
@@ -183,8 +191,22 @@
      * @param item the item to check
      * @return true, if item is in the list; false, otherwise
-     */
+     * @deprecated to be removed end of 2017. Use {@link #contains(AutoCompletionItem)} instead
+     */
+    @Deprecated
     public boolean contains(AutoCompletionListItem item) {
         if (item == null)
             return false;
+        return contains(item.getItem());
+    }
+
+    /**
+     * checks whether a specific item is already in the list. Matches for the
+     * the value <strong>and</strong> the priority of the item
+     *
+     * @param item the item to check
+     * @return true, if item is in the list; false, otherwise
+     * @since 12859
+     */
+    public boolean contains(AutoCompletionItem item) {
         return list.contains(item);
     }
@@ -198,34 +220,15 @@
      */
     public boolean contains(String value) {
-        if (value == null)
-            return false;
-        for (AutoCompletionListItem item: list) {
-            if (item.getValue().equals(value))
-                return true;
-        }
-        return false;
+        return list.contains(value);
     }
 
     /**
      * removes the auto completion item with key <code>key</code>
-     * @param key  the key;
+     * @param key the key
      */
     public void remove(String key) {
-        if (key == null)
-            return;
-        for (int i = 0; i < list.size(); i++) {
-            AutoCompletionListItem item = list.get(i);
-            if (item.getValue().equals(key)) {
-                list.remove(i);
-                return;
-            }
-        }
-    }
-
-    /**
-     * sorts the list
-     */
-    protected void sort() {
-        Collections.sort(list);
+        if (key != null) {
+            list.remove(key);
+        }
     }
 
@@ -235,7 +238,5 @@
             // Collections.copy throws an exception "Source does not fit in dest"
             filtered.ensureCapacity(list.size());
-            for (AutoCompletionListItem item: list) {
-                filtered.add(item);
-            }
+            filtered.addAll(list);
             return;
         }
@@ -244,9 +245,5 @@
         // value to the list of filtered values
         //
-        for (AutoCompletionListItem item : list) {
-            if (item.getValue().startsWith(filter)) {
-                filtered.add(item);
-            }
-        }
+        list.stream().filter(e -> e.getValue().startsWith(filter)).forEach(filtered::add);
         fireTableDataChanged();
     }
@@ -258,5 +255,5 @@
      */
     public int getFilteredSize() {
-        return this.filtered.size();
+        return filtered.size();
     }
 
@@ -267,25 +264,35 @@
      *
      * @throws IndexOutOfBoundsException if idx is out of bounds
-     */
+     * @deprecated to be removed end of 2017. Use {@link #getFilteredItemAt(int)} instead
+     */
+    @Deprecated
     public AutoCompletionListItem getFilteredItem(int idx) {
-        if (idx < 0 || idx >= getFilteredSize())
-            throw new IndexOutOfBoundsException("idx out of bounds. idx=" + idx);
+        return new AutoCompletionListItem(getFilteredItemAt(idx));
+    }
+
+    /**
+     * replies the idx-th item from the list of filtered items
+     * @param idx the index; must be in the range 0 &lt;= idx &lt; {@link #getFilteredSize()}
+     * @return the item
+     *
+     * @throws IndexOutOfBoundsException if idx is out of bounds
+     * @since 12859
+     */
+    public AutoCompletionItem getFilteredItemAt(int idx) {
         return filtered.get(idx);
     }
 
-    List<AutoCompletionListItem> getList() {
+    AutoCompletionSet getSet() {
         return list;
     }
 
-    List<AutoCompletionListItem> getUnmodifiableList() {
-        return Collections.unmodifiableList(list);
+    Set<AutoCompletionItem> getUnmodifiableSet() {
+        return Collections.unmodifiableSet(list);
     }
 
     /**
      * removes all elements from the auto completion list
-     *
      */
     public void clear() {
-        valutToItemMap.clear();
         list.clear();
         fireTableDataChanged();
@@ -299,5 +306,4 @@
     @Override
     public int getRowCount() {
-
         return list == null ? 0 : getFilteredSize();
     }
@@ -305,5 +311,5 @@
     @Override
     public Object getValueAt(int rowIndex, int columnIndex) {
-        return list == null ? null : getFilteredItem(rowIndex);
+        return list == null ? null : getFilteredItemAt(rowIndex);
     }
 }
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionListItem.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionListItem.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionListItem.java	(revision 12859)
@@ -2,5 +2,5 @@
 package org.openstreetmap.josm.gui.tagging.ac;
 
-import org.openstreetmap.josm.tools.CheckParameterUtil;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
 
 /**
@@ -15,12 +15,11 @@
  *
  * The value is a string which will be displayed in the auto completion list.
- *
+ * @deprecated To be removed end of 2017. Use {@link AutoCompletionItem} instead
  */
+@Deprecated
 public class AutoCompletionListItem implements Comparable<AutoCompletionListItem> {
 
-    /** the pritority of this item */
-    private AutoCompletionItemPriority priority;
-    /** the value of this item */
-    private String value;
+    /** the item */
+    private final AutoCompletionItem item;
 
     /**
@@ -30,6 +29,5 @@
      */
     public AutoCompletionListItem(String value, AutoCompletionItemPriority priority) {
-        this.value = value;
-        this.priority = priority;
+        this.item = new AutoCompletionItem(value, priority.getPriority());
     }
 
@@ -39,6 +37,5 @@
      */
     public AutoCompletionListItem(String value) {
-        this.value = value;
-        priority = AutoCompletionItemPriority.UNKNOWN;
+        this.item = new AutoCompletionItem(value);
     }
 
@@ -47,6 +44,14 @@
      */
     public AutoCompletionListItem() {
-        value = "";
-        priority = AutoCompletionItemPriority.UNKNOWN;
+        this.item = new AutoCompletionItem();
+    }
+
+    /**
+     * Constructs a new {@code AutoCompletionListItem} from an existing {@link AutoCompletionItem}.
+     * @param other {@code AutoCompletionItem} to convert
+     * @since 12859
+     */
+    public AutoCompletionListItem(AutoCompletionItem other) {
+        this.item = other;
     }
 
@@ -56,5 +61,5 @@
      */
     public AutoCompletionItemPriority getPriority() {
-        return priority;
+        return new AutoCompletionItemPriority(item.getPriority());
     }
 
@@ -64,5 +69,5 @@
      */
     public void setPriority(AutoCompletionItemPriority priority) {
-        this.priority = priority;
+        item.setPriority(priority.getPriority());
     }
 
@@ -72,5 +77,5 @@
      */
     public String getValue() {
-        return value;
+        return item.getValue();
     }
 
@@ -81,27 +86,15 @@
      */
     public void setValue(String value) {
-        CheckParameterUtil.ensureParameterNotNull(value, "value");
-        this.value = value;
+        item.setValue(value);
     }
 
     @Override
     public String toString() {
-        StringBuilder sb = new StringBuilder();
-        sb.append("<val='")
-          .append(value)
-          .append("',")
-          .append(priority)
-          .append('>');
-        return sb.toString();
+        return item.toString();
     }
 
     @Override
     public int hashCode() {
-        final int prime = 31;
-        int result = 1;
-        result = prime * result
-                + ((priority == null) ? 0 : priority.hashCode());
-        result = prime * result + ((value == null) ? 0 : value.hashCode());
-        return result;
+        return item.hashCode();
     }
 
@@ -113,28 +106,23 @@
             return false;
         if (obj instanceof String)
-            return obj.equals(value);
+            return obj.equals(item.getValue());
         if (getClass() != obj.getClass())
             return false;
         final AutoCompletionListItem other = (AutoCompletionListItem) obj;
-        if (priority == null) {
-            if (other.priority != null)
-                return false;
-        } else if (!priority.equals(other.priority))
-            return false;
-        if (value == null) {
-            if (other.value != null)
-                return false;
-        } else if (!value.equals(other.value))
-            return false;
-        return true;
+        return item.equals(other.item);
     }
 
     @Override
     public int compareTo(AutoCompletionListItem other) {
-        int ret = other.priority.compareTo(priority); // higher priority items come first in the list
-        if (ret != 0)
-            return ret;
-        else
-            return this.value.compareTo(other.value);
+        return item.compareTo(other.item);
+    }
+
+    /**
+     * Returns the underlying item.
+     * @return the underlying item
+     * @since 12859
+     */
+    public AutoCompletionItem getItem() {
+        return item;
     }
 }
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionManager.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionManager.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionManager.java	(revision 12859)
@@ -6,4 +6,5 @@
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -15,4 +16,5 @@
 import java.util.Set;
 import java.util.function.Function;
+import java.util.stream.Collectors;
 
 import org.openstreetmap.josm.data.osm.DataSet;
@@ -29,4 +31,7 @@
 import org.openstreetmap.josm.data.osm.event.TagsChangedEvent;
 import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionPriority;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionSet;
 import org.openstreetmap.josm.gui.MainApplication;
 import org.openstreetmap.josm.gui.layer.LayerManager.LayerAddEvent;
@@ -46,9 +51,8 @@
  * possible auto completion values for each key.
  *
- * Each DataSet is assigned one AutoCompletionManager instance such that
+ * Each DataSet can be assigned one AutoCompletionManager instance such that
  * <ol>
  *   <li>any key used in a tag in the data set is part of the key list in the cache</li>
- *   <li>any value used in a tag for a specific key is part of the autocompletion list of
- *     this key</li>
+ *   <li>any value used in a tag for a specific key is part of the autocompletion list of this key</li>
  * </ol>
  *
@@ -271,12 +275,11 @@
 
     /**
-     * Populates the {@link AutoCompletionList} with the currently cached
-     * member roles.
+     * Populates the {@link AutoCompletionList} with the currently cached member roles.
      *
      * @param list the list to populate
      */
     public void populateWithMemberRoles(AutoCompletionList list) {
-        list.add(TaggingPresets.getPresetRoles(), AutoCompletionItemPriority.IS_IN_STANDARD);
-        list.add(getRoleCache(), AutoCompletionItemPriority.IS_IN_DATASET);
+        list.add(TaggingPresets.getPresetRoles(), AutoCompletionPriority.IS_IN_STANDARD);
+        list.add(getRoleCache(), AutoCompletionPriority.IS_IN_DATASET);
     }
 
@@ -297,8 +300,8 @@
             for (TaggingPreset tp : presets) {
                 if (tp.roles != null) {
-                    list.add(Utils.transform(tp.roles.roles, (Function<Role, String>) x -> x.key), AutoCompletionItemPriority.IS_IN_STANDARD);
+                    list.add(Utils.transform(tp.roles.roles, (Function<Role, String>) x -> x.key), AutoCompletionPriority.IS_IN_STANDARD);
                 }
             }
-            list.add(r.getMemberRoles(), AutoCompletionItemPriority.IS_IN_DATASET);
+            list.add(r.getMemberRoles(), AutoCompletionPriority.IS_IN_DATASET);
         } else {
             populateWithMemberRoles(list);
@@ -312,13 +315,12 @@
      */
     public void populateWithKeys(AutoCompletionList list) {
-        list.add(TaggingPresets.getPresetKeys(), AutoCompletionItemPriority.IS_IN_STANDARD);
-        list.add(new AutoCompletionListItem("source", AutoCompletionItemPriority.IS_IN_STANDARD));
-        list.add(getDataKeys(), AutoCompletionItemPriority.IS_IN_DATASET);
+        list.add(TaggingPresets.getPresetKeys(), AutoCompletionPriority.IS_IN_STANDARD);
+        list.add(new AutoCompletionItem("source", AutoCompletionPriority.IS_IN_STANDARD));
+        list.add(getDataKeys(), AutoCompletionPriority.IS_IN_DATASET);
         list.addUserInput(getUserInputKeys());
     }
 
     /**
-     * Populates the an {@link AutoCompletionList} with the currently cached
-     * values for a tag
+     * Populates the an {@link AutoCompletionList} with the currently cached values for a tag
      *
      * @param list the list to populate
@@ -330,6 +332,5 @@
 
     /**
-     * Populates the an {@link AutoCompletionList} with the currently cached
-     * values for some given tags
+     * Populates the an {@link AutoCompletionList} with the currently cached values for some given tags
      *
      * @param list the list to populate
@@ -338,6 +339,6 @@
     public void populateWithTagValues(AutoCompletionList list, List<String> keys) {
         for (String key : keys) {
-            list.add(TaggingPresets.getPresetValues(key), AutoCompletionItemPriority.IS_IN_STANDARD);
-            list.add(getDataValues(key), AutoCompletionItemPriority.IS_IN_DATASET);
+            list.add(TaggingPresets.getPresetValues(key), AutoCompletionPriority.IS_IN_STANDARD);
+            list.add(getDataValues(key), AutoCompletionPriority.IS_IN_DATASET);
             list.addUserInput(getUserInputValues(key));
         }
@@ -347,9 +348,9 @@
      * Returns the currently cached tag keys.
      * @return a list of tag keys
-     */
+     * @deprecated to be removed end of 2017. Use {@link #getTagKeys()} instead
+     */
+    @Deprecated
     public List<AutoCompletionListItem> getKeys() {
-        AutoCompletionList list = new AutoCompletionList();
-        populateWithKeys(list);
-        return list.getList();
+        return getTagKeys().stream().map(AutoCompletionListItem::new).collect(Collectors.toList());
     }
 
@@ -358,7 +359,9 @@
      * @param key the tag key
      * @return a list of tag values
-     */
+     * @deprecated to be removed end of 2017. Use {@link #getTagValues(String)} instead
+     */
+    @Deprecated
     public List<AutoCompletionListItem> getValues(String key) {
-        return getValues(Arrays.asList(key));
+        return getTagValues(key).stream().map(AutoCompletionListItem::new).collect(Collectors.toList());
     }
 
@@ -367,15 +370,86 @@
      * @param keys the tag keys
      * @return a list of tag values
-     */
+     * @deprecated to be removed end of 2017. Use {@link #getTagValues(List)} instead
+     */
+    @Deprecated
     public List<AutoCompletionListItem> getValues(List<String> keys) {
+        return getTagValues(keys).stream().map(AutoCompletionListItem::new).collect(Collectors.toList());
+    }
+
+    private static List<AutoCompletionItem> setToList(AutoCompletionSet set, Comparator<AutoCompletionItem> comparator) {
+        List<AutoCompletionItem> list = set.stream().collect(Collectors.toList());
+        list.sort(comparator);
+        return list;
+    }
+
+    /**
+     * Returns the currently cached tag keys.
+     * @return a set of tag keys
+     * @since 12859
+     */
+    public AutoCompletionSet getTagKeys() {
+        AutoCompletionList list = new AutoCompletionList();
+        populateWithKeys(list);
+        return list.getSet();
+    }
+
+    /**
+     * Returns the currently cached tag keys.
+     * @param comparator the custom comparator used to sort the list
+     * @return a list of tag keys
+     * @since 12859
+     */
+    public List<AutoCompletionItem> getTagKeys(Comparator<AutoCompletionItem> comparator) {
+        return setToList(getTagKeys(), comparator);
+    }
+
+    /**
+     * Returns the currently cached tag values for a given tag key.
+     * @param key the tag key
+     * @return a set of tag values
+     * @since 12859
+     */
+    public AutoCompletionSet getTagValues(String key) {
+        return getTagValues(Arrays.asList(key));
+    }
+
+    /**
+     * Returns the currently cached tag values for a given tag key.
+     * @param key the tag key
+     * @param comparator the custom comparator used to sort the list
+     * @return a list of tag values
+     * @since 12859
+     */
+    public List<AutoCompletionItem> getTagValues(String key, Comparator<AutoCompletionItem> comparator) {
+        return setToList(getTagValues(key), comparator);
+    }
+
+    /**
+     * Returns the currently cached tag values for a given list of tag keys.
+     * @param keys the tag keys
+     * @return a set of tag values
+     * @since 12859
+     */
+    public AutoCompletionSet getTagValues(List<String> keys) {
         AutoCompletionList list = new AutoCompletionList();
         populateWithTagValues(list, keys);
-        return list.getList();
-    }
-
-    /*********************************************************
+        return list.getSet();
+    }
+
+    /**
+     * Returns the currently cached tag values for a given list of tag keys.
+     * @param keys the tag keys
+     * @param comparator the custom comparator used to sort the list
+     * @return a set of tag values
+     * @since 12859
+     */
+    public List<AutoCompletionItem> getTagValues(List<String> keys, Comparator<AutoCompletionItem> comparator) {
+        return setToList(getTagValues(keys), comparator);
+    }
+
+    /*
      * Implementation of the DataSetListener interface
      *
-     **/
+     */
 
     @Override
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/package-info.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/package-info.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/package-info.java	(revision 12859)
@@ -2,5 +2,5 @@
 
 /**
- * Provides classes for handling autocompletion of tags.
+ * Provides GUI classes for handling autocompletion of tags.
  */
 package org.openstreetmap.josm.gui.tagging.ac;
Index: trunk/src/org/openstreetmap/josm/gui/tagging/presets/items/Combo.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/presets/items/Combo.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/presets/items/Combo.java	(revision 12859)
@@ -4,6 +4,6 @@
 import javax.swing.JPanel;
 
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionPriority;
 import org.openstreetmap.josm.gui.tagging.ac.AutoCompletingTextField;
-import org.openstreetmap.josm.gui.tagging.ac.AutoCompletionItemPriority;
 import org.openstreetmap.josm.gui.tagging.ac.AutoCompletionList;
 import org.openstreetmap.josm.gui.widgets.JosmComboBox;
@@ -64,5 +64,5 @@
         AutoCompletionList acList = tf.getAutoCompletionList();
         if (acList != null) {
-            acList.add(getDisplayValues(), AutoCompletionItemPriority.IS_IN_STANDARD);
+            acList.add(getDisplayValues(), AutoCompletionPriority.IS_IN_STANDARD);
         }
         combobox.setEditor(tf);
Index: trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java	(revision 12858)
+++ trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java	(revision 12859)
@@ -9,10 +9,10 @@
 import javax.swing.DefaultComboBoxModel;
 
-import org.openstreetmap.josm.gui.tagging.ac.AutoCompletionListItem;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
 
 /**
  * A data model for {@link HistoryComboBox}
  */
-class ComboBoxHistory extends DefaultComboBoxModel<AutoCompletionListItem> implements Iterable<AutoCompletionListItem> {
+class ComboBoxHistory extends DefaultComboBoxModel<AutoCompletionItem> implements Iterable<AutoCompletionItem> {
 
     private final int maxSize;
@@ -31,5 +31,5 @@
      */
     public void addElement(String s) {
-        addElement(new AutoCompletionListItem(s));
+        addElement(new AutoCompletionItem(s));
     }
 
@@ -39,5 +39,5 @@
      */
     @Override
-    public void addElement(AutoCompletionListItem o) {
+    public void addElement(AutoCompletionItem o) {
         String newEntry = o.getValue();
 
@@ -64,6 +64,6 @@
 
     @Override
-    public Iterator<AutoCompletionListItem> iterator() {
-        return new Iterator<AutoCompletionListItem>() {
+    public Iterator<AutoCompletionItem> iterator() {
+        return new Iterator<AutoCompletionItem>() {
 
             private int position = -1;
@@ -80,5 +80,5 @@
 
             @Override
-            public AutoCompletionListItem next() {
+            public AutoCompletionItem next() {
                 if (!hasNext())
                     throw new NoSuchElementException();
@@ -102,10 +102,10 @@
 
     /**
-     * Returns the {@link AutoCompletionListItem} items as strings
+     * Returns the {@link AutoCompletionItem} items as strings
      * @return a list of strings
      */
     public List<String> asStringList() {
         List<String> list = new ArrayList<>(maxSize);
-        for (AutoCompletionListItem item : this) {
+        for (AutoCompletionItem item : this) {
             list.add(item.getValue());
         }
Index: trunk/test/unit/org/openstreetmap/josm/data/tagging/ac/AutoCompletionPriorityTest.java
===================================================================
--- trunk/test/unit/org/openstreetmap/josm/data/tagging/ac/AutoCompletionPriorityTest.java	(revision 12859)
+++ trunk/test/unit/org/openstreetmap/josm/data/tagging/ac/AutoCompletionPriorityTest.java	(revision 12859)
@@ -0,0 +1,127 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.tagging.ac;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.junit.Rule;
+import org.junit.Test;
+import org.openstreetmap.josm.testutils.JOSMTestRules;
+
+import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
+import nl.jqno.equalsverifier.EqualsVerifier;
+
+/**
+ * Unit tests of {@link AutoCompletionPriority}.
+ */
+public class AutoCompletionPriorityTest {
+
+    /**
+     * Setup test.
+     */
+    @Rule
+    @SuppressFBWarnings(value = "URF_UNREAD_PUBLIC_OR_PROTECTED_FIELD")
+    public JOSMTestRules test = new JOSMTestRules();
+
+    /**
+     * Test getters.
+     */
+    @Test
+    public void testGetters() {
+        assertTrue(AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET.isInStandard());
+        assertTrue(AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET.isInDataSet());
+        assertFalse(AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET.isSelected());
+        assertNull(AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET.getUserInput());
+
+        assertFalse(AutoCompletionPriority.IS_IN_DATASET.isInStandard());
+        assertTrue(AutoCompletionPriority.IS_IN_DATASET.isInDataSet());
+        assertFalse(AutoCompletionPriority.IS_IN_DATASET.isSelected());
+        assertNull(AutoCompletionPriority.IS_IN_DATASET.getUserInput());
+
+        assertTrue(AutoCompletionPriority.IS_IN_STANDARD.isInStandard());
+        assertFalse(AutoCompletionPriority.IS_IN_STANDARD.isInDataSet());
+        assertFalse(AutoCompletionPriority.IS_IN_STANDARD.isSelected());
+        assertNull(AutoCompletionPriority.IS_IN_STANDARD.getUserInput());
+
+        assertFalse(AutoCompletionPriority.IS_IN_SELECTION.isInStandard());
+        assertFalse(AutoCompletionPriority.IS_IN_SELECTION.isInDataSet());
+        assertTrue(AutoCompletionPriority.IS_IN_SELECTION.isSelected());
+        assertNull(AutoCompletionPriority.IS_IN_SELECTION.getUserInput());
+
+        assertFalse(AutoCompletionPriority.UNKNOWN.isInStandard());
+        assertFalse(AutoCompletionPriority.UNKNOWN.isInDataSet());
+        assertFalse(AutoCompletionPriority.UNKNOWN.isSelected());
+        assertNull(AutoCompletionPriority.UNKNOWN.getUserInput());
+
+        assertEquals(Integer.valueOf(5), new AutoCompletionPriority(false, false, false, 5).getUserInput());
+    }
+
+    /**
+     * Test ordering of priorities.
+     */
+    @Test
+    public void testOrdering() {
+        SortedSet<AutoCompletionPriority> set = new TreeSet<>();
+        set.add(AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET);
+        set.add(AutoCompletionPriority.IS_IN_DATASET);
+        set.add(AutoCompletionPriority.IS_IN_STANDARD);
+        set.add(AutoCompletionPriority.IS_IN_SELECTION);
+        set.add(AutoCompletionPriority.UNKNOWN);
+        set.add(new AutoCompletionPriority(false, false, false, 5));
+        set.add(new AutoCompletionPriority(false, false, false, 0));
+        set.add(new AutoCompletionPriority(false, false, false, 1));
+
+        assertEquals(Arrays.asList(
+                AutoCompletionPriority.UNKNOWN,
+                AutoCompletionPriority.IS_IN_STANDARD,
+                AutoCompletionPriority.IS_IN_DATASET,
+                AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET,
+                AutoCompletionPriority.IS_IN_SELECTION,
+                new AutoCompletionPriority(false, false, false, 5),
+                new AutoCompletionPriority(false, false, false, 1),
+                new AutoCompletionPriority(false, false, false, 0)
+                ), new ArrayList<>(set));
+    }
+
+    /**
+     * Unit test of methods {@link AutoCompletionPriority#equals} and {@link AutoCompletionPriority#hashCode}.
+     */
+    @Test
+    public void testEqualsContract() {
+        EqualsVerifier.forClass(AutoCompletionPriority.class).usingGetClass()
+            .verify();
+    }
+
+    /**
+     * Unit test of method {@link AutoCompletionPriority#toString()}.
+     */
+    @Test
+    public void testToString() {
+        assertEquals("<Priority; userInput: no, inDataSet: true, inStandard: false, selected: false>",
+                AutoCompletionPriority.IS_IN_DATASET.toString());
+        assertEquals("<Priority; userInput: 5, inDataSet: false, inStandard: false, selected: false>",
+                new AutoCompletionPriority(false, false, false, 5).toString());
+    }
+
+    /**
+     * Unit test of method {@link AutoCompletionPriority#mergeWith(AutoCompletionPriority)}.
+     */
+    @Test
+    public void testMergeWith() {
+        assertEquals(AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET,
+                AutoCompletionPriority.IS_IN_DATASET.mergeWith(AutoCompletionPriority.IS_IN_STANDARD));
+        assertEquals(AutoCompletionPriority.IS_IN_STANDARD_AND_IN_DATASET,
+                AutoCompletionPriority.IS_IN_STANDARD.mergeWith(AutoCompletionPriority.IS_IN_DATASET));
+        assertEquals(AutoCompletionPriority.IS_IN_SELECTION,
+                AutoCompletionPriority.UNKNOWN.mergeWith(AutoCompletionPriority.IS_IN_SELECTION));
+        assertEquals(new AutoCompletionPriority(false, false, false, 0),
+                new AutoCompletionPriority(false, false, false, 5).mergeWith(new AutoCompletionPriority(false, false, false, 0)));
+    }
+}
Index: trunk/test/unit/org/openstreetmap/josm/gui/dialogs/properties/TagEditHelperTest.java
===================================================================
--- trunk/test/unit/org/openstreetmap/josm/gui/dialogs/properties/TagEditHelperTest.java	(revision 12858)
+++ trunk/test/unit/org/openstreetmap/josm/gui/dialogs/properties/TagEditHelperTest.java	(revision 12859)
@@ -17,5 +17,5 @@
 import org.junit.Rule;
 import org.junit.Test;
-import org.openstreetmap.josm.gui.tagging.ac.AutoCompletionListItem;
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
 import org.openstreetmap.josm.testutils.JOSMTestRules;
 
@@ -46,14 +46,14 @@
     @Test
     public void testAcItemComparator() {
-        List<AutoCompletionListItem> list = new ArrayList<>();
-        list.add(new AutoCompletionListItem("Bing Sat"));
-        list.add(new AutoCompletionListItem("survey"));
-        list.add(new AutoCompletionListItem("Bing"));
-        list.add(new AutoCompletionListItem("digitalglobe"));
-        list.add(new AutoCompletionListItem("bing"));
-        list.add(new AutoCompletionListItem("DigitalGlobe"));
+        List<AutoCompletionItem> list = new ArrayList<>();
+        list.add(new AutoCompletionItem("Bing Sat"));
+        list.add(new AutoCompletionItem("survey"));
+        list.add(new AutoCompletionItem("Bing"));
+        list.add(new AutoCompletionItem("digitalglobe"));
+        list.add(new AutoCompletionItem("bing"));
+        list.add(new AutoCompletionItem("DigitalGlobe"));
         list.sort(TagEditHelper.DEFAULT_AC_ITEM_COMPARATOR);
         assertEquals(Arrays.asList("Bing", "bing", "Bing Sat", "digitalglobe", "DigitalGlobe", "survey"),
-                list.stream().map(AutoCompletionListItem::getValue).collect(Collectors.toList()));
+                list.stream().map(AutoCompletionItem::getValue).collect(Collectors.toList()));
     }
 
