Mercurial > hg4j

annotate src/org/tmatesoft/hg/internal/IntMap.java @ 587:a52f4cc56f9c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Minimize vectors re-allocating when merging patches
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 26 Apr 2013 20:04:17 +0200
parents 4ea0351ca878
children f41dd9a3b8af
rev   line source
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
2 * Copyright (c) 2011-2013 TMate Software Ltd
276
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
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
19 import java.util.Arrays;
415
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
20 import java.util.Iterator;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
21 import java.util.Map;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
22 import java.util.Map.Entry;
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 import java.util.NoSuchElementException;
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
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 /**
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 * Map implementation that uses plain int keys and performs with log n effectiveness.
448
2e402c12ebc6 Issue 31: Revlog#walk() fails with AIOOBE when start > 0
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
28 * May contain null values
276
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 * @author Artem Tikhomirov
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 * @author TMate Software Ltd.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 */
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 public class IntMap<V> {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 private int[] keys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 private Object[] values;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 private int size;
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 IntMap(int size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 keys = new int[size <= 0 ? 16 : size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 values = new Object[keys.length];
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
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 public int size() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 return size;
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
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 public int firstKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 throw new NoSuchElementException();
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 return keys[0];
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
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 public int lastKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 throw new NoSuchElementException();
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59 return keys[size-1];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 public void trimToSize() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 if (size < keys.length) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 int[] newKeys = new int[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 Object[] newValues = new Object[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 System.arraycopy(keys, 0, newKeys, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 System.arraycopy(values, 0, newValues, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 public void put(int key, V value) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 if (ix < 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 final int insertPoint = -ix - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 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
78 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
79 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
80 int newCapacity = size + (capInc < 2 ? 2 : capInc) ;
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 int[] newKeys = new int[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 Object[] newValues = new Object[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 System.arraycopy(keys, 0, newKeys, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 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
85 System.arraycopy(values, 0, newValues, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 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
87 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 // arrays got enough capacity
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 if (insertPoint != size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 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
93 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
94 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 // 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
96 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 keys[insertPoint] = key;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 values[insertPoint] = value;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 size++;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 values[ix] = value;
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
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 public boolean containsKey(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 return binarySearch(keys, size, key) >= 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 @SuppressWarnings("unchecked")
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 public V get(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 if (ix >= 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 return (V) values[ix];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 return null;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 }
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
117
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
118 public void remove(int key) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
119 int ix = binarySearch(keys, size, key);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
120 if (ix >= 0) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
121 if (ix <= size - 1) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
122 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
123 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
124 } // 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
125 size--;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
126 keys[size] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
127 values[size] = null;
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 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
130
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
131 public void clear() {
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
132 Arrays.fill(values, 0, size, null); // do not keep the references
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
133 size = 0;
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
134 }
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
135
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
136 /**
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
137 * 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
138 */
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
139 @Experimental
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
140 public void removeFromStart(int count) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
141 if (count > 0 && count <= size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
142 if (count < size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
143 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
144 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
145 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
146 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
147 keys[i] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
148 values[i] = null;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
149 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
150 size -= count;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
151 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
152 }
415
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
153
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
154 // document iterator is non-modifying (neither remove() nor setValue() works)
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
155 // perhaps, may also implement Iterable<Map.Entry> to use nice for()
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
156 public Iterator<Map.Entry<Integer, V>> entryIterator() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
157 class E implements Map.Entry<Integer, V> {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
158 private Integer key;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
159 private V value;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
160
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
161 public Integer getKey() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
162 return key;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
163 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
164
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
165 public V getValue() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
166 return value;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
167 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
168
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
169 public V setValue(V value) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
170 throw new UnsupportedOperationException();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
171 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
172
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
173 void init(Integer k, V v) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
174 key = k;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
175 value = v;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
176 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
177 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
178
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
179 return new Iterator<Map.Entry<Integer, V>>() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
180 private int i = 0;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
181 private final E entry = new E();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
182 private final int _size;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
183 private final int[] _keys;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
184 private final Object[] _values;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
185
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
186 {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
187 _size = IntMap.this.size;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
188 _keys = IntMap.this.keys;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
189 _values = IntMap.this.values;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
190 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
191
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
192 public boolean hasNext() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
193 return i < _size;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
194 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
195
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
196 public Entry<Integer, V> next() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
197 if (i >= _size) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
198 throw new NoSuchElementException();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
199 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
200 @SuppressWarnings("unchecked")
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
201 V val = (V) _values[i];
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
202 entry.init(_keys[i], val);
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
203 i++;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
204 return entry;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
205 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
206
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
207 public void remove() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
208 throw new UnsupportedOperationException();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
209 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
210 };
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
211 }
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
212
415
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
213 public Map<Integer, ? super V> fill(Map<Integer, ? super V> map) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
214 for (Iterator<Map.Entry<Integer, V>> it = entryIterator(); it.hasNext(); ) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
215 Map.Entry<Integer, V> next = it.next();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
216 map.put(next.getKey(), next.getValue());
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
217 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
218 return map;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
219 }
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
220
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
221 // 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
222 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
223 int low = 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
224 high--;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
225
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
226 while (low <= high) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
227 int mid = (low + high) >> 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
228 int midVal = a[mid];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
229
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
230 if (midVal < key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
231 low = mid + 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
232 else if (midVal > key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
233 high = mid - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
234 else
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
235 return mid; // key found
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
236 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
237 return -(low + 1); // key not found.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
238 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
239 }