core :: union_find
core :: DisjointSet
Data structure to keep track of elements partitioned into disjoint subsetsnitc :: actors_generation_phase
Generate a support module for each module that contain a class annotated withis actor
nitc :: actors_injection_phase
Injects model for the classes annotated with "is actor" sonitc :: api_metrics
nitc :: astbuilder
Instantiation and transformation of semantic nodes in the AST of expressions and statementsbucketed_game :: bucketed_game
Game framework with an emphasis on efficient event coordinationcflags
and ldflags
to specify
accept_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 cameranitc :: commands_ini
pthreads :: 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.nitc :: detect_variance_constraints
Collect metrics about detected variances constraints on formal types.egl
, sdl
and x11
extra_java_files
to compile extra java files
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
nitc :: i18n_phase
Basic support of internationalization through the generation of id-to-string tablesSerializable::inspect
to show more useful information
Iterator
.
nitc :: light_only
Compiler support for the light FFI only, detects unsupported usage of callbacksactors :: 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 documentsnitc
.
nitc :: modelbuilder
more_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 nitccnitc :: nitmetrics
A program that collects various metrics on nit programs and librariesnitc :: nitrestful
Tool generating boilerplate code linking RESTful actions to Nit methodsnlp :: nlp_server
glesv2 :: opengles2_hello_triangle
Basic example of OpenGL ES 2.0 usage using SDL 2threaded
annotation
performance_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
.
nitc :: separate_erasure_compiler
Separate compilation of a Nit program with generic type erasurenitc :: serialization_code_gen_phase
Phase generating methods (code) to serialize Nit objectsmsgpack :: serialization_common
Serialization services forserialization_write
and serialization_read
serialization :: serialization_core
Abstract services to serialize Nit objects to different formatsnitc :: serialization_model_phase
Phase generating methods (model-only) to serialize Nit objectsdeserialize_json
and JsonDeserializer
msgpack :: serialization_write
Serialize full Nit objects to MessagePack formatserialize_to_json
and JsonSerializer
root
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
clone
method of the astbuilder tool
gamnit :: texture_atlas_parser
Tool to parse XML texture atlas and generated Nit code to access subtexturesnitc :: toolcontext
Common command-line tool infrastructure than handle options and error messagesnitc :: uml_module
Services for generation of a UML package diagram based on aModel
# union–find algorithm using an efficient disjoint-set data structure
module union_find
import hash_collection
# Data structure to keep track of elements partitioned into disjoint subsets
#
# var s = new DisjointSet[Int]
# s.add(1)
# s.add(2)
# assert not s.in_same_subset(1,2)
# s.union(1,2)
# assert s.in_same_subset(1,2)
#
# `in_same_subset` is transitive, reflexive and symmetric
#
# s.add(3)
# assert not s.in_same_subset(1,3)
# s.union(3,2)
# assert s.in_same_subset(1,3)
#
# Unlike theoretical Disjoint-set data structures, the underling implementation is opaque
# making the traditional `find` method unavailable for clients.
# The methods `in_same_subset`, `to_partitions`, and their variations are offered instead.
class DisjointSet[E]
super SimpleCollection[E]
super Cloneable
# The node in the hiearchical structure for each element
private var nodes = new HashMap[E, DisjointSetNode]
# Copy constructor
init from(other: DisjointSet[E])
do
# Associate a root node in other to the associated root node in self
var map = new HashMap[DisjointSetNode, DisjointSetNode]
for e, v in other.nodes do
# Create the associated node
var n2 = new DisjointSetNode
nodes[e] = n2
# Get the root node in other and the associated one in self
var p = other.find(e)
var p2 = map.get_or_null(p)
if p2 == null then
# if no associated root node, then a new subset is created
map[p] = n2.parent
number_of_subsets += 1
else
# else attach the new node to the subset of the root node
n2.parent = p2
end
end
end
# Shallow copy
#
# var s = new DisjointSet[Int]
# s.add_all([1,2,3,4,5])
# s.union_all([1,4,5])
# var s2 = s.clone
# assert s2.number_of_subsets == 3
# assert s2.all_in_same_subset([1,4,5]) == true
# assert s2.in_same_subset(1,2) == false
redef fun clone do return new DisjointSet[E].from(self)
# The number of subsets in the partition
#
# var s = new DisjointSet[Int]
# s.add_all([1,2,3,4,5])
# assert s.number_of_subsets == 5
# s.union_all([1,4,5])
# assert s.number_of_subsets == 3
# s.union(4,5)
# assert s.number_of_subsets == 3
var number_of_subsets: Int = 0
# Get the root node of an element
# require: `has(e)`
private fun find(e:E): DisjointSetNode
do
assert nodes.has_key(e)
var ne = nodes[e]
if ne.parent == ne then return ne
var res = nfind(ne)
nodes[e] = res
return res
end
# Get the root node of a node
# Use *path compression* to flatten the structure
# ENSURE: `result.parent == result`
private fun nfind(ne: DisjointSetNode): DisjointSetNode
do
var nf = ne.parent
if nf == ne then return ne
var ng = nfind(nf)
ne.parent = ng
return ng
end
# Is the element in the structure
#
# var s = new DisjointSet[Int]
# assert not s.has(1)
# s.add(1)
# assert s.has(1)
# assert not s.has(2)
redef fun has(e) do
return nodes.has_key(e)
end
redef fun iterator do return nodes.keys.iterator
# Add a new element in the structure.
# Initially it is in its own disjoint subset
#
# ENSURE: `has(e)`
redef fun add(e) do
if nodes.has_key(e) then return
var ne = new DisjointSetNode
nodes[e] = ne
number_of_subsets += 1
end
# Are two elements in the same subset?
fun in_same_subset(e,f:E): Bool
do
return e == f or find(e) == find(f)
end
# Are all elements of `es` in the same subset?
#
# var s = new DisjointSet[Int]
# s.add_all([1,2,3,4,5,6])
# s.union_all([1,2,3])
# assert not s.all_in_same_subset([2,3,4])
# s.union_all([1,4,5])
# assert s.all_in_same_subset([2,3,4])
fun all_in_same_subset(es: Collection[E]): Bool
do
if es.is_empty then return true
var nf = find(es.first)
for e in es do
var ne = find(e)
if ne != nf then return false
end
return true
end
# Construct the current partitionning
#
# var s = new DisjointSet[Int]
# s.add_all([1,2,3,4,5,6])
# s.union(1,2)
# s.union(1,3)
# s.union(4,5)
# var p = s.to_partitions
# assert p.length == 3
fun to_partitions: Collection[Set[E]]
do
return to_subpartition(self)
end
# Construct a partitioning on `es`, a subset of elements
#
# var s = new DisjointSet[Int]
# s.add_all([1,2,3,4,5,6])
# s.union(1,2)
# s.union(1,3)
# s.union(4,5)
# var p = s.to_subpartition([1,2,4])
# assert p.length == 2
fun to_subpartition(es: Collection[E]): Collection[Set[E]]
do
var map = new HashMap[DisjointSetNode, Set[E]]
for e in es do
var ne = find(e)
var set = map.get_or_null(ne)
if set == null then
set = new HashSet[E]
map[ne] = set
end
set.add(e)
end
return map.values
end
# Combine the subsets of `e` and `f`
# ENSURE: `in_same_subset(e,f)`
fun union(e,f:E)
do
var ne = find(e)
var nf = find(f)
if ne == nf then return
# merge them using *union by rank*
# attach the smaller tree to the root of the deeper tree
var er = ne.rank
var fr = nf.rank
if er < fr then
ne.parent = nf
nodes[e] = nf
else
nf.parent = ne
nodes[f] = ne
if er == fr then
# The only case where the deep is increased is when both are equals
ne.rank = er+1
end
end
number_of_subsets -= 1
end
# Combine the subsets of all elements of `es`
# ENSURE: `all_in_same_subset(cs)`
fun union_all(es:Collection[E])
do
if es.is_empty then return
var f = es.first
for e in es do union(e,f)
end
end
# A node in the hierarchical representation of subsets
private class DisjointSetNode
# If parent == self then the node is a root
var parent: DisjointSetNode = self
# The rank to keep the structure balanced.
# The term rank is used instead of depth since
# path compression is used, see `DisjointSet::nfind`
var rank = 0
end
lib/core/collection/union_find.nit:11,1--244,3