ddrt

v0.2.1

ddrt v0.2.1 DDRT.DynamicRtree behaviour View Source

Use this module if you're interested in creating an R-Tree optimized to run on a single machine. If you'd instead like to run a distributed R-Tree on a cluster of Elixir nodes, use the DDRT module.

Link to this section Summary

Types

bounding_box()
coord_range()
ddrt_mode()
id()
leaf()
member()
tree_config()
tree_init()

Functions

bulk_update(updates, name \\ DDRT)

Update a bunch of r-tree leaves to the new bounding boxes defined.

child_spec(init_arg)

Returns a specification to start this module under a supervisor.

delete(ids, name \\ DDRT)

Delete the leaves with the given ids.

insert(leaves, name \\ DDRT)

Insert leaves into the r-tree with process with name name

metadata(name \\ DDRT)

Get the r-tree metadata

new(opts \\ [width: 6, type: Map, mode: :standalone, verbose: false, seed: 0], name \\ DDRT)
pquery(box, depth, name \\ DDRT)

Query to get every node id overlapped by box at the defined depth.

query(box, name \\ DDRT)

Query to get every leaf id overlapped by box.

set_members(name, members)

Set the members of the DDRT cluster.

start_link(opts)

These are all of the possible configuration parameters for opts and their default values

tree(name \\ DDRT)

Get the r-tree representation

update(id, update, name \\ DDRT)

Update a single leaf bounding box

Callbacks

bulk_update(leaves, name)
delete(ids, name)
insert(leaves, name)
metadata(name)
new(opts, name)
pquery(box, depth, name)
query(box, name)
set_members(name, list)
tree(name)
update(ids, box, name)

Link to this section Types

Link to this type

bounding_box()

View Source 
bounding_box() :: [coord_range()]
Link to this type

coord_range()

View Source 
coord_range() :: {number(), number()}
Link to this type

ddrt_mode()

View Source 
ddrt_mode() :: :standalone | :distributed
Link to this type

id()

View Source 
id() :: number() | String.t()
Link to this type

leaf()

View Source 
leaf() :: {id(), bounding_box()}
Link to this type

member()

View Source 
member() :: GenServer.name() | {GenServer.name(), node()}
Link to this type

tree_config()

View Source 
tree_config() :: [
  name: GenServer.name(),
  width: integer(),
  type: module(),
  verbose: boolean(),
  seed: integer(),
  mode: ddrt_mode()
]
Link to this type

tree_init()

View Source 
tree_init() :: [name: GenServer.name(), crdt: module(), conf: tree_config()]

Link to this section Functions

Link to this function

bulk_update(updates, name \\ DDRT)

View Source 
bulk_update(leaves :: [leaf()], name :: GenServer.name()) :: {:ok, map()}

Update a bunch of r-tree leaves to the new bounding boxes defined.

Returns {:ok,map()}

Examples 

iex> DynamicRtree.bulk_update([{"Griffin",[{0,1},{0,1}]},{"Parker",[{10,11},{10,11}]}],:my_rtree)

{:ok,
%{
 43143342109176739 => {["Parker", "Griffin"], nil, [{0, 11}, {0, 11}]},
 :root => 43143342109176739,
 :ticket => [19125803434255161 | 82545666616502197],
 "Griffin" => {:leaf, 43143342109176739, [{0, 1}, {0, 1}]},
 "Parker" => {:leaf, 43143342109176739, [{10, 11}, {10, 11}]}
}}
Link to this function

child_spec(init_arg)

View Source

Returns a specification to start this module under a supervisor.

See Supervisor.

Link to this function

delete(ids, name \\ DDRT)

View Source 
delete(ids :: id() | [id()], name :: GenServer.name()) :: {:ok, map()}

Delete the leaves with the given ids.

Returns {:ok,map()}

Parameters

  • ids: Id or list of Id that you want to delete.
  • name: the name of the rtree process.

Examples

Individual deletion:

  iex> DynamicRtree.delete("Griffin",:my_rtree)
  iex> DynamicRtree.delete("Parker",:my_rtree)

Bulk Deletion:

  iex> DynamicRtree.delete(["Griffin","Parker"],:my_rtree)
Link to this function

insert(leaves, name \\ DDRT)

View Source 
insert(leaves :: leaf() | [leaf()], name :: GenServer.name()) :: {:ok, map()}

Insert leaves into the r-tree with process with name name

Returns {:ok,map()}

Parameters

  • leaves: the data to insert.
  • name: the r-tree name where you want to insert.

Examples

Individual insertion:

  iex> DynamicRtree.insert({"Griffin", [{4,5},{6,7}]}, :my_rtree)
  iex> DynamicRtree.insert({"Parker", [{14,15},{16,17}]}, :my_rtree)

  {:ok,
  %{
   43143342109176739 => {["Parker", "Griffin"], nil, [{4, 15}, {6, 17}]},
   :root => 43143342109176739,
   :ticket => [19125803434255161 | 82545666616502197],
   "Griffin" => {:leaf, 43143342109176739, [{4, 5}, {6, 7}]},
   "Parker" => {:leaf, 43143342109176739, [{14, 15}, {16, 17}]}
  }}

Bulk Insertion:

  iex> DynamicRtree.insert([{"Griffin", [{4,5},{6,7}]}, {"Parker", [{14,15},{16,17}]}], :my_rtree)

  {:ok,
  %{
   43143342109176739 => {["Parker", "Griffin"], nil, [{4, 15}, {6, 17}]},
   :root => 43143342109176739,
   :ticket => [19125803434255161 | 82545666616502197],
   "Griffin" => {:leaf, 43143342109176739, [{4, 5}, {6, 7}]},
   "Parker" => {:leaf, 43143342109176739, [{14, 15}, {16, 17}]}
  }}
