Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/IntMap.java @ 278:55fad5e0e98b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Ensure capacity grows regardless of initial map size. Separate unit test
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Mon, 29 Aug 2011 23:31:37 +0200
parents 6355ecda1f08
children 81e9a3c9bafe
rev   line source
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2011 TMate Software Ltd
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.internal;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 import java.util.NoSuchElementException;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22 /**
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 * Map implementation that uses plain int keys and performs with log n effectiveness.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 * @author Artem Tikhomirov
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 * @author TMate Software Ltd.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 */
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 public class IntMap<V> {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 private int[] keys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 private Object[] values;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 private int size;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 public IntMap(int size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 keys = new int[size <= 0 ? 16 : size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 values = new Object[keys.length];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39 public int size() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 return size;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 public int firstKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 throw new NoSuchElementException();
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 return keys[0];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 public int lastKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 throw new NoSuchElementException();
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 return keys[size-1];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 public void trimToSize() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 if (size < keys.length) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59 int[] newKeys = new int[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 Object[] newValues = new Object[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 System.arraycopy(keys, 0, newKeys, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 System.arraycopy(values, 0, newValues, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 public void put(int key, V value) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 if (ix < 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 final int insertPoint = -ix - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 assert insertPoint <= size; // can't be greater, provided binarySearch didn't malfunction.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 if (size == keys.length) {
278
55fad5e0e98b Ensure capacity grows regardless of initial map size. Separate unit test
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 276
diff changeset
74 int capInc = size >>> 2; // +25%
55fad5e0e98b Ensure capacity grows regardless of initial map size. Separate unit test
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 276
diff changeset
75 int newCapacity = size + (capInc < 2 ? 2 : capInc) ;
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 int[] newKeys = new int[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 Object[] newValues = new Object[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 System.arraycopy(keys, 0, newKeys, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 System.arraycopy(keys, insertPoint, newKeys, insertPoint+1, keys.length - insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 System.arraycopy(values, 0, newValues, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 System.arraycopy(values, insertPoint, newValues, insertPoint+1, values.length - insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 // arrays got enough capacity
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 if (insertPoint != size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 System.arraycopy(keys, insertPoint, keys, insertPoint+1, keys.length - insertPoint - 1);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 System.arraycopy(values, insertPoint, values, insertPoint+1, values.length - insertPoint - 1);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 // else insertPoint is past known elements, no need to copy arrays
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 keys[insertPoint] = key;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 values[insertPoint] = value;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 size++;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 values[ix] = value;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 public boolean containsKey(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 return binarySearch(keys, size, key) >= 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 @SuppressWarnings("unchecked")
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 public V get(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 if (ix >= 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 return (V) values[ix];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 return null;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 // copy of Arrays.binarySearch, with upper search limit as argument
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 private static int binarySearch(int[] a, int high, int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 int low = 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 high--;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 while (low <= high) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 int mid = (low + high) >> 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
120 int midVal = a[mid];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
122 if (midVal < key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
123 low = mid + 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 else if (midVal > key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 high = mid - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 else
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 return mid; // key found
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 return -(low + 1); // key not found.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 }