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