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 /** A more efficient List<Long> using a primitive long array. */
50 public class LongList {
51 private long[] entries;
52
53 private int count;
54
55 /** Create an empty list with a default capacity. */
56 public LongList() {
57 this(10);
58 }
59
60 /**
61 * Create an empty list with the specified capacity.
62 *
63 * @param capacity
64 * number of entries the list can initially hold.
65 */
66 public LongList(final int capacity) {
67 entries = new long[capacity];
68 }
69
70 /** @return number of entries in this list */
71 public int size() {
72 return count;
73 }
74
75 /**
76 * @param i
77 * index to read, must be in the range [0, {@link #size()}).
78 * @return the number at the specified index
79 * @throws ArrayIndexOutOfBoundsException
80 * the index outside the valid range
81 */
82 public long get(final int i) {
83 if (count <= i)
84 throw new ArrayIndexOutOfBoundsException(i);
85 return entries[i];
86 }
87
88 /**
89 * Determine if an entry appears in this collection.
90 *
91 * @param value
92 * the value to search for.
93 * @return true of {@code value} appears in this list.
94 */
95 public boolean contains(final long value) {
96 for (int i = 0; i < count; i++)
97 if (entries[i] == value)
98 return true;
99 return false;
100 }
101
102 /** Empty this list */
103 public void clear() {
104 count = 0;
105 }
106
107 /**
108 * Add an entry to the end of the list.
109 *
110 * @param n
111 * the number to add.
112 */
113 public void add(final long n) {
114 if (count == entries.length)
115 grow();
116 entries[count++] = n;
117 }
118
119 /**
120 * Assign an entry in the list.
121 *
122 * @param index
123 * index to set, must be in the range [0, {@link #size()}).
124 * @param n
125 * value to store at the position.
126 */
127 public void set(final int index, final long n) {
128 if (count < index)
129 throw new ArrayIndexOutOfBoundsException(index);
130 else if (count == index)
131 add(n);
132 else
133 entries[index] = n;
134 }
135
136 /**
137 * Pad the list with entries.
138 *
139 * @param toIndex
140 * index position to stop filling at. 0 inserts no filler. 1
141 * ensures the list has a size of 1, adding <code>val</code> if
142 * the list is currently empty.
143 * @param val
144 * value to insert into padded positions.
145 */
146 public void fillTo(int toIndex, final long val) {
147 while (count < toIndex)
148 add(val);
149 }
150
151 /** Sort the list of longs according to their natural ordering. */
152 public void sort() {
153 Arrays.sort(entries, 0, count);
154 }
155
156 private void grow() {
157 final long[] n = new long[(entries.length + 16) * 3 / 2];
158 System.arraycopy(entries, 0, n, 0, count);
159 entries = n;
160 }
161
162 @Override
163 public String toString() {
164 final StringBuilder r = new StringBuilder();
165 r.append('[');
166 for (int i = 0; i < count; i++) {
167 if (i > 0)
168 r.append(", "); //$NON-NLS-1$
169 r.append(entries[i]);
170 }
171 r.append(']');
172 return r.toString();
173 }
174 }