/*

**** BEGIN LICENSE BLOCK *****

* Version: EPL 1.0/GPL 2.0/LGPL 2.1

*

* The contents of this file are subject to the Eclipse Public

* License Version 1.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.eclipse.org/legal/epl-v10.html

*

* Software distributed under the License is distributed on an "AS

* IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or

* implied. See the License for the specific language governing

* rights and limitations under the License.

*

* Copyright (C) 2001 Alan Moore <alan_moore@gmx.net>

* Copyright (C) 2001 Chad Fowler <chadfowler@chadfowler.com>

* Copyright (C) 2001-2002 Benoit Cerrina <b.cerrina@wanadoo.fr>

* Copyright (C) 2001-2004 Jan Arne Petersen <jpetersen@uni-bonn.de>

* Copyright (C) 2002-2004 Anders Bengtsson <ndrsbngtssn@yahoo.se>

* Copyright (C) 2002-2005 Thomas E Enebo <enebo@acm.org>

* Copyright (C) 2004-2005 Charles O Nutter <headius@headius.com>

* Copyright (C) 2004 Stefan Matthias Aust <sma@3plus4.de>

* Copyright (C) 2006 Ola Bini <Ola.Bini@ki.se>

* Copyright (C) 2006 Daniel Steer <damian.steer@hp.com>

*

* Alternatively, the contents of this file may be used under the terms of

* either of the GNU General Public License Version 2 or later (the "GPL"),

* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),

* in which case the provisions of the GPL or the LGPL are applicable instead

* of those above. If you wish to allow use of your version of this file only

* under the terms of either the GPL or the LGPL, and not to allow others to

* use your version of this file under the terms of the EPL, indicate your

* decision by deleting the provisions above and replace them with the notice

* and other provisions required by the GPL or the LGPL. If you do not delete

* the provisions above, a recipient may use your version of this file under

* the terms of any one of the EPL, the GPL or the LGPL.

***** END LICENSE BLOCK *****/

package org.jruby;

import static org.jruby.RubyEnumerator.enumeratorize;

import java.io.IOException;

import java.lang.reflect.Array;

import java.util.Arrays;

import java.util.Collection;

import java.util.Comparator;

import java.util.IdentityHashMap;

import java.util.Iterator;

import java.util.List;

import java.util.ListIterator;

import java.util.RandomAccess;

import java.util.concurrent.Callable;

import org.jcodings.Encoding;

import org.jcodings.specific.USASCIIEncoding;

import org.jruby.anno.JRubyClass;

import org.jruby.anno.JRubyMethod;

import org.jruby.common.IRubyWarnings.ID;

import org.jruby.javasupport.JavaUtil;

import org.jruby.javasupport.util.RuntimeHelpers;

import org.jruby.runtime.Arity;

import org.jruby.runtime.Block;

import org.jruby.runtime.BlockBody;

import org.jruby.runtime.ClassIndex;

import org.jruby.runtime.ObjectAllocator;

import org.jruby.runtime.ThreadContext;

import static org.jruby.runtime.Visibility.*;

import static org.jruby.CompatVersion.*;

import org.jruby.java.util.ArrayUtils;

import org.jruby.runtime.builtin.IRubyObject;

import org.jruby.runtime.encoding.EncodingCapable;

import org.jruby.runtime.invokedynamic.MethodNames;

import org.jruby.runtime.marshal.MarshalStream;

import org.jruby.runtime.marshal.UnmarshalStream;

import org.jruby.util.ByteList;

import org.jruby.util.Pack;

import org.jruby.util.Qsort;

import org.jruby.util.RecursiveComparator;

import org.jruby.util.TypeConverter;

import static org.jruby.javasupport.util.RuntimeHelpers.invokedynamic;

import static org.jruby.runtime.invokedynamic.MethodNames.HASH;

import static org.jruby.runtime.invokedynamic.MethodNames.OP_CMP;

