LongList.java

  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. package org.eclipse.jgit.util;

  45. import java.util.Arrays;

  46. /**
  47.  * A more efficient List&lt;Long&gt; using a primitive long array.
  48.  */
  49. public class LongList {
  50.     private long[] entries;

  51.     private int count;

  52.     /**
  53.      * Create an empty list with a default capacity.
  54.      */
  55.     public LongList() {
  56.         this(10);
  57.     }

  58.     /**
  59.      * Create an empty list with the specified capacity.
  60.      *
  61.      * @param capacity
  62.      *            number of entries the list can initially hold.
  63.      */
  64.     public LongList(int capacity) {
  65.         entries = new long[capacity];
  66.     }

  67.     /**
  68.      * Get number of entries in this list
  69.      *
  70.      * @return number of entries in this list
  71.      */
  72.     public int size() {
  73.         return count;
  74.     }

  75.     /**
  76.      * Get the value at the specified index
  77.      *
  78.      * @param i
  79.      *            index to read, must be in the range [0, {@link #size()}).
  80.      * @return the number at the specified index
  81.      * @throws java.lang.ArrayIndexOutOfBoundsException
  82.      *             the index outside the valid range
  83.      */
  84.     public long get(int i) {
  85.         if (count <= i)
  86.             throw new ArrayIndexOutOfBoundsException(i);
  87.         return entries[i];
  88.     }

  89.     /**
  90.      * Determine if an entry appears in this collection.
  91.      *
  92.      * @param value
  93.      *            the value to search for.
  94.      * @return true of {@code value} appears in this list.
  95.      */
  96.     public boolean contains(long value) {
  97.         for (int i = 0; i < count; i++)
  98.             if (entries[i] == value)
  99.                 return true;
  100.         return false;
  101.     }

  102.     /**
  103.      * Clear this list
  104.      */
  105.     public void clear() {
  106.         count = 0;
  107.     }

  108.     /**
  109.      * Add an entry to the end of the list.
  110.      *
  111.      * @param n
  112.      *            the number to add.
  113.      */
  114.     public void add(long n) {
  115.         if (count == entries.length)
  116.             grow();
  117.         entries[count++] = n;
  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(int index, 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.      * Pad the list with entries.
  137.      *
  138.      * @param toIndex
  139.      *            index position to stop filling at. 0 inserts no filler. 1
  140.      *            ensures the list has a size of 1, adding <code>val</code> if
  141.      *            the list is currently empty.
  142.      * @param val
  143.      *            value to insert into padded positions.
  144.      */
  145.     public void fillTo(int toIndex, long val) {
  146.         while (count < toIndex)
  147.             add(val);
  148.     }

  149.     /**
  150.      * Sort the list of longs according to their natural ordering.
  151.      */
  152.     public void sort() {
  153.         Arrays.sort(entries, 0, count);
  154.     }

  155.     private void grow() {
  156.         final long[] n = new long[(entries.length + 16) * 3 / 2];
  157.         System.arraycopy(entries, 0, n, 0, count);
  158.         entries = n;
  159.     }

  160.     /** {@inheritDoc} */
  161.     @Override
  162.     public String toString() {
  163.         final StringBuilder r = new StringBuilder();
  164.         r.append('[');
  165.         for (int i = 0; i < count; i++) {
  166.             if (i > 0)
  167.                 r.append(", "); //$NON-NLS-1$
  168.             r.append(entries[i]);
  169.         }
  170.         r.append(']');
  171.         return r.toString();
  172.     }
  173. }