1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package org.apache.harmony.tests.java.util;
19
20import java.io.IOException;
21import java.io.ObjectInputStream;
22import java.io.ObjectOutputStream;
23import java.io.Serializable;
24import java.util.AbstractSet;
25import java.util.ArrayList;
26import java.util.Collection;
27import java.util.Collections;
28import java.util.Comparator;
29import java.util.ConcurrentModificationException;
30import java.util.Iterator;
31import java.util.Map;
32import java.util.NoSuchElementException;
33import java.util.Set;
34import java.util.SortedMap;
35
36public class RefSortedMap<K, V> extends java.util.AbstractMap<K, V>
37        implements SortedMap<K, V>, Cloneable, Serializable {
38
39    private static final long serialVersionUID = 1L;
40
41    private static final class MapEntry<K, V> implements Map.Entry<K, V> {
42
43        final K key;
44        V value;
45
46        MapEntry(K key, V value) {
47            this.key = key;
48            this.value = value;
49        }
50
51        public K getKey() {
52            return key;
53        }
54
55        public V getValue() {
56            return value;
57        }
58
59        public V setValue(V v) {
60            V res = value;
61            value = v;
62            return res;
63        }
64
65        public int hashCode() {
66            return (getKey() == null ? 0 : getKey().hashCode())
67                    ^ (getValue() == null ? 0 : getValue().hashCode());
68        }
69
70        public boolean equals(Object object) {
71            if (this == object) {
72                return true;
73            }
74            if (object instanceof Map.Entry) {
75                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
76                return (getKey() == null ? entry.getKey() == null : getKey().equals(entry
77                        .getKey()))
78                        && (getValue() == null ? entry.getValue() == null : getValue()
79                        .equals(entry.getValue()));
80            }
81            return false;
82        }
83    }
84
85    transient ArrayList<MapEntry<K, V>> entries = new ArrayList<MapEntry<K, V>>();
86    transient int modCnt;
87
88    private final Comparator<? super K> comparator;
89
90    class SubMap extends java.util.AbstractMap<K, V>
91            implements SortedMap<K, V>, Cloneable {
92
93        final boolean hasStart, hasEnd;
94        final K start, end;
95
96        SubMap(boolean hasFirst, K first, boolean hasLast, K last) {
97            this.hasStart = hasFirst;
98            this.start = first;
99            this.hasEnd = hasLast;
100            this.end = last;
101            if (hasStart && hasEnd && compare(start, end) >= 0) {
102                throw new IllegalArgumentException();
103            }
104        }
105
106        @Override
107        public Set<java.util.Map.Entry<K, V>> entrySet() {
108            return new AbstractSet<Entry<K, V>>() {
109
110                @Override
111                public Iterator<java.util.Map.Entry<K, V>> iterator() {
112                    return new Iterator<Entry<K, V>>() {
113                        int modCnt = RefSortedMap.this.modCnt;
114                        int offset = SubMap.this.size() > 0 ?
115                                bsearch(SubMap.this.firstKey()) - 1 :
116                                entries.size();
117
118                        public boolean hasNext() {
119                            if (modCnt != RefSortedMap.this.modCnt) {
120                                throw new ConcurrentModificationException();
121                            }
122                            return offset + 1 < entries.size()
123                                    && isInRange(entries.get(offset + 1).getKey());
124                        }
125
126                        public Map.Entry<K, V> next() {
127                            if (modCnt != RefSortedMap.this.modCnt) {
128                                throw new ConcurrentModificationException();
129                            }
130                            if (!hasNext()) {
131                                throw new NoSuchElementException();
132                            }
133                            offset++;
134                            return entries.get(offset);
135                        }
136
137                        public void remove() {
138                            if (modCnt != RefSortedMap.this.modCnt) {
139                                throw new ConcurrentModificationException();
140                            }
141                            modCnt++;
142                            RefSortedMap.this.modCnt++;
143                            RefSortedMap.this.entries.remove(offset);
144                            offset--;
145                        }
146
147                    };
148                }
149
150                @Override
151                public int size() {
152                    try {
153                        int lastIdx = bsearch(SubMap.this.lastKey());
154                        int firstIdx = bsearch(SubMap.this.firstKey());
155                        return lastIdx - firstIdx + 1;
156                    } catch (NoSuchElementException e) {
157                        return 0;
158                    } catch (ArrayIndexOutOfBoundsException e) {
159                        return 0;
160                    }
161                }
162
163            };
164        }
165
166        public Comparator<? super K> comparator() {
167            return RefSortedMap.this.comparator();
168        }
169
170        public K firstKey() {
171            if (!hasStart) {
172                K res = RefSortedMap.this.firstKey();
173                if (!isInRange(res)) {
174                    throw new NoSuchElementException();
175                }
176                return res;
177            }
178            int idx = bsearch(start);
179            if (idx >= 0) {
180                return start;
181            }
182            if (-idx - 1 >= entries.size() || !isInRange(entries.get(-idx - 1).getKey())) {
183                throw new NoSuchElementException();
184            }
185            return entries.get(-idx - 1).getKey();
186        }
187
188        public SortedMap<K, V> headMap(K key) {
189            if (!isInRange(key)) {
190                throw new IllegalArgumentException();
191            }
192            return new SubMap(hasStart, start, true, key);
193        }
194
195        public K lastKey() {
196            if (!hasEnd) {
197                K res = RefSortedMap.this.lastKey();
198                if (!isInRange(res)) {
199                    throw new NoSuchElementException();
200                }
201                return res;
202            }
203            int idx = bsearch(end);
204            idx = idx >= 0 ? idx - 1 : -idx - 2;
205            if (idx < 0 || !isInRange(entries.get(idx).getKey())) {
206                throw new NoSuchElementException();
207            }
208            return entries.get(idx).getKey();
209        }
210
211        public SortedMap<K, V> subMap(K startKey, K endKey) {
212            if (!isInRange(startKey)) {
213                throw new IllegalArgumentException();
214            }
215            if (!isInRange(endKey)) {
216                throw new IllegalArgumentException();
217            }
218            return new SubMap(true, startKey, true, endKey);
219        }
220
221        public SortedMap<K, V> tailMap(K key) {
222            if (!isInRange(key)) {
223                throw new IllegalArgumentException();
224            }
225            return new SubMap(true, key, hasEnd, end);
226        }
227
228        private boolean isInRange(K key) {
229            if (hasStart && compare(key, start) < 0) {
230                return false;
231            }
232            if (hasEnd && compare(key, end) >= 0) {
233                return false;
234            }
235            return true;
236        }
237
238    }
239
240    public RefSortedMap() {
241        this((Comparator<? super K>) null);
242    }
243
244    @SuppressWarnings("unchecked")
245    public int compare(K start, K end) {
246        return comparator != null ? comparator.compare(start, end)
247                : ((Comparable<K>) start).compareTo(end);
248    }
249
250    @SuppressWarnings("unchecked")
251    public RefSortedMap(Comparator<? super K> comparator) {
252        this.comparator = comparator;
253        cmp = createCmp();
254    }
255
256    public RefSortedMap(Map<? extends K, ? extends V> map) {
257        this();
258        putAll(map);
259    }
260
261    public RefSortedMap(SortedMap<K, ? extends V> map) {
262        this(map.comparator());
263        putAll(map);
264    }
265
266    public Comparator<? super K> comparator() {
267        return comparator;
268    }
269
270    public Set<Map.Entry<K, V>> entrySet() {
271        return tailMap(firstKey()).entrySet();
272    }
273
274    public K firstKey() {
275        return entries.get(0).getKey();
276    }
277
278    public SortedMap<K, V> headMap(K key) {
279        return new SubMap(false, null, true, key);
280    }
281
282    public Set<K> keySet() {
283        return tailMap(firstKey()).keySet();
284    }
285
286    public K lastKey() {
287        return entries.get(entries.size() - 1).getKey();
288    }
289
290    public SortedMap<K, V> subMap(K startKey, K endKey) {
291        return new SubMap(true, startKey, true, endKey);
292    }
293
294    public SortedMap<K, V> tailMap(K key) {
295        return new SubMap(true, key, false, null);
296    }
297
298    public Collection<V> values() {
299        return tailMap(firstKey()).values();
300    }
301
302    public void clear() {
303        entries.clear();
304    }
305
306    public boolean containsKey(Object arg0) {
307        return bsearch(arg0) >= 0;
308    }
309
310    public boolean containsValue(Object arg0) {
311        for (V v : values()) {
312            if (arg0.equals(v)) {
313                return true;
314            }
315        }
316        return false;
317    }
318
319    @SuppressWarnings("unchecked")
320    public V get(Object arg0) {
321        int idx = bsearch(arg0);
322        return idx >= 0 ? entries.get(idx).getValue() : null;
323    }
324
325    public boolean isEmpty() {
326        return entries.isEmpty();
327    }
328
329    public V put(K arg0, V arg1) {
330        modCnt++;
331        int idx = bsearch(arg0);
332        if (idx >= 0) {
333            return entries.get(idx).setValue(arg1);
334        }
335        entries.add(-idx - 1, new MapEntry<K, V>(arg0, arg1));
336        return null;
337    }
338
339    public void putAll(Map<? extends K, ? extends V> arg0) {
340        for (Map.Entry<? extends K, ? extends V> e : arg0.entrySet()) {
341            put(e.getKey(), e.getValue());
342        }
343    }
344
345    @SuppressWarnings("unchecked")
346    public V remove(Object arg0) {
347        modCnt++;
348        int idx = bsearch(arg0);
349        if (idx < 0) {
350            return null;
351        }
352        return entries.remove(idx).getValue();
353    }
354
355    transient private Comparator<MapEntry<K, V>> cmp = createCmp();
356
357    Comparator<MapEntry<K, V>> createCmp() {
358        return new Comparator<MapEntry<K, V>>() {
359
360            public int compare(MapEntry<K, V> arg0, MapEntry<K, V> arg1) {
361                return RefSortedMap.this.compare(arg0.getKey(), arg1.getKey());
362            }
363
364        };
365    }
366
367    @SuppressWarnings("unchecked")
368    private int bsearch(Object arg0) {
369        return Collections.binarySearch(entries, new MapEntry<K, V>((K) arg0, null), cmp);
370    }
371
372    public int size() {
373        return entries.size();
374    }
375
376    public RefSortedMap<K, V> clone() {
377        return new RefSortedMap<K, V>(this);
378    }
379
380    private void writeObject(ObjectOutputStream stream) throws IOException {
381        stream.defaultWriteObject();
382        stream.writeInt(size());
383        for (Map.Entry<K, V> e : entrySet()) {
384            stream.writeObject(e.getKey());
385            stream.writeObject(e.getValue());
386        }
387    }
388
389    @SuppressWarnings("unchecked")
390    private void readObject(ObjectInputStream stream) throws IOException,
391            ClassNotFoundException {
392
393        cmp = createCmp();
394        stream.defaultReadObject();
395        int size = stream.readInt();
396        entries = new ArrayList<MapEntry<K, V>>(size);
397        for (int i = 0; i < size; i++) {
398            put((K) stream.readObject(), (V) stream.readObject());
399        }
400    }
401
402}
403