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}