001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm;
003
004import java.io.Serializable;
005import java.util.AbstractMap;
006import java.util.AbstractSet;
007import java.util.ArrayList;
008import java.util.Arrays;
009import java.util.Collection;
010import java.util.ConcurrentModificationException;
011import java.util.Iterator;
012import java.util.List;
013import java.util.Map;
014import java.util.NoSuchElementException;
015import java.util.Objects;
016import java.util.Set;
017
018/**
019 * This class provides a read/write map that uses the same format as {@link AbstractPrimitive#keys}.
020 * It offers good performance for few keys.
021 * It uses copy on write, so there cannot be a {@link ConcurrentModificationException} while iterating through it.
022 *
023 * @author Michael Zangl
024 */
025public class TagMap extends AbstractMap<String, String> implements Serializable {
026    static final long serialVersionUID = 1;
027    /**
028     * We use this array every time we want to represent an empty map.
029     * This saves us the burden of checking for null every time but saves some object allocations.
030     */
031    private static final String[] EMPTY_TAGS = new String[0];
032
033    /**
034     * An iterator that iterates over the tags in this map. The iterator always represents the state of the map when it was created.
035     * Further changes to the map won't change the tags that we iterate over but they also won't raise any exceptions.
036     * @author Michael Zangl
037     */
038    private static class TagEntryInterator implements Iterator<Entry<String, String>> {
039        /**
040         * The current state of the tags we iterate over.
041         */
042        private final String[] tags;
043        /**
044         * Current tag index. Always a multiple of 2.
045         */
046        private int currentIndex;
047
048        /**
049         * Create a new {@link TagEntryInterator}
050         * @param tags The tags array. It is never changed but should also not be changed by you.
051         */
052        TagEntryInterator(String... tags) {
053            super();
054            this.tags = tags;
055        }
056
057        @Override
058        public boolean hasNext() {
059            return currentIndex < tags.length;
060        }
061
062        @Override
063        public Entry<String, String> next() {
064            if (!hasNext()) {
065                throw new NoSuchElementException();
066            }
067
068            Tag tag = new Tag(tags[currentIndex], tags[currentIndex + 1]);
069            currentIndex += 2;
070            return tag;
071        }
072
073        @Override
074        public void remove() {
075            throw new UnsupportedOperationException();
076        }
077
078    }
079
080    /**
081     * This is the entry set of this map. It represents the state when it was created.
082     * @author Michael Zangl
083     */
084    private static class TagEntrySet extends AbstractSet<Entry<String, String>> {
085        private final String[] tags;
086
087        /**
088         * Create a new {@link TagEntrySet}
089         * @param tags The tags array. It is never changed but should also not be changed by you.
090         */
091        TagEntrySet(String... tags) {
092            super();
093            this.tags = tags;
094        }
095
096        @Override
097        public Iterator<Entry<String, String>> iterator() {
098            return new TagEntryInterator(tags);
099        }
100
101        @Override
102        public int size() {
103            return tags.length / 2;
104        }
105
106    }
107
108    /**
109     * The tags field. This field is guarded using RCU.
110     */
111    private volatile String[] tags;
112
113    /**
114     * Creates a new, empty tag map.
115     */
116    public TagMap() {
117        this((String[]) null);
118    }
119
120    /**
121     * Create a new tag map and load it from the other map.
122     * @param tags The map to load from.
123     * @since 10604
124     */
125    public TagMap(Map<String, String> tags) {
126        putAll(tags);
127    }
128
129    /**
130     * Copy constructor.
131     * @param tagMap The map to copy from.
132     * @since 10604
133     */
134    public TagMap(TagMap tagMap) {
135        this(tagMap.tags);
136    }
137
138    /**
139     * Creates a new read only tag map using a key/value/key/value/... array.
140     * <p>
141     * The array that is passed as parameter may not be modified after passing it to this map.
142     * @param tags The tags array. It is not modified by this map.
143     */
144    public TagMap(String... tags) {
145        if (tags == null || tags.length == 0) {
146            this.tags = EMPTY_TAGS;
147        } else {
148            if (tags.length % 2 != 0) {
149                throw new IllegalArgumentException("tags array length needs to be multiple of two.");
150            }
151            this.tags = tags;
152        }
153    }
154
155    /**
156     * Creates a new map using the given list of tags. For dupplicate keys the last value found is used.
157     * @param tags The tags
158     * @since 10736
159     */
160    public TagMap(Collection<Tag> tags) {
161        for (Tag tag : tags) {
162            put(tag.getKey(), tag.getValue());
163        }
164    }
165
166    @Override
167    public Set<Entry<String, String>> entrySet() {
168        return new TagEntrySet(tags);
169    }
170
171    @Override
172    public boolean containsKey(Object key) {
173        return indexOfKey(tags, key) >= 0;
174    }
175
176    @Override
177    public String get(Object key) {
178        int index = indexOfKey(tags, key);
179        return index < 0 ? null : tags[index + 1];
180    }
181
182    @Override
183    public boolean containsValue(Object value) {
184        for (int i = 1; i < tags.length; i += 2) {
185            if (value.equals(tags[i])) {
186                return true;
187            }
188        }
189        return false;
190    }
191
192    @Override
193    public synchronized String put(String key, String value) {
194        Objects.requireNonNull(key);
195        Objects.requireNonNull(value);
196        int index = indexOfKey(tags, key);
197        int newTagArrayLength = tags.length;
198        if (index < 0) {
199            index = newTagArrayLength;
200            newTagArrayLength += 2;
201        }
202
203        String[] newTags = Arrays.copyOf(tags, newTagArrayLength);
204        String old = newTags[index + 1];
205        newTags[index] = key;
206        newTags[index + 1] = value;
207        tags = newTags;
208        return old;
209    }
210
211    @Override
212    public synchronized String remove(Object key) {
213        int index = indexOfKey(tags, key);
214        if (index < 0) {
215            return null;
216        }
217        String old = tags[index + 1];
218        int newLength = tags.length - 2;
219        if (newLength == 0) {
220            tags = EMPTY_TAGS;
221        } else {
222            String[] newTags = new String[newLength];
223            System.arraycopy(tags, 0, newTags, 0, index);
224            System.arraycopy(tags, index + 2, newTags, index, newLength - index);
225            tags = newTags;
226        }
227
228        return old;
229    }
230
231    @Override
232    public synchronized void clear() {
233        tags = EMPTY_TAGS;
234    }
235
236    @Override
237    public int size() {
238        return tags.length / 2;
239    }
240
241    /**
242     * Gets a list of all tags contained in this map.
243     * @return The list of tags in the order they were added.
244     * @since 10604
245     */
246    public List<Tag> getTags() {
247        List<Tag> tagList = new ArrayList<>();
248        for (int i = 0; i < tags.length; i += 2) {
249            tagList.add(new Tag(tags[i], tags[i+1]));
250        }
251        return tagList;
252    }
253
254    /**
255     * Finds a key in an array that is structured like the {@link #tags} array and returns the position.
256     * <p>
257     * We allow the parameter to be passed to allow for better synchronization.
258     *
259     * @param tags The tags array to search through.
260     * @param key The key to search.
261     * @return The index of the key (a multiple of two) or -1 if it was not found.
262     */
263    private static int indexOfKey(String[] tags, Object key) {
264        for (int i = 0; i < tags.length; i += 2) {
265            if (tags[i].equals(key)) {
266                return i;
267            }
268        }
269        return -1;
270    }
271
272    @Override
273    public String toString() {
274        StringBuilder stringBuilder = new StringBuilder();
275        stringBuilder.append("TagMap[");
276        boolean first = true;
277        for (Map.Entry<String, String> e : entrySet()) {
278            if (!first) {
279                stringBuilder.append(',');
280            }
281            stringBuilder.append(e.getKey());
282            stringBuilder.append('=');
283            stringBuilder.append(e.getValue());
284            first = false;
285        }
286        stringBuilder.append(']');
287        return stringBuilder.toString();
288    }
289
290    /**
291     * Gets the backing tags array. Do not modify this array.
292     * @return The tags array.
293     */
294    String[] getTagsArray() {
295        return tags;
296    }
297}