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}