main
1// Copyright (c) 2015, Emir Pasic. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Package arraylist implements the array list.
6//
7// Structure is not thread safe.
8//
9// Reference: https://en.wikipedia.org/wiki/List_%28abstract_data_type%29
10package arraylist
11
12import (
13 "fmt"
14 "strings"
15
16 "github.com/emirpasic/gods/lists"
17 "github.com/emirpasic/gods/utils"
18)
19
20// Assert List implementation
21var _ lists.List = (*List)(nil)
22
23// List holds the elements in a slice
24type List struct {
25 elements []interface{}
26 size int
27}
28
29const (
30 growthFactor = float32(2.0) // growth by 100%
31 shrinkFactor = float32(0.25) // shrink when size is 25% of capacity (0 means never shrink)
32)
33
34// New instantiates a new list and adds the passed values, if any, to the list
35func New(values ...interface{}) *List {
36 list := &List{}
37 if len(values) > 0 {
38 list.Add(values...)
39 }
40 return list
41}
42
43// Add appends a value at the end of the list
44func (list *List) Add(values ...interface{}) {
45 list.growBy(len(values))
46 for _, value := range values {
47 list.elements[list.size] = value
48 list.size++
49 }
50}
51
52// Get returns the element at index.
53// Second return parameter is true if index is within bounds of the array and array is not empty, otherwise false.
54func (list *List) Get(index int) (interface{}, bool) {
55
56 if !list.withinRange(index) {
57 return nil, false
58 }
59
60 return list.elements[index], true
61}
62
63// Remove removes the element at the given index from the list.
64func (list *List) Remove(index int) {
65
66 if !list.withinRange(index) {
67 return
68 }
69
70 list.elements[index] = nil // cleanup reference
71 copy(list.elements[index:], list.elements[index+1:list.size]) // shift to the left by one (slow operation, need ways to optimize this)
72 list.size--
73
74 list.shrink()
75}
76
77// Contains checks if elements (one or more) are present in the set.
78// All elements have to be present in the set for the method to return true.
79// Performance time complexity of n^2.
80// Returns true if no arguments are passed at all, i.e. set is always super-set of empty set.
81func (list *List) Contains(values ...interface{}) bool {
82
83 for _, searchValue := range values {
84 found := false
85 for index := 0; index < list.size; index++ {
86 if list.elements[index] == searchValue {
87 found = true
88 break
89 }
90 }
91 if !found {
92 return false
93 }
94 }
95 return true
96}
97
98// Values returns all elements in the list.
99func (list *List) Values() []interface{} {
100 newElements := make([]interface{}, list.size, list.size)
101 copy(newElements, list.elements[:list.size])
102 return newElements
103}
104
105//IndexOf returns index of provided element
106func (list *List) IndexOf(value interface{}) int {
107 if list.size == 0 {
108 return -1
109 }
110 for index, element := range list.elements {
111 if element == value {
112 return index
113 }
114 }
115 return -1
116}
117
118// Empty returns true if list does not contain any elements.
119func (list *List) Empty() bool {
120 return list.size == 0
121}
122
123// Size returns number of elements within the list.
124func (list *List) Size() int {
125 return list.size
126}
127
128// Clear removes all elements from the list.
129func (list *List) Clear() {
130 list.size = 0
131 list.elements = []interface{}{}
132}
133
134// Sort sorts values (in-place) using.
135func (list *List) Sort(comparator utils.Comparator) {
136 if len(list.elements) < 2 {
137 return
138 }
139 utils.Sort(list.elements[:list.size], comparator)
140}
141
142// Swap swaps the two values at the specified positions.
143func (list *List) Swap(i, j int) {
144 if list.withinRange(i) && list.withinRange(j) {
145 list.elements[i], list.elements[j] = list.elements[j], list.elements[i]
146 }
147}
148
149// Insert inserts values at specified index position shifting the value at that position (if any) and any subsequent elements to the right.
150// Does not do anything if position is negative or bigger than list's size
151// Note: position equal to list's size is valid, i.e. append.
152func (list *List) Insert(index int, values ...interface{}) {
153
154 if !list.withinRange(index) {
155 // Append
156 if index == list.size {
157 list.Add(values...)
158 }
159 return
160 }
161
162 l := len(values)
163 list.growBy(l)
164 list.size += l
165 copy(list.elements[index+l:], list.elements[index:list.size-l])
166 copy(list.elements[index:], values)
167}
168
169// Set the value at specified index
170// Does not do anything if position is negative or bigger than list's size
171// Note: position equal to list's size is valid, i.e. append.
172func (list *List) Set(index int, value interface{}) {
173
174 if !list.withinRange(index) {
175 // Append
176 if index == list.size {
177 list.Add(value)
178 }
179 return
180 }
181
182 list.elements[index] = value
183}
184
185// String returns a string representation of container
186func (list *List) String() string {
187 str := "ArrayList\n"
188 values := []string{}
189 for _, value := range list.elements[:list.size] {
190 values = append(values, fmt.Sprintf("%v", value))
191 }
192 str += strings.Join(values, ", ")
193 return str
194}
195
196// Check that the index is within bounds of the list
197func (list *List) withinRange(index int) bool {
198 return index >= 0 && index < list.size
199}
200
201func (list *List) resize(cap int) {
202 newElements := make([]interface{}, cap, cap)
203 copy(newElements, list.elements)
204 list.elements = newElements
205}
206
207// Expand the array if necessary, i.e. capacity will be reached if we add n elements
208func (list *List) growBy(n int) {
209 // When capacity is reached, grow by a factor of growthFactor and add number of elements
210 currentCapacity := cap(list.elements)
211 if list.size+n >= currentCapacity {
212 newCapacity := int(growthFactor * float32(currentCapacity+n))
213 list.resize(newCapacity)
214 }
215}
216
217// Shrink the array if necessary, i.e. when size is shrinkFactor percent of current capacity
218func (list *List) shrink() {
219 if shrinkFactor == 0.0 {
220 return
221 }
222 // Shrink when size is at shrinkFactor * capacity
223 currentCapacity := cap(list.elements)
224 if list.size <= int(float32(currentCapacity)*shrinkFactor) {
225 list.resize(list.size)
226 }
227}