Mercurial > jhg

comparison 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
comparison
equal deleted inserted replaced
277:74e7493a042a 278:55fad5e0e98b
69 int ix = binarySearch(keys, size, key); 69 int ix = binarySearch(keys, size, key);
70 if (ix < 0) { 70 if (ix < 0) {
71 final int insertPoint = -ix - 1; 71 final int insertPoint = -ix - 1;
72 assert insertPoint <= size; // can't be greater, provided binarySearch didn't malfunction. 72 assert insertPoint <= size; // can't be greater, provided binarySearch didn't malfunction.
73 if (size == keys.length) { 73 if (size == keys.length) {
74 int newCapacity = size + (size >>> 2); 74 int capInc = size >>> 2; // +25%
75 int newCapacity = size + (capInc < 2 ? 2 : capInc) ;
75 int[] newKeys = new int[newCapacity]; 76 int[] newKeys = new int[newCapacity];
76 Object[] newValues = new Object[newCapacity]; 77 Object[] newValues = new Object[newCapacity];
77 System.arraycopy(keys, 0, newKeys, 0, insertPoint); 78 System.arraycopy(keys, 0, newKeys, 0, insertPoint);
78 System.arraycopy(keys, insertPoint, newKeys, insertPoint+1, keys.length - insertPoint); 79 System.arraycopy(keys, insertPoint, newKeys, insertPoint+1, keys.length - insertPoint);
79 System.arraycopy(values, 0, newValues, 0, insertPoint); 80 System.arraycopy(values, 0, newValues, 0, insertPoint);
125 else 126 else
126 return mid; // key found 127 return mid; // key found
127 } 128 }
128 return -(low + 1); // key not found. 129 return -(low + 1); // key not found.
129 } 130 }
130
131 public static void main(String[] args) {
132 IntMap<String> m = new IntMap<String>(-1);
133 m.put(18, "18");
134 m.put(1, "1");
135 m.put(9, "9");
136 m.put(20, "20");
137 m.put(2, "2");
138 m.put(3, "3");
139 m.put(21, "21");
140 m.put(15, "15");
141 m.put(12, "12");
142 m.put(11, "11");
143 m.put(31, "31");
144 System.out.printf("%d [%d..%d]\n", m.size(), m.firstKey(), m.lastKey());
145 for (int i = m.firstKey(); i <= m.lastKey(); i++) {
146 if (m.containsKey(i)) {
147 System.out.printf("@%02d:%s\n", i, m.get(i));
148 }
149 }
150 }
151 } 131 }