Link to this function

metadata(name \\ DDRT)

View Source 
metadata(name :: GenServer.name()) :: map()

Get the r-tree metadata

Returns map()

Examples 

iex> DynamicRtree.metadata(:my_rtree)

%{
  params: %{mode: :standalone, seed: 0, type: Map, verbose: false, width: 6},
  seeding: %{
    bits: 58,
    jump: #Function<3.53802439/1 in :rand.mk_alg/1>,
    next: #Function<0.53802439/1 in :rand.mk_alg/1>,
    type: :exrop,
    uniform: #Function<1.53802439/1 in :rand.mk_alg/1>,
    uniform_n: #Function<2.53802439/2 in :rand.mk_alg/1>,
    weak_low_bits: 1
  }
}
Link to this function

new(opts \\ [width: 6, type: Map, mode: :standalone, verbose: false, seed: 0], name \\ DDRT)

View Source 
new(opts :: Keyword.t(), name :: GenServer.name()) :: {:ok, map()}
Link to this function

pquery(box, depth, name \\ DDRT)

View Source 
pquery(box :: bounding_box(), depth :: integer(), name :: GenServer.name()) :: [
  id()
]

Query to get every node id overlapped by box at the defined depth.

Returns [id's].

Link to this function

query(box, name \\ DDRT)

View Source 
query(box :: bounding_box(), name :: GenServer.name()) :: [id()]

Query to get every leaf id overlapped by box.

Returns [id's].

Examples 

iex> DynamicRtree.query([{0,7},{4,8}],:my_rtree)
{:ok, ["Griffin"]}
Link to this function

set_members(name, members)

View Source 
set_members(name :: GenServer.name(), [member()]) :: :ok

Set the members of the DDRT cluster.

members should be in the format {GenServer.name(), node()}.

Examples 

DDRT.set_members(DDRT, [{DDRT.A, :yournode@foreignhost}, {DDRT.B, :yournode@foreignhost}])
Link to this function

start_link(opts)

View Source 
start_link(opts :: tree_init()) :: {:ok, pid()} | {:error, term()}

These are all of the possible configuration parameters for opts and their default values:

  • name: The name of the DDRT process. Defaults to DDRT
  • width: The max number of children a node may have. Defaults to 6
  • verbose: allows Logger to report console logs. (Also decreases performance). Defaults to false.
  • seed: Sets the seed value for the pseudo-random number generator which generates the unique IDs for each node in the tree. This is a deterministic process; so the same seed value will guarantee the same pseudo-random unique IDs being generated for your tree in the same order each time. Defaults to 0
Link to this function

tree(name \\ DDRT)

View Source 
tree(name :: GenServer.name()) :: map()

Get the r-tree representation

Returns map()

Examples 

iex> DynamicRtree.metadata(:my_rtree)

%{
  43143342109176739 => {["Parker", "Griffin"], nil, [{0, 11}, {0, 11}]},
  :root => 43143342109176739,
  :ticket => [19125803434255161 | 82545666616502197],
  "Griffin" => {:leaf, 43143342109176739, [{0, 1}, {0, 1}]},
  "Parker" => {:leaf, 43143342109176739, [{10, 11}, {10, 11}]}
}
Link to this function

update(id, update, name \\ DDRT)

View Source 
update(
  ids :: id(),
  box :: bounding_box() | {bounding_box(), bounding_box()},
  name :: GenServer.name()
) :: {:ok, map()}

Update a single leaf bounding box

Returns {:ok,map()}

Examples 

iex> DynamicRtree.update({"Griffin",[{0,1},{0,1}]},:my_rtree)

{:ok,
%{
 43143342109176739 => {["Parker", "Griffin"], nil, [{0, 11}, {0, 11}]},
 :root => 43143342109176739,
 :ticket => [19125803434255161 | 82545666616502197],
 "Griffin" => {:leaf, 43143342109176739, [{0, 1}, {0, 1}]},
 "Parker" => {:leaf, 43143342109176739, [{10, 11}, {16, 17}]}
}}

Link to this section Callbacks

Link to this callback

bulk_update(leaves, name)

View Source 
bulk_update(leaves :: [leaf()], name :: GenServer.name()) :: {:ok, map()}
Link to this callback

delete(ids, name)

View Source 
delete(ids :: id() | [id()], name :: GenServer.name()) :: {:ok, map()}
Link to this callback

insert(leaves, name)

View Source 
insert(leaves :: leaf() | [leaf()], name :: GenServer.name()) :: {:ok, map()}
Link to this callback

metadata(name)

View Source 
metadata(name :: GenServer.name()) :: map()
Link to this callback

new(opts, name)

View Source 
new(opts :: Keyword.t(), name :: GenServer.name()) :: {:ok, map()}
Link to this callback

pquery(box, depth, name)

View Source 
pquery(box :: bounding_box(), depth :: integer(), name :: GenServer.name()) :: [
  id()
]
Link to this callback

query(box, name)

View Source 
query(box :: bounding_box(), name :: GenServer.name()) :: [id()]
Link to this callback

set_members(name, list)

View Source 
set_members(name :: GenServer.name(), [member()]) :: :ok
Link to this callback

tree(name)

View Source 
tree(name :: GenServer.name()) :: map()
Link to this callback

update(ids, box, name)

View Source 
update(
  ids :: id(),
  box :: bounding_box() | {bounding_box(), bounding_box()},
  name :: GenServer.name()
) :: {:ok, map()}