Copyright (c) 2015, Emir Pasic. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
Package arraylist implements the array list. Structure is not thread safe. Reference: https://en.wikipedia.org/wiki/List_%28abstract_data_type%29
package arraylist

import (
	
	

	
	
)

func () {
	var  lists.List = (*List)(nil)
}
List holds the elements in a slice
type List struct {
	elements []interface{}
	size     int
}

const (
	growthFactor = float32(2.0)  // growth by 100%
	shrinkFactor = float32(0.25) // shrink when size is 25% of capacity (0 means never shrink)
)
New instantiates a new list and adds the passed values, if any, to the list
func ( ...interface{}) *List {
	 := &List{}
	if len() > 0 {
		.Add(...)
	}
	return 
}
Add appends a value at the end of the list
func ( *List) ( ...interface{}) {
	.growBy(len())
	for ,  := range  {
		.elements[.size] = 
		.size++
	}
}
Get returns the element at index. Second return parameter is true if index is within bounds of the array and array is not empty, otherwise false.
func ( *List) ( int) (interface{}, bool) {

	if !.withinRange() {
		return nil, false
	}

	return .elements[], true
}
Remove removes the element at the given index from the list.
func ( *List) ( int) {

	if !.withinRange() {
		return
	}

	.elements[] = nil                                    // cleanup reference
	copy(.elements[:], .elements[+1:.size]) // shift to the left by one (slow operation, need ways to optimize this)
	.size--

	.shrink()
}
Contains checks if elements (one or more) are present in the set. All elements have to be present in the set for the method to return true. Performance time complexity of n^2. Returns true if no arguments are passed at all, i.e. set is always super-set of empty set.
func ( *List) ( ...interface{}) bool {

	for ,  := range  {
		 := false
		for ,  := range .elements {
			if  ==  {
				 = true
				break
			}
		}
		if ! {
			return false
		}
	}
	return true
}
Values returns all elements in the list.
func ( *List) () []interface{} {
	 := make([]interface{}, .size, .size)
	copy(, .elements[:.size])
	return 
}
IndexOf returns index of provided element
func ( *List) ( interface{}) int {
	if .size == 0 {
		return -1
	}
	for ,  := range .elements {
		if  ==  {
			return 
		}
	}
	return -1
}
Empty returns true if list does not contain any elements.
func ( *List) () bool {
	return .size == 0
}
Size returns number of elements within the list.
func ( *List) () int {
	return .size
}
Clear removes all elements from the list.
func ( *List) () {
	.size = 0
	.elements = []interface{}{}
}
Sort sorts values (in-place) using.
func ( *List) ( utils.Comparator) {
	if len(.elements) < 2 {
		return
	}
	utils.Sort(.elements[:.size], )
}
Swap swaps the two values at the specified positions.
func ( *List) (,  int) {
	if .withinRange() && .withinRange() {
		.elements[], .elements[] = .elements[], .elements[]
	}
}
Insert inserts values at specified index position shifting the value at that position (if any) and any subsequent elements to the right. Does not do anything if position is negative or bigger than list's size Note: position equal to list's size is valid, i.e. append.
func ( *List) ( int,  ...interface{}) {

Append
		if  == .size {
			.Add(...)
		}
		return
	}

	 := len()
	.growBy()
	.size += 
	copy(.elements[+:], .elements[:.size-])
	copy(.elements[:], )
}
Set the value at specified index Does not do anything if position is negative or bigger than list's size Note: position equal to list's size is valid, i.e. append.
func ( *List) ( int,  interface{}) {

Append
		if  == .size {
			.Add()
		}
		return
	}

	.elements[] = 
}
String returns a string representation of container
func ( *List) () string {
	 := "ArrayList\n"
	 := []string{}
	for ,  := range .elements[:.size] {
		 = append(, fmt.Sprintf("%v", ))
	}
	 += strings.Join(, ", ")
	return 
}
Check that the index is within bounds of the list
func ( *List) ( int) bool {
	return  >= 0 &&  < .size
}

func ( *List) ( int) {
	 := make([]interface{}, , )
	copy(, .elements)
	.elements = 
}
Expand the array if necessary, i.e. capacity will be reached if we add n elements
When capacity is reached, grow by a factor of growthFactor and add number of elements
	 := cap(.elements)
	if .size+ >=  {
		 := int(growthFactor * float32(+))
		.resize()
	}
}
Shrink the array if necessary, i.e. when size is shrinkFactor percent of current capacity
func ( *List) () {
	if shrinkFactor == 0.0 {
		return
Shrink when size is at shrinkFactor * capacity
	 := cap(.elements)
	if .size <= int(float32()*shrinkFactor) {
		.resize(.size)
	}