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