class DQuadTree[E: Boxed[Numeric]]

geometry :: DQuadTree

A dynamic implementation of the quadtree data structure

The center of the parent node is determined by the average values of the data it contains when item_limit is reached.

Introduced properties

fun average_x: Numeric

geometry :: DQuadTree :: average_x

Average X coordinate of the items in this node
fun average_y: Numeric

geometry :: DQuadTree :: average_y

Average Y coordinate of the items in this node
init defaultinit(item_limit: Int)

geometry :: DQuadTree :: defaultinit

Redefined properties

redef type SELF: DQuadTree[E]

geometry $ DQuadTree :: SELF

Type of this instance, automatically specialized in every class
redef fun subdivide

geometry $ DQuadTree :: subdivide

Create children nodes, depends on the concrete implementation

All properties

fun !=(other: nullable Object): Bool

core :: Object :: !=

Have self and other different values?
fun ==(other: nullable Object): Bool

core :: Object :: ==

Have self and other the same value?
type CLASS: Class[SELF]

core :: Object :: CLASS

The type of the class of self.
type CONCURRENT: ConcurrentCollection[E]

core :: Collection :: CONCURRENT

Type of the concurrent variant of this collection
type SELF: Object

core :: Object :: SELF

Type of this instance, automatically specialized in every class
private var _center: nullable Point[Numeric]

geometry :: QuadTree :: _center

Center coordinate of the children
private var _children: Array[QuadTree[E]]

geometry :: QuadTree :: _children

Children nodes, if not is_leaf
private var _data: Array[E]

geometry :: QuadTree :: _data

Items in this node
private var _item_limit: Int

geometry :: QuadTree :: _item_limit

Maximum number of items in this node before subdividing
private var _parent_node: nullable QuadTree[E]

geometry :: QuadTree :: _parent_node

Parent node in the tree
protected fun accept_json_serializer(v: JsonSerializer)

serialization :: Serializable :: accept_json_serializer

Refinable service to customize the serialization of this class to JSON
protected fun accept_msgpack_attribute_counter(v: AttributeCounter)

serialization :: Serializable :: accept_msgpack_attribute_counter

Hook to customize the behavior of the AttributeCounter
protected fun accept_msgpack_serializer(v: MsgPackSerializer)

serialization :: Serializable :: accept_msgpack_serializer

Hook to customize the serialization of this class to MessagePack
abstract fun add(item: E)

core :: SimpleCollection :: add

Add item to this collection.
fun add_all(coll: Collection[E])

core :: SimpleCollection :: add_all

Add each item of coll.
protected fun add_to_bundle(bundle: NativeBundle, key: JavaString)

serialization :: Serializable :: add_to_bundle

Called by []= to dynamically choose the appropriate method according
fun as_random: Queue[E]

core :: SimpleCollection :: as_random

Return a random proxy queue where result.take is random.
fun average_x: Numeric

geometry :: DQuadTree :: average_x

Average X coordinate of the items in this node
fun average_y: Numeric

geometry :: DQuadTree :: average_y

Average Y coordinate of the items in this node
protected fun center: nullable Point[Numeric]

geometry :: QuadTree :: center

Center coordinate of the children
protected fun center=(center: nullable Point[Numeric])

geometry :: QuadTree :: center=

Center coordinate of the children
protected fun children: Array[QuadTree[E]]

geometry :: QuadTree :: children

Children nodes, if not is_leaf
protected fun children=(children: Array[QuadTree[E]])

geometry :: QuadTree :: children=

Children nodes, if not is_leaf
protected fun class_factory(name: String): CLASS

core :: Object :: class_factory

Implementation used by get_class to create the specific class.
fun class_name: String

core :: Object :: class_name

The class name of the object.
abstract fun clear

core :: RemovableCollection :: clear

Remove all items
fun combinations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations

