Mercurial > jhg

comparison src/org/tmatesoft/hg/internal/IntMap.java @ 276:6355ecda1f08

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