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