Class new title: HashSet
	subclassof: Object
	fields: 'objects'
	declare: ''

asStream 
	[self contents asStream]

contents | t1 t2  
	[t2 _ (Vector new: objects length) asStream.
	for t1 from: objects do
		[t1  nil  []
		t2 next_ t1].
	t2 contents]

copy 
	[self class new copyfrom: self]

copyfrom: t1 
	[objects _ t1 objects copy]

delete: t1 | t2 t3 t4  
	[t1 is: Vector  [for t2 from: t1 do
			[self delete: t2]]
	t2 _ self findorerror: t1.
	objects  t2 _ nil.
	t4 _ objects length.
	while [t2 _ [t2 = t4  [1]
			t2 + 1].
	objects  t2  nil  false] do
		[t3 _ self findornil: objects  t2.
		t2 = t3  []
		self swap: t2 with: t3]]

find: t1 | t2 
	[t2 _ self findornil: t1.
	objects  t2 = t1  [t2]
	false]

findorerror: t1 | t2 
	[t2 _ self findornil: t1.
	objects  t2 = t1  [t2]
	user notify: t1 asString + ' cannot be found'.
	t2]

findorinsert: t1 | t2 
	[t2 _ self findornil: t1.
	objects  t2 = t1  [t2]
	self sparse 
		[objects  t2 _ t1.
		t2]
	self growto: objects length * 2.
	self findorinsert: t1]

findornil: t1 | t2 t3  
	[t3 _ t1 hash \ objects length.
	for t2 to: objects length do
		[t3 _ [t3 = objects length  [1]
				t3 + 1].
		objects  t3  nil  [t3]
		objects  t3 = t1  [t3]].
	1]

growto: t1 | t2 t3   
	[t2 _ self class new init: t1.
	[t1 < objects length  [for t3 from: self do
			[t2 insert: t3]]
	for t3 from: self do
		[t2 rawinsert: t3]].
	objects _ t2 objects]

has: t1 
	[objects  (self findornil: t1) = t1]

init 
	[self init: 4]

init: t1 
	[objects _ Vector new: (t1 max: 2)]

insert: t1 | t2 
	[self findorinsert: t1.
	t1]

insertall: t1 | t2  
	[for t2 from: t1 do
		[self insert: t2]]

objects [objects]

objects_ t1 
	[objects _ t1]

packprobes | t1 t2 t3 t4 t5 t6  
	[t2 _ 0.
	t1 _ t2.
	t3 _ objects length.
	for t4 to: t3 do
		[t5 _ objects  t4.
		t5  nil  []
		t6 _ t5 hash \ t3.
		t1 _ t1 + [t4 < t6  [t3 - t6 + t4]
				t4 - t6].
		t2 _ t2 + 1].
	t2 = 0  [1 , 1]
	t2 asFloat / t3 , (t1 asFloat / t2)]

rawinsert: t1 | t2 
	[t2 _ self findornil: t1.
	objects  t2 _ t1.
	t2]

rehash | t1 t2  
	[t2 _ HashSet new init: self size.
	for t1 to: objects length do
		[objects  t1  nil  []
		t2 insert: objects  t1].
	objects _ t2 objects]

shrink | t1 t2 
	[t2 _ self.
	t1 _ t2 growto: (2 max: t2 size / 2).
	until t1 size = t2 size do
		[(t2 size - t1 size) print.
		user show: ' '.
		t2 _ t1.
		t1 _ t2 growto: (2 max: t2 size / 2)].
	t1]

size 
	[objects length]

sparse | t1 t2  
	[t2 _ objects length.
	for t1 to: objects length do
		[objects  t1  nil 
			[t2 _ t2 - 8.
			t2 
 0  [true]]].
	false]

swap: t1 with: t2 
	[objects swap: t1 with: t2]