list.bmx 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398
  1. SuperStrict
  2. Import "collection.bmx"
  3. Import "errors.bmx"
  4. Import "sort.bmx"
  5. Interface IList<T> Extends ICollection<T>
  6. Method Add(element:T)
  7. Method Clear()
  8. Method Contains:Int(element:T)
  9. Method IndexOf:Int(element:T)
  10. Method Insert(index:Int, element:T)
  11. Method Remove:Int(element:T)
  12. Method RemoveAt:T(index:Int)
  13. End Interface
  14. Rem
  15. bbdoc: Represents a collection of elements that can be individually accessed by index.
  16. End Rem
  17. Type TArrayList<T> Implements IList<T>
  18. Private
  19. Field data:T[]
  20. Field size:Int
  21. Field initialCapacity:Int
  22. Public
  23. Rem
  24. bbdoc: Creates a new TArrayList
  25. End Rem
  26. Method New(initialCapacity:Int = 16)
  27. Self.initialCapacity = initialCapacity
  28. data = New T[initialCapacity]
  29. End Method
  30. Rem
  31. bbdoc: Creates a new #TArrayList initialised by @array.
  32. End Rem
  33. Method New(array:T[])
  34. initialCapacity = 16
  35. If array Then
  36. initialCapacity = Max(initialCapacity, array.length)
  37. End If
  38. data = New T[initialCapacity]
  39. If data Then
  40. For Local element:T = EachIn array
  41. Add(element)
  42. Next
  43. End If
  44. End Method
  45. Rem
  46. bbdoc: Creates a new #TArrayList initialised by @iterable.
  47. End Rem
  48. Method New(iterable:IIterable<T>)
  49. New(16)
  50. If iterable Then
  51. For Local value:T = EachIn iterable
  52. Add(value)
  53. Next
  54. End If
  55. End Method
  56. Rem
  57. bbdoc: Returns an iterator that iterates through the #TList.
  58. End Rem
  59. Method GetIterator:IIterator<T>() Override
  60. Return New TArrayListIterator<T>(Self)
  61. End Method
  62. Rem
  63. bbdoc: Gets the number of elements contained in the #TArrayList.
  64. End Rem
  65. Method Count:Int() Override
  66. Return size
  67. End Method
  68. Rem
  69. bbdoc: Returns #True if the #TArrayList is empty, otherwise #False.
  70. End Rem
  71. Method IsEmpty:Int() Override
  72. Return size = 0
  73. End Method
  74. Rem
  75. bbdoc: Gets the total number of elements the internal data structure can hold without resizing.
  76. about: #Capacity is the number of elements that the #TArrayList can store before resizing is required, whereas #Count is
  77. the number of elements that are actually in the #TArrayList.
  78. End Rem
  79. Method Capacity:Int()
  80. Return data.length
  81. End Method
  82. Rem
  83. bbdoc: Sets the total number of elements the internal data structure can hold without resizing.
  84. about: #Capacity is the number of elements that the #TArrayList can store before resizing is required, whereas #Count is
  85. the number of elements that are actually in the #TArrayList.
  86. End Rem
  87. Method SetCapacity(value:Int)
  88. If value < data.length Then
  89. Throw New TArgumentOutOfRangeException
  90. End If
  91. data = data[..value]
  92. End Method
  93. Method CopyTo(array:T[], index:Int = 0) Override
  94. ' TODO
  95. End Method
  96. Rem
  97. bbdoc: Adds an element to the end of the #TArrayList.
  98. End Rem
  99. Method Add(element:T) Override
  100. ResizeAsNeeded(size + 1)
  101. data[size] = element
  102. size :+ 1
  103. End Method
  104. Rem
  105. bbdoc: Removes all elements from the #TArrayList.
  106. End Rem
  107. Method Clear() Override
  108. For Local i:Int = 0 Until size
  109. data[i] = Null
  110. Next
  111. size = 0
  112. End Method
  113. Rem
  114. bbdoc: Determines whether an element is in the #TArrayList.
  115. End Rem
  116. Method Contains:Int(element:T) Override
  117. Return IndexOf(element) >= 0
  118. End Method
  119. Rem
  120. bbdoc: Returns the zero-based index of the first occurrence of a value in the #TArrayList.
  121. End Rem
  122. Method IndexOf:Int(element:T) Override
  123. For Local i:Int = 0 Until size
  124. If data[i] = element Then
  125. Return i
  126. End If
  127. Next
  128. Return -1
  129. End Method
  130. Rem
  131. bbdoc: Returns the zero-based index of the first occurrence of a value in a portion of the #TArrayList.
  132. End Rem
  133. Method IndexOf:Int(element:T, index:Int)
  134. If index < 0 Or index >= size Then
  135. Throw New TIndexOutOfBoundsException
  136. End If
  137. For Local i:Int = index Until size
  138. If data[i] = element Then
  139. Return i
  140. End If
  141. Next
  142. Return -1
  143. End Method
  144. Rem
  145. bbdoc: Returns the zero-based index of the first occurrence of a value in a portion of the #TArrayList.
  146. End Rem
  147. Method IndexOf:Int(element:T, index:Int, count:Int)
  148. If index < 0 Or index >= size Or count < 0 Or index + count > size Then
  149. Throw New TIndexOutOfBoundsException
  150. End If
  151. For Local i:Int = index Until index + count
  152. If data[i] = element Then
  153. Return i
  154. End If
  155. Next
  156. Return -1
  157. End Method
  158. Rem
  159. bbdoc: Inserts an element into the #TArrayList at the specified index.
  160. End Rem
  161. Method Insert(index:Int, element:T) Override
  162. If index < 0 Or index > size Then
  163. Throw New TIndexOutOfBoundsException
  164. End If
  165. ResizeAsNeeded(size + 1)
  166. ArrayCopy(data, index, data, index + 1, size - index)
  167. data[index] = element
  168. size :+ 1
  169. End Method
  170. Rem
  171. bbdoc: Returns the zero-based index of the last occurrence of a value in the #TArrayList.
  172. End Rem
  173. Method LastIndexOf:Int(element:T)
  174. Local i:Int = size - 1
  175. While i >= 0
  176. If data[i] = element Then
  177. Return i
  178. End If
  179. i :- 1
  180. Wend
  181. Return -1
  182. End Method
  183. Rem
  184. bbdoc: Returns the zero-based index of the last occurrence of a value in a portion of the #TArrayList.
  185. End Rem
  186. Method LastIndexOf:Int(element:T, index:Int)
  187. If index < 0 Or index >= size Then
  188. Throw New TIndexOutOfBoundsException
  189. End If
  190. Local i:Int = index
  191. While i >= 0
  192. If data[i] = element Then
  193. Return i
  194. End If
  195. i :- 1
  196. Wend
  197. Return -1
  198. End Method
  199. Rem
  200. bbdoc: Returns the zero-based index of the last occurrence of a value in a portion of the #TArrayList.
  201. End Rem
  202. Method LastIndexOf:Int(element:T, index:Int, count:Int)
  203. If index < 0 Or index >= size Or count < 0 Or index - count < -1 Then
  204. Throw New TIndexOutOfBoundsException
  205. End If
  206. Local i:Int = index
  207. While i >= 0 And count > 0
  208. If data[i] = element Then
  209. Return i
  210. End If
  211. i :- 1
  212. count :- 1
  213. Wend
  214. Return -1
  215. End Method
  216. Rem
  217. bbdoc: Removes the first occurrence of a specific element from the #TArrayList.
  218. returns: #True if the element was successfully removed from the #TArrayList, otherwise #False.
  219. End Rem
  220. Method Remove:Int(element:T) Override
  221. Local index:Int = IndexOf(element)
  222. If index >= 0 Then
  223. RemoveAt(index)
  224. Return True
  225. End If
  226. Return False
  227. End Method
  228. Rem
  229. bbdoc: Removes the element at the specified index of the #TArrayList.
  230. returns: The element that was removed from the #TArrayList.
  231. End Rem
  232. Method RemoveAt:T(index:Int) Override
  233. If index < 0 Or index >= size Then
  234. Throw New TIndexOutOfBoundsException
  235. End If
  236. Local element:T = data[index]
  237. Local moveCount:Int = size - index - 1
  238. If moveCount > 0 Then
  239. ArrayCopy(data, index + 1, data, index, moveCount)
  240. End If
  241. size :- 1
  242. data[size] = Null
  243. Return element
  244. End Method
  245. Rem
  246. bbdoc: Sorts the elements in the entire #TArrayList using the specified comparator, or the default if #Null.
  247. End Rem
  248. Method Sort(comparator:IComparator<T> = Null)
  249. ' nothing to sort
  250. If size < 2 Then
  251. Return
  252. End If
  253. Local depth:Int
  254. Local n:Int = size
  255. While n >= 1
  256. depth :+ 1
  257. n = n / 2
  258. Wend
  259. depth :* 2
  260. If comparator Then
  261. New TComparatorArraySort<T>(comparator).Sort(data, 0, size - 1, depth)
  262. Else
  263. New TArraySort<T>().Sort(data, 0, size - 1, depth)
  264. End If
  265. End Method
  266. Rem
  267. bbdoc: Converts a #TArrayList to an array.
  268. returns: An array of elements.
  269. End Rem
  270. Method ToArray:T[]()
  271. Local arr:T[size]
  272. ArrayCopy(data, 0, arr, 0, size)
  273. Return arr
  274. End Method
  275. Rem
  276. bbdoc: Sets the capacity to the actual number of elements in the #TArrayList.
  277. about: This method can be used to minimize a collection's memory overhead if no new elements will be added to the collection.
  278. End Rem
  279. Method TrimExcess()
  280. If size = 0 Then
  281. data = data[..initialCapacity]
  282. Else If size < data.length Then
  283. data = data[..size]
  284. End If
  285. End Method
  286. Rem
  287. bbdoc: Returns the element at the specified index.
  288. End Rem
  289. Method Operator [] :T(index:Int)
  290. If index < 0 Or index >= size Then
  291. Throw New TIndexOutOfBoundsException
  292. End If
  293. Return data[index]
  294. End Method
  295. Rem
  296. bbdoc: Sets the element at the specified index.
  297. End Rem
  298. Method Operator []= (index:Int, value:T)
  299. If index < 0 Or index >= size Then
  300. Throw New TIndexOutOfBoundsException
  301. End If
  302. data[index] = value
  303. End Method
  304. Private
  305. Method ResizeAsNeeded(minCapacity:Int)
  306. Local capacity:Int = data.length
  307. If minCapacity > capacity Then
  308. Local newCapacity:Int = (capacity * 3) / 2 + 1
  309. If newCapacity < minCapacity Then
  310. newCapacity = minCapacity
  311. End If
  312. data = data[..newCapacity]
  313. End If
  314. End Method
  315. Public
  316. End Type
  317. Type TArrayListIterator<T> Implements IIterator<T>
  318. Private
  319. Field list:TArrayList<T>
  320. Field index:Int = -1
  321. Method New(list:TArrayList<T>)
  322. Self.list = list
  323. End Method
  324. Public
  325. Method Current:T() Override
  326. Return list[index]
  327. End Method
  328. Method MoveNext:Int() Override
  329. index :+ 1
  330. Return index < list.size
  331. End Method
  332. End Type