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 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 the Comparator to use for ordering the keys.
111 */
112 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final @NotNull Comparator<? super K> comparator) {
113 notNull("comparator", comparator);
114 return new CopyOnWriteSortedMap<K, V>() {
115 private static final long serialVersionUID = -7243810284130497340L;
116
117 @Override
118 public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
119 final TreeMap<K, V> treeMap = new TreeMap<K, V>(comparator);
120 treeMap.putAll(map);
121 return treeMap;
122 };
123 };
124 }
125
126 /**
127 * Create a new {@link CopyOnWriteSortedMap} where the underlying map
128 * instances are {@link TreeMap}, the sort uses the key's natural order and
129 * the initial values are supplied.
130 *
131 * @param map to use as the initial values.
132 * @param comparator for ordering.
133 */
134 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final @NotNull Map<? extends K, ? extends V> map,
135 final @NotNull Comparator<? super K> comparator) {
136 notNull("comparator", comparator);
137 return new CopyOnWriteSortedMap<K, V>(map) {
138 private static final long serialVersionUID = -6016130690072425548L;
139
140 @Override
141 public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
142 final TreeMap<K, V> treeMap = new TreeMap<K, V>(comparator);
143 treeMap.putAll(map);
144 return treeMap;
145 };
146 };
147 }
148
149 //
150 // constructors
151 //
152
153 /**
154 * Create a new empty {@link CopyOnWriteMap}.
155 */
156 public CopyOnWriteSortedMap() {
157 super(Collections.<K, V> emptyMap());
158 }
159
160 /**
161 * Create a new {@link CopyOnWriteMap} with the supplied {@link Map} to
162 * initialize the values.
163 *
164 * @param map the initial map to initialize with
165 */
166 public CopyOnWriteSortedMap(final Map<? extends K, ? extends V> map) {
167 super(map);
168 }
169
170 //
171 // methods
172 //
173
174 @Override
175 @GuardedBy("internal-lock")
176 protected abstract <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(N map);
177
178 public Comparator<? super K> comparator() {
179 return getDelegate().comparator();
180 }
181
182 public K firstKey() {
183 return getDelegate().firstKey();
184 }
185
186 public K lastKey() {
187 return getDelegate().lastKey();
188 }
189
190 public SortedMap<K, V> headMap(final K toKey) {
191 return Collections.unmodifiableSortedMap(getDelegate().headMap(toKey));
192 };
193
194 public SortedMap<K, V> tailMap(final K fromKey) {
195 return Collections.unmodifiableSortedMap(getDelegate().tailMap(fromKey));
196 };
197
198 public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
199 return Collections.unmodifiableSortedMap(getDelegate().subMap(fromKey, toKey));
200 };
201 }