HashMap
and HashSet
.core :: union_find
union–find algorithm using an efficient disjoint-set data structurebucketed_game :: bucketed_game
Game framework with an emphasis on efficient event coordinationaccept_scroll_and_zoom
gamnit :: camera_control_android
Two fingers camera manipulation, pinch to zoom and slide to scrollgamnit :: camera_control_linux
Mouse wheel and middle mouse button to control camerapthreads :: concurrent_array_and_barrier
A basic usage example of the modulespthreads
and pthreads::cocurrent_collections
pthreads :: concurrent_collections
Introduces thread-safe concurrent collectionsserialization :: custom_serialization
Example of an ad hoc serializer that is tailored to transform business specific objects into customized representation.egl
, sdl
and x11
FileServer
action, which is a standard and minimal file server
cocoa :: foundation
The Foundation Kit provides basic Objective-C classes and structuresfunctional_types.nit
functional :: functional_types
This module provides functional type to represents various function forms.gtk :: gtk_assistant
gtk :: gtk_dialogs
HttpRequest
class and services to create it
app::http_request
main service AsyncHttpRequest
Serializable::inspect
to show more useful information
Iterator
.
actors :: mandelbrot
Example implemented from "The computer Language Benchmarks Game" - Mandelbrotmarkdown2 :: markdown_html_rendering
HTML rendering of Markdown documentsmarkdown2 :: markdown_latex_rendering
LaTeX rendering of Markdown documentsmarkdown2 :: markdown_man_rendering
Manpages rendering of Markdown documentsmarkdown2 :: markdown_md_rendering
Markdown rendering of Markdown documentsmore_collections :: more_collections
Highly specific, but useful, collections-related classes.mpi :: mpi_simple
curl :: native_curl
Binding of C libCurl which allow us to interact with network.app.nit
on Android using a custom Java entry point
nitcc_runtime :: nitcc_runtime
Runtime library required by parsers and lexers generated by nitccnlp :: nlp_server
glesv2 :: opengles2_hello_triangle
Basic example of OpenGL ES 2.0 usage using SDL 2performance_analysis :: performance_analysis
Services to gather information on the performance of events by categoriesrestful
annotation documented at lib/nitcorn/restful.nit
sax :: sax_locator
Interface for associating a SAX event with a document location.Locator
.
msgpack :: serialization_common
Serialization services forserialization_write
and serialization_read
serialization :: serialization_core
Abstract services to serialize Nit objects to different formatsdeserialize_json
and JsonDeserializer
serialize_to_json
and JsonSerializer
msgpack :: serialization_write
Serialize full Nit objects to MessagePack formatroot
to execute
agent_simulation
by refining the Agent class to make
socket :: socket_simple_server
Simple server example using a non-blockingTCPServer
EulerCamera
and App::frame_core_draw
to get a stereoscopic view
gamnit :: texture_atlas_parser
Tool to parse XML texture atlas and generated Nit code to access subtextures
# Introduce `HashMap` and `HashSet`.
module hash_collection
import array
redef class Map[K, V]
# Get a `HashMap[K, V]` as default implementation
new do return new HashMap[K, V]
end
redef class Set[E]
# Get an instance of `HashSet[E]`, the default implementation
new do return new HashSet[E]
end
# A HashCollection is an array of HashNode[K] indexed by the K hash value
private abstract class HashCollection[K]
type N: HashNode[K]
var array: NativeArray[nullable N] is noautoinit # Used to store items
var capacity: Int = 0 # Size of _array
var the_length: Int = 0 # Number of items in the map
var first_item: nullable N = null # First added item (used to visit items in nice order)
var last_item: nullable N = null # Last added item (same)
# The last key accessed (used for cache)
var last_accessed_key: nullable Object = null
# The last node accessed (used for cache)
var last_accessed_node: nullable N = null
# Return the index of the key k
fun index_at(k: nullable Object): Int
do
if k == null then return 0
var i = k.hash % _capacity
if i < 0 then i = - i
return i
end
# Return the node associated with the key
fun node_at(k: nullable Object): nullable N
do
if _the_length == 0 then return null
# cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
if k.is_same_instance(_last_accessed_key) then return _last_accessed_node
var res = node_at_idx(index_at(k), k)
_last_accessed_key = k
_last_accessed_node = res
return res
end
# Return the node associated with the key (but with the index already known)
fun node_at_idx(i: Int, k: nullable Object): nullable N
do
if _the_length == 0 then return null
var c = _array[i]
while c != null do
var ck = c._key
if ck.is_same_instance(k) or ck == k then # FIXME prefilter because the compiler is not smart enought yet
break
end
c = c._next_in_bucklet
end
return c
end
# Add a new node at a given index
fun store(index: Int, node: N)
do
# Store the item in the list
if _first_item == null then
_first_item = node
else
_last_item._next_item = node
end
node._prev_item = _last_item
node._next_item = null
_last_item = node
# Then store it in the array
var next = _array[index]
_array[index] = node
node._next_in_bucklet = next
if next != null then next._prev_in_bucklet = node
_last_accessed_key = node._key
_last_accessed_node = node
# Enlarge if needed
var l = _the_length
_the_length = l + 1
# Magic values determined empirically
# We do not want to enlarge too much
# We also want a odd capacity so that the modulo is more distributive
l = (l + 5) * 2 + 1
if l >= _capacity then
enlarge(l * 3 / 2 + 1)
end
end
# Remove the node assosiated with the key
fun remove_node(k: nullable Object)
do
if _the_length == 0 then return
var i = index_at(k)
var node = node_at_idx(i, k)
if node == null then return
# Remove the item in the list
var prev = node._prev_item
var next = node._next_item
if prev != null then
prev._next_item = next
else
_first_item = next
end
if next != null then
next._prev_item = prev
else
_last_item = prev
end
# Remove the item in the array
_the_length -= 1
prev = node._prev_in_bucklet
next = node._next_in_bucklet
if prev != null then
prev._next_in_bucklet = next
else
_array[i] = next
end
if next != null then
next._prev_in_bucklet = prev
end
_last_accessed_key = null
end
# Clear the whole structure
fun raz
do
var i = _capacity - 1
while i >= 0 do
_array[i] = null
i -= 1
end
_the_length = 0
_first_item = null
_last_item = null
_last_accessed_key = null
end
# Force a capacity
fun enlarge(cap: Int)
do
# get a new capacity
if cap < _the_length + 1 then cap = _the_length + 1
if cap <= _capacity then return
_capacity = cap
_last_accessed_key = null
# get a new array
var new_array = new NativeArray[nullable N](cap)
_array = new_array
# Reput items in the array
var node = _first_item
while node != null do
var index = index_at(node._key)
# Then store it in the array
var next = new_array[index]
new_array[index] = node
node._prev_in_bucklet = null
node._next_in_bucklet = next
if next != null then next._prev_in_bucklet = node
node = node._next_item
end
end
end
private abstract class HashNode[K]
var key: K
type N: HashNode[K]
var next_item: nullable N = null
var prev_item: nullable N = null
var prev_in_bucklet: nullable N = null
var next_in_bucklet: nullable N = null
end
# A `Map` implemented with a hash table.
#
# ~~~
# var map = new HashMap[nullable String, Int]
# map[null] = 0
# map["one"] = 1
# map["two"] = 2
#
# assert map[null] == 0
# assert map["one"] == 1
# assert map.keys.has("two")
# assert map.values.length == 3
# ~~~
class HashMap[K, V]
super Map[K, V]
super HashCollection[K]
redef type N: HashMapNode[K, V] is fixed
redef fun [](key)
do
var c = node_at(key)
if c == null then
return provide_default_value(key)
else
return c._value
end
end
redef fun get_or_null(key)
do
var c = node_at(key)
if c == null then
return null
else
return c._value
end
end
redef fun iterator do return new HashMapIterator[K,V](self)
redef fun length do return _the_length
redef fun is_empty do return _the_length == 0
redef fun []=(key, v)
do
if _capacity == 0 then enlarge(17) # 17 because magic in `store`
var i = index_at(key)
var c = node_at_idx(i, key)
if c != null then
c._key = key
c._value = v
else
store(i, new HashMapNode[K, V](key, v))
end
end
redef fun clear do raz
init
do
_capacity = 0
_the_length = 0
end
# Build a list filled with the items of `coll`.
init from(coll: Map[K, V]) do
init
add_all(coll)
end
redef var keys: RemovableCollection[K] = new HashMapKeys[K, V](self) is lazy
redef var values: RemovableCollection[V] = new HashMapValues[K, V](self) is lazy
redef fun has_key(k) do return node_at(k) != null
end
# View of the keys of a HashMap
private class HashMapKeys[K, V]
super RemovableCollection[K]
# The original map
var map: HashMap[K, V]
redef fun count(k) do if self.has(k) then return 1 else return 0
redef fun first do return self.map._first_item._key
redef fun has(k) do return self.map.node_at(k) != null
redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
redef fun is_empty do return self.map.is_empty
redef fun length do return self.map.length
redef fun iterator do return new MapKeysIterator[K, V](self.map.iterator)
redef fun clear do self.map.clear
redef fun remove(key) do self.map.remove_node(key)
redef fun remove_all(key) do self.map.remove_node(key)
end
# View of the values of a Map
private class HashMapValues[K, V]
super RemovableCollection[V]
# The original map
var map: HashMap[K, V]
redef fun count(item)
do
var nb = 0
var c = self.map._first_item
while c != null do
if c._value == item then nb += 1
c = c._next_item
end
return nb
end
redef fun first do return self.map._first_item._value
redef fun has(item)
do
var c = self.map._first_item
while c != null do
if c._value == item then return true
c = c._next_item
end
return false
end
redef fun has_only(item)
do
var c = self.map._first_item
while c != null do
if c._value != item then return false
c = c._next_item
end
return true
end
redef fun is_empty do return self.map.is_empty
redef fun length do return self.map.length
redef fun iterator do return new MapValuesIterator[K, V](self.map.iterator)
redef fun clear do self.map.clear
redef fun remove(item)
do
var map = self.map
var c = map._first_item
while c != null do
if c._value == item then
map.remove_node(c._key)
return
end
c = c._next_item
end
end
redef fun remove_all(item)
do
var map = self.map
var c = map._first_item
while c != null do
if c._value == item then
map.remove_node(c._key)
end
c = c._next_item
end
end
end
private class HashMapNode[K, V]
super HashNode[K]
redef type N: HashMapNode[K, V]
var value: V
end
# A `MapIterator` over a `HashMap`.
private class HashMapIterator[K, V]
super MapIterator[K, V]
redef fun is_ok do return _node != null
redef fun item
do
assert is_ok
return _node._value
end
#redef fun item=(value)
#do
# assert is_ok
# _node.second = value
#end
redef fun key
do
assert is_ok
return _node._key
end
redef fun next
do
assert is_ok
_node = _node._next_item
end
# The map to iterate on
var map: HashMap[K, V]
# The current node
var node: nullable HashMapNode[K, V] = null
init
do
_map = map
_node = _map._first_item
end
end
# A `Set` implemented with a hash table.
# Keys of such a map cannot be null and require a working `hash` method
class HashSet[E]
super Set[E]
super HashCollection[E]
redef type N: HashSetNode[E] is fixed
redef fun length do return _the_length
redef fun is_empty do return _the_length == 0
redef fun first
do
assert _the_length > 0
return _first_item._key
end
redef fun has(item)
do
return node_at(item) != null
end
redef fun add(item)
do
if _capacity == 0 then enlarge(17) # 17 because magic in `store`
var i = index_at(item)
var c = node_at_idx(i, item)
if c != null then
c._key = item
else
store(i,new HashSetNode[E](item))
end
end
redef fun remove(item) do remove_node(item)
redef fun clear do raz
redef fun iterator do return new HashSetIterator[E](self)
init
do
_capacity = 0
_the_length = 0
end
# Build a list filled with the items of `coll`.
init from(coll: Collection[E]) do
init
add_all(coll)
end
redef fun new_set do return new HashSet[E]
end
private class HashSetNode[E]
super HashNode[E]
redef type N: HashSetNode[E]
end
private class HashSetIterator[E]
super Iterator[E]
redef fun is_ok do return _node != null
redef fun item
do
assert is_ok
return _node._key
end
redef fun next
do
assert is_ok
_node = _node._next_item
end
# The set to iterate on
var set: HashSet[E]
# The position in the internal map storage
var node: nullable HashSetNode[E] = null
init
do
_node = _set._first_item
end
end
lib/core/collection/hash_collection.nit:13,1--511,3