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 String[] tags = this.tags; 179 int index = indexOfKey(tags, key); 180 return index < 0 ? null : tags[index + 1]; 181 } 182 183 @Override 184 public boolean containsValue(Object value) { 185 String[] tags = this.tags; 186 for (int i = 1; i < tags.length; i += 2) { 187 if (value.equals(tags[i])) { 188 return true; 189 } 190 } 191 return false; 192 } 193 194 @Override 195 public synchronized String put(String key, String value) { 196 Objects.requireNonNull(key); 197 Objects.requireNonNull(value); 198 int index = indexOfKey(tags, key); 199 int newTagArrayLength = tags.length; 200 if (index < 0) { 201 index = newTagArrayLength; 202 newTagArrayLength += 2; 203 } 204 205 String[] newTags = Arrays.copyOf(tags, newTagArrayLength); 206 String old = newTags[index + 1]; 207 newTags[index] = key; 208 newTags[index + 1] = value; 209 tags = newTags; 210 return old; 211 } 212 213 @Override 214 public synchronized String remove(Object key) { 215 int index = indexOfKey(tags, key); 216 if (index < 0) { 217 return null; 218 } 219 String old = tags[index + 1]; 220 int newLength = tags.length - 2; 221 if (newLength == 0) { 222 tags = EMPTY_TAGS; 223 } else { 224 String[] newTags = new String[newLength]; 225 System.arraycopy(tags, 0, newTags, 0, index); 226 System.arraycopy(tags, index + 2, newTags, index, newLength - index); 227 tags = newTags; 228 } 229 230 return old; 231 } 232 233 @Override 234 public synchronized void clear() { 235 tags = EMPTY_TAGS; 236 } 237 238 @Override 239 public int size() { 240 return tags.length / 2; 241 } 242 243 /** 244 * Gets a list of all tags contained in this map. 245 * @return The list of tags in the order they were added. 246 * @since 10604 247 */ 248 public List<Tag> getTags() { 249 List<Tag> tagList = new ArrayList<>(); 250 for (int i = 0; i < tags.length; i += 2) { 251 tagList.add(new Tag(tags[i], tags[i+1])); 252 } 253 return tagList; 254 } 255 256 /** 257 * Finds a key in an array that is structured like the {@link #tags} array and returns the position. 258 * <p> 259 * We allow the parameter to be passed to allow for better synchronization. 260 * 261 * @param tags The tags array to search through. 262 * @param key The key to search. 263 * @return The index of the key (a multiple of two) or -1 if it was not found. 264 */ 265 private static int indexOfKey(String[] tags, Object key) { 266 for (int i = 0; i < tags.length; i += 2) { 267 if (tags[i].equals(key)) { 268 return i; 269 } 270 } 271 return -1; 272 } 273 274 @Override 275 public String toString() { 276 StringBuilder stringBuilder = new StringBuilder(); 277 stringBuilder.append("TagMap["); 278 boolean first = true; 279 for (Map.Entry<String, String> e : entrySet()) { 280 if (!first) { 281 stringBuilder.append(','); 282 } 283 stringBuilder.append(e.getKey()); 284 stringBuilder.append('='); 285 stringBuilder.append(e.getValue()); 286 first = false; 287 } 288 stringBuilder.append(']'); 289 return stringBuilder.toString(); 290 } 291 292 /** 293 * Gets the backing tags array. Do not modify this array. 294 * @return The tags array. 295 */ 296 String[] getTagsArray() { 297 return tags; 298 } 299}