Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/IntMap.java @ 430:d280759c2a3f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
branch information is not directly related to dirstate, clean API from this dependency
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 29 Mar 2012 18:48:23 +0200
parents ccd7d25e5aea
children 7bcfbc255f48
rev   line source
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
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
2 * Copyright (c) 2011-2012 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
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
19 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
20 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
21 import java.util.Map.Entry;
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22 import java.util.NoSuchElementException;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23
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 * 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
27 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 * @author Artem Tikhomirov
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 * @author TMate Software Ltd.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 */
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 public class IntMap<V> {
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 private int[] keys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 private Object[] values;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 private int size;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 public IntMap(int size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 keys = new int[size <= 0 ? 16 : size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39 values = new Object[keys.length];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 }
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 public int size() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 return size;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 public int firstKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 throw new NoSuchElementException();
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 return keys[0];
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
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 public int lastKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 throw new NoSuchElementException();
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 return keys[size-1];
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
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 public void trimToSize() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 if (size < keys.length) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 int[] newKeys = new int[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 Object[] newValues = new Object[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 System.arraycopy(keys, 0, newKeys, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 System.arraycopy(values, 0, newValues, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 }
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 public void put(int key, V value) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 if (ix < 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 final int insertPoint = -ix - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 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
76 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
77 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
78 int newCapacity = size + (capInc < 2 ? 2 : capInc) ;
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 int[] newKeys = new int[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 Object[] newValues = new Object[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 System.arraycopy(keys, 0, newKeys, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 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
83 System.arraycopy(values, 0, newValues, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 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
85 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 // arrays got enough capacity
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 if (insertPoint != size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 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
91 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
92 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 // 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
94 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 keys[insertPoint] = key;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 values[insertPoint] = value;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 size++;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 values[ix] = value;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 }
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 public boolean containsKey(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 return binarySearch(keys, size, key) >= 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 @SuppressWarnings("unchecked")
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 public V get(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 if (ix >= 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 return (V) values[ix];
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 return null;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 }
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
115
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
116 public void remove(int key) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
117 int ix = binarySearch(keys, size, key);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
118 if (ix >= 0) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
119 if (ix <= size - 1) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
120 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
121 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
122 } // 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
123 size--;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
124 keys[size] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
125 values[size] = null;
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 }
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 * 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
131 */
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
132 @Experimental
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
133 public void removeFromStart(int count) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
134 if (count > 0 && count <= size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
135 if (count < size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
136 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
137 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
138 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
139 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
140 keys[i] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
141 values[i] = null;
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 size -= count;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
144 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
145 }
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
146
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
147 // 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
148 // 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
149 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
150 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
151 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
152 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
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 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
155 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
156 }
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
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 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
159 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
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
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 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
163 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
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
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 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
167 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
168 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
169 }
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 }
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 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
173 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
174 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
175 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
176 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
177 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
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 {
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 _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
181 _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
182 _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
183 }
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
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 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
186 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
187 }
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
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 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
190 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
191 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
192 }
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 @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
194 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
195 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
196 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
197 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
198 }
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 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
201 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
202 }
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 };
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 }
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
205
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
206 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
207 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
208 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
209 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
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 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
212 }
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
213
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
214 // 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
215 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
216 int low = 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
217 high--;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
218
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
219 while (low <= high) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
220 int mid = (low + high) >> 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
221 int midVal = a[mid];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
222
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
223 if (midVal < key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
224 low = mid + 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
225 else if (midVal > key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
226 high = mid - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
227 else
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
228 return mid; // key found
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 return -(low + 1); // key not found.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
231 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
232 }