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.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 TagEntryInterator 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 TagEntryInterator}
049         * @param tags The tags array. It is never changed but should also not be changed by you.
050         */
051        TagEntryInterator(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    /**
080     * This is the entry set of this map. It represents the state when it was created.
081     * @author Michael Zangl
082     */
083    private static class TagEntrySet extends AbstractSet<Entry<String, String>> {
084        private final String[] tags;
085
086        /**
087         * Create a new {@link TagEntrySet}
088         * @param tags The tags array. It is never changed but should also not be changed by you.
089         */
090        TagEntrySet(String ... tags) {
091            super();
092            this.tags = tags;
093        }
094
095        @Override
096        public Iterator<Entry<String, String>> iterator() {
097            return new TagEntryInterator(tags);
098        }
099
100        @Override
101        public int size() {
102            return tags.length / 2;
103        }
104
105    }
106
107    /**
108     * The tags field. This field is guarded using RCU.
109     */
110    private volatile String[] tags;
111
112    /**
113     * Creates a new, empty tag map.
114     */
115    public TagMap() {
116        this((String[]) null);
117    }
118
119    /**
120     * Create a new tag map and load it from the other map.
121     * @param tags The map to load from.
122     * @since 10604
123     */
124    public TagMap(Map<String, String> tags) {
125        putAll(tags);
126    }
127
128    /**
129     * Copy constructor.
130     * @param tagMap The map to copy from.
131     * @since 10604
132     */
133    public TagMap(TagMap tagMap) {
134        this(tagMap.tags);
135    }
136
137    /**
138     * Creates a new read only tag map using a key/value/key/value/... array.
139     * <p>
140     * The array that is passed as parameter may not be modified after passing it to this map.
141     * @param tags The tags array. It is not modified by this map.
142     */
143    public TagMap(String ... tags) {
144        if (tags == null || tags.length == 0) {
145            this.tags = EMPTY_TAGS;
146        } else {
147            if (tags.length % 2 != 0) {
148                throw new IllegalArgumentException("tags array length needs to be multiple of two.");
149            }
150            this.tags = tags;
151        }
152    }
153
154    /**
155     * Creates a new map using the given list of tags. For dupplicate keys the last value found is used.
156     * @param tags The tags
157     * @since 10736
158     */
159    public TagMap(Collection<Tag> tags) {
160        for (Tag tag : tags) {
161            put(tag.getKey(), tag.getValue());
162        }
163    }
164
165    @Override
166    public Set<Entry<String, String>> entrySet() {
167        return new TagEntrySet(tags);
168    }
169
170    @Override
171    public boolean containsKey(Object key) {
172        return indexOfKey(tags, key) >= 0;
173    }
174
175    @Override
176    public String get(Object key) {
177        String[] tags = this.tags;
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        String[] tags = this.tags;
185        for (int i = 1; i < tags.length; i += 2) {
186            if (value.equals(tags[i])) {
187                return true;
188            }
189        }
190        return false;
191    }
192
193    @Override
194    public synchronized String put(String key, String value) {
195        if (key == null) {
196            throw new NullPointerException();
197        }
198        if (value == null) {
199            throw new NullPointerException();
200        }
201        int index = indexOfKey(tags, key);
202        int newTagArrayLength = tags.length;
203        if (index < 0) {
204            index = newTagArrayLength;
205            newTagArrayLength += 2;
206        }
207
208        String[] newTags = Arrays.copyOf(tags, newTagArrayLength);
209        String old = newTags[index + 1];
210        newTags[index] = key;
211        newTags[index + 1] = value;
212        tags = newTags;
213        return old;
214    }
215
216    @Override
217    public synchronized String remove(Object key) {
218        int index = indexOfKey(tags, key);
219        if (index < 0) {
220            return null;
221        }
222        String old = tags[index + 1];
223        int newLength = tags.length - 2;
224        if (newLength == 0) {
225            tags = EMPTY_TAGS;
226        } else {
227            String[] newTags = new String[newLength];
228            System.arraycopy(tags, 0, newTags, 0, index);
229            System.arraycopy(tags, index + 2, newTags, index, newLength - index);
230            tags = newTags;
231        }
232
233        return old;
234    }
235
236    @Override
237    public synchronized void clear() {
238        tags = EMPTY_TAGS;
239    }
240
241    @Override
242    public int size() {
243        return tags.length / 2;
244    }
245
246    /**
247     * Gets a list of all tags contained in this map.
248     * @return The list of tags in the order they were added.
249     * @since 10604
250     */
251    public List<Tag> getTags() {
252        List<Tag> tagList = new ArrayList<>();
253        for (int i = 0; i < tags.length; i += 2) {
254            tagList.add(new Tag(tags[i], tags[i+1]));
255        }
256        return tagList;
257    }
258
259    /**
260     * Finds a key in an array that is structured like the {@link #tags} array and returns the position.
261     * <p>
262     * We allow the parameter to be passed to allow for better synchronization.
263     *
264     * @param tags The tags array to search through.
265     * @param key The key to search.
266     * @return The index of the key (a multiple of two) or -1 if it was not found.
267     */
268    private static int indexOfKey(String[] tags, Object key) {
269        for (int i = 0; i < tags.length; i += 2) {
270            if (tags[i].equals(key)) {
271                return i;
272            }
273        }
274        return -1;
275    }
276
277    @Override
278    public String toString() {
279        StringBuilder stringBuilder = new StringBuilder();
280        stringBuilder.append("TagMap[");
281        boolean first = true;
282        for (Map.Entry<String, String> e : entrySet()) {
283            if (!first) {
284                stringBuilder.append(',');
285            }
286            stringBuilder.append(e.getKey());
287            stringBuilder.append('=');
288            stringBuilder.append(e.getValue());
289            first = false;
290        }
291        stringBuilder.append(']');
292        return stringBuilder.toString();
293    }
294
295    /**
296     * Gets the backing tags array. Do not modify this array.
297     * @return The tags array.
298     */
299    String[] getTagsArray() {
300        return tags;
301    }
302}