All r-length combinations on self (in same order) without repeated elements.
fun combinations_with_replacement(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations_with_replacement

All r-length combination on self (in same order) with repeated elements.
fun core_serialize_to(serializer: Serializer)

serialization :: Serializable :: core_serialize_to

Actual serialization of self to serializer
fun count(item: nullable Object): Int

core :: Collection :: count

How many occurrences of item are in the collection?
protected fun data: Array[E]

geometry :: QuadTree :: data

Items in this node
protected fun data=(data: Array[E])

geometry :: QuadTree :: data=

Items in this node
init defaultinit(item_limit: Int)

geometry :: DQuadTree :: defaultinit

init defaultinit(item_limit: Int)

geometry :: QuadTree :: defaultinit

fun first: E

core :: Collection :: first

Return the first item of the collection
init from_deserializer(deserializer: Deserializer)

serialization :: Serializable :: from_deserializer

Create an instance of this class from the deserializer
fun get_class: CLASS

core :: Object :: get_class

The meta-object representing the dynamic type of self.
fun has(item: nullable Object): Bool

core :: Collection :: has

Is item in the collection ?
fun has_all(other: Collection[nullable Object]): Bool

core :: Collection :: has_all

Does the collection contain at least each element of other?
fun has_any(other: Collection[nullable Object]): Bool

core :: Collection :: has_any

Does the collection contain at least one element of other?
fun has_exactly(other: Collection[nullable Object]): Bool

core :: Collection :: has_exactly

Does the collection contain exactly all the elements of other?
fun has_only(item: nullable Object): Bool

core :: Collection :: has_only

Is the collection contain only item?
fun hash: Int

core :: Object :: hash

The hash code of the object.
init init

core :: Object :: init

fun inspect: String

core :: Object :: inspect

Developer readable representation of self.
protected fun inspect_head: String

core :: Object :: inspect_head

Return "CLASSNAME:#OBJECTID".
fun is_empty: Bool

core :: Collection :: is_empty

Is there no item in the collection?
fun is_leaf: Bool

geometry :: QuadTree :: is_leaf

Return whether or not the Node is a leaf of the tree
intern fun is_same_instance(other: nullable Object): Bool

core :: Object :: is_same_instance

Return true if self and other are the same instance (i.e. same identity).
fun is_same_serialized(other: nullable Object): Bool

core :: Object :: is_same_serialized

Is self the same as other in a serialization context?
intern fun is_same_type(other: Object): Bool

core :: Object :: is_same_type

Return true if self and other have the same dynamic type.
protected fun item_limit: Int

geometry :: QuadTree :: item_limit

Maximum number of items in this node before subdividing
protected fun item_limit=(item_limit: Int)

geometry :: QuadTree :: item_limit=

Maximum number of items in this node before subdividing
abstract fun items_overlapping(region: Boxed[Numeric]): SimpleCollection[E]

geometry :: BoxedCollection :: items_overlapping

returns all the items overlapping with region
private fun items_overlapping_in(region: Boxed[Numeric], mdata: SimpleCollection[E])

geometry :: QuadTree :: items_overlapping_in

var dquadtree = new DQuadTree[Point[Int]](2)
abstract fun iterator: Iterator[E]

core :: Collection :: iterator

Get a new iterator on the collection.
fun join(separator: nullable Text, last_separator: nullable Text): String

core :: Collection :: join

Concatenate and separate each elements with separator.
fun length: Int

core :: Collection :: length

Number of items in the collection.
protected fun msgpack_extra_array_items: Int

serialization :: Serializable :: msgpack_extra_array_items

Hook to request a larger than usual metadata array
private intern fun native_class_name: CString

core :: Object :: native_class_name

The class name of the object in CString format.
fun not_empty: Bool

core :: Collection :: not_empty

Alias for not is_empty.
intern fun object_id: Int

core :: Object :: object_id

An internal hash code for the object based on its identity.
fun output

core :: Object :: output

Display self on stdout (debug only).
intern fun output_class_name

core :: Object :: output_class_name

Display class name on stdout (debug only).
protected fun parent_node: nullable QuadTree[E]

geometry :: QuadTree :: parent_node

Parent node in the tree
protected fun parent_node=(parent_node: nullable QuadTree[E])

geometry :: QuadTree :: parent_node=

Parent node in the tree
fun permutations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: permutations

All r-length permutations on self (all possible ordering) without repeated elements.
fun plain_to_s: String

core :: Collection :: plain_to_s

Concatenate elements without separators
fun product(r: Int): Collection[SequenceRead[E]]

core :: Collection :: product

Cartesian product, over r times self.
fun rand: E

core :: Collection :: rand

Return a random element form the collection
abstract fun remove(item: nullable Object)

core :: RemovableCollection :: remove

Remove an occurrence of item
fun remove_all(item: nullable Object)

core :: RemovableCollection :: remove_all

Remove all occurrences of item
fun sample(length: Int): Array[E]

core :: Collection :: sample

Return a new array made of (at most) length elements randomly chosen.
fun serialization_hash: Int

core :: Object :: serialization_hash

Hash value use for serialization
fun serialize_msgpack(plain: nullable Bool): Bytes

serialization :: Serializable :: serialize_msgpack

Serialize self to MessagePack bytes
fun serialize_to(serializer: Serializer)

serialization :: Serializable :: serialize_to

Serialize self to serializer
fun serialize_to_json(plain: nullable Bool, pretty: nullable Bool): String

serialization :: Serializable :: serialize_to_json

Serialize self to JSON
private fun serialize_to_or_delay(v: Serializer)

serialization :: Serializable :: serialize_to_or_delay

Accept references or force direct serialization (using serialize_to)
private fun serialize_to_pure_json(v: JsonSerializer)

core :: Collection :: serialize_to_pure_json

Utility to serialize a normal Json array
protected abstract fun subdivide

geometry :: QuadTree :: subdivide

Create children nodes, depends on the concrete implementation
intern fun sys: Sys

core :: Object :: sys

Return the global sys object, the only instance of the Sys class.
fun to_a: Array[E]

core :: Collection :: to_a

Build a new array from a collection
abstract fun to_concurrent: CONCURRENT

core :: Collection :: to_concurrent

Wraps self in a thread-safe collection
fun to_counter: Counter[E]

core :: Collection :: to_counter

Create and fill up a counter with the elements of `self.
fun to_curlslist: CURLSList

core :: Collection :: to_curlslist

Convert Collection[String] to CURLSList
fun to_json: String

serialization :: Serializable :: to_json

Serialize self to plain JSON
abstract fun to_jvalue(env: JniEnv): JValue

core :: Object :: to_jvalue

fun to_pretty_json: String

serialization :: Serializable :: to_pretty_json

Serialize self to plain pretty JSON
fun to_s: String

core :: Object :: to_s

User readable representation of self.
fun to_shuffle: Array[E]

core :: Collection :: to_shuffle

Return a new array made of elements in a random order.
init with_parent(limit: Int, parent: QuadTree[E])

geometry :: QuadTree :: with_parent

Create a child node to parent
package_diagram geometry::DQuadTree DQuadTree geometry::QuadTree QuadTree geometry::DQuadTree->geometry::QuadTree geometry::BoxedCollection BoxedCollection geometry::QuadTree->geometry::BoxedCollection ...geometry::BoxedCollection ... ...geometry::BoxedCollection->geometry::BoxedCollection

Ancestors

interface BoxedCollection[E: Boxed[Numeric]]

geometry :: BoxedCollection

Base for all data structures containing multiple Boxed Objects
interface Collection[E: nullable Object]

core :: Collection

The root of the collection hierarchy.
interface Object

core :: Object

The root of the class hierarchy.
interface RemovableCollection[E: nullable Object]

core :: RemovableCollection

Items can be removed from this collection
interface Serializable

serialization :: Serializable

Instances of this class can be passed to Serializer::serialize
interface SimpleCollection[E: nullable Object]

core :: SimpleCollection

Items can be added to these collections.

Parents

abstract class QuadTree[E: Boxed[Numeric]]

geometry :: QuadTree

Abstract QuadTree implementing the basic functions and data

Class definitions

geometry $ DQuadTree 
# A dynamic implementation of the quadtree data structure
#
# The center of the parent node is determined by the average
# values of the data it contains when `item_limit` is reached.
class DQuadTree[E: Boxed[Numeric]]
	super QuadTree[E]

	redef fun subdivide
	do
		self.center = new Point[Numeric](average_x, average_y)
		children[0] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[1] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[2] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[3] = new DQuadTree[E].with_parent(self.item_limit, self)
	end

	# Average X coordinate of the items in this node
	fun average_x: Numeric
	do
		var x_total = data.first.left.zero
		for data in self.data do
			x_total += (data.left + data.right)/x_total.value_of(2)
		end
		return x_total/x_total.value_of(self.data.length)
	end

	# Average Y coordinate of the items in this node
	fun average_y: Numeric
	do
		var y_total = data.first.left.zero
		for data in self.data do
			y_total += (data.left + data.right)/y_total.value_of(2)
		end
		return y_total/y_total.value_of(self.data.length)
	end
end
lib/geometry/quadtree.nit:190,1--225,3
Nit tools. Version v0.8-3595-g3f58b4f.