import org.jruby.util.Numeric;

/**

* The implementation of the built-in class Array in Ruby.

*

* Concurrency: no synchronization is required among readers, but

* all users must synchronize externally with writers.

*

*/

@JRubyClass(name="Array")

public class RubyArray extends RubyObject implements List, RandomAccess {

public static final int DEFAULT_INSPECT_STR_SIZE = 10;

public static RubyClass createArrayClass(Ruby runtime) {

RubyClass arrayc = runtime.defineClass("Array", runtime.getObject(), ARRAY_ALLOCATOR);

runtime.setArray(arrayc);

arrayc.index = ClassIndex.ARRAY;

arrayc.setReifiedClass(RubyArray.class);

arrayc.kindOf = new RubyModule.KindOf() {

@Override

public boolean isKindOf(IRubyObject obj, RubyModule type) {

return obj instanceof RubyArray;

}

};

arrayc.includeModule(runtime.getEnumerable());

arrayc.defineAnnotatedMethods(RubyArray.class);

return arrayc;

}

private static ObjectAllocator ARRAY_ALLOCATOR = new ObjectAllocator() {

public IRubyObject allocate(Ruby runtime, RubyClass klass) {

return new RubyArray(runtime, klass, IRubyObject.NULL_ARRAY);

}

};

@Override

public int getNativeTypeIndex() {

return ClassIndex.ARRAY;

}

private final void concurrentModification() {

concurrentModification(getRuntime());

}

private static void concurrentModification(Ruby runtime) {

throw runtime.newConcurrencyError("Detected invalid array contents due to unsynchronized modifications with concurrent users");

}

/** rb_ary_s_create

*

*/

@JRubyMethod(name = "[]", rest = true, meta = true)

public static IRubyObject create(IRubyObject klass, IRubyObject[] args, Block block) {

RubyArray arr = (RubyArray) ((RubyClass) klass).allocate();

if (args.length > 0) {

arr.values = new IRubyObject[args.length];

System.arraycopy(args, 0, arr.values, 0, args.length);

arr.realLength = args.length;

}

return arr;

}

/** rb_ary_new2

*

*/

public static final RubyArray newArray(final Ruby runtime, final long len) {

checkLength(runtime, len);

return newArray(runtime, (int)len);

}

public static final RubyArray newArrayLight(final Ruby runtime, final long len) {

checkLength(runtime, len);

return newArrayLight(runtime, (int)len);

}

public static final RubyArray newArray(final Ruby runtime, final int len) {

RubyArray array = new RubyArray(runtime, len);

RuntimeHelpers.fillNil(array.values, 0, array.values.length, runtime);

return array;

}

public static final RubyArray newArrayLight(final Ruby runtime, final int len) {

RubyArray array = new RubyArray(runtime, len, false);

RuntimeHelpers.fillNil(array.values, 0, array.values.length, runtime);

return array;

}

/** rb_ary_new

*

*/

public static final RubyArray newArray(final Ruby runtime) {

return newArray(runtime, ARRAY_DEFAULT_SIZE);

}

/** rb_ary_new

*

*/

public static final RubyArray newArrayLight(final Ruby runtime) {

/* Ruby arrays default to holding 16 elements, so we create an

* ArrayList of the same size if we're not told otherwise

*/

return newArrayLight(runtime, ARRAY_DEFAULT_SIZE);

}

public static RubyArray newArray(Ruby runtime, IRubyObject obj) {

return new RubyArray(runtime, new IRubyObject[] { obj });

}

public static RubyArray newArrayLight(Ruby runtime, IRubyObject obj) {

return new RubyArray(runtime, new IRubyObject[] { obj }, false);

}

public static RubyArray newArrayLight(Ruby runtime, IRubyObject... objs) {

return new RubyArray(runtime, objs, false);

}

/** rb_assoc_new

*

*/

public static RubyArray newArray(Ruby runtime, IRubyObject car, IRubyObject cdr) {

return new RubyArray(runtime, new IRubyObject[] { car, cdr });

}

public static RubyArray newEmptyArray(Ruby runtime) {

return new RubyArray(runtime, NULL_ARRAY);

}

/** rb_ary_new4, rb_ary_new3

*

*/

public static RubyArray newArray(Ruby runtime, IRubyObject[] args) {

RubyArray arr = new RubyArray(runtime, new IRubyObject[args.length]);

System.arraycopy(args, 0, arr.values, 0, args.length);

arr.realLength = args.length;

return arr;

}

public static RubyArray newArrayNoCopy(Ruby runtime, IRubyObject[] args) {

return new RubyArray(runtime, args);

}

public static RubyArray newArrayNoCopy(Ruby runtime, IRubyObject[] args, int begin) {

return new RubyArray(runtime, args, begin);

}

public static RubyArray newArrayNoCopy(Ruby runtime, IRubyObject[] args, int begin, int length) {

assert begin >= 0 : "begin must be >= 0";

assert length >= 0 : "length must be >= 0";

return new RubyArray(runtime, args, begin, length);

}

public static RubyArray newArrayNoCopyLight(Ruby runtime, IRubyObject[] args) {

RubyArray arr = new RubyArray(runtime, false);

arr.values = args;

arr.realLength = args.length;

return arr;

}

public static RubyArray newArray(Ruby runtime, Collection<? extends IRubyObject> collection) {

return new RubyArray(runtime, collection.toArray(new IRubyObject[collection.size()]));

}

public static final int ARRAY_DEFAULT_SIZE = 16;

// volatile to ensure that initial nil-fill is visible to other threads

private volatile IRubyObject[] values;

private static final int TMPLOCK_ARR_F = 1 << 9;

private static final int TMPLOCK_OR_FROZEN_ARR_F = TMPLOCK_ARR_F | FROZEN_F;

private volatile boolean isShared = false;

private int begin = 0;

private int realLength = 0;

/*

* plain internal array assignment

*/

private RubyArray(Ruby runtime, IRubyObject[] vals) {

super(runtime, runtime.getArray());

values = vals;

realLength = vals.length;

}

/*

* plain internal array assignment

*/

private RubyArray(Ruby runtime, IRubyObject[] vals, boolean objectSpace) {

super(runtime, runtime.getArray(), objectSpace);

values = vals;

realLength = vals.length;

}

/*

* plain internal array assignment

*/

private RubyArray(Ruby runtime, IRubyObject[] vals, int begin) {

super(runtime, runtime.getArray());

this.values = vals;

this.begin = begin;

this.realLength = vals.length - begin;

this.isShared = true;

}

private RubyArray(Ruby runtime, IRubyObject[] vals, int begin, int length) {

super(runtime, runtime.getArray());

this.values = vals;

this.begin = begin;

this.realLength = length;

this.isShared = true;

}

private RubyArray(Ruby runtime, RubyClass metaClass, IRubyObject[] vals, int begin, int length) {

super(runtime, metaClass);

this.values = vals;

this.begin = begin;

this.realLength = length;

this.isShared = true;

}

protected RubyArray(Ruby runtime, int length) {

super(runtime, runtime.getArray());

values = new IRubyObject[length];

}

private RubyArray(Ruby runtime, int length, boolean objectspace) {

super(runtime, runtime.getArray(), objectspace);

values = new IRubyObject[length];

}

/* NEWOBJ and OBJSETUP equivalent

* fastest one, for shared arrays, optional objectspace

*/

private RubyArray(Ruby runtime, boolean objectSpace) {

super(runtime, runtime.getArray(), objectSpace);

}

private RubyArray(Ruby runtime, RubyClass klass) {

super(runtime, klass);

}

/* Array constructors taking the MetaClass to fulfil MRI Array subclass behaviour

*

*/

private RubyArray(Ruby runtime, RubyClass klass, int length) {

super(runtime, klass);

values = new IRubyObject[length];

}

private RubyArray(Ruby runtime, RubyClass klass, IRubyObject[]vals, boolean objectspace) {

super(runtime, klass, objectspace);

values = vals;

}

private RubyArray(Ruby runtime, RubyClass klass, boolean objectSpace) {

super(runtime, klass, objectSpace);

}

private RubyArray(Ruby runtime, RubyClass klass, RubyArray original) {

super(runtime, klass);

realLength = original.realLength;

values = new IRubyObject[realLength];

safeArrayCopy(runtime, original.values, original.begin, values, 0, realLength);

}

private RubyArray(Ruby runtime, RubyClass klass, IRubyObject[] vals) {

super(runtime, klass);

values = vals;

realLength = vals.length;

}

private void alloc(int length) {

final IRubyObject[] newValues = new IRubyObject[length];

RuntimeHelpers.fillNil(newValues, getRuntime());

values = newValues;

begin = 0;

}

private void realloc(int newLength, int valuesLength) {

IRubyObject[] reallocated = new IRubyObject[newLength];

if (newLength > valuesLength) {

RuntimeHelpers.fillNil(reallocated, valuesLength, newLength, getRuntime());

safeArrayCopy(values, begin, reallocated, 0, valuesLength); // elements and trailing nils

} else {

safeArrayCopy(values, begin, reallocated, 0, newLength); // ???

}

begin = 0;

values = reallocated;

}

private static void fill(IRubyObject[]arr, int from, int to, IRubyObject with) {

for (int i=from; i<to; i++) {

arr[i] = with;

}

}

private static final void checkLength(Ruby runtime, long length) {

if (length < 0) {

throw runtime.newArgumentError("negative array size (or size too big)");

}

if (length >= Integer.MAX_VALUE) {

throw runtime.newArgumentError("array size too big");

}

}

/** Getter for property list.

* @return Value of property list.

*/

public List getList() {

return Arrays.asList(toJavaArray());

}

public int getLength() {

return realLength;

}

public IRubyObject[] toJavaArray() {

IRubyObject[] copy = new IRubyObject[realLength];

safeArrayCopy(values, begin, copy, 0, realLength);

return copy;

}

public IRubyObject[] toJavaArrayUnsafe() {

return !isShared ? values : toJavaArray();

}

public IRubyObject[] toJavaArrayMaybeUnsafe() {

return (!isShared && begin == 0 && values.length == realLength) ? values : toJavaArray();

}

/** rb_ary_make_shared

*

*/

private RubyArray makeShared() {

return makeShared(begin, realLength, getMetaClass());

}

private RubyArray makeShared(int beg, int len, RubyClass klass) {

return makeShared(beg, len, new RubyArray(klass.getRuntime(), klass));

}

private RubyArray makeShared(int beg, int len, RubyArray sharedArray) {

isShared = true;

sharedArray.values = values;

sharedArray.isShared = true;

sharedArray.begin = beg;

sharedArray.realLength = len;

return sharedArray;

}

/** ary_shared_first

*

*/

private RubyArray makeSharedFirst(ThreadContext context, IRubyObject num, boolean last, RubyClass klass) {

int n = RubyNumeric.num2int(num);

if (n > realLength) {

n = realLength;

} else if (n < 0) {

throw context.runtime.newArgumentError("negative array size");

}

return makeShared(last ? begin + realLength - n : begin, n, klass);

}

/** rb_ary_modify_check

*

*/

private final void modifyCheck() {

if ((flags & TMPLOCK_OR_FROZEN_ARR_F) != 0) {

if ((flags & FROZEN_F) != 0) throw getRuntime().newFrozenError("array");

if ((flags & TMPLOCK_ARR_F) != 0) throw getRuntime().newTypeError("can't modify array during iteration");

}

}

/** rb_ary_modify

*

*/

private final void modify() {

modifyCheck();

if (isShared) {

IRubyObject[] vals = new IRubyObject[realLength];

safeArrayCopy(values, begin, vals, 0, realLength);

begin = 0;

values = vals;

isShared = false;

}

}

/* ================

* Instance Methods

* ================

*/

/**

* Variable arity version for compatibility. Not bound to a Ruby method.

* @deprecated Use the versions with zero, one, or two args.

*/

public IRubyObject initialize(ThreadContext context, IRubyObject[] args, Block block) {

switch (args.length) {

case 0:

return initialize(context, block);

case 1:

return initializeCommon(context, args[0], null, block);

case 2:

return initializeCommon(context, args[0], args[1], block);

default:

Arity.raiseArgumentError(getRuntime(), args.length, 0, 2);

return null; // not reached

}

}

/** rb_ary_initialize

*

*/

@JRubyMethod(visibility = PRIVATE)

public IRubyObject initialize(ThreadContext context, Block block) {

modifyCheck();

Ruby runtime = context.runtime;

realLength = 0;

if (block.isGiven() && runtime.isVerbose()) {

runtime.getWarnings().warning(ID.BLOCK_UNUSED, "given block not used");

}

return this;

}

/** rb_ary_initialize

*

*/

@JRubyMethod(visibility = PRIVATE)

public IRubyObject initialize(ThreadContext context, IRubyObject arg0, Block block) {

return initializeCommon(context, arg0, null, block);

}

/** rb_ary_initialize

*

*/

@JRubyMethod(visibility = PRIVATE)

public IRubyObject initialize(ThreadContext context, IRubyObject arg0, IRubyObject arg1, Block block) {

return initializeCommon(context, arg0, arg1, block);

}

private IRubyObject initializeCommon(ThreadContext context, IRubyObject arg0, IRubyObject arg1, Block block) {

Ruby runtime = context.runtime;

if (arg1 == null && !(arg0 instanceof RubyFixnum)) {

IRubyObject val = arg0.checkArrayType();

if (!val.isNil()) {

replace(val);

return this;

}

}

long len = RubyNumeric.num2long(arg0);

if (len < 0) throw runtime.newArgumentError("negative array size");

if (len >= Integer.MAX_VALUE) throw runtime.newArgumentError("array size too big");

int ilen = (int) len;

modify();

if (ilen > values.length - begin) {

values = new IRubyObject[ilen];

begin = 0;

}

if (block.isGiven()) {

if (arg1 != null) {

runtime.getWarnings().warn(ID.BLOCK_BEATS_DEFAULT_VALUE, "block supersedes default value argument");

}

if (block.getBody().getArgumentType() == BlockBody.ZERO_ARGS) {

IRubyObject nil = runtime.getNil();

for (int i = 0; i < ilen; i++) {

store(i, block.yield(context, nil));

realLength = i + 1;

}

} else {

for (int i = 0; i < ilen; i++) {

store(i, block.yield(context, RubyFixnum.newFixnum(runtime, i)));

realLength = i + 1;

}

}

} else {

try {

if (arg1 == null) {

RuntimeHelpers.fillNil(values, begin, begin + ilen, runtime);

} else {

fill(values, begin, begin + ilen, arg1);

}

} catch (ArrayIndexOutOfBoundsException e) {

concurrentModification();

}

realLength = ilen;

}

return this;

}

/** rb_ary_initialize_copy

*

*/

@JRubyMethod(name = {"initialize_copy"}, required = 1, visibility=PRIVATE)

@Override

public IRubyObject initialize_copy(IRubyObject orig) {

return this.replace(orig);

}

/**

* Overridden dup for fast-path logic.

*

* @return A new RubyArray sharing the original backing store.

*/

public IRubyObject dup() {

if (metaClass.index != ClassIndex.ARRAY) return super.dup();

RubyArray dup = new RubyArray(metaClass.getClassRuntime(), values, begin, realLength);

dup.isShared = isShared = true;

dup.flags |= flags & TAINTED_F; // from DUP_SETUP

dup.flags |= flags & UNTRUSTED_F;

return dup;

}

/** rb_ary_replace

*

*/

@JRubyMethod(name = {"replace"}, required = 1)

public IRubyObject replace(IRubyObject orig) {

modifyCheck();

RubyArray origArr = orig.convertToArray();

if (this == orig) return this;

origArr.isShared = true;

isShared = true;

values = origArr.values;

realLength = origArr.realLength;

begin = origArr.begin;

return this;

}

/** rb_ary_to_s

*

*/

@JRubyMethod(name = "to_s")

@Override

public IRubyObject to_s() {

if (getRuntime().is1_9()) {

// 1.9 seems to just do inspect for to_s now

return inspect();

}

if (realLength == 0) return RubyString.newEmptyString(getRuntime());

return join(getRuntime().getCurrentContext(), getRuntime().getGlobalVariables().get("$,"));

}

public boolean includes(ThreadContext context, IRubyObject item) {

int myBegin = this.begin;

int end = myBegin + realLength;

IRubyObject[] values = this.values;

for (int i = myBegin; i < end; i++) {

final IRubyObject value = safeArrayRef(values, i);

if (equalInternal(context, value, item)) return true;

}

return false;

}

/** rb_ary_hash

*

*/

@JRubyMethod(name = "hash", compat = RUBY1_8)

public RubyFixnum hash(ThreadContext context) {

Ruby runtime = context.runtime;

if (runtime.isInspecting(this)) return RubyFixnum.zero(runtime);

try {

runtime.registerInspecting(this);

int myBegin = this.begin;

int h = realLength;

for (int i = myBegin; i < myBegin + realLength; i++) {

h = (h << 1) | (h < 0 ? 1 : 0);

final IRubyObject value = safeArrayRef(values, i);

h ^= RubyNumeric.num2long(invokedynamic(context, value, HASH));

}

return runtime.newFixnum(h);

} finally {

runtime.unregisterInspecting(this);

}

}

/** rb_ary_hash

*

*/

@JRubyMethod(name = "hash", compat = RUBY1_9)

public RubyFixnum hash19(final ThreadContext context) {

return (RubyFixnum) getRuntime().execRecursiveOuter(new Ruby.RecursiveFunction() {

public IRubyObject call(IRubyObject obj, boolean recur) {

int begin = RubyArray.this.begin;

long h = realLength;

if (recur) {

h ^= RubyNumeric.num2long(invokedynamic(context, context.runtime.getArray(), HASH));

} else {

for (int i = begin; i < begin + realLength; i++) {

h = (h << 1) | (h < 0 ? 1 : 0);

final IRubyObject value = safeArrayRef(values, i);

h ^= RubyNumeric.num2long(invokedynamic(context, value, HASH));

}

}

return getRuntime().newFixnum(h);

}

}, RubyArray.this);

}

/** rb_ary_store

*

*/

public final IRubyObject store(long index, IRubyObject value) {

if (index < 0 && (index += realLength) < 0) throw getRuntime().newIndexError("index " + (index - realLength) + " out of array");

modify();

if (index >= realLength) {

int valuesLength = values.length - begin;

if (index >= valuesLength) storeRealloc(index, valuesLength);

realLength = (int) index + 1;

}

safeArraySet(values, begin + (int) index, value);

return value;

}

private void storeRealloc(long index, int valuesLength) {

long newLength = valuesLength >> 1;

if (newLength < ARRAY_DEFAULT_SIZE) newLength = ARRAY_DEFAULT_SIZE;

newLength += index;

if (index >= Integer.MAX_VALUE || newLength >= Integer.MAX_VALUE) {

throw getRuntime().newArgumentError("index too big");

}

realloc((int) newLength, valuesLength);

}

/** rb_ary_elt

*

*/

private final IRubyObject elt(long offset) {

if (offset < 0 || offset >= realLength) {

return getRuntime().getNil();

}

return eltOk(offset);

}

public final IRubyObject eltOk(long offset) {

return safeArrayRef(values, begin + (int)offset);

}

/** rb_ary_entry

*

*/

public final IRubyObject entry(long offset) {

return (offset < 0 ) ? elt(offset + realLength) : elt(offset);

}

public final IRubyObject entry(int offset) {

return (offset < 0 ) ? elt(offset + realLength) : elt(offset);

}

public final IRubyObject eltInternal(int offset) {

return values[begin + offset];

}

public final IRubyObject eltInternalSet(int offset, IRubyObject item) {

return values[begin + offset] = item;

}

/**

* Variable arity version for compatibility. Not bound to a Ruby method.

* @deprecated Use the versions with zero, one, or two args.

*/

public IRubyObject fetch(ThreadContext context, IRubyObject[] args, Block block) {

switch (args.length) {

case 1:

return fetch(context, args[0], block);

case 2:

return fetch(context, args[0], args[1], block);

default:

Arity.raiseArgumentError(getRuntime(), args.length, 1, 2);

return null; // not reached

}

}

/** rb_ary_fetch

*

*/

@JRubyMethod

public IRubyObject fetch(ThreadContext context, IRubyObject arg0, Block block) {

long index = RubyNumeric.num2long(arg0);

if (index < 0) index += realLength;

if (index < 0 || index >= realLength) {

if (block.isGiven()) return block.yield(context, arg0);

throw getRuntime().newIndexError("index " + index + " out of array");

}

return safeArrayRef(values, begin + (int) index);

}

/** rb_ary_fetch

*

*/

@JRubyMethod

public IRubyObject fetch(ThreadContext context, IRubyObject arg0, IRubyObject arg1, Block block) {

if (block.isGiven()) getRuntime().getWarnings().warn(ID.BLOCK_BEATS_DEFAULT_VALUE, "block supersedes default value argument");

long index = RubyNumeric.num2long(arg0);

if (index < 0) index += realLength;

if (index < 0 || index >= realLength) {

if (block.isGiven()) return block.yield(context, arg0);

return arg1;

}

return safeArrayRef(values, begin + (int) index);

}

/** rb_ary_to_ary

*

*/

private static RubyArray aryToAry(IRubyObject obj) {

if (obj instanceof RubyArray) return (RubyArray) obj;

if (obj.respondsTo("to_ary")) return obj.convertToArray();

RubyArray arr = new RubyArray(obj.getRuntime(), false); // possibly should not in object space

arr.values = new IRubyObject[]{obj};

arr.realLength = 1;

return arr;

}

/** rb_ary_splice

*

*/

private final void splice(long beg, long len, IRubyObject rpl, boolean oneNine) {

if (len < 0) throw getRuntime().newIndexError("negative length (" + len + ")");

if (beg < 0 && (beg += realLength) < 0) throw getRuntime().newIndexError("index " + (beg - realLength) + " out of array");

final RubyArray rplArr;

final int rlen;

if (rpl == null || (rpl.isNil() && !oneNine)) {

rplArr = null;

rlen = 0;

} else if (rpl.isNil()) {

// 1.9 replaces with nil

rplArr = newArray(getRuntime(), rpl);

rlen = 1;

} else {

rplArr = aryToAry(rpl);

rlen = rplArr.realLength;

}

modify();

int valuesLength = values.length - begin;

if (beg >= realLength) {

len = beg + rlen;

if (len >= valuesLength) spliceRealloc((int)len, valuesLength);

try {

RuntimeHelpers.fillNil(values, begin + realLength, begin + ((int)beg), getRuntime());

} catch (ArrayIndexOutOfBoundsException e) {

concurrentModification();

}

realLength = (int) len;

} else {

if (beg + len > realLength) len = realLength - beg;

int alen = realLength + rlen - (int)len;

if (alen >= valuesLength) spliceRealloc(alen, valuesLength);

if (len != rlen) {

safeArrayCopy(values, begin + (int) (beg + len), values, begin + (int) beg + rlen, realLength - (int) (beg + len));

realLength = alen;

}

}

if (rlen > 0) {

safeArrayCopy(rplArr.values, rplArr.begin, values, begin + (int) beg, rlen);

}

}

/** rb_ary_splice

*

*/

private final void spliceOne(long beg, IRubyObject rpl) {

if (beg < 0 && (beg += realLength) < 0) throw getRuntime().newIndexError("index " + (beg - realLength) + " out of array");

modify();

int valuesLength = values.length - begin;

if (beg >= realLength) {

int len = (int)beg + 1;

if (len >= valuesLength) spliceRealloc((int)len, valuesLength);

RuntimeHelpers.fillNil(values, begin + realLength, begin + ((int)beg), getRuntime());

realLength = (int) len;

} else {

int len = beg > realLength ? realLength - (int)beg : 0;

int alen = realLength + 1 - len;

if (alen >= valuesLength) spliceRealloc((int)alen, valuesLength);

if (len == 0) {

safeArrayCopy(values, begin + (int) beg, values, begin + (int) beg + 1, realLength - (int) beg);

realLength = alen;

}

}

safeArraySet(values, begin + (int)beg, rpl);

}

private void spliceRealloc(int length, int valuesLength) {

int tryLength = valuesLength + (valuesLength >> 1);

int len = length > tryLength ? length : tryLength;

IRubyObject[] vals = new IRubyObject[len];

System.arraycopy(values, begin, vals, 0, realLength);

// only fill if there actually will remain trailing storage

if (len > length) RuntimeHelpers.fillNil(vals, length, len, getRuntime());

begin = 0;

values = vals;

}

@JRubyMethod

public IRubyObject insert() {

throw getRuntime().newArgumentError(0, 1);

}

/** rb_ary_insert

*

*/

@JRubyMethod(name = "insert", compat = RUBY1_8)

public IRubyObject insert(IRubyObject arg) {

return this;

}

@JRubyMethod(name = "insert", compat = RUBY1_9)

public IRubyObject insert19(IRubyObject arg) {

modifyCheck();

return insert(arg);

}

@JRubyMethod(name = "insert", compat = RUBY1_8)

public IRubyObject insert(IRubyObject arg1, IRubyObject arg2) {

long pos = RubyNumeric.num2long(arg1);

if (pos == -1) pos = realLength;

if (pos < 0) pos++;

spliceOne(pos, arg2); // rb_ary_new4

return this;

}

@JRubyMethod(name = "insert", compat = RUBY1_9)

public IRubyObject insert19(IRubyObject arg1, IRubyObject arg2) {

modifyCheck();

return insert(arg1, arg2);

}

@JRubyMethod(name = "insert", required = 1, rest = true, compat = RUBY1_8)

public IRubyObject insert(IRubyObject[] args) {

if (args.length == 1) return this;

long pos = RubyNumeric.num2long(args[0]);

if (pos == -1) pos = realLength;

if (pos < 0) pos++;

RubyArray inserted = new RubyArray(getRuntime(), false);

inserted.values = args;

inserted.begin = 1;

inserted.realLength = args.length - 1;

splice(pos, 0, inserted, false); // rb_ary_new4

return this;

}

@JRubyMethod(name = "insert", required = 1, rest = true, compat = RUBY1_9)

public IRubyObject insert19(IRubyObject[] args) {

modifyCheck();

return insert(args);

}

/** rb_ary_dup

*

*/

public final RubyArray aryDup() {

RubyArray dup = new RubyArray(metaClass.getClassRuntime(), metaClass, values, begin, realLength);

dup.isShared = true;

isShared = true;