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}