Collections.ns

Newspeak3
'Root'
class Collections usingPlatform: p = (
(*
Newspeak collections library.
This code was derived by converting the Strongtalk Collections classes to Newspeak, which is why the Sun Microsystems copyright and BSD license below applies.

Copyright (c) 1995-2006 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
Copyright 2008-2009 Yardena Meymann, Gilad Bracha and other contributors.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice,
 this  list of conditions and the following disclaimer.

* Redistribution in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation and/o other materials provided with the distribution.

Neither the name of Sun Microsystems or the names of contributors may
be used to endorse or promote products derived from this software without
specific prior written permission.

>>
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.>> *)
|	private MutableAddableList = MutableList mixinApply: AddableList. (* -- streams -- *)	private ListReadStream = p streams SeqCltnReadStream. 	private ListReadWriteStream = p streams SeqCltnReadWriteStream.		(* magic collections *)	(* Not yet supported by NS2JS or NS2Dart *)	public WeakArray = Future computing: [p squeak WeakArray]. |) (
class AbstractList = Collection (
(* This class implements the read-only protocol for indexed collections that order their elements using integer indices. *)
) (
public , other <List[X]> ^<MutableList[E | X]> = (
	^self copyReplaceFrom: size + 1 to: size with: other
)
public allButFirst ^ <MutableList[E]> = (
	^copyFrom: 2 to: size
)
public allButLast ^ <MutableList[E]> = (
	^copyFrom: 1 to: size - 1
)
public anyOne = (
	^ first
)
public at: index <Integer> ^<E> = (
	subclassResponsibility
)
public at: index <Integer> ifAbsent: fail <[X def]> ^<E|X> = (
	^(index between: 1 and: size)
		ifTrue: [ at: index ]
		ifFalse: [ fail value ]
)
binarySearchFor: el <EL>
between: start <Integer>
and: end <Integer>
toCompare: compare <[:EL def :EL| Boolean]>
^<Int>
= (
			(* {where CONSTRAINER <EL> is returnType of #anElement message of receiverType} *)
	(* This does a binary search for the index such that if el was inserted before it
	  the receiver would remain sorted.  The receiver must be sorted relative to the
	  comparison block.  The comparison block should return true if the first block argument
	  cannot appear after the second block argument *)

	| low <Integer> high <Integer> |
	low:: start.
	high:: end.
	[ low <= high ]
		whileTrue:
				[ | mid <Integer> |
					mid:: (low + high)  // 2.
	  				(* The guaranteed below is safe because of the inference clause *)
					(compare value: (
(* guaranteed <EL> *) (at: mid)) value: el)
						ifTrue: [ low:: mid + 1 ]
						ifFalse: [ high:: mid - 1 ].
				].
	^low
)
public binarySearchFor: el <EL>
toCompare: compare <[:EL def :EL| Boolean]>
^ <Integer>
= (
	#BOGUS. (* Remove me. *)
	(* {where CONSTRAINER <EL> is returnType of #anElement message of receiverType} *)

	(* The guarantee is safe because of the inference clause *)
	^(
(* guaranteed <List[EL]> *) self)
			binarySearchFor: el
			between: 1
			and: size
			toCompare: compare
)
public collect: map <[:E | R def]> ^<List[R]> = (
	^collectUsingAtPut: map
)
protected collectUsingAtPut: map <[:E | R def]> ^<List[R]> = (
	| c <MutableList[R]> |
	(* See #newForCollect: for explanation of why the guarantee is safe *)
	c:: (* guaranteed <MutableList[R]> ( *)newForCollectUsingAtPut: size(* ) *).
	1 to: self size do:
		[:i <Integer> |
			c at: i put: (map value: (at: i)) ].
	^c
)
collection: cltn <List[Object]>
matchesElementsAt: index <Integer>
^<Boolean> = (
	(* Test whether we contain the given subcollection at index.  This method assumes
	  that there are at least as many elements in this collection after index as cltn size *)

	| offset <Integer> |
	offset:: index - 1.
	1 to: cltn size do:
		[:i <Integer> |
			(cltn at: i) = (at: i+offset)
				ifFalse: [ ^false ]		].
	^true
)
public copyFrom: start <Integer> to: stop <Integer> ^<MutableList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)

	(* The guarantee is typesafe since the inference clause guarantees that E < EX at the call site *)
	| cp <MutableList[EX]> safeme <List[EX]> |
	safeme:: (* guaranteed <List[EX]> *) self.
	cp:: (* guaranteed <MutableList[EX]> *)
				newCopyOfSize: (stop - start) + 1 thatCanAlsoHoldElementsOf: safeme.
	cp replaceFrom: 1 to: cp size with: safeme startingAt: start.
	^cp
)
public copyReplaceAll: oldSub <List[Object]> with: newSub <List[X]> ^<MutableList[EX | X]> = (
	(* {where EX is returnType of #anElement message of receiverType;
			where X is returnType of #anElement message of arg 2} *)

	|	spots <List[Integer]>
		subDelta <Integer>
		copy <MutableList[EX | X]>
		current <Integer>
		offset <Integer>
		newSubSize <Integer>
		oldSubSize <Integer>
		safeself <List[EX]>
		|
	newSubSize:: newSub size.
	oldSubSize:: oldSub size.
	subDelta:: newSub size - oldSubSize.
	spots:: indicesOfSubCollection: oldSub.

	(* This guarantee is typesafe since the inference clause guarantees that E < EX at the call site *)
	safeself:: (* guaranteed <List[EX]> *) self.

	spots size = 0
		ifTrue: [ copy:: safeself newCopyOfSize: size
								thatCanAlsoHoldElementsOf: newSub.
						copy replaceFrom: 1 to: size with: safeself.
						^copy
						].

	copy:: safeself newCopyOfSize: size + (spots size * subDelta)
				thatCanAlsoHoldElementsOf: newSub.
	current:: 1.
	offset:: 0.
	spots do:
		[:spot <Int> |	| offspot <Int> |
			offspot:: spot + offset.

			(* copy segment of self before the next occurrence *)
			copy	replaceFrom: current + offset
					to: offspot - 1
					with: safeself
					startingAt: current.
			(* copy the new subcollection at the next occurrence *)
			copy	replaceFrom: offspot
					to: (offspot + newSubSize) - 1
					with: newSub.
			current:: spot + oldSubSize.
			offset:: offset + subDelta.	].
	(* copy the final segment from self after the last occurrence *)
	copy	replaceFrom: current + offset
			to: copy size
			with: safeself
			startingAt: current.
	^copy
)
copyReplaceFrom: start <Integer> to: stop <Integer> with: other <List[X]> ^<MutableList[EX | X]> = (
	(* {where EX is returnType of #anElement message of receiverType;
			where X is returnType of #anElement message of arg 3} *)

	|	copy <MutableList[EX | X]>
		sizeChange <Integer>
		sz <Integer>
		afterNew <Integer>
		safeself <List[EX]> |

	(* The guarantee is typesafe since the inference clause guarantees that E < EX at the call site *)
	safeself:: (* guaranteed <List[EX]> *) self.

	sizeChange:: other size - ((stop - start) + 1).
	sz:: size.
	copy:: safeself newCopyOfSize: sz + sizeChange
				thatCanAlsoHoldElementsOf: other.
	afterNew:: start + other size.
	copy replaceFrom: 1 to: start - 1 with: safeself startingAt: 1.
	copy replaceFrom: start to: afterNew - 1 with: other.
	copy replaceFrom: afterNew to: copy size with: (
(* guaranteed <List[EX]> *) self) startingAt: stop + 1.
	^copy
)
public copyWith: element <X> ^<MutableList[E | X]> = (
	^self , {element}
)
public copyWithSize: s <Integer> ^<MutableList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)

	(* return a mutable copy of the receiver of a different size, that is either truncated
		or extended with nils as necessary.  Note this works even if the receiver itself
		is not mutable *)

	(* %note: the inference clause above is a tricky way of doing something very difficult:
	  it allows us to effectively return a mutable copy of the receiver in a typesafe way,
	  even though the
	  receiver itself may not be mutable.  This would be impossible to type reasonably
	  without the inference clause, because we would have to have a return type of
	 <MutableList[E]>, which isn't typesafe since  E is a 'covariant' generic variable of this
	  class, whereas E is an 'unrelated' generic variable in MutableList. - D.G. *)

	(* %note: The inference clause above should really read ... EX <E> ..., but the type
		system implementation for some reason can't deal with implementations
		of such a method in subclasses that have bound E (i.e. are not generic on E).
		For an example, see the implementation in ReadString, which would not have to
		have a guarantee in the method body if this worked right - D.G. *)

	subclassResponsibility
)
public copyWithout: el <Object> ^<MutableList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)

	| safeself <List[EX]> |

	(* The following guarantee is safe because the inference clause ensures that E < EX
		at the call site *)
	safeself:: (* guaranteed <List[EX]> *) self.

	^safeself copyReplaceAll: (Array(* [Object] *) with: el) with: {}
)
public do: f <[:E]> = (
	1 to: size do:
		[:i <Integer> |
			f value: (at: i)	]
)
public doWithIndex: f <[:E :Integer]> = (
	1 to: size do:
		[:i <Integer> |
			f value: (at: i) value: i]
)
public findFirst: predicate <[:E| Boolean]> ^<Integer> = (
	1 to: size do:
		[:i <Integer> |
			(predicate value: (at: i))
				ifTrue: [ ^i ]	].
	^0
)
public findLast: predicate <[:E| Boolean]> ^<Integer> = (
	size to: 1 by: -1 do:
		[:i <Integer> |
			(predicate value: (at: i))
				ifTrue: [ ^i ]	].
	^0
)
public first ^<E> = (
	^self at: 1
)
public hasSameElementsAndOrderAs: other <List[Object]> ^<Boolean> = (
	#ACCESSBOGUS.
	(* Like #hasSameElementsAs:, but also requires the elements to be in the same order *)

	size = other size
		ifFalse: [ ^false ].
	1 to: size do:
		[:i <Integer> |
			(at: i) = (other at: i)
				ifFalse: [ ^false ]	].
	^true
)
public hash ^<Integer> = (
	(* This function should not be changed, since it is designed to produce the
		same results as the identityHash primitive, for strings and symbols *)
	| sz <Integer> val <Integer> |
	sz:: size.
	sz < 2
		ifTrue: [ ^sz = 1 ifTrue: [ self hashAt: 1 ] ifFalse: [ 1 ] ].
	val:: hashAt: 1.
	val:: (val bitShift: 3) bitXor: ((hashAt: 2) bitXor: val).
	val:: (val bitShift: 3) bitXor: ((hashAt: sz) bitXor: val).
	val:: (val bitShift: 3) bitXor: ((hashAt: sz - 1) bitXor: val).
	val:: (val bitShift: 3) bitXor: ((hashAt: (sz bitShift: -1) + 1) bitXor: val).
	val:: (val bitShift: 3) bitXor: (sz bitXor: val).

	(* mask it to 20 bits to match VM *)
	val:: val bitAnd: 16rFFFFF.
	^val
)
protected hashAt: index <Integer> ^<Integer> = (
	^(at: index) hash
)
protected includesIndex: index <Integer> ^<Boolean> = (
	^index between: 1 and: size
)
public indexOf: element <Object> ^<Integer> = (
	^self indexOf: element ifAbsent: [ 0 ]
)
public indexOf: element <Object> ifAbsent: f <[X def]> ^<Integer | X> = (
	1 to: size do:
 [:index <Integer> |
 (at: index) =
element ifTrue: [^index]].
	^f value
)
indexOfSubCollection: sub <List[Object]>
startingAt: index <Integer>
^<Integer> = (
	^indexOfSubCollection: sub
		startingAt: index
		ifAbsent: [ error: 'subcollection not found' ]
)
indexOfSubCollection: sub <List[Object]>
startingAt: index <Integer>
ifAbsent: f <[X def]>
^<Integer | X> = (
	index to: (size - sub size) + 1 do:
		[:i <Integer> |
			(collection: sub matchesElementsAt: i)
				ifTrue: [ ^i ]		].
	^f value
)
indicesOfSubCollection: sub <List[Object]> ^<List[Int]> = (
	^indicesOfSubCollection: sub startingAt: 1
)
indicesOfSubCollection: sub <List[Object]>
startingAt: index <Integer>
^<List[Integer]> = (
	| indices <MutableArrayList[Integer]> subSize <Integer> current <Integer> |
	indices:: MutableArrayList(* [Int] *) new.
	subSize:: sub size.
	current:: index.
	[ current:: self indexOfSubCollection: sub startingAt: current ifAbsent: [ 0 ].
	  current = 0
		] whileFalse:
			[ indices addLast: current.
				current:: current + subSize.		].
	^indices
)
public isKindOfList ^ <Boolean> = (
	^true
)
public isSequenceable = (
	^true
)
isSortedBy: compare <[:E :E | Boolean]> ^<Boolean> = (
	(* Returns true if the receiver is in sorted order, using the specified comparison *)

	| last <E> |
	size < 2
		ifTrue: [ ^true ].
	last:: at: 1.
	2 to: size do:
		[:i <Integer> |
			(compare value: last value: (at: i))
				ifFalse: [ ^false ]	].
	^true
)
public keysAndValuesDo: action <[:Integer :E]> = (
	1 to: size do:
		[:index <Integer> |
 action value: index value: (at: index)]
)
public last ^<E> = (
	^self at: self size
)
public newCopyOfSize: size <Integer>
thatCanAlsoHoldElementsOf: other <List[X]>
^<MutableList[EX | X]>
= (
		(* {where X is returnType of #anElement message of arg 2;
		     where EX is returnType of #anElement message of receiverType} *)

	(* Return a fresh collection of a closely related type
	that can hold both elements of self and elements of the other collection *)

	^Array(* [EX | X] *) new: size
)
newForCollectUsingAtPut: size <Integer> ^<MutableList[Object]> = (
	(* Return a new extensible collection that is as closely related to the receiver's class as possible.  The
	 returned collection must be unaliased and empty, so it is safe for the caller to guarantee that the type
	 variable is of a more specific type *)

	^Array(* [Object] *) new: size
)
public readStream ^<ReadStream[E]> = (
	^ListReadStream on: self
)
public reverse ^<MutableList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)

	(* The guarantees are typesafe since the inference clause guarantees that E < EX at the call site *)
	| copy <MutableList[EX]> |

	#BOGUS. (* #reverse implies an in-place operation, should be #reversed *)
	copy:: (* guaranteed <MutableList[EX]> *)
		(newCopyOfSize: size thatCanAlsoHoldElementsOf: self).
	1 to: size do:
		[:i <Integer> |
			| el <EX> |
			el:: (
(* guaranteed <MutableList[EX]> *) self) at: i.
			copy at: size + 1 - i put: el.	].
	^copy
)
public reverseDo: action <[:E]> = (
	size to: 1 by: -1 do:
		[:index <Integer> |
 action value: (at: index)]
)
public size ^<Integer> = (
	subclassResponsibility
)
public species ^<Collection[E] class> = (
	^Array(* [E] *)
)
public with: other <List[X def]> do: action <[:E :X]> = (
	assert: [ self size = other size ] message: 'Cannot jointly interate collections of different size'.
	1 to: size do:
		[:index <Integer> |
 action value: (at: index) value: (other at: index)].
)
) : (
)
class AddableList = AbstractList (
(* AddableLists are Lists that support the Extensible protocol, and which support indexing in constant time. *)
|
	protected contents <Array[E]>
	protected startGap <Integer> (* number of empty slots at the beginning of contents *)
	protected lastIndex <Integer> (* (internal) index of last occupied table entry *)
|initCapacity: self class defaultCapacity) (
public add: e <E> ^<E> = (
	subclassResponsibility
)
public addAll: c <Collection[E]> ^<Collection[E]> = (
	c do: [:el <E> |
		add: el	].
	^c
)
public at: i <Integer> ^<E> = (
	| adjusted <Int> |
	adjusted:: i + startGap.
	((0 < i) and: [adjusted <= self lastIndex])
		ifFalse: [ error: 'invalid index' ].
	^contents at: adjusted
)
public at: i <Integer> ifAbsent: f <[X def]> ^<E | X> = (
	| internal <Int> |
	internal:: i + self startGap.
	^(internalIndexIsValid: internal)
		ifTrue: [ contents at: internal ]
		ifFalse: [ f value ]
)
public copyWithSize: s <Integer> ^<MutableList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)

	| safeself <List[EX]> |

	(* This guarantee is safe because the inference clause guarantees
		that E < EX at each call site *)
	safeself:: (* guaranteed <List[EX]> *) self.

	^(Array(* [EX] *) new: s)
		replaceFrom: 1 to: (s min: size) with: safeself
)
public do: action <[:E]> = (
	startGap + 1 to: lastIndex do:
		[:index <Integer> | action value: (contents at: index) ]
)
endGap ^<Integer> = (
	^contents size - lastIndex
)
firstIndex ^<Integer> = (
	^1 + startGap
)
public include: e <E> ^<E> = (
	^include: e ifNew: []
)
public include: e <E> ifNew: blk <[]> ^<E> = (
	(includes: e)
		ifFalse: [ add: e.
						blk value. ].
	^e
)
public includeAll: c <Collection[E]> ^<Collection[E]> = (
	c do: [:el <E> |
		include: el ].
	^c
)
public indexOf: el <Object> ifAbsent: f <[X def]> ^<Integer | X> = (
	1 to: size do: [:i <Integer> |
		(at: i) = el
			ifTrue: [ ^i ].	].
	^f value
)
public initCapacity: c <Integer> = (
	(* Need proper factories to pass initial capacity and make this non-public. *)

	contents:: Array(* [E] *) new: c.
	startGap:: 0.
	lastIndex:: 0.
)
internalIndexIsValid: index <Integer> ^<Boolean> = (
	^index > startGap and: [ index <= lastIndex ]
)
internalRangeCheck: index <Integer> = (
	(internalIndexIsValid: index )
		ifFalse: [ error: 'invalid index' ].
)
makeSpace: slots <Integer> beforeIndex: i <Integer> ^<Integer> = (
	(* assume: i is a valid internal index.  The index is returned, adjusted
	 for any resizing of the internal array that may have taken place
	 (i.e. the index of the beginning of the created gap is returned) *)

	(* # before i is (i - startGap) - 1, # after is (lastIndex - i) + 1 *)
	^((i - startGap) - 1) > ((lastIndex - i) + 1)
		ifTrue: [ 	(* fewer elements after, so move them *)
			      	needSpaceAtEnd: slots.
			      	contents
					replaceFrom: i + slots
					to: lastIndex + slots
					with: contents
					startingAt: i.
			    	lastIndex:: lastIndex + slots.
				i	]
		ifFalse: [ (* fewer elements before, so move them *)
				| newI <Integer> |
				newI:: i + (needSpaceAtStart: slots) - slots.
				contents
					replaceFrom: (startGap + 1) - slots
					to: newI - 1
					with: contents
					startingAt: startGap + 1.
				startGap:: startGap - slots.
				newI	].
)
makeSpaceAtStart: nslots <Integer> ^<Integer> = (
	(* Make sure that there are at least nslots of unused capacity at the low
	 end of contents.  The # of slots added at the beginning is returned. *)

	|	newGap <Integer>
		diff <Integer>
		newContents <AbsoluteArray[E]>
		sz <Integer>
		newLastIndex <Integer> |
	(isEmpty and: [nslots <= contents size])
		ifTrue: [startGap: nslots.
  				lastIndex: nslots.
				^nslots].

	sz:: size.
	newGap:: nslots max: sz.
	diff:: newGap - startGap.
	newLastIndex:: newGap + sz.
	newContents:: Array(* [E] *) new:
		contents size + diff.
	newContents
		replaceFrom: newGap + 1
		to: newLastIndex
		with: contents
		startingAt: firstIndex.
	startGap: newGap.
	contents: newContents.
	lastIndex: newLastIndex.
	^diff
)
needSpaceAtEnd: slots <Integer> = (
	slots > endGap
		ifTrue: [ contents:
							(contents copyWithSize:
								contents size + (slots max: size)	)]
)
needSpaceAtStart: nslots <Integer> ^<Integer> = (
	(* Make sure that there are at least nslots of unused capacity at the low
	 end of contents.  The # of slots added at the beginning is returned. *)

	^nslots > startGap
		ifTrue: [makeSpaceAtStart: nslots]
		ifFalse: [ 0 ]
)
public postCopy = (
	super postCopy.
	(* We potentially may change the size of the contents array so that this can work for copyWithSize:
	  as well *)
	contents: (contents copyWithSize: (contents size max: lastIndex))
)
public remove: el <E> ^<E> = (
	^remove: el
		ifAbsent: [ error: 'element not found' ]
)
public remove: nElements <Integer> at: i <Integer> = (
	| el <E> internal <Integer> |
	el:: at: i.
	internal:: startGap + i.
	internalRangeCheck: internal.
	internalRangeCheck: (internal + nElements) - 1.
	internal  to: lastIndex - nElements
		 do: [:index <Integer> |
			  contents at: index put: (contents at: index + nElements).	].
	contents at: lastIndex put: nil.
	lastIndex: lastIndex - nElements.
)
public remove: el <E> ifAbsent: f <[X def]> ^<E|X> = (
	removeAt: (indexOf: el ifAbsent: [^f value]).
	^el
)
public removeAll = (
	startGap + 1 to: lastIndex do:
		[:i <Integer> |
			contents at: i put: nil].
	lastIndex: startGap
)
public removeAll: c <Collection[E]> ^<Collection[E]> = (
	c do: [:el <E> |
		remove: el ].
	^c
)
public removeAllSuchThat: test <[:E | Boolean]> = (
	| i <Integer> |
	i:: 1.
	[ i <= size ]
		whileTrue:
			[ (test value: (at: i))
					ifTrue: [ removeAt: i ]
					ifFalse: [ i:: i + 1 ]	]
)
public removeAt: index <Integer> ^<E> = (
	| el <E> |
	el:: at: index.
	remove: 1 at: index.
	^el
)
public removeEvery: val <E> ^<E> = (
	^removeEvery: val startingAt: 1
)
public removeEvery: val <X def> startingAt: start <Integer> ^<X> = (
	| index <Integer> |
	index:: indexOf: val ifAbsent: [ ^val ].
	removeAt: index.
	^removeEvery: val startingAt: index
)
public removeFirst ^<E> = (
	^removeAt: 1
)
public removeLast ^<E> = (
	^removeAt: size
)
public size ^<Integer> = (
	^lastIndex - startGap
)
public size: s <Integer> = (
	(* Change the size of the ordered collection to s (not the capacity).  This will truncate elements at the end if the current size
	  is larger.  If the current size is smaller, the added elements will be undefined, in which case it is erroneous to access them until they have been set.
	  This method should be used very rarely and carefully as a result. *)

	| delta <Integer> newLastIndex <Integer> |
	delta:: s - size.
	newLastIndex:: lastIndex + delta.
	delta < 0
		ifTrue: [ newLastIndex + 1 to: lastIndex do:
					[:i <Integer> |
						contents at: i put: nil]].
	delta > 0
		ifTrue: [ needSpaceAtEnd: delta ].
	lastIndex: lastIndex + delta.
)
public sort: compare <[:E :E | Boolean]> = (
	(* In-place sort. *)
	lastIndex < firstIndex ifTrue: [^self].
	contents
		mergeSortFrom: firstIndex
		to: lastIndex
		by: compare
)
) : (
public defaultCapacity ^<Integer> = (
	^5
)
public new: capacity <Integer> ^<Instance> = (
	^new initCapacity: capacity
)
public with: val1 <E> ^<Instance> = (
	^(new: 1) add: val1; yourself
)
public withAll: cltn <Collection[E]> ^<Instance> = (
	^(new: cltn size) addAll: cltn; yourself
)
)
public class Association key: k value: v = (
(* Associates an object of type K with an object of type V. *)
|
	public key <K> ::= k.
	public value <V> ::= v.
|) (
public = other <Object> ^<Boolean> = (
	(* | othera <Assoc[Object,Object]> | *)
	(* %todo: replace Association with Assoc when typecase is fully impl *)
	(* othera:: Association[Object,Object] coerce: other else: [ ^false ]. *)
	^key = other key and: [ value = other value ].
)
public copy = (
	^class key: key value: value
)
public hash ^<Integer> = (
	^key hash bitXor: value hash
)
public printOn: strm <CharOutputStream> = (
	key printOn: strm.
	strm nextPutAll: ' -> '.
	value printOn: strm.
)
) : (
public new ^<Instance> = (
	self warnObsolete.
	^self key: nil value: nil
)
)
public class Collection = (
(* A Collection is an object that represents a group of objects.

The only message that must be implemented by subclasses is the #do: message.
All other Collection messages are then defined in terms of #do:.

%responsibility size
	Subclasses usually reimplement the #size message if possible, since the
	implementation provided in this class is very inefficient.
%responsibility collect:
	Subclasses may wish to consider overriding the #collect: (and #select: and #reject:)
	messages to specialize their return
	types to match the receiver type more closely. *)
) (
public allSatisfy: predicate <[:E | Boolean]> ^<Boolean> = (
	self do: [:each | (predicate value: each) ifFalse: [^false]].
	^true
)
public anySatisfy: predicate <[:E | Boolean]> ^<Boolean> = (
	self do: [:each | (predicate value: each) ifTrue: [^true]].
	^false
)
public asArray ^<Array[E]> = (
	|
	array <Array[E]> = Array new: size.
	index <Integer> ::= 1.
	|
	self do: [:element <E> |
		array at: index put: element.
		index:: index + 1].
	^array
)
public asCollection = (
	(* Squeak 5.0 *)
	^self
)
public asMutableArrayList ^<MutableArrayList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)
(* Return a new MutableArrayList holding the elements of this collection.  The element type of the ordered collection
	is whatever the static type of the receiver is at the point of send. *)
	^MutableArrayList(* [EX] *) withAll: (* (guaranteed <CollectionEX]> *)self(* ) *)
)
public asSet ^<Extensible[EX]> = (
	 (* Return a new extensible collection holding the elements of this collection. *)

	^Set(* [EX] *) withAll: (* (guaranteed <Collection[EX]> *)self(* ) *)
)
public asSortedList ^<List[Object]> = (
	(* This message is NOT typesafe, and should only be used for compatibility reasons, since there is
 	 no way of knowing whether the elements of this collection support #< or not.  You should use
	 #asSortedList: instead, if possible *)

	^SortedList(* [Object] *) withAll: self
)
public asSortedList: sortPredicate <[:E :EX | Boolean]> ^ <SortedList[EX]> = (
	(* { where EX is  arg 1 of #value:value: message of arg 1 } *)
	(* Return a new sorted collection ordered by the given sortPredicate.  Note that Magnitude
	 supports the defaultSort message for convenience, so that for example if you have a collection
	 of strings strc, you can say:
		strc asSortedList: String defaultSort
	*)

	(* This is typesafe despite the guarantee because the inference clause requires that E = EX at the
	call site *)
	^(SortedList(* [EX] *) new: size sortBlock: (* (guaranteed <[EX,EX,^Boolean]> *)sortPredicate(* ) *))
		addAll: (* (guaranteed <Collection[EX]> *)self(* ) *); yourself
)
public collect: map <[:E | R def]> ^<Collection[R]> = (
	^self collectUsingAdd: map
)
protected collectUsingAdd: map <[:E | R def]> ^<Collection[R]> = (
	| c |
	(* See #newForCollect: for explanation of why the guarantee is safe *)
	c:: (newForCollectUsingAdd: size).
	do: [:e | c add: (map value: e) ].
	^c
)
public copy = (
	#BOGUS. (* Questionable. Probably should be shallowCopy if we keep it. *)
	^self class withAll: self
)
public detect: predicate <[:E | Boolean]> ^<E> = (
	^self detect: predicate ifNone: [Error signal: 'No matching element detected']
)
public detect: aBlock ifFound: foundBlock ifNone: exceptionBlock = (
	self
		do: [ :each |
			(aBlock value: each)
				ifTrue: [ ^ foundBlock cull: each ] ].
	^ exceptionBlock value
)
public detect: predicate <[:E | Boolean]> ifNone: fail <[X def]> ^<E | X> = (
	self do: [:element | (predicate value: element) ifTrue: [^element]].
	^fail value
)
public do: action <[:E]> = (
	subclassResponsibility
)
public do: action <[:E]> separatedBy: betweenAction <[]> = (
	(* Useful when you need to do something 'between' elements (i.e. not before the first one, and not after the last one). [action] is evaluated the same way as for #do:, but [betweenAction] is evaluated once between each pair of elements. *)
	| firstTime <Boolean> ::= true. |
	firstTime:: true.
	self do:
		[:element <E> |
		firstTime
			ifTrue: [firstTime:: false]
			ifFalse: [betweenAction value].
			action value: element].
)
public flatMap: map <[:E | R def]> ^<Collection[R]> = (
	^(collect: map) flatten
)
public flatten ^ <Collection[E]> = (
	| totalSize <Integer> ::= 0. c |
	do: [:e <E> | totalSize:: totalSize + (e isKindOfCollection ifTrue: [e size] ifFalse: [1])].
	c:: newForCollectUsingAdd: totalSize.
	do: [:e <E> | e isKindOfCollection ifTrue: [e do: [:x | c add: x]] ifFalse: [c add: e]].
	^c
)
public hash ^<Integer> = (
	| count ::= 0. |
	^self inject: 0 into:
		[:previousHash <Integer> :element <E> |
		| newHash |
		newHash:: previousHash bitXor: element hash.
		count:: count + 1.
		count > 2 ifTrue: [^newHash].
		newHash]
)
public includes: o <Object> ^<Boolean> = (
	self do: [:element <E> | element = o ifTrue: [^true]].
	^false
)
public inject: initialValue <X> into: foldBlock <[:X def :E | X]> ^<X> = (
	| runningValue <X> |
	runningValue:: initialValue.
	self do: [:element <X> | runningValue:: foldBlock value: runningValue value: element].
	^runningValue
)
public intersection: other <Collection[Object]> ^<List[E]> = (
	^self select: [:each | other includes: each]
)
public isCollection ^<Boolean> = (
	^true
)
public isEmpty ^<Boolean> = (
	^0 == self size
)
public isKindOfCollection = (
	(* Should be auto-generated *)
	^true
)
public max = (
	^ self inject: self anyOne into: [:m :each | m max: each]
)
protected maxPrintElements ^<Int> = (
	^100
)
protected newForCollectUsingAdd: size <Int> ^<MutableArrayList[Object]> = (
	(* Return a new extensible collection that is as closely related to the receiver's class as possible.  The
	 returned collection must be unaliased and empty, so it is safe for the caller to guarantee that the type
	 variable is of a more specific type *)

	^MutableArrayList new: size
)
public noneSatisfy: predicate <[:E | Boolean]> ^<Boolean> = (
	self do: [:each | (predicate value: each) ifTrue: [^false]].
	^true
)
protected occurrencesOf: o <Object> ^<Int> = (
	| c <Int> |
	#BOGUS. (* Questionable *)
	c:: 0.
	do: [:e <E> | e = o ifTrue: [ c:: c + 1 ]].
	^c
)
public postCopy = (
	#BOGUS. (* Squeakism *)
)
protected printElementsDo: f <[:Object]> = (
	(* Evaluate the block with all the elements that should be shown as the contents in the printstring.  This provides a hook for things like MutableHashedMaps, which want to show their associations, not their values *)
	self do: f
)
public printOn: stream <CharOutputStream> = (
	| count <Integer> first <Boolean> |
	stream	nextPutAll: class mixin simpleName;
			nextPut: "(".
	count:: 0.
	first:: true.
	self printElementsDo:
		[:element <Object> |
		first
			ifTrue: [ first:: false ]
			ifFalse: [ stream space ].
		element printOn: stream.
		count:: count + 1.
		count >= maxPrintElements
			ifTrue: [ stream nextPut: "<"; print: size - count; nextPutAll: ' more elements>)'.
						^self]].
	stream nextPut: ")".
)
public reduce: reduceFn <[:RE def :RE | RE]> ^<RE> = (
	(* {where CONSTRAINER <RE> is returnType of #anElement message of receiverType} *)
	(* Like reduce:ifEmpty: except that it is a dynamic error to send this to an empty collection *)

	^self reduce: reduceFn ifEmpty: [Error signal: 'Cannot reduce an empty collection' ]
)
public reduce: reduceFn <[:RE def :RE| RE]> ifEmpty: onEmpty <[X def]> ^<RE | X> = (
	(* {where CONSTRAINER <RE> is returnType of #anElement message of receiverType} *)
	(* Reduce is similar to inject except that the first element is used as the injected
	  element for the rest of the collection.  It is often handier than inject.  For example:
		(#(1 2 3 4) reduce: [:a <Int> :b <Int> | a + b ]) sums a collection of numbers. *)

	(* esoteric typing %note: We need to ensure that E is a subtype of RE (the argument type for the reduction
		function), but since that would require a
		supertype constraint (which neither we nor anyone else support, we accomplish the same
	    thing indirectly by introducing an unreferenced type
		variable CONSTRAINER that is inferred to be E at the call site, and then constraining it with a bound
		of RE.  This will prevent any call where E > RE from typechecking.  However, since the
		typesystem doesn't 'know' that, we have to tell it that with a guarantee in the method body.
		Because of the CONSTRAINER, we know that the guarantee is true for all calls that typecheck.
		Of course, this is tricky, but at least we can express it, and in a way that hides the guarantee from
		callers! *)

	| current <RE> |
	self do:
		[:element <E> |
		| rel <RE> |
		rel:: element.
		current isNil
			ifTrue: [ current:: rel ]
			ifFalse: [ current:: reduceFn value: current value: rel ]	].
	^current isNil
		ifFalse: [ current ]
		ifTrue: [ onEmpty value ]
)
public reject: predicate <[:E | Boolean]> ^<List[E]> = (
	^self select: [:e | (predicate value: e) not ]
)
public select: predicate <[:E | Boolean]> ^<List[E]> = (
	| result <MutableArrayList[E]> |
	result:: self newForCollectUsingAdd: size.
	self do: [:element | (predicate value: element) ifTrue: [result add: element]].
	^result
)
public size ^<Integer> = (
	| count ::= 0. |
	self do: [:element <E> | count:: count + 1 ].
	^count
)
public species ^<Collection[E] class> = (
	^Set
)
public union: other <Collection[Object]> ^ <Set[Object]> = (
	^self asSet addAll: other; yourself
)
public value = (
	#BOGUS. (* Questionable *)
	^self
)
) : (
)
class HashedCollection new: cap = Collection (|
	protected table_0 <Array[A|Object]>
			(* The table holds either included entries, or an object indicating a deleted entry,
			which is currently the table itself.  This of course means that the table is not allowed
			as a valid element of the collection, but this is only an issue when writing reflective
			system code that violates encapsulation. *)
	protected size_0 <Integer>
			(* the number of collection elements (not the size of the table) *)
	protected deleted <Integer>
			(* the number of slots marked with the deletion placeholder *)
|initCapacity: cap) (
public add: val <A> ^<A> = (
	^include: val
)
public addAll: c <Collection[A]> ^<Collection[A]> = (
	c do: [:e <A> |
		add: e. ].
	^c
)
advanceAmount ^<Int> = (
	(* a large prime - 1 *)
		^99990
)
public at: key <K> ^<E> = (
	^at: key ifAbsent: [ Error signal: 'key not found' ]
)
public at: key <Object> ifAbsent: f <[X def]> ^<E|X> = (
	^elementFor:
			(valAt: key ifAbsent: [ ^f value ])
)
atIndex: i <Int>
inTable: tbl <Array[Object|A]>
occupiedSlotDo: occupied <[:A| X def]>
emptySlotDo: empty <[Y def]>
deletedSlotDo: deleted <[Z def]>
^<X|Y|Z> = (
	(* This is the core method that does the case analysis for a slot to
		determine whether it is occupied, deleted, or empty *)

	| el <A|Object> |
	el:: tbl at: i.
	el == nil
		ifTrue: [ ^empty value ].
	el == tbl
		ifTrue: [ ^deleted value ].

	(* The following guarantee is because the table uses a non-typesafe trick in
	  which the table pointer itself is used to indicate a deleted slot; thus the table
	  doesn't hold only values of type A.  The guarantee is safe because we know that
	  we only put either values or the table into the table, and the previous
	  statement already handled the case when el is the table pointer-
	  thus at this point by elimination el has to be a value of type A *)
	^occupied value: (* (guaranteed <A> *)el(* ) *)
)
buildValForKey: k <K> element: el <E> ^<A> = (
	(* construct an A from a K and an E *)
	subclassResponsibility
)
checkValidity = (
	(* This method performs various validity checks on the receiver *)

	| c <Int> |
	c:: 0.
	contentsDo:
		[:val <A> |
			assert: [ (at: (keyFor: val)) = (elementFor: val) ] message: ''.
			c:: c + 1.		].

	assert: [ c = size ] message: ''.
)
public contentsDo: f <[:A]> = (
	| tbl <Array[A|Object]> |
	#ACCESSBOGUS.
	tbl:: table.
	tbl == nil
		ifTrue: [ ^self ].

	1 to: tbl size do:
		[:index <Int> |
				atIndex: index
					inTable: tbl
					occupiedSlotDo:
						[:val <A> |
							f value: val	]
					emptySlotDo: [ ]
					deletedSlotDo: [ ]
		]
)
createFirstTable = (
	table:: newTableWithSize: firstTableSize.
)
public do: f <[:E]> = (
	contentsDo:
		[:val <A> |
			f value: (elementFor: val)		]
)
elementFor: val <A> ^<E> = (
	(* extract an E from an A *)
	subclassResponsibility
)
elementForCopy: el <A> ^<A> = (
	(* When a copy of the collection is made, this method implements what happens
	  to each element.  For example, MutableHashedMaps copy their elements, since the
	  associations are really part of the MutableHashedMap, whereas KeyedSets don't since the
	  associations are really elements of the collection. *)

	subclassResponsibility
)
firstTableSize ^<Integer> = (
	(* The size used for the table when the capacity is 0 and the first element is added *)

	^8
)
growIfNeeded = (
	(minTableSizeForCapacity: occupied) > table size
		ifTrue: [ growTable ]
)
growTable = (
	| new <Array[A|Object]> |
	new:: newTableWithSize: table size + table size.
	contentsDo:
		[:a_value <A> |
				lookup: (keyFor: a_value)
					inTable: new
					matchingSlotDo:
						[:index <Int> :val <A> |
							shouldNotHappen	]
					emptySlotDo:
						[:index <Int> |
							new at: index put: a_value	]
					deletedSlotsDo:
						[:index <Int> |
							shouldNotHappen ]
					mismatchingSlotsDo:
						[:index <Int> | (* ignore *) ]
		].
	deleted: 0.
	table: new.
)
hashFor: key <Object> ^<Int> = (
	(* return the appropriate hash value for a key *)
	subclassResponsibility
)
public include: val <A> ^<A> = (
	^include: val ifNew: []
)
public include: val <A> ifNew: ifNew <[]> ^<A> = (
	^tableAt: (keyFor: val) put: (elementFor: val) ifNew: ifNew
)
public includeAll: c <Collection[A]> ^<Collection[A]> = (
	c do: [:el <A> |
		include: el ].
	^c
)
public includesIndex: k <Object> ^<Boolean> = (
	valAt: k ifAbsent: [ ^false ].
	^true
)
public includesKey: k <Object> ^<Boolean> = (
	^includesIndex: k
)
public indexOf: el <Object> ^<K> = (
	^indexOf: el
			ifAbsent: [ error: 'Element not found' ]
)
public indexOf: el <Object> ifAbsent: blk <[X def]> ^<K | X> = (
	contentsDo:
		[:v <A> |
			(elementFor: v) = el
				ifTrue: [ ^keyFor: v ] ].
	^blk value
)
indexOf: key <Object> tableMask: mask <Int> ^<Int> = (
	^((hashFor: key) bitAnd: mask) + 1
)
initCapacity: cap <Int> = (
	size: 0.
	deleted: 0.
	cap > 0
		ifTrue: [ table:: newTableWithSize: (tableSizeForCapacity: cap). ].
)
key: key1 <Object> matches: key2 <Object> ^<Boolean> = (
	(* Test whether two keys match *)
	self subclassResponsibility
)
public keyAtValue: v <Object> ^<K> = (
	^indexOf: v
)
public keyAtValue: v <Object> ifAbsent: blk <[X def]> ^<K | X> = (
	^indexOf: v ifAbsent: blk
)
keyFor: val <A> ^<K> = (
	(* extract an K from an A *)
	subclassResponsibility
)
public keysDo: f <[:K]> = (
	contentsDo:
		[:val <A> |
			f value: (keyFor: val)		]
)
lookup: key <Object>
inTable: tbl <Array[Object|A]>
matchingSlotDo: matching <[:Int :A | X def]>
emptySlotDo: empty <[:Int | Y def]>
deletedSlotsDo: marked <[:Int]>
mismatchingSlotsDo: mismatch <[:Int]>
^<X|Y> = (
	(* This is the core method that looks for a slot suitable for the key,
		and evaluates the appropriate blocks.
	   The lookup process is iterative, terminating when a slot that is empty
	   or has a matching key is found *)

	| i <Int> mask <Int> |
	mask:: tbl size - 1.
	i:: indexOf: key tableMask: mask.
	[ 			atIndex: i
				inTable: tbl
				occupiedSlotDo:
					[:val <A> |
						(key: key matches: (keyFor: val))
							ifTrue: [ ^matching value: i value: val	 ]
							ifFalse: [ mismatch value: i	 ]
					]
				emptySlotDo:
					[ ^empty value: i ]
				deletedSlotDo:
					[ marked value: i	 ].
		i:: ((i + advanceAmount) bitAnd: mask) + 1.
	] repeat
)
lookup: key <Object>
matchingSlotDo: matching <[:Integer :A| X def]>
emptySlotDo: empty <[:Integer | Y def]>
deletedSlotsDo: marked <[:Integer]>
^<X|Y> = (
	^self		lookup: key
				inTable: self table
				matchingSlotDo: matching
				emptySlotDo: empty
				deletedSlotsDo: marked
				mismatchingSlotsDo: [:index <Integer> | (* ignore *) ]
)
markDeleted: index <Int> = (
	| tbl <Array[A|Object]> |
	tbl:: table.
	tbl at: index put: tbl.
	deleted: deleted + 1
)
minTableSize ^<Int> = (
	^4
)
minTableSizeForCapacity: cap <Integer> ^<Integer> = (
	(* max density is 50% full *)
	^cap + cap
)
newTableWithSize: tableSize <Int> ^<Array[A|Object]> = (
	^Array new: tableSize
)
objToIncludeFor: new <A> withExisting: other <A> ^<A> = (
	(* In the situation where a new value  is being 'include'ed in the collection, and there is already an existing
	 value with a matching key, this method determines what value is actually placed in the collection *)

	subclassResponsibility
)
occupied ^<Integer> = (
	^size + deleted
)
postCopy = (
	| tbl <Array[A|Object]> newtbl <Array[A|Object]> |

	super postCopy.
	tbl:: table.
	tbl == nil
		ifTrue: [ ^self ].

	newtbl:: newTableWithSize: tbl size.
	1 to: tbl size do:
		[:index <Int> |
			atIndex: index
					inTable: tbl
					occupiedSlotDo:
						[:val <A> |
							newtbl at: index put: (elementForCopy: val)	]
					emptySlotDo: [ ]
					deletedSlotDo:
						[ newtbl at: index put: newtbl		]
		].
	setTable: newtbl
)
printElementsDo: f <[:Object]> = (
	contentsDo: f
)
public remove: val <A> ^<A> = (
	^remove: val ifAbsent: [ error: 'value not in collection' ]
)
public remove: val <A> ifAbsent: f <[X def]> ^<A|X> = (
	removeKey: (keyFor: val) ifAbsent: f.
	^val
)
public removeAll: c <Collection[A]> ^<Collection[A]> = (
	c do: [:el <A> |
		remove: el ].
	^c
)
public removeAllSuchThat: test <[:A | Boolean]> = (
	copy contentsDo:
		[:el <A> |
			(test value: el)
				ifTrue: [ remove: el ]		]
)
public removeAt: k <K> ^<E> = (
	(* A synonym for #removeKey: for consistency with AddableList *)

	^removeKey: k
)
public removeAt: k <K> ifAbsent: f <[X def]> ^<E|X> = (
	(* A synonym for #removeKey:ifAbsent: for consistency with AddableList *)

	^removeKey: k ifAbsent: f
)
public removeEvery: val <A> ^<A> = (
	remove: val ifAbsent: [].
	^val
)
public removeKey: key <K> ^<E> = (
	^removeKey: key ifAbsent: [ error: 'key not found' ]
)
public removeKey: key <K> ifAbsent: f <[X def]> ^<E|X> = (
	table == nil
		ifTrue: [ ^f value	 ].
	^			lookup: key
				matchingSlotDo:
						[:index <Int> :val <A> |
							markDeleted: index.
							size: size - 1.
							elementFor: val		]
				emptySlotDo:
						[:index <Int> |
							f value	]
				deletedSlotsDo:
						[:index <Int> |
							(* ignore *)
						]
)
setTable: t <Array[A|Object]> = (
	table_0:: t.
)
public size ^<Int> = (
	^size_0
)
size: s <Int> = (
	size_0:: s
)
table = (
	^table_0
)
table: t <Array[A|Object]> = (
	setTable: t.
	assert: [deleted = 0] message: ''.
)
tableAt: key <K> put: el <E> ifNew: onNew <[]> ^<A> = (
	(* put a value for el in the right spot in the table, and return the val *)

	| reusableSlot <Integer> |
	table == nil
		ifTrue: [ self createFirstTable.	 ].
	^			lookup: key
				matchingSlotDo:
						[:index <Integer> :val <A> |
							self tableAt: key put: el inMatchingSlot: index value: val		]
				emptySlotDo:
						[:index <Integer> |
							| newVal <A> |
							reusableSlot == nil
								ifTrue: [ newVal:: self tableAt: key put: el inEmptySlot: index ]
								ifFalse: [ newVal:: self tableAt: key put: el inDeletedSlot: reusableSlot ].
							onNew value.
							newVal	]
				deletedSlotsDo:
						[:index <Integer> |
							reusableSlot == nil
								ifTrue: [ reusableSlot:: index ].
						]
)
tableAt: key <K>
put: el <E>
inDeletedSlot: index <Integer>
^<A> = (
	| val <A> |
	val:: tableAt: key put: el inUnusedSlot: index.
	deleted: deleted - 1.
	(* we don't have to check for growth when reusing a previously used slot *)
	^val
)
tableAt: key <K>
put: el <E>
inEmptySlot: index <Integer>
^<A> = (
	| val <A> |
	val:: tableAt: key put: el inUnusedSlot: index.
	growIfNeeded.
	^val
)
tableAt: key <K>
put: el <E>
inMatchingSlot: index <Integer>
value: val <A>
^<A> = (
	| newVal <A> |
	newVal:: objToIncludeFor: (buildValForKey: key element: el)
								withExisting: val.
	table at: index put: newVal.
	^newVal
)
tableAt: key <K>
put: el <E>
inUnusedSlot: index <Integer>
^<A> = (
	(* This does the core work for #tableAt:put: [inDeletedSlot:|inEmptySlot:] *)

	| newVal <A> |
	newVal:: buildValForKey: key element: el.
	table at: index put: newVal.
	size: size + 1.
	^newVal
)
tableSizeForCapacity: cap <Integer> ^<Integer> = (
	| min <Integer> tsize <Integer> |
	min:: minTableSizeForCapacity: cap.
	(* search for the smallest power of two that is >= min *)
	tsize:: minTableSize.
	[ tsize < min ]
	      whileTrue: [ tsize:: tsize + tsize ].
	^tsize
)
valAt: key <Object> ifAbsent: f <[X def]> ^<A|X> = (
	table == nil
		ifTrue: [ ^f value ].

	^			lookup: key
				matchingSlotDo:
					[:index <Integer> :val <A> |
						val	]
				emptySlotDo:
					[:index <Integer> |
						f value	]
				deletedSlotsDo:
					[:index <Integer> |
						(* ignore deleted slots *) ]
)
) : (
public defaultCapacity ^<Integer> = (
	^0
)
)
class IdentityMutableHashedMap new: cap = MutableHashedMap new: cap (
(* IdentityMutableHashedMaps are efficient HashedCollections that let you dynamically associate key->value
pairs,  where the keys are matched using the #== message. *)
) (
hashFor: key <Object> ^<Int> = (
	^key identityHash
)
key: k <Object> matches: another <Object> ^<Boolean> = (
	^k == another
)
) : (
public defaultCapacity ^<Int> = (
	^0
)
public new = (
	^new: defaultCapacity
)
)
public class IdentitySet new: cap <Integer> = Set new: cap () (
hashFor: key <Object> ^<Int> = (
		^key identityHash
)
key: k <Object> matches: another <Object> ^<Boolean> = (
	^k == another
)
) : (
public defaultCapacity = (
	^0
)
public new ^ <Instance> = (
	^self new: defaultCapacity
)
public withAll: cltn <Collection[A]> ^<Instance> = (
	^(new: cltn size) includeAll: cltn; yourself
)
)
public class Interval from: p_start <Number> to: p_stop <Number> by: p_step <Number> = AbstractList (
(* Intervals are Lists that generate their contents on the fly as a progression
of numbers from a start number to a stop number, separated by a step number.  Usually, the
to: [by:]do: messages defined in the Number subclasses are used instead of Intervals
when just a control structure is needed, since they are much faster.

Note on strong typing issues:

The to: [by:]do: messages in the Number hierarchy are typed restrictively, in such a way that they
can only be used in non-coercive situations (i.e. where the start, stop, and step are all integers,
or all floats, etc.).  This is done to preserve the type of the iteration value passed to the iteration block
in the pure integer form, so that bit operations etc. can be performed etc.  This would not be possible
if Number was the type for the step.  Although this may seem restrictive, the following points should
be noted about this design:

	1) explicit coercions handle the vast majority of these cases;
		for example, use (j asFloat to: k asFloat by: 0.1) rather than
		 (j to: k by: 0.1) when j and k are typed as Numbers or Integers.
	2) this scheme is perfectly compatible with untyped code, since the typed versions will work correctly
	    even if called with arguments of mismatched numeric types, so that things like (1 to: 10 by: 0.1) will
	    work, even though they don't typecheck.
	3) If full coercive generality is needed in typesafe code, the Interval class can be used, which has been
	    designed using values of type Number, so that things like (1 to: 10 by: 0.1) are ok.  They cannot, however,
		preserve more detailed information about the kinds of numbers in the Interval. *)
|
	public start <Number> = p_start.
	public stop <Number> = p_stop.
	public increment <Number> = p_step.
|) (
public at: index <Integer> ^<Number> = (
	(start - stop) sign = increment sign
		ifFalse: [ | value <Number> |
						value: start + (increment * (index - 1)).
						increment >= 0
							ifTrue: [ ( value between: start and: stop)
												ifTrue: [ ^value ]	]
							ifFalse: [ (value between: stop and: start)
												ifTrue: [ ^value ]	]	].
	Error signal: 'Index out-of-range'.
)
copyWithSize: s <Int> ^<MutableList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)
	self unimplemented
)
public do: action <[:Number]> = (
	|
	value <Number> ::= self start.
	incr <Number> = self increment.
	stp <Number> = self stop.
	|
	incr >= 0
		ifTrue: [ [ value <= stp ]
							whileTrue: [ action value: value.
										value:: value + incr.	]	]
		ifFalse: [ [ value >= stp ]
							whileTrue: [ action value: value.
										value:: value + incr.	]	]
)
public size ^<Integer> = (
	^((stop - start) // increment) + 1 max: 0
)
) : (
public from: start <Number> to: stop <Number> ^<Instance> = (
	^self from: start to: stop by: 1
)
)
class MutableArrayList = MutableAddableList (
(* MutableArrayLists are AddableLists that also support setting
elements in place (the MutableList protocol). *)
) (
public add: e <E> ^<E> = (
	^addLast: e
)
public add: el <E> after: existing <E> ^<E> = (
	| index <Int> |
	index:: indexOf: existing.
	index = size
		ifFalse: [ index:: makeSpace: 1
							beforeIndex: index + startGap + 1 ]
		ifTrue: [ needSpaceAtEnd: 1.
						index:: index + startGap + 1.	].
	^contents at: index put: el.
)
public add: el <E> afterIndex: i <Int> ^<E> = (
	^add: el beforeIndex: i + 1
)
public add: el <E> before: existing <E> ^<E> = (
	| index <Int> |
	index:: indexOf: existing.
	index:: makeSpace: 1 beforeIndex: index + startGap.
	^contents at: index put: el.
)
public add: el <E> beforeIndex: i <Int> ^<E> = (
	| index <Int> |
	i > size
		ifFalse: [ index:: makeSpace: 1 beforeIndex: i + startGap]
		ifTrue: [ needSpaceAtEnd: 1.
					index:: i + startGap. ].
	^contents at: index put: el.
)
public addAllFirst: c <Collection[E]> ^<Collection[E]> = (
	c do: [:el <E> | 	addFirst: el ].
	^c
)
public addAllLast: c <Collection[E]> ^<Collection[E]> = (
	c do: [:el <E> | 	addLast: el ].
	^c
)
public addFirst: e <E> ^<E> = (
	needSpaceAtStart: 1.
	contents at: startGap put: e.
	startGap: startGap - 1.
	^e
)
public addLast: e <E> ^<E> = (
	needSpaceAtEnd: 1.
	lastIndex: lastIndex + 1.
	contents at: lastIndex put: e.
	^e
)
public asMutableArrayList ^<MutableArrayList[EX]> = (
		(* {where EX is returnType of #anElement message of receiverType} *)

	(* the guarantee is safe because of the inference clause *)
	^(* guaranteed <MutableArrayList[EX]> *) self
)
public at: i <Int> put: el <E> ^<E> = (
	| adjusted <Int> |
	adjusted:: i + startGap.
	((0 < i) and: [adjusted <= lastIndex])
		ifFalse: [ error: 'invalid index' ].
	^contents at: adjusted put: el
)
public collect: map <[:E | R def]> ^<MutableArrayList[R]> = (
	^(collectUsingAdd: map) asMutableArrayList
)
public copyWithSize: s <Int> ^<MutableArrayList[EX]> = (
	(* {where EX is returnType of #anElement message of receiverType} *)

	(* Note: this method temporarily mutates the receiver, so it should not be sent to an object that
		another process might be accessing. *)

	(* We use a trick here: we temporarily fudge the lastIndex to be the value we want to use in the copy,
	  which will cause postCopy to copy the contents with a different size, and then we restore the old
	  lastIndex value for this instance.  This lets the normal copy mechanism handle subclass instance
	  variable copying. *)
	| oldLastIndex <Int> safeself <MutableArrayList[EX]> copy <MutableArrayList[EX]> |

	(* This guarantee is safe because the inference clause guarantees
		that E < EX at each call site *)
	safeself:: (* guaranteed <MutableArrayList[EX]> *) self.

	oldLastIndex:: lastIndex.
	lastIndex: s + startGap.
	copy:: safeself copy.
	lastIndex: oldLastIndex.

	^copy
)
public newCopyOfSize: size <Int>
thatCanAlsoHoldElementsOf: other <List[X]>
^<MutableArrayList[EX | X]> = (
		(* {where X is returnType of #anElement message of arg 2;
		     where EX is returnType of #anElement message of receiverType} *)

	^(MutableArrayList(* [EX | X] *) new: size) size: size
)
public replaceFrom: start <Int>
to: stop <Int>
with: other <List[E]>
startingAt: repStart <Int> = (
	(* replace the elements of the receiver from start to stop with elements from other,
	  starting with the element of other with index repStart. *)

	| otheri <Int> |
	(start >= 1 and: [ stop <= size ])
		ifFalse: [ error: 'range out of bounds' ].

	contents replaceFrom: start + startGap to: stop + startGap with: other startingAt: repStart
)
) : (
public defaultCapacity ^<Int> = (
	^5
)
public new: capacity <Int> ^<Instance> = (
	^new initCapacity: capacity
)
public with: val1 <E> ^<Instance> = (
	^(new: 1) add: val1; yourself
)
public withAll: cltn <Collection[E]> ^<Instance> = (
	^(new: cltn size) addAll: cltn; yourself
)
)
class MutableHashedMap new: cap = HashedCollection new: cap (
(* MutableHashMaps are efficient HashedCollections that let you dynamically associate key->value
pairs,  where the keys are matched using the #= message.  Equal keys must have equal #hash
values. *)
) (
public = other <Object> ^<Boolean> = (
	^super = other and: [
		self == other or: [
			(* We already know that the other object must be a MutableHashedMap *)
			self keys = other keys	]]
)
associationAt: key <K> ^<Assoc[K,E]> = (
	^associationAt: key ifAbsent: [ error: 'key not found' ]
)
associationAt: key <K> ifAbsent: failBlock <[X def]> ^<Assoc[K,E] | X> = (
	^valAt: key ifAbsent: failBlock
)
associations ^<MutableArrayList[Assoc[K,E]]> = (
	| oc <MutableArrayList[Assoc[K,E]]> |

	oc:: MutableArrayList new: size.
	associationsDo:
		[:assoc <Assoc[K,E]> |
			oc add: assoc	].
	^oc
)
associationsDo: f <[:Assoc[K,E]]> = (
	contentsDo:
		[:assoc <Assoc[K,E]> |
			f value: assoc ]
)
public at: key <K> ifAbsentPut: ablk <[V]> ^<V> = (
	^self at: key ifPresent: [:e | e] ifAbsentPut: ablk
)
public at: key <K> ifPresent: pblk <[:E]> ifAbsentPut: ablk <[E]> ^<E> = (
	(* This is a method that is useful in the common case when you want
		to find out if a key is present, and if it isn't, put an entry in for it.
		It is much faster than a construct like (hc at: k ifAbsent: [ hc at: k put: e ])
		for the case when a new entry must be added.
		If the key is present, pblk is evaluated with the associated element.
		If it is absent, then ablk is evaluated, and the value that it returns
		is associated with k in the receiver.  In either case, the associated element
		is returned. *)

	| reusableSlot <Int> |
	#BOGUS. (* Remove this method. *)
	table == nil
		ifTrue: [ createFirstTable.	 ].
	^lookup: key
				matchingSlotDo:
						[:index <Int> :assoc <VarAssoc[K,E]> |
							| el <E> |
							el:: assoc value.
							pblk value: el.
							el		]
				emptySlotDo:
						[:index <Int> |
							| newEl <E> |
							newEl:: ablk value.
							reusableSlot == nil
								ifTrue: [ tableAt: key put: newEl inEmptySlot: index ]
								ifFalse: [ tableAt: key put: newEl inDeletedSlot: reusableSlot ].
							newEl	]
				deletedSlotsDo:
						[:index <Int> |
							reusableSlot == nil
								ifTrue: [ reusableSlot:: index ].
						]
)
public at: key <K> put: el <E> ^<E> = (
	^at: key put: el ifNew: []
)
protected at: key <K> put: el <E> ifNew: blk <[]> ^<E> = (
	#BOGUS. (* Remove this method. *)
	tableAt: key put: el ifNew: blk.
	^el
)
protected buildValForKey: k <K> element: el <E> ^<VarAssoc[K,E]> = (
	^Association key: k value: el
)
protected elementFor: assoc <Assoc[K,E]> ^<E> = (
	^assoc value
)
protected elementForCopy: el <VarAssoc[K,E]> ^<VarAssoc[K,E]> = (
	^el copy
)
protected hashFor: key <Object> ^<Int> = (
	^key hash
)
public includesAssociation: assoc <Assoc[K,Object]> ^<Boolean> = (
	^(at: assoc key ifAbsent: [ ^false ]) = assoc value
)
public isDictionary ^<Boolean> = (
	^true
)
public isKindOfMap ^<Boolean> = (
	^true
)
protected key: k <Object> matches: another <Object> ^<Boolean> = (
	^k = another
)
protected keyFor: assoc <Association[K, V]> ^<K> = (
	^assoc key
)
public keys ^<Set[K]> = (
	| s <Set[K]> |
	s:: Set new: size.
	self keysDo: [:key <K> | s include: key ].
	^s
)
public keysAndValuesDo: action <[:K :V]> = (
	self contentsDo:
		[:assoc <Association[K, V]> | action value: assoc key value: assoc value ]
)
protected objToIncludeFor: newAssoc <VarAssoc[K,E]> withExisting: assoc <VarAssoc[K,E]> ^<VarAssoc[K,E]> = (
	(* MutableHashMaps reuse the previous association *)
	assoc value: newAssoc value.
	^assoc
)
protected tableAt: key <K>
put: el <E>
inMatchingSlot: index <Int>
value: val <VarAssoc[K,E]>
^<VarAssoc[K,E]> = (
	val value: el.
	^val
)
public values ^<MutableArrayList[V]> = (
	^self inject: (MutableArrayList new: size) into:
		[:oc <MutableArrayList[V]> :el <V> |
			oc add: el; yourself ]
)
) : (
public defaultCapacity ^<Integer> = (
	^0
)
public new = (
	^self new: defaultCapacity
)
public with: val1 <A> ^<Instance> = (
	^(self new: 1) include: val1; yourself
)
public withAll: cltn <Collection[A]> ^<Instance> = (
	^(self new: cltn size) includeAll: cltn; yourself
)
)
class MutableList = AbstractList (
(* This class extends List[E] with mutation operations defined in terms of #at:put:.
The List[E] protocol is defined from this class' interface. *)
) (
public at: index <Int> put: el <E> ^<E> = (
	self subclassResponsibility
)
defaultMedianOf: a <Int> and: b <Int> and: c <Int> ^<Int> = (
	(* This is an untypesafe method that only works for MutableLists of elements that
		have Magnitude relationships with each other.  It is used by the default sorting
		method. *)

	| atA <E> atB <E> atC <E> |
	atA:: at: a.
	atB:: at: b.
	atC:: at: c.
	^atB <= atA
		ifFalse: [ atC <= atB
							ifFalse: [ b ]
							ifTrue: [ atC <= atA
												ifFalse: [ c ]
												ifTrue: [ a ] 	] ]
		ifTrue: [ atB <= atC
							ifFalse: [ b ]
							ifTrue: [ atA <= atC
												ifFalse: [ c ]
												ifTrue: [ a ] 	] ]
)
defaultSort: l <Int> to: r <Int> = (
	(* This is an untypesafe method that only works for MutableLists of elements that
		have Magnitude relationships with each other *)

	| i <Int> j <Int> x <E> m <Int> n <Int> |
	i:: l.
	j:: r.
	n:: ((r - l) + 1).
	n == 0
		ifTrue: [ ^self ].

	(* Pick the partition value.  For <=7 elements, use the middle element.
		For more than 7 but <= 40, use a median of three elements.  For > 40,
		use a median of three medians of three *)
	m:: (l + r) // 2.
	n > 7
		ifTrue: [ | pl <Int> pn <Int> s <Int> |
						pl:: l.
						pn:: r.
						n > 40
							ifTrue: [ s:: n // 8.
											pl:: defaultMedianOf: pl and: pl+s and: pl+s+s.
											m:: defaultMedianOf: m-s and: m and: m+s.
											pn:: defaultMedianOf: (pn-s)-s and: pn-s and: pn.	].
						m:: defaultMedianOf: pl and: m and: pn.		].
	x:: at: m.

	[i <= j]
		whileTrue:
			[ | ati <E> atj <E> |
			 	[ x <= (ati:: at: i)]
					whileFalse: [i:: i + 1].
				[(atj:: at: j) <= x]
					whileFalse: [j:: j - 1].
				i <= j
					ifTrue: [ at: i put: atj.
									at: j put: ati.
									i:: i + 1.
									j:: j - 1]
			].
	l < j ifTrue: [defaultSort: l to: j ].
	i < r ifTrue: [defaultSort: i to: r ].
)
medianOf: a <Int> and: b <Int> and: c <Int> using: compare <[:E :E | Boolean]> ^ <Int> = (
	| atA <E> atB <E> atC <E> |
	atA:: at: a.
	atB:: at: b.
	atC:: at: c.
	^(compare value: atB value: atA)
		ifFalse: [ (compare value: atC value: atB)
							ifFalse: [ b ]
							ifTrue: [ (compare value: atC value: atA)
												ifFalse: [ c ]
												ifTrue: [ a ] 	] ]
		ifTrue: [ (compare value: atB value: atC)
							ifFalse: [ b ]
							ifTrue: [ (compare value: atA value: atC)
												ifFalse: [ c ]
												ifTrue: [ a ] 	] ]
)
readWriteStream ^<ReadWriteStream[E]> = (
	^ListReadWriteStream on: self
)
public replaceFrom: start <Int>
to: stop <Int>
with: other <List[E]> = (
	(* replace the elements of the receiver from start to stop with elements from other,
	  starting with the first element of other. *)

	^replaceFrom: start to: stop with: other startingAt: 1
)
public replaceFrom: start <Int>
to: stop <Int>
with: other <List[E]>
startingAt: repStart <Int> = (
	(* replace the elements of the receiver from start to stop with elements from other,
	  starting with the element of other with index repStart. *)

	| otheri <Int> |

	repStart < start
		ifFalse: [ otheri:: repStart.
				  start to: stop do:
					[:i <Int> |
						at: i put: (other at: otheri).
						otheri:: otheri + 1.	]]
		ifTrue: [ otheri:: repStart + (stop - start).
				stop to: start by: -1 do:
					[:i <Int> |
						at: i put: (other at: otheri).
						otheri:: otheri - 1.	]]
)
swap: i <Int> with: j <Int> = (
	| t <E> |
	t:: at: i.
	at: i put: (at: j).
	at: j put: t.
)
writeStream ^<WriteStream[E]> = (
	^readWriteStream
)
) : (
)
public class Set new: cap = HashedCollection new: cap () (
public asSet ^<Extensible[EX]> = (
		(* {where EX is returnType of #anElement message of receiverType} *)

	(* The guarantee is safe because of the inference clause *)
	^(* guaranteed <Set[EX]> *) self
)
buildValForKey: key <Object> element: el <E> ^<E> = (
	^el
)
elementFor: el <E> ^<E> = (
	^el
)
elementForCopy: el <E> ^<E> = (
	^el
)
public hasSameElementsAs: other <Collection[Object]> ^<Boolean> = (
	(* A faster reimplementation of the inherited version, to speed up set comparisons *)

	| otherSet <Extensible[Object]> |
	size = other size
		ifFalse: [ ^false ].
	otherSet:: other asSet.
	size = otherSet size
		ifFalse: [ ^false ].
	do:
		[:el <Object> |
			(otherSet includes: el)
				ifFalse: [ ^false ] ].
	^true
)
hashFor: key <Object> ^<Int> = (
	^key hash
)
public includes: o <Object> ^<Boolean> = (
	^includesKey: o
)
public isKindOfSet ^ <Boolean> = (
	^true
)
key: k <Object> matches: another <Object> ^<Boolean> = (
	^k = another
)
keyFor: e <E> ^<Object> = (
	^e
)
objToIncludeFor: new <E> withExisting: other <E> ^<E> = (
	^new
)
) : (
public defaultCapacity = (
	^0
)
public new = (
	^new: defaultCapacity
)
public with: val1 <A> ^<Instance> = (
	^(new: 1) include: val1; yourself
)
public withAll: cltn <Collection[A]> ^<Instance> = (
	^(new: cltn size) includeAll: cltn; yourself
)
)
public class SortedList = AddableList (
	(* Sorted collections are addable collections that always keep their elements in sorted order.  The
	sort order is determined by the sortPredicate, which is a function that compares 2 elements and
	returns true if the first argument should be before the second argument in the collection.
	The sortPredicate should be provided when the collection is created.

	Unfortunately, Smalltalk defines SortedList as having a default sortPredicate that uses #<= to compare
	elements.  This is NOT typesafe, since there are many kinds of objects that you might want to sort that don't support
	the #<= operator; however, this feature is retained in Strongtalk for compatibility.   If you wish to write typesafe programs,
	then SortedLists should always be given a sort block when they are created.  This involves using the creation
	messages #new:sortBlock:, #sortBlock: and the Collection utility message #asSortedList: instead of #new:, #new,
	and #asSortedList, respectively. *)
|
	private usesDefaultSortBlock_private <Boolean>
	private sortBlock_private <[:E :E | Boolean]>
|initCapacity: self class defaultCapacity.
	sortBlock_private:: SortedList defaultSortBlock.
	usesDefaultSortBlock_private:: true) (
public add: el <E> ^<E> = (
	| index <Integer> |
	index:: indexFor: el.
	index > contents size
		ifFalse: [ index:: makeSpace: 1 beforeIndex: index]
		ifTrue: [ needSpaceAtEnd: 1.
						lastIndex: lastIndex + 1. ].
	^contents at: index put: el.
)
public addAll: els <Collection[E]> ^<Collection[E]> = (
	els size > (size // 8) 		 (* %todo: do measurements to see if 8 is reasonable *)
		ifTrue: [ 	needSpaceAtEnd: els size.
				els do: [:el <E> |
					lastIndex: lastIndex + 1.
					contents at: lastIndex put: el.	].
				sort.		]
		ifFalse: [ els do: [:el <E> |
					add: el	]].
	^els
)
public asSortedList ^<List[Object]> = (
	^self
)
indexFor: el <E> ^<Integer> = (
	(* This returns an internal index such that if el was inserted before it
	  the collection would remain sorted *)

	^contents
		binarySearchFor: el
		between: startGap + 1
		and: lastIndex
		toCompare: sortBlock
)
public initCapacity: cap <Int> = (
	super initCapacity: cap.
)
public isSorted ^<Boolean> = (
	(* testing function used for sort routine validation *)

	^isSortedBy: sortBlock
)
public sort = (
	usesDefaultSortBlock
		ifTrue: [ contents defaultSort: startGap + 1 to: lastIndex ]
		ifFalse: [ 	contents sort: startGap + 1 to: lastIndex using: sortBlock ]
)
public sortBlock ^<[:E :E | Boolean]> = (
	^sortBlock_private
)
public sortBlock: sortBy <[:E :E | Boolean]> = (
	sortBlock_private:: sortBy.
	usesDefaultSortBlock_private:: false.
	isEmpty ifFalse: [ sort. ].
)
public usesDefaultSortBlock ^<Boolean> = (
	^usesDefaultSortBlock_private
)
) : (
public defaultCapacity ^<Int> = (
	^5
)
public defaultSortBlock ^<[:E :E | Boolean]> = (
	^[:el1 <E> :el2 <E> |
		(* The default sort block for SortedLists is is not typesafe, but is included for
		 Smalltalk compatibility (that's the way Smalltalk is!). *)
		(
(* guaranteed <Magnitude[E]> *) el1) <= el2	].
)
public new: capacity <Integer> ^<Instance> = (
	^new initCapacity: capacity
)
public new: capacity <Integer> sortBlock: sort <[:E :E | Boolean]> ^<Instance> = (
	^(new: capacity) sortBlock: sort
)
public sortBlock: sort <[:E :E | Boolean]> ^<Instance> = (
	^new: defaultCapacity sortBlock: sort
)
public with: val1 <E> ^<Instance> = (
	^(new: 1) add: val1; yourself
)
public withAll: cltn <Collection[E]> ^<Instance> = (
	^(new: cltn size) addAll: cltn; yourself
)
)
public class NotFound element: e = Exception (
	|
	public element = e.
	|
) (
public printString = (
	^'NotFound: ', element printString
)
) : (
)
public class OrderedMap new: capacity <Integer> = (
(* Like Map, but iteration happens in insertion order.

If the value associated with a key changes while the key is already in the map, the key's order does not change. Removing a key and adding it back will change the key's order to last. *)
	|
	protected nextKeyIndex_ <Integer>
	protected deleted_ <Integer>
	protected buckets_ <Integer>
	protected table_ <Array>
	|
	createTable: capacity.
) (
public at: key <K> ^<V> = (
	^self at: key ifAbsent: [(NotFound element: key) signal]
)
public at: key <K> ifAbsent: onAbsent <X def> ^<K | X> = (
	| bucketIndex keyIndex |
	bucketIndex:: scanFor: key.
	bucketIndex < 0 ifTrue:
		[^onAbsent value].
	keyIndex:: table_ at: bucketIndex.
	^table_ at: 1 + keyIndex
)
public at: key <K> ifAbsentPut: valueGenerator <[V]> ^<V> = (
	| bucketIndex keyIndex |
	bucketIndex:: scanFor: key.
	bucketIndex < 0 ifTrue:
		[^insert: 0 - bucketIndex key: key value: valueGenerator value].
	keyIndex:: table_ at: bucketIndex.
	^table_ at: 1 + keyIndex
)
public at: key <K> put: value ^<V> = (
	| bucketIndex keyIndex |
	bucketIndex:: scanFor: key.
	bucketIndex < 0 ifTrue:
		[^insert: 0 - bucketIndex key: key value: value].
	keyIndex:: table_ at: bucketIndex.
	^table_ at: 1 + keyIndex put: value
)
checkRehash = (
	| oldTable oldFirstKeyIndex oldLastKeyIndex |
	nextKeyIndex_ + 2 < table_ size ifTrue: [^self].

	oldTable:: table_.
	oldFirstKeyIndex:: 1 + buckets_.
	oldLastKeyIndex:: nextKeyIndex_ - 1.

	createTable: size << 1.

	oldFirstKeyIndex to: oldLastKeyIndex by: 2 do:
		[:oldKeyIndex | | key newBucketIndex newKeyIndex |
		 key:: oldTable at: oldKeyIndex.
		 oldTable = key ifFalse:
			[newBucketIndex:: scanForEmptySlotFor: key.
			 newKeyIndex:: nextKeyIndex_.
			 nextKeyIndex_:: 2 + newKeyIndex.
			 table_
				at: newBucketIndex put: newKeyIndex;
				at: newKeyIndex put: key;
				at: 1 + newKeyIndex put: (oldTable at: 1 + oldKeyIndex)]].
)
public collect: transform <[:V | W]> ^<Map[K, W]> = (
	|
	result = OrderedMap new: size.
	table = table_.
	|
	1 + buckets_ to: nextKeyIndex_ - 2 by: 2 do:
		[:keyIndex | | key |
		 key:: table at: keyIndex.
		 table = key ifFalse:
			[result at: key put: (transform value: (table at: 1 + keyIndex))]].
	^result
)
createTable: numElements <Integer> = (
	(* [1, buckets_] is the hash table. 0 means empty, 1 means deleted, otherwise the index of the key.
	   [buckets_ + 1, size] are the keys and values in insertion order. table_ means deleted. *)
	numElements < 0 ifTrue: [^(ArgumentError value: numElements) signal].
	buckets_:: numElements + 1 * 4 // 3.
	nextKeyIndex_:: 1 + buckets_.
	table_:: Array new: numElements + 1 << 1 + buckets_.
	deleted_:: 0.
	1 to: buckets_ do: [:hashIndex | table_ at: hashIndex put: 0].
)
public do: action <[:V]> = (
	| table = table_. |
	1 + buckets_ to: nextKeyIndex_ - 2 by: 2 do:
		[:keyIndex | | key |
		 key:: table at: keyIndex.
		 table = key ifFalse:
			[action value: (table at: 1 + keyIndex)]].
)
public includesKey: key <K> ^<Boolean> = (
	^(scanFor: key) > 0
)
insert: bucketIndex key: key value: value = (
	| keyIndex |
	keyIndex:: nextKeyIndex_.
	nextKeyIndex_:: 2 + keyIndex.
	table_
		at: bucketIndex put: keyIndex;
		at: keyIndex put: key;
		at: 1 + keyIndex put: value.
	checkRehash.
	^value
)
public isEmpty ^<Boolean> = (
	^0 = size
)
public isKindOfMap ^<Boolean> = (
	^true
)
public isKindOfOrderedMap ^<Boolean> = (
	^true
)
public keys ^<OrderedSet[V]> = (
	|
	result = OrderedSet new: size.
	table = table_.
	|
	1 + buckets_ to: nextKeyIndex_ - 2 by: 2 do:
		[:keyIndex | | key |
		 key:: table at: keyIndex.
		 table = key ifFalse: [result add: key]].
	^result
)
public keysAndValuesDo: action <[:K :V]>  = (
	| table = table_. |
	1 + buckets_ to: nextKeyIndex_ - 2 by: 2 do:
		[:keyIndex | | key |
		 key:: table at: keyIndex.
		 table = key ifFalse:
			[action value: key value: (table at: 1 + keyIndex)]].
)
public reject: predicate <[:V | Boolean]> ^<Map[K, V]> = (
	|
	result = OrderedMap new: size.
	table = table_.
	|
	1 + buckets_ to: nextKeyIndex_ - 2 by: 2 do:
		[:keyIndex | | key |
		 table = (key:: table at: keyIndex) ifFalse:
			[ | value = table at: 1 + keyIndex. |
			 (predicate value: value) ifFalse:
				[result at: key put: value]]].
	^result
)
public removeKey: key <K> ^<V> = (
	^self removeKey: key ifAbsent: [(NotFound element: key) signal]
)
public removeKey: key <K> ifAbsent: onAbsent <[X def]> ^<V | X> = (
	| bucketIndex table keyIndex oldValue |
	bucketIndex:: scanFor: key.
	bucketIndex < 0 ifTrue:
		[^onAbsent value].
	table:: table_.
	keyIndex:: table at: bucketIndex.
	table at: bucketIndex put: 1 (* deleted *).
	deleted_:: 1 + deleted_.
	oldValue:: table at: 1 + keyIndex.
	table at: 1 + keyIndex put: table.
	table at: keyIndex put: table.
	^oldValue
)
scanFor: key <K> ^<Integer> = (
	(* Positive: key present. Negative: insert point. *)
	| table buckets bucketIndex start |
	table:: table_.
	buckets:: buckets_.
	bucketIndex:: start:: key hash \\ buckets + 1.
	[ | keyIndex |
	 0 (* empty *) = (keyIndex:: table at: bucketIndex) ifTrue:
		[^0 - bucketIndex].
	 1 (* deleted *) = keyIndex ifFalse:
		[key = (table at: keyIndex) ifTrue:
			[^bucketIndex]].
	 (bucketIndex:: bucketIndex \\ buckets + 1) = start] whileFalse.
	self errorNoFreeSpace
)
scanForEmptySlotFor: key <K> ^<Integer> = (
	| table buckets bucketIndex start |
	table:: table_.
	buckets:: buckets_.
	bucketIndex:: start:: key hash \\ buckets + 1.
	[0 = (table at: bucketIndex) ifTrue: [^bucketIndex].
	 (bucketIndex:: bucketIndex \\ buckets + 1) = start] whileFalse.
	self errorNoFreeSpace
)
public select: predicate <[:V | Boolean]> ^<Map[K, V]> = (
	|
	result = OrderedMap new: size.
	table = table_.
	|
	1 + buckets_ to: nextKeyIndex_ - 2 by: 2 do:
		[:keyIndex | | key |
		 table = (key:: table at: keyIndex) ifFalse:
			[ | value = table at: 1 + keyIndex. |
			 (predicate value: value) ifTrue:
				[result at: key put: value]]].
	^result
)
public size ^<Integer> = (
	^(nextKeyIndex_ - buckets_) >> 1 - deleted_
)
public values ^<List[V]> = (
	|
	result = List new: size.
	table = table_.
	|
	1 + buckets_ to: nextKeyIndex_ - 2 by: 2 do:
		[:keyIndex |
		 table = (table at: keyIndex) ifFalse:
			[result add: (table at: 1 + keyIndex)]].
	^result
)
) : (
public new ^<OrderedMap[K, V]> = (
	^self new: 3
)
)
public IdentityMap = (
	^IdentityMutableHashedMap
)
public List = (
	^MutableArrayList
)
public Map = (
	^MutableHashedMap
)
error: s = (
	^Error signal: s
)
) : (
)