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