Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/IntMap.java @ 370:a2341e761609

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Let callback implementations deliver errors (e,g. own exceptions) to client code
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 22 Dec 2011 02:37:10 +0300
parents 81e9a3c9bafe
children ee8264d80747 2e402c12ebc6
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 }
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
112
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
113 public void remove(int key) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
114 int ix = binarySearch(keys, size, key);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
115 if (ix >= 0) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
116 if (ix <= size - 1) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
117 System.arraycopy(keys, ix+1, keys, ix, size - ix - 1);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
118 System.arraycopy(values, ix+1, values, ix, size - ix - 1);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
119 } // if ix points to last element, no reason to attempt a copy
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
120 size--;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
121 keys[size] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
122 values[size] = null;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
123 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
124 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
125
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
126 /**
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
127 * Forget first N entries (in natural order) in the map.
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
128 */
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
129 @Experimental
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
130 public void removeFromStart(int count) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
131 if (count > 0 && count <= size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
132 if (count < size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
133 System.arraycopy(keys, count, keys, 0, size - count);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
134 System.arraycopy(values, count, values, 0, size - count);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
135 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
136 for (int i = size - count; i < size; i++) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
137 keys[i] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
138 values[i] = null;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
139 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
140 size -= count;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
141 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
142 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
143
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
144
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
145
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
146 // 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
147 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
148 int low = 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
149 high--;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
150
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
151 while (low <= high) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
152 int mid = (low + high) >> 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
153 int midVal = a[mid];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
154
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
155 if (midVal < key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
156 low = mid + 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
157 else if (midVal > key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
158 high = mid - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
159 else
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
160 return mid; // key found
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
161 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
162 return -(low + 1); // key not found.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
163 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
164 }