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 net.jcip.annotations.ThreadSafe;
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 /**
28 * /** A thread-safe variant of {@link SortedMap} in which all mutative operations (the
29 * "destructive" operations described by {@link SortedMap} put, remove and so on) are implemented by
30 * making a fresh copy of the underlying map.
31 * <p>
32 * This is ordinarily too costly, but may be <em>more</em> efficient than alternatives when
33 * traversal operations vastly out-number mutations, and is useful when you cannot or don't want to
34 * synchronize traversals, yet need to preclude interference among concurrent threads. The
35 * "snapshot" style iterators on the collections returned by {@link #entrySet()}, {@link #keySet()}
36 * and {@link #values()} use a reference to the internal map at the point that the iterator was
37 * created. This map never changes during the lifetime of the iterator, so interference is
38 * impossible and the iterator is guaranteed not to throw <tt>ConcurrentModificationException</tt>.
39 * The iterators will not reflect additions, removals, or changes to the list since the iterator was
40 * created. Removing elements via these iterators is not supported. The mutable operations on these
41 * collections (remove, retain etc.) are supported but as with the {@link Map} interface, add and
42 * addAll are not and throw {@link UnsupportedOperationException}.
43 * <p>
44 * The actual copy is performed by a supplied {@link CopyFunction} object. The Factory is
45 * responsible for the underlying {@link SortedMap} implementation (for instance a {@link TreeMap})
46 * and therefore the semantics of what this map will cope with as far as null keys and values,
47 * iteration ordering etc.
48 * <p>
49 * There are supplied {@link Functions} for the Java Collections {@link SortedMap} implementation.
50 * <p>
51 * Views of the keys, values and entries are modifiable and will cause a copy. Views taken using
52 * {@link #subMap(Object, Object)}, {@link #headMap(Object)} and {@link #tailMap(Object)} are
53 * unmodifiable.
54 * <p>
55 * <strong>Please note</strong> that the thread-safety guarantees are limited to the thread-safety
56 * of the non-mutative (non-destructive) operations of the underlying map implementation. For
57 * instance implementations with access ordering are actually structurally modified by the
58 * {@link #get(Object)} method and are therefore not suitable candidates as delegates for this
59 * class.
60 *
61 * @author Jed Wesley-Smith
62 * @param <K> the key type
63 * @param <V> the value type
64 */
65 @ThreadSafe public abstract class CopyOnWriteSortedMap<K, V> extends AbstractCopyOnWriteMap<K, V, SortedMap<K, V>> implements SortedMap<K, V> {
66
67 private static final long serialVersionUID = 7375772978175545647L;
68
69 public interface CopyFunction<M extends SortedMap<?, ?>> extends AbstractCopyOnWriteMap.CopyFunction<M> {}
70
71 //
72 // factory methods
73 //
74
75 /**
76 * Create a new {@link CopyOnWriteSortedMap} where the underlying map instances are
77 * {@link TreeMap} and the sort uses the key's natural order.
78 */
79 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap() {
80 return new CopyOnWriteSortedMap<K, V>() {
81 @Override public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
82 return new TreeMap<K, V>(map);
83 };
84 };
85 }
86
87 /**
88 * Create a new {@link CopyOnWriteSortedMap} where the underlying map instances are
89 * {@link TreeMap}, the sort uses the key's natural order and the initial values are supplied.
90 *
91 * @param the map to use as the initial values.
92 */
93 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final Map<? extends K, ? extends V> map) {
94 return new CopyOnWriteSortedMap<K, V>() {
95 @Override public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
96 return new TreeMap<K, V>(map);
97 };
98 };
99 }
100
101 /**
102 * Create a new {@link CopyOnWriteSortedMap} where the underlying map instances are
103 * {@link TreeMap}.
104 *
105 * @param the Comparator to use for ordering the keys.
106 */
107 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final Comparator<? super K> comparator) {
108
109 return new CopyOnWriteSortedMap<K, V>() {
110 @Override public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
111 final TreeMap<K, V> treeMap = new TreeMap<K, V>(comparator);
112 treeMap.putAll(map);
113 return treeMap;
114 };
115 };
116 }
117
118 /**
119 * Create a new {@link CopyOnWriteSortedMap} where the underlying map instances are
120 * {@link TreeMap}, the sort uses the key's natural order and the initial values are supplied.
121 *
122 * @param map to use as the initial values.
123 * @param comparator for ordering.
124 */
125 public static <K, V> CopyOnWriteSortedMap<K, V> newTreeMap(final Map<? extends K, ? extends V> map, final Comparator<? super K> comparator) {
126 return new CopyOnWriteSortedMap<K, V>() {
127 @Override public <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(final N map) {
128 final TreeMap<K, V> treeMap = new TreeMap<K, V>(comparator);
129 treeMap.putAll(map);
130 return treeMap;
131 };
132 };
133 }
134
135 //
136 // constructors
137 //
138
139 /**
140 * Create a new empty {@link CopyOnWriteMap}.
141 */
142 public CopyOnWriteSortedMap() {
143 super(Collections.<K, V> emptyMap());
144 }
145
146 /**
147 * Create a new {@link CopyOnWriteMap} with the supplied {@link Map} to initialize the values.
148 *
149 * @param map the initial map to initialize with
150 */
151 public CopyOnWriteSortedMap(final Map<? extends K, ? extends V> map) {
152 super(map);
153 }
154
155 //
156 // methods
157 //
158
159 @Override public abstract <N extends Map<? extends K, ? extends V>> SortedMap<K, V> copy(N map);
160
161 public Comparator<? super K> comparator() {
162 return getDelegate().comparator();
163 }
164
165 public K firstKey() {
166 return getDelegate().firstKey();
167 }
168
169 public K lastKey() {
170 return getDelegate().lastKey();
171 }
172
173 public SortedMap<K, V> headMap(final K toKey) {
174 return Collections.unmodifiableSortedMap(getDelegate().headMap(toKey));
175 };
176
177 public SortedMap<K, V> tailMap(final K fromKey) {
178 return Collections.unmodifiableSortedMap(getDelegate().tailMap(fromKey));
179 };
180
181 public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
182 return Collections.unmodifiableSortedMap(getDelegate().subMap(fromKey, toKey));
183 };
184 }