1 /*
2 * Copyright (C) 2009, Christian Halstrick <christian.halstrick@sap.com>
3 * Copyright (C) 2009, Google Inc.
4 * and other copyright owners as documented in the project's IP log.
5 *
6 * This program and the accompanying materials are made available
7 * under the terms of the Eclipse Distribution License v1.0 which
8 * accompanies this distribution, is reproduced below, and is
9 * available at http://www.eclipse.org/org/documents/edl-v10.php
10 *
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or
14 * without modification, are permitted provided that the following
15 * conditions are met:
16 *
17 * - Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 *
20 * - Redistributions in binary form must reproduce the above
21 * copyright notice, this list of conditions and the following
22 * disclaimer in the documentation and/or other materials provided
23 * with the distribution.
24 *
25 * - Neither the name of the Eclipse Foundation, Inc. nor the
26 * names of its contributors may be used to endorse or promote
27 * products derived from this software without specific prior
28 * written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
31 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
32 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
33 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
34 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
35 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
36 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
37 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
38 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
39 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
42 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 */
44
45 package org.eclipse.jgit.util;
46
47 import java.util.Arrays;
48
49 /**
50 * A more efficient List<Long> using a primitive long array.
51 */
52 public class LongList {
53 private long[] entries;
54
55 private int count;
56
57 /**
58 * Create an empty list with a default capacity.
59 */
60 public LongList() {
61 this(10);
62 }
63
64 /**
65 * Create an empty list with the specified capacity.
66 *
67 * @param capacity
68 * number of entries the list can initially hold.
69 */
70 public LongList(int capacity) {
71 entries = new long[capacity];
72 }
73
74 /**
75 * Get number of entries in this list
76 *
77 * @return number of entries in this list
78 */
79 public int size() {
80 return count;
81 }
82
83 /**
84 * Get the value at the specified index
85 *
86 * @param i
87 * index to read, must be in the range [0, {@link #size()}).
88 * @return the number at the specified index
89 * @throws java.lang.ArrayIndexOutOfBoundsException
90 * the index outside the valid range
91 */
92 public long get(int i) {
93 if (count <= i)
94 throw new ArrayIndexOutOfBoundsException(i);
95 return entries[i];
96 }
97
98 /**
99 * Determine if an entry appears in this collection.
100 *
101 * @param value
102 * the value to search for.
103 * @return true of {@code value} appears in this list.
104 */
105 public boolean contains(long value) {
106 for (int i = 0; i < count; i++)
107 if (entries[i] == value)
108 return true;
109 return false;
110 }
111
112 /**
113 * Clear this list
114 */
115 public void clear() {
116 count = 0;
117 }
118
119 /**
120 * Add an entry to the end of the list.
121 *
122 * @param n
123 * the number to add.
124 */
125 public void add(long n) {
126 if (count == entries.length)
127 grow();
128 entries[count++] = n;
129 }
130
131 /**
132 * Assign an entry in the list.
133 *
134 * @param index
135 * index to set, must be in the range [0, {@link #size()}).
136 * @param n
137 * value to store at the position.
138 */
139 public void set(int index, long n) {
140 if (count < index)
141 throw new ArrayIndexOutOfBoundsException(index);
142 else if (count == index)
143 add(n);
144 else
145 entries[index] = n;
146 }
147
148 /**
149 * Pad the list with entries.
150 *
151 * @param toIndex
152 * index position to stop filling at. 0 inserts no filler. 1
153 * ensures the list has a size of 1, adding <code>val</code> if
154 * the list is currently empty.
155 * @param val
156 * value to insert into padded positions.
157 */
158 public void fillTo(int toIndex, long val) {
159 while (count < toIndex)
160 add(val);
161 }
162
163 /**
164 * Sort the list of longs according to their natural ordering.
165 */
166 public void sort() {
167 Arrays.sort(entries, 0, count);
168 }
169
170 private void grow() {
171 final long[] n = new long[(entries.length + 16) * 3 / 2];
172 System.arraycopy(entries, 0, n, 0, count);
173 entries = n;
174 }
175
176 /** {@inheritDoc} */
177 @Override
178 public String toString() {
179 final StringBuilder r = new StringBuilder();
180 r.append('[');
181 for (int i = 0; i < count; i++) {
182 if (i > 0)
183 r.append(", "); //$NON-NLS-1$
184 r.append(entries[i]);
185 }
186 r.append(']');
187 return r.toString();
188 }
189 }