1 /**
2 * Copyright 2008 Atlassian Pty Ltd
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.atlassian.util.concurrent;
18
19 import static com.atlassian.util.concurrent.Assertions.notNull;
20
21 import java.util.Collections;
22 import java.util.Comparator;
23 import java.util.Map;
24 import java.util.SortedMap;
25 import java.util.TreeMap;
26
27 import net.jcip.annotations.GuardedBy;
28 import net.jcip.annotations.ThreadSafe;
29
30 /**
31 * /** A thread-safe variant of {@link SortedMap} in which all mutative
32 * operations (the "destructive" operations described by {@link SortedMap} put,
33 * remove and so on) are implemented by making a fresh copy of the underlying
34 * map.
35 * <p>
36 * This is ordinarily too costly, but may be <em>more</em> efficient than
37 * alternatives when traversal operations vastly out-number mutations, and is
38 * useful when you cannot or don't want to synchronize traversals, yet need to
39 * preclude interference among concurrent threads. The "snapshot" style
40 * iterators on the collections returned by {@link #entrySet()},
41 * {@link #keySet()} and {@link #values()} use a reference to the internal map
42 * at the point that the iterator was created. This map never changes during the
43 * lifetime of the iterator, so interference is impossible and the iterator is
44 * guaranteed not to throw <tt>ConcurrentModificationException</tt>. The
45 * iterators will not reflect additions, removals, or changes to the list since
46 * the iterator was created. Removing elements via these iterators is not
47 * supported. The mutable operations on these collections (remove, retain etc.)
48 * are supported but as with the {@link Map} interface, add and addAll are not
49 * and throw {@link UnsupportedOperationException}.
50 * <p>
51 * The actual copy is performed by the abstract {@link #copy(Map)} method. This
52 * implementation of this method is responsible for the underlying
53 * {@link SortedMap} implementation (for instance a {@link TreeMap}) and
54 * therefore the semantics of what this map will cope with as far as null keys
55 * and values, iteration ordering etc.
56 * <p>
57 * Views of the keys, values and entries are modifiable and will cause a copy.
58 * Views taken using {@link #subMap(Object, Object)}, {@link #headMap(Object)}
59 * and {@link #tailMap(Object)} are unmodifiable.
60 * <p>
61 * <strong>Please note</strong> that the thread-safety guarantees are limited to
62 * the thread-safety of the non-mutative (non-destructive) operations of the
63 * underlying map implementation.
64 *
65 * @param <K> the key type
66 * @param <V> the value type
67 * @author Jed Wesley-Smith
68 */
69 @ThreadSafe
70 public abstract class CopyOnWriteSortedMap<K, V> extends AbstractCopyOnWriteMap<K, V, SortedMap<K, V>> implements SortedMap<K, V> {
71 private static final long serialVersionUID = 7375772978175545647L;
72
73 /**
74 * Create a new {@link CopyOnWriteSortedMap} where the underlying map
75 * instances are {@link TreeMap} and the sort uses the key's natural order.
76 */
77 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap() {
78 return new CopyOnWriteSortedMap<K, V>() {
79 private static final long serialVersionUID = 8015823768891873357L;
80
81 @Override
82 public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
83 return new TreeMap<K, V>(map);
84 };
85 };
86 }
87
88 /**
89 * Create a new {@link CopyOnWriteSortedMap} where the underlying map
90 * instances are {@link TreeMap}, the sort uses the key's natural order and
91 * the initial values are supplied.
92 *
93 * @param map the map to use as the initial values.
94 */
95 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final @NotNull Map<? extends K, ? extends V> map) {
96 return new CopyOnWriteSortedMap<K, V>(map) {
97 private static final long serialVersionUID = 6065245106313875871L;
98
99 @Override
100 public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
101 return new TreeMap<K, V>(map);
102 };
103 };
104 }
105
106 /**
107 * Create a new {@link CopyOnWriteSortedMap} where the underlying map
108 * instances are {@link TreeMap}.
109 *
110 * @param comparator the Comparator to use for ordering the keys. Note,
111 * should be serializable if this map is to be serialized.
112 */
113 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final @NotNull Comparator<? super K> comparator) {
114 notNull("comparator", comparator);
115 return new CopyOnWriteSortedMap<K, V>() {
116 private static final long serialVersionUID = -7243810284130497340L;
117
118 @Override
119 public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
120 final TreeMap<K, V> treeMap = new TreeMap<K, V>(comparator);
121 treeMap.putAll(map);
122 return treeMap;
123 };
124 };
125 }
126
127 /**
128 * Create a new {@link CopyOnWriteSortedMap} where the underlying map
129 * instances are {@link TreeMap}, the sort uses the key's natural order and
130 * the initial values are supplied.
131 *
132 * @param map to use as the initial values.
133 * @param comparator for ordering.
134 */
135 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final @NotNull Map<? extends K, ? extends V> map,
136 final @NotNull Comparator<? super K> comparator) {
137 notNull("comparator", comparator);
138 return new CopyOnWriteSortedMap<K, V>(map) {
139 private static final long serialVersionUID = -6016130690072425548L;
140
141 @Override
142 public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
143 final TreeMap<K, V> treeMap = new TreeMap<K, V>(comparator);
144 treeMap.putAll(map);
145 return treeMap;
146 };
147 };
148 }
149
150 //
151 // constructors
152 //
153
154 /**
155 * Create a new empty {@link CopyOnWriteMap}.
156 */
157 protected CopyOnWriteSortedMap() {
158 super(Collections.<K, V> emptyMap());
159 }
160
161 /**
162 * Create a new {@link CopyOnWriteMap} with the supplied {@link Map} to
163 * initialize the values.
164 *
165 * @param map the initial map to initialize with
166 */
167 protected CopyOnWriteSortedMap(final Map<? extends K, ? extends V> map) {
168 super(map);
169 }
170
171 //
172 // methods
173 //
174
175 @Override
176 @GuardedBy("internal-lock")
177 protected abstract <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(N map);
178
179 public Comparator<? super K> comparator() {
180 return getDelegate().comparator();
181 }
182
183 public K firstKey() {
184 return getDelegate().firstKey();
185 }
186
187 public K lastKey() {
188 return getDelegate().lastKey();
189 }
190
191 public SortedMap<K, V> headMap(final K toKey) {
192 return Collections.unmodifiableSortedMap(getDelegate().headMap(toKey));
193 };
194
195 public SortedMap<K, V> tailMap(final K fromKey) {
196 return Collections.unmodifiableSortedMap(getDelegate().tailMap(fromKey));
197 };
198
199 public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
200 return Collections.unmodifiableSortedMap(getDelegate().subMap(fromKey, toKey));
201 };
202 }