/**
* Copyright 2014 Netflix, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package rx.internal.util;
import java.util.*;
/**
* A list implementation which combines an ArrayList with a LinkedList to
* avoid copying values when the capacity needs to be increased.
* <p>
* The class is non final to allow embedding it directly and thus saving on object allocation.
*/
public class
LinkedArrayList {
/** The capacity of each array segment. */
final int
capacityHint;
/**
* Contains the head of the linked array list if not null. The
* length is always capacityHint + 1 and the last element is an Object[] pointing
* to the next element of the linked array list.
*/
Object[]
head;
/** The tail array where new elements will be added. */
Object[]
tail;
/**
* The total size of the list; written after elements have been added (release) and
* and when read, the value indicates how many elements can be safely read (acquire).
*/
volatile int
size;
/** The next available slot in the current tail. */
int
indexInTail;
/**
* Constructor with the capacity hint of each array segment.
* @param capacityHint the hint used for pre-sizing the internal array
*/
public
LinkedArrayList(int
capacityHint) {
this.
capacityHint =
capacityHint;
}
/**
* Adds a new element to this list.
* @param o the object to add, nulls are accepted
*/
public void
add(
Object o) {
// if no value yet, create the first array
if (
size == 0) {
head = new
Object[
capacityHint + 1];
tail =
head;
head[0] =
o;
indexInTail = 1;
size = 1;
} else
// if the tail is full, create a new tail and link
if (
indexInTail ==
capacityHint) {
Object[]
t = new
Object[
capacityHint + 1];
t[0] =
o;
tail[
capacityHint] =
t;
tail =
t;
indexInTail = 1;
size++;
} else {
tail[
indexInTail] =
o;
indexInTail++;
size++;
}
}
/**
* Returns the head buffer segment or null if the list is empty.
* @return the head object array
*/
public
Object[]
head() {
return
head; // NOPMD
}
/**
* Returns the tail buffer segment or null if the list is empty.
* @return the tail object array
*/
public
Object[]
tail() {
return
tail; // NOPMD
}
/**
* Returns the total size of the list.
* @return the total size of the list
*/
public int
size() {
return
size;
}
/**
* Returns the index of the next slot in the tail buffer segment.
* @return the index of the next slot in the tail buffer segment
*/
public int
indexInTail() {
return
indexInTail;
}
/**
* Returns the capacity hint that indicates the capacity of each buffer segment.
* @return the capacity hint that indicates the capacity of each buffer segment
*/
public int
capacityHint() {
return
capacityHint;
}
/* Test support */
List<
Object>
toList() {
final int
cap =
capacityHint;
final int
s =
size;
final
List<
Object>
list = new
ArrayList<
Object>(
s + 1);
Object[]
h =
head();
int
j = 0;
int
k = 0;
while (
j <
s) {
list.
add(
h[
k]);
j++;
if (++
k ==
cap) {
k = 0;
h = (
Object[])
h[
cap];
}
}
return
list;
}
@
Override
public
String toString() {
return
toList().
toString();
}
}