Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F94918975
aka_tree.hh
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Wed, Dec 11, 09:51
Size
56 KB
Mime Type
text/x-c++
Expires
Fri, Dec 13, 09:51 (2 d)
Engine
blob
Format
Raw Data
Handle
22864735
Attached To
rAKA akantu
aka_tree.hh
View Options
/**
* @file aka_tree.hh
*
* @author Alejandro M. Aragón <alejandro.aragon@epfl.ch>
*
* @date creation: Fri Jan 04 2013
* @date last modification: Sun Oct 19 2014
*
* @brief bounding volume hierarchies
*
* @section LICENSE
*
* Copyright (©) 2014, 2015 EPFL (Ecole Polytechnique Fédérale de Lausanne)
* Laboratory (LSMS - Laboratoire de Simulation en Mécanique des Solides)
*
* Akantu is free software: you can redistribute it and/or modify it under the
* terms of the GNU Lesser General Public License as published by the Free
* Software Foundation, either version 3 of the License, or (at your option) any
* later version.
*
* Akantu is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
* A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
* details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with Akantu. If not, see <http://www.gnu.org/licenses/>.
*
*/
/* -------------------------------------------------------------------------- */
#ifndef __AKANTU_TREE_HH__
#define __AKANTU_TREE_HH__
#include <cassert>
#include <queue>
#include <set>
#include <iomanip>
//#include <limits>
#include "aka_ball.hh"
#include "aka_bounding_box.hh"
#include "aka_array.hh"
//#define DEBUG_TREE 1
__BEGIN_AKANTU__
using
std
::
cout
;
using
std
::
endl
;
struct
Tree_node_base
{
typedef
Tree_node_base
*
base_ptr
;
typedef
const
Tree_node_base
*
const_base_ptr
;
base_ptr
parent_
;
base_ptr
left_
;
base_ptr
right_
;
static
base_ptr
_minimum
(
base_ptr
x
)
{
while
(
x
->
left_
!=
0
)
x
=
x
->
left_
;
return
x
;
}
static
const_base_ptr
_minimum
(
const_base_ptr
x
)
{
while
(
x
->
left_
!=
0
)
x
=
x
->
left_
;
return
x
;
}
static
base_ptr
_maximum
(
base_ptr
x
)
{
while
(
x
->
right_
!=
0
)
x
=
x
->
right_
;
return
x
;
}
static
const_base_ptr
_maximum
(
const_base_ptr
x
)
{
while
(
x
->
right_
!=
0
)
x
=
x
->
right_
;
return
x
;
}
};
template
<
typename
T
>
struct
Tree_node
:
public
Tree_node_base
{
typedef
T
value_tpe
;
typedef
Tree_node
<
value_tpe
>*
link_type
;
value_tpe
value_
;
template
<
typename
...
Args
>
Tree_node
(
Args
&&
...
args
)
:
Tree_node_base
(),
value_
(
std
::
forward
<
Args
>
(
args
)...)
{
}
};
// iterators
static
Tree_node_base
*
local_leaf_increment
(
Tree_node_base
*
x
)
throw
()
{
Tree_node_base
*
y
=
x
->
parent_
;
if
(
y
->
parent_
==
x
)
return
y
;
while
(
x
==
y
->
right_
)
{
x
=
y
;
y
=
y
->
parent_
;
}
if
(
y
->
parent_
==
x
)
return
y
;
if
(
x
->
right_
!=
y
)
x
=
y
;
if
(
x
->
right_
!=
0
)
{
x
=
x
->
right_
;
while
(
x
->
left_
!=
0
)
x
=
x
->
left_
;
}
return
x
;
}
template
<
class
tree_pointer
>
tree_pointer
*
_tree_leaf_increment
(
tree_pointer
*
x
)
throw
()
{
return
local_leaf_increment
(
x
);
}
template
<
class
tree_pointer
>
const
tree_pointer
*
_tree_leaf_increment
(
const
tree_pointer
*
x
)
throw
()
{
return
local_leaf_increment
(
const_cast
<
tree_pointer
*>
(
x
));
}
template
<
typename
_Tp
>
struct
Tree_leaf_iterator
{
typedef
_Tp
value_type
;
typedef
_Tp
&
reference
;
typedef
_Tp
*
pointer
;
typedef
std
::
bidirectional_iterator_tag
iterator_category
;
typedef
std
::
ptrdiff_t
difference_type
;
typedef
Tree_leaf_iterator
<
_Tp
>
self_type
;
typedef
Tree_node_base
::
base_ptr
base_ptr
;
typedef
Tree_node
<
_Tp
>*
link_type
;
Tree_leaf_iterator
()
:
node_
()
{
}
explicit
Tree_leaf_iterator
(
link_type
x
)
:
node_
(
x
)
{
}
reference
operator
*
()
const
{
return
static_cast
<
link_type
>
(
node_
)
->
value_
;
}
pointer
operator
->
()
const
{
return
std
::
__addressof
(
static_cast
<
link_type
>
(
node_
)
->
value_
);
}
self_type
&
operator
++
()
{
node_
=
_tree_leaf_increment
(
node_
);
return
*
this
;
}
self_type
operator
++
(
int
)
{
self_type
tmp
=
*
this
;
node_
=
_tree_leaf_increment
(
node_
);
return
tmp
;
}
bool
operator
==
(
const
self_type
&
x
)
const
{
return
node_
==
x
.
node_
;
}
bool
operator
!=
(
const
self_type
&
x
)
const
{
return
node_
!=
x
.
node_
;
}
bool
operator
<
(
const
self_type
&
x
)
const
{
return
node_
<
x
.
node_
;
}
base_ptr
node_
;
};
template
<
typename
_Tp
>
struct
Tree_leaf_const_iterator
{
typedef
_Tp
value_type
;
typedef
const
_Tp
&
reference
;
typedef
const
_Tp
*
pointer
;
typedef
Tree_leaf_iterator
<
_Tp
>
iterator
;
typedef
std
::
bidirectional_iterator_tag
iterator_category
;
typedef
std
::
ptrdiff_t
difference_type
;
typedef
Tree_leaf_const_iterator
<
_Tp
>
self_type
;
typedef
Tree_node_base
::
const_base_ptr
base_ptr
;
typedef
const
Tree_node
<
_Tp
>*
link_type
;
Tree_leaf_const_iterator
()
:
node_
()
{
}
explicit
Tree_leaf_const_iterator
(
link_type
x
)
:
node_
(
x
)
{
}
Tree_leaf_const_iterator
(
const
iterator
&
it
)
:
node_
(
it
.
node_
)
{
}
iterator
_const_cast
()
const
{
return
iterator
(
static_cast
<
typename
iterator
::
link_type
>
(
const_cast
<
typename
iterator
::
base_ptr
>
(
node_
)));
}
reference
operator
*
()
const
{
return
static_cast
<
link_type
>
(
node_
)
->
value_
;
}
pointer
operator
->
()
const
{
return
std
::
__addressof
(
static_cast
<
link_type
>
(
node_
)
->
value_
);
}
self_type
&
operator
++
()
{
node_
=
_tree_leaf_increment
(
node_
);
return
*
this
;
}
self_type
operator
++
(
int
)
{
self_type
tmp
=
*
this
;
node_
=
_tree_leaf_increment
(
node_
);
return
tmp
;
}
bool
operator
==
(
const
self_type
&
x
)
const
{
return
node_
==
x
.
node_
;
}
bool
operator
!=
(
const
self_type
&
x
)
const
{
return
node_
!=
x
.
node_
;
}
bool
operator
<
(
const
self_type
&
x
)
const
{
return
node_
<
x
.
node_
;
}
base_ptr
node_
;
};
template
<
typename
_Val
>
inline
bool
operator
==
(
const
Tree_leaf_iterator
<
_Val
>&
x
,
const
Tree_leaf_const_iterator
<
_Val
>&
y
)
{
return
x
.
node_
==
y
.
node_
;
}
template
<
typename
_Val
>
inline
bool
operator
!=
(
const
Tree_leaf_iterator
<
_Val
>&
x
,
const
Tree_leaf_const_iterator
<
_Val
>&
y
)
{
return
x
.
node_
!=
y
.
node_
;
}
template
<
class
tree_pointer
>
static
tree_pointer
*
local_tree_increment
(
tree_pointer
*
x
)
throw
()
{
if
(
x
->
right_
!=
0
)
{
x
=
x
->
right_
;
while
(
x
->
left_
!=
0
)
x
=
x
->
left_
;
}
else
{
tree_pointer
*
y
=
x
->
parent_
;
while
(
x
==
y
->
right_
)
{
x
=
y
;
y
=
y
->
parent_
;
}
if
(
x
->
right_
!=
y
)
x
=
y
;
}
return
x
;
}
template
<
class
tree_pointer
>
tree_pointer
*
_tree_increment
(
tree_pointer
*
x
)
throw
()
{
return
local_tree_increment
(
x
);
}
template
<
class
tree_pointer
>
const
tree_pointer
*
_tree_increment
(
const
tree_pointer
*
x
)
throw
()
{
return
local_tree_increment
(
const_cast
<
tree_pointer
*>
(
x
));
}
template
<
class
tree_pointer
>
static
tree_pointer
*
local_tree_decrement
(
tree_pointer
*
x
)
throw
()
{
if
(
x
->
parent_
->
parent_
==
x
)
x
=
x
->
right_
;
else
if
(
x
->
left_
!=
0
)
{
Tree_node_base
*
y
=
x
->
left_
;
while
(
y
->
right_
!=
0
)
y
=
y
->
right_
;
x
=
y
;
}
else
{
tree_pointer
*
y
=
x
->
parent_
;
while
(
x
==
y
->
left_
)
{
x
=
y
;
y
=
y
->
parent_
;
}
x
=
y
;
}
return
x
;
}
template
<
class
tree_pointer
>
tree_pointer
*
_tree_decrement
(
tree_pointer
*
x
)
throw
()
{
return
local_tree_decrement
(
x
);
}
template
<
class
tree_pointer
>
const
tree_pointer
*
_tree_decrement
(
const
tree_pointer
*
x
)
throw
()
{
return
local_tree_decrement
(
const_cast
<
tree_pointer
*>
(
x
));
}
// iterators
template
<
typename
_Tp
>
struct
Tree_iterator
{
typedef
_Tp
value_type
;
typedef
_Tp
&
reference
;
typedef
_Tp
*
pointer
;
typedef
std
::
bidirectional_iterator_tag
iterator_category
;
typedef
std
::
ptrdiff_t
difference_type
;
typedef
Tree_iterator
<
_Tp
>
self_type
;
typedef
Tree_node_base
::
base_ptr
base_ptr
;
typedef
Tree_node
<
_Tp
>*
link_type
;
typedef
Tree_leaf_iterator
<
value_type
>
leaf_iterator
;
Tree_iterator
()
:
node_
()
{
}
explicit
Tree_iterator
(
link_type
x
)
:
node_
(
x
)
{
}
Tree_iterator
(
const
leaf_iterator
&
it
)
:
node_
(
it
.
node_
)
{
}
reference
operator
*
()
const
{
return
static_cast
<
link_type
>
(
node_
)
->
value_
;
}
pointer
operator
->
()
const
{
return
std
::
__addressof
(
static_cast
<
link_type
>
(
node_
)
->
value_
);
}
self_type
&
operator
++
()
{
node_
=
_tree_increment
(
node_
);
return
*
this
;
}
self_type
operator
++
(
int
)
{
self_type
tmp
=
*
this
;
node_
=
_tree_increment
(
node_
);
return
tmp
;
}
self_type
&
operator
--
()
{
node_
=
_tree_decrement
(
node_
);
return
*
this
;
}
self_type
operator
--
(
int
)
{
self_type
tmp
=
*
this
;
node_
=
_tree_decrement
(
node_
);
return
tmp
;
}
self_type
left
()
{
return
self_type
(
static_cast
<
link_type
>
(
node_
->
left_
));
}
self_type
right
()
{
return
self_type
(
static_cast
<
link_type
>
(
node_
->
right_
));
}
self_type
parent
()
{
return
self_type
(
static_cast
<
link_type
>
(
node_
->
parent_
));
}
bool
is_leaf
()
{
assert
(
node_
!=
nullptr
);
return
node_
->
left_
==
nullptr
&&
node_
->
right_
==
nullptr
;
}
bool
operator
==
(
const
self_type
&
x
)
const
{
return
node_
==
x
.
node_
;
}
bool
operator
!=
(
const
self_type
&
x
)
const
{
return
node_
!=
x
.
node_
;
}
bool
operator
<
(
const
self_type
&
x
)
const
{
return
node_
<
x
.
node_
;
}
base_ptr
node_
;
};
template
<
typename
_Tp
>
struct
Tree_const_iterator
{
typedef
_Tp
value_type
;
typedef
const
_Tp
&
reference
;
typedef
const
_Tp
*
pointer
;
typedef
Tree_iterator
<
_Tp
>
iterator
;
typedef
std
::
bidirectional_iterator_tag
iterator_category
;
typedef
std
::
ptrdiff_t
difference_type
;
typedef
Tree_const_iterator
<
_Tp
>
self_type
;
typedef
Tree_node_base
::
const_base_ptr
base_ptr
;
typedef
const
Tree_node
<
_Tp
>*
link_type
;
Tree_const_iterator
()
:
node_
()
{
}
explicit
Tree_const_iterator
(
link_type
x
)
:
node_
(
x
)
{
}
Tree_const_iterator
(
const
iterator
&
it
)
:
node_
(
it
.
node_
)
{
}
iterator
_const_cast
()
const
{
return
iterator
(
static_cast
<
typename
iterator
::
link_type
>
(
const_cast
<
typename
iterator
::
base_ptr
>
(
node_
)));
}
reference
operator
*
()
const
{
return
static_cast
<
link_type
>
(
node_
)
->
value_
;
}
pointer
operator
->
()
const
{
return
std
::
__addressof
(
static_cast
<
link_type
>
(
node_
)
->
value_
);
}
self_type
&
operator
++
()
{
node_
=
_tree_increment
(
node_
);
return
*
this
;
}
self_type
operator
++
(
int
)
{
self_type
tmp
=
*
this
;
node_
=
_tree_increment
(
node_
);
return
tmp
;
}
self_type
&
operator
--
()
{
node_
=
_tree_decrement
(
node_
);
return
*
this
;
}
self_type
operator
--
(
int
)
{
self_type
tmp
=
*
this
;
node_
=
_tree_decrement
(
node_
);
return
tmp
;
}
self_type
left
()
{
return
self_type
(
static_cast
<
link_type
>
(
node_
->
left_
));
}
self_type
right
()
{
return
self_type
(
static_cast
<
link_type
>
(
node_
->
right_
));
}
self_type
parent
()
{
return
self_type
(
static_cast
<
link_type
>
(
node_
->
parent_
));
}
bool
is_leaf
()
{
assert
(
node_
!=
nullptr
);
return
node_
->
left_
==
nullptr
&&
node_
->
right_
==
nullptr
;
}
bool
operator
==
(
const
self_type
&
x
)
const
{
return
node_
==
x
.
node_
;
}
bool
operator
!=
(
const
self_type
&
x
)
const
{
return
node_
!=
x
.
node_
;
}
bool
operator
<
(
const
self_type
&
x
)
const
{
return
node_
<
x
.
node_
;
}
base_ptr
node_
;
};
template
<
typename
_Val
>
inline
bool
operator
==
(
const
Tree_iterator
<
_Val
>&
x
,
const
Tree_const_iterator
<
_Val
>&
y
)
{
return
x
.
node_
==
y
.
node_
;
}
template
<
typename
_Val
>
inline
bool
operator
!=
(
const
Tree_iterator
<
_Val
>&
x
,
const
Tree_const_iterator
<
_Val
>&
y
)
{
return
x
.
node_
!=
y
.
node_
;
}
// traversal
template
<
class
iterator_type
,
class
functor_type
>
void
inorder
(
iterator_type
it
,
functor_type
&
fn
)
{
if
(
it
.
node_
==
nullptr
)
return
;
inorder
(
it
.
left
(),
fn
);
fn
(
it
);
inorder
(
it
.
right
(),
fn
);
}
template
<
class
iterator_type
,
class
functor_type
>
void
preorder
(
iterator_type
it
,
functor_type
&
fn
)
{
if
(
it
.
node_
==
nullptr
)
return
;
fn
(
it
);
preorder
(
it
.
left
(),
fn
);
preorder
(
it
.
right
(),
fn
);
}
template
<
class
iterator_type
,
class
functor_type
>
void
postorder
(
iterator_type
it
,
functor_type
&
fn
)
{
if
(
it
.
node_
==
nullptr
)
return
;
postorder
(
it
.
left
(),
fn
);
postorder
(
it
.
right
(),
fn
);
fn
(
it
);
}
//! Tree class
template
<
typename
T
,
template
<
class
>
class
_Cost
,
typename
_Alloc
=
std
::
allocator
<
T
>
>
class
Tree
{
typedef
typename
_Alloc
::
template
rebind
<
Tree_node
<
T
>
>::
other
_Node_allocator
;
protected
:
typedef
Tree_node_base
*
base_ptr
;
typedef
const
Tree_node_base
*
const_base_ptr
;
public
:
typedef
T
value_type
;
typedef
value_type
*
pointer
;
typedef
const
value_type
*
const_pointer
;
typedef
value_type
&
reference
;
typedef
const
value_type
&
const_reference
;
typedef
Tree_node
<
T
>*
link_type
;
typedef
const
Tree_node
<
T
>*
const_link_type
;
typedef
size_t
size_type
;
typedef
std
::
ptrdiff_t
difference_type
;
typedef
_Cost
<
value_type
>
cost_functor
;
typedef
_Alloc
allocator_type
;
_Node_allocator
&
_get_Node_allocator
()
{
return
*
static_cast
<
_Node_allocator
*>
(
&
this
->
impl_
);
}
const
_Node_allocator
&
_get_Node_allocator
()
const
{
return
*
static_cast
<
const
_Node_allocator
*>
(
&
this
->
impl_
);
}
allocator_type
get_allocator
()
const
{
return
allocator_type
(
_get_Node_allocator
());
}
private
:
link_type
_get_node
()
{
return
impl_
.
_Node_allocator
::
allocate
(
1
);
}
void
_put_node
(
link_type
p
)
{
impl_
.
_Node_allocator
::
deallocate
(
p
,
1
);
}
void
_destroy_node
(
link_type
p
)
{
_get_Node_allocator
().
destroy
(
p
);
_put_node
(
p
);
}
link_type
_clone_node
(
const_link_type
x
)
{
link_type
tmp
=
_create_node
(
x
->
value_
);
tmp
->
left_
=
0
;
tmp
->
right_
=
0
;
return
tmp
;
}
template
<
typename
...
_Args
>
link_type
_create_node
(
_Args
&&
...
args
)
{
link_type
tmp
=
_get_node
();
try
{
_get_Node_allocator
().
construct
(
tmp
,
std
::
forward
<
_Args
>
(
args
)...);
tmp
->
left_
=
0
;
tmp
->
right_
=
0
;
tmp
->
parent_
=
0
;
}
catch
(...)
{
_put_node
(
tmp
);
throw
;
}
return
tmp
;
}
private
:
template
<
typename
_Cost_functor
>
struct
Tree_impl
:
public
_Node_allocator
{
_Cost_functor
cost_
;
Tree_node_base
header_
;
size_type
node_count_
;
// Keeps track of size of tree.
Tree_impl
()
:
_Node_allocator
(),
cost_
(),
header_
(),
node_count_
(
0
)
{
_M_initialize
();
}
Tree_impl
(
const
_Cost_functor
&
comp
,
const
_Node_allocator
&
a
)
:
_Node_allocator
(
a
),
cost_
(
comp
),
header_
(),
node_count_
(
0
)
{
_M_initialize
();
}
Tree_impl
(
const
_Cost_functor
&
comp
,
_Node_allocator
&&
a
)
:
_Node_allocator
(
std
::
move
(
a
)),
cost_
(
comp
),
header_
(),
node_count_
(
0
)
{
_M_initialize
();
}
private
:
void
_M_initialize
()
{
this
->
header_
.
parent_
=
0
;
this
->
header_
.
left_
=
&
this
->
header_
;
this
->
header_
.
right_
=
&
this
->
header_
;
}
};
private
:
Tree_impl
<
cost_functor
>
impl_
;
//!< Tree implementation instance
base_ptr
&
_root
()
{
return
this
->
impl_
.
header_
.
parent_
;
}
const_base_ptr
_root
()
const
{
return
this
->
impl_
.
header_
.
parent_
;
}
base_ptr
&
_leftmost
()
{
return
this
->
impl_
.
header_
.
left_
;
}
const_base_ptr
_leftmost
()
const
{
return
this
->
impl_
.
header_
.
left_
;
}
base_ptr
&
_rightmost
()
{
return
this
->
impl_
.
header_
.
right_
;
}
const_base_ptr
_rightmost
()
const
{
return
this
->
impl_
.
header_
.
right_
;
}
link_type
_begin
()
{
return
static_cast
<
link_type
>
(
this
->
impl_
.
header_
.
parent_
);
}
const_link_type
_begin
()
const
{
return
static_cast
<
const_link_type
>
(
this
->
impl_
.
header_
.
parent_
);
}
link_type
_end
()
{
return
static_cast
<
link_type
>
(
&
this
->
impl_
.
header_
);
}
const_link_type
_end
()
const
{
return
static_cast
<
const_link_type
>
(
&
this
->
impl_
.
header_
);
}
static
reference
_value
(
link_type
x
)
{
return
x
->
value_
;
}
static
const_reference
_value
(
const_link_type
x
)
{
return
x
->
value_
;
}
static
reference
_value
(
base_ptr
x
)
{
return
static_cast
<
link_type
>
(
x
)
->
value_
;
}
static
const_reference
_value
(
const_base_ptr
x
)
{
return
static_cast
<
const_link_type
>
(
x
)
->
value_
;
}
static
link_type
_left
(
base_ptr
x
)
{
return
static_cast
<
link_type
>
(
x
->
left_
);
}
static
const_link_type
_left
(
const_base_ptr
x
)
{
return
static_cast
<
const_link_type
>
(
x
->
left_
);
}
static
link_type
_right
(
base_ptr
x
)
{
return
static_cast
<
link_type
>
(
x
->
right_
);
}
static
const_link_type
_right
(
const_base_ptr
x
)
{
return
static_cast
<
const_link_type
>
(
x
->
right_
);
}
static
link_type
_parent
(
base_ptr
x
)
{
return
static_cast
<
link_type
>
(
x
->
parent_
);
}
static
const_link_type
_parent
(
const_base_ptr
x
)
{
return
static_cast
<
const_link_type
>
(
x
->
parent_
);
}
void
_erase
(
link_type
x
)
{
while
(
x
!=
0
)
{
#ifdef DEBUG_TREE
cout
<<
"pointer x -> "
<<
x
<<
endl
;
cout
<<
"calling erase on right -> "
<<
_right
(
x
)
<<
endl
;
cout
<<
"destroying node -> "
<<
_value
(
x
)
<<
endl
;
cout
<<
"setting x to left -> "
<<
_left
(
x
)
<<
endl
;
#endif
_erase
(
_right
(
x
));
link_type
y
=
_left
(
x
);
_destroy_node
(
x
);
--
impl_
.
node_count_
;
// decrement nodes
x
=
y
;
}
}
link_type
_copy
(
const_link_type
x
,
link_type
p
)
{
link_type
top
=
_clone_node
(
x
);
top
->
parent_
=
p
;
try
{
if
(
x
->
right_
)
top
->
right_
=
_copy
(
_right
(
x
),
top
);
p
=
top
;
x
=
_left
(
x
);
while
(
x
!=
0
)
{
link_type
y
=
_clone_node
(
x
);
p
->
left_
=
y
;
y
->
parent_
=
p
;
if
(
x
->
right_
)
y
->
right_
=
_copy
(
_right
(
x
),
y
);
p
=
y
;
x
=
_left
(
x
);
}
}
catch
(...)
{
_erase
(
top
);
throw
;
}
return
top
;
}
void
_check_integrity
(
link_type
x
)
{
while
(
x
!=
0
)
{
link_type
r
=
_right
(
x
);
if
(
r
)
if
(
r
->
parent_
!=
x
)
{
cout
<<
"*** ERROR *** Integrity check failed"
<<
endl
;
cout
<<
"Right child parent mismatch"
<<
endl
;
exit
(
1
);
}
link_type
l
=
_left
(
x
);
if
(
l
)
if
(
l
->
parent_
!=
x
)
{
cout
<<
"*** ERROR *** Integrity check failed"
<<
endl
;
cout
<<
"Left child parent mismatch"
<<
endl
;
exit
(
1
);
}
_check_integrity
(
r
);
x
=
_left
(
x
);
}
}
public
:
typedef
Tree_iterator
<
value_type
>
iterator
;
typedef
Tree_const_iterator
<
value_type
>
const_iterator
;
typedef
std
::
reverse_iterator
<
iterator
>
reverse_iterator
;
typedef
std
::
reverse_iterator
<
const_iterator
>
const_reverse_iterator
;
typedef
Tree_leaf_iterator
<
value_type
>
leaf_iterator
;
typedef
Tree_leaf_const_iterator
<
value_type
>
const_leaf_iterator
;
// allocation/deallocation
Tree
()
{}
Tree
(
const
cost_functor
&
cost
,
const
allocator_type
&
a
=
allocator_type
())
:
impl_
(
cost
,
_Node_allocator
(
a
))
{
}
Tree
(
const
Tree
&
x
)
:
impl_
(
x
.
impl_
.
cost_
,
x
.
_get_Node_allocator
())
{
if
(
x
.
_root
()
!=
0
)
{
_root
()
=
_copy
(
x
.
_begin
(),
_end
());
_leftmost
()
=
Tree_node_base
::
_minimum
(
_root
());
_rightmost
()
=
Tree_node_base
::
_maximum
(
_root
());
impl_
.
node_count_
=
x
.
impl_
.
node_count_
;
}
}
//! construct a tree from link type, defined by the user in any way
Tree
(
link_type
x
)
{
// integrity check
_check_integrity
(
x
);
if
(
x
)
_insert
(
0
,
x
);
}
~
Tree
()
noexcept
{
_erase
(
_begin
());
}
const
cost_functor
&
cost
()
const
{
return
impl_
.
cost_
;
}
void
clear
()
noexcept
{
_erase
(
_begin
());
_leftmost
()
=
_end
();
_root
()
=
0
;
_rightmost
()
=
_end
();
// assert count == 0, _erase should take care of decrementing the node count
assert
(
impl_
.
node_count_
==
0
);
// impl_.node_count_ = 0;
}
iterator
begin
()
{
return
iterator
(
static_cast
<
link_type
>
(
this
->
impl_
.
header_
.
left_
));
}
const_iterator
begin
()
const
{
return
const_iterator
(
static_cast
<
const_link_type
>
(
this
->
impl_
.
header_
.
left_
));
}
iterator
end
()
{
return
iterator
(
static_cast
<
link_type
>
(
&
this
->
impl_
.
header_
));
}
const_iterator
end
()
const
{
return
const_iterator
(
static_cast
<
const_link_type
>
(
&
this
->
impl_
.
header_
));
}
reverse_iterator
rbegin
()
{
return
reverse_iterator
(
end
());
}
const_reverse_iterator
rbegin
()
const
{
return
const_reverse_iterator
(
end
());
}
reverse_iterator
rend
()
{
return
reverse_iterator
(
begin
());
}
const_reverse_iterator
rend
()
const
{
return
const_reverse_iterator
(
begin
());
}
leaf_iterator
leaves_begin
()
{
return
leaf_iterator
(
static_cast
<
link_type
>
(
impl_
.
header_
.
left_
));
}
const_leaf_iterator
leaves_begin
()
const
{
return
const_leaf_iterator
(
static_cast
<
const_link_type
>
(
impl_
.
header_
.
left_
));
}
leaf_iterator
leaves_end
()
{
return
leaf_iterator
(
static_cast
<
link_type
>
(
&
impl_
.
header_
));
}
const_leaf_iterator
leaves_end
()
const
{
return
const_leaf_iterator
(
static_cast
<
const_link_type
>
(
&
impl_
.
header_
));
}
iterator
root
()
{
return
iterator
(
static_cast
<
link_type
>
(
impl_
.
header_
.
parent_
));
}
const_iterator
root
()
const
{
return
const_iterator
(
static_cast
<
const_link_type
>
(
impl_
.
header_
.
parent_
));
}
bool
empty
()
const
{
return
impl_
.
node_count_
==
0
;
}
size_type
size
()
const
{
return
impl_
.
node_count_
;
}
size_type
max_size
()
const
{
return
_get_Node_allocator
().
max_size
();
}
std
::
tuple
<
size_t
,
size_t
,
size_t
>
height
()
const
{
size_t
count
=
0
;
size_t
min
=
std
::
numeric_limits
<
size_t
>::
max
();
size_t
max
=
0
;
size_t
h
=
0
;
for
(
const_leaf_iterator
it
=
leaves_begin
();
it
!=
leaves_end
();
++
it
)
{
const_base_ptr
x
=
it
.
node_
;
size_t
h1
=
0
;
while
(
x
->
parent_
!=
_end
())
{
++
h1
;
x
=
x
->
parent_
;
}
min
=
std
::
min
(
min
,
h1
);
max
=
std
::
max
(
max
,
h1
);
++
count
;
h
+=
h1
;
}
return
std
::
make_tuple
(
h
/
count
,
min
,
max
);
}
private
:
void
_add_level
(
std
::
queue
<
link_type
>&
q
,
base_ptr
x
,
size_t
h
,
size_t
level
)
{
if
(
h
<
level
)
{
if
(
x
->
left_
!=
0
)
_add_level
(
q
,
x
->
left_
,
h
+
1
,
level
);
if
(
x
->
right_
!=
0
)
_add_level
(
q
,
x
->
right_
,
h
+
1
,
level
);
}
else
if
(
h
==
level
)
q
.
push
(
static_cast
<
link_type
>
(
x
));
else
return
;
}
iterator
_insert
(
base_ptr
l
,
base_ptr
r
,
bool
count
=
true
)
{
#ifdef DEBUG_TREE
cout
<<
"inside inserting two for iterators"
<<
endl
;
cout
<<
"left pointer "
<<
l
<<
endl
;
if
(
l
)
cout
<<
"left "
<<
_value
(
l
)
<<
endl
;
cout
<<
"right pointer "
<<
r
<<
endl
;
cout
<<
"right "
<<
_value
(
r
)
<<
endl
;
#endif
// set parent to header to count nodes
link_type
p
=
_end
();
r
->
parent_
=
p
;
// get left most
base_ptr
lt
=
r
;
while
(
lt
->
left_
!=
0
)
lt
=
lt
->
left_
;
#ifdef DEBUG_TREE
cout
<<
"left most -> "
<<
_value
(
lt
)
<<
endl
;
#endif
// count nodes
if
(
count
)
for
(
iterator
it
(
static_cast
<
link_type
>
(
lt
));
it
!=
end
();
++
it
)
++
impl_
.
node_count_
;
// get right most
base_ptr
rt
=
r
;
while
(
rt
->
right_
!=
0
)
rt
=
rt
->
right_
;
// if l is not null, create a new node
link_type
lr
=
static_cast
<
link_type
>
(
r
);
if
(
l
)
{
auto
vp
=
impl_
.
cost_
(
_value
(
l
),
_value
(
r
));
lr
=
_create_node
(
vp
);
++
impl_
.
node_count_
;
p
=
_parent
(
l
);
lr
->
parent_
=
p
;
lr
->
right_
=
r
;
lr
->
left_
=
l
;
r
->
parent_
=
lr
;
l
->
parent_
=
lr
;
}
else
_leftmost
()
=
lt
;
// fix header
if
(
lr
->
parent_
==
_end
())
{
_root
()
=
lr
;
_rightmost
()
=
rt
;
}
else
{
// fix parent pointers
if
(
p
->
right_
==
l
)
p
->
right_
=
lr
;
else
if
(
p
->
left_
==
l
)
p
->
left_
=
lr
;
}
// recursively fix parents
auto
fix
=
_value
(
lr
);
while
(
lr
->
parent_
!=
_end
())
{
p
=
_parent
(
lr
);
fix
=
impl_
.
cost_
(
_value
(
p
),
fix
);
p
->
value_
=
fix
;
lr
=
p
;
}
return
iterator
(
static_cast
<
link_type
>
(
r
));
}
bool
_is_leaf
(
const_base_ptr
x
)
const
{
assert
(
x
!=
nullptr
);
return
(
_right
(
x
)
==
nullptr
)
&&
(
_left
(
x
)
==
nullptr
);
}
public
:
struct
_Queue_compare
{
// pointer - ancestor expansion - best cost tuples
typedef
std
::
tuple
<
link_type
,
Real
,
Real
>
tuple_type
;
bool
operator
()(
const
tuple_type
&
t1
,
const
tuple_type
&
t2
)
const
{
return
std
::
get
<
1
>
(
t1
)
>
std
::
get
<
1
>
(
t2
);
}
};
//! Adapted from Omohundro:89 routine best_sib
template
<
typename
Arg
>
iterator
best_sibling
(
Arg
&&
v
)
{
#ifdef DEBUG_TREE
cout
<<
"--------------------"
<<
endl
;
cout
<<
"inserting "
<<
v
<<
endl
;
#endif
typedef
typename
_Queue_compare
::
tuple_type
tuple_type
;
typedef
typename
std
::
priority_queue
<
tuple_type
,
std
::
vector
<
tuple_type
>
,
_Queue_compare
>
queue_type
;
// set result to root
link_type
result
=
_begin
();
// check for empty tree
if
(
!
result
)
return
iterator
(
nullptr
);
// check for leaf node
else
if
(
_is_leaf
(
result
))
return
iterator
(
result
);
// compute combined cost
Real
bcost
=
impl_
.
cost_
(
impl_
.
cost_
(
v
,
_value
(
result
)));
#ifdef DEBUG_TREE
cout
<<
"root -> "
<<
_value
(
result
)
<<
endl
;
cout
<<
"bcost -> "
<<
bcost
<<
endl
;
#endif
// start the queue
queue_type
q
;
decltype
(
impl_
.
cost_
(
v
))
e
,
c
;
q
.
push
(
std
::
make_tuple
(
result
,
0.
,
bcost
));
// while queue is not empty
while
(
!
q
.
empty
())
{
// best candidate
auto
t
=
q
.
top
();
auto
nd
=
std
::
get
<
0
>
(
t
);
auto
aexp
=
std
::
get
<
1
>
(
t
);
auto
ndvol
=
std
::
get
<
2
>
(
t
);
// remove top most element
q
.
pop
();
#ifdef DEBUG_TREE
cout
<<
" inside while"
<<
endl
;
cout
<<
" top queue item "
<<
_value
(
nd
)
<<
endl
;
#endif
// no way to get better than bnd
if
(
aexp
>=
bcost
)
{
#ifdef DEBUG_TREE
cout
<<
"*** BREAKING"
<<
endl
;
#endif
break
;
}
// new ancestor expansion
e
=
aexp
+
ndvol
-
impl_
.
cost_
(
_value
(
nd
));
#ifdef DEBUG_TREE
cout
<<
" a exp "
<<
e
<<
endl
;
cout
<<
" bcost "
<<
bcost
<<
endl
;
cout
<<
" cost x "
<<
impl_
.
cost_
(
_value
(
nd
))
<<
endl
;
cout
<<
" e -> "
<<
e
<<
endl
;
#endif
// do left node
c
=
impl_
.
cost_
(
impl_
.
cost_
(
v
,
_value
(
nd
->
left_
)));
#ifdef DEBUG_TREE
cout
<<
" c left -> "
<<
c
<<
endl
;
#endif
if
(
c
+
e
<=
bcost
)
{
bcost
=
c
+
e
;
result
=
_left
(
nd
);
#ifdef DEBUG_TREE
cout
<<
" c+e < bcost!!! result set to left "
<<
_value
(
result
)
<<
endl
;
#endif
}
if
(
!
_is_leaf
(
nd
->
left_
))
q
.
push
(
std
::
make_tuple
(
_left
(
nd
),
e
,
c
));
// do right node
c
=
impl_
.
cost_
(
impl_
.
cost_
(
v
,
_value
(
nd
->
right_
)));
#ifdef DEBUG_TREE
cout
<<
" c right -> "
<<
c
<<
endl
;
#endif
if
(
c
+
e
<=
bcost
)
{
bcost
=
c
+
e
;
result
=
_right
(
nd
);
#ifdef DEBUG_TREE
cout
<<
" c+e < bcost!!! result set to right "
<<
_value
(
result
)
<<
endl
;
#endif
}
if
(
!
_is_leaf
(
nd
->
right_
))
q
.
push
(
std
::
make_tuple
(
_right
(
nd
),
e
,
c
));
}
// while queue is not empty
#ifdef DEBUG_TREE
cout
<<
"best sibling -> "
<<
_value
(
result
)
<<
endl
;
#endif
return
iterator
(
result
);
}
//! Adapted from Omohundro:89 routine cheap_best_sib
template
<
typename
Arg
>
iterator
cheap_best_sibling
(
Arg
&&
v
)
{
#ifdef DEBUG_TREE
cout
<<
"--------------------"
<<
endl
;
cout
<<
"inserting "
<<
v
<<
endl
;
#endif
link_type
x
=
_begin
();
if
(
!
x
)
return
iterator
(
nullptr
);
#ifdef DEBUG_TREE
cout
<<
"root -> "
<<
_value
(
x
)
<<
endl
;
#endif
link_type
result
=
x
;
// compute combined cost
Real
wv
=
impl_
.
cost_
(
v
,
_value
(
x
));
// node vol + ancestor expansion
Real
bcost
=
wv
;
// ancestor expansion starts at zero
Real
ae
=
0
;
#ifdef DEBUG_TREE
cout
<<
"bcost -> "
<<
bcost
<<
endl
;
#endif
// while not a leaf node
while
(
x
->
left_
&&
x
->
right_
)
{
#ifdef DEBUG_TREE
cout
<<
" inside while"
<<
endl
;
#endif
auto
nd
=
impl_
.
cost_
(
_value
(
x
));
// correct for both children
ae
+=
wv
-
nd
;
#ifdef DEBUG_TREE
cout
<<
" top queue item "
<<
_value
(
x
)
<<
endl
;
cout
<<
" a exp "
<<
ae
<<
endl
;
cout
<<
" bcost "
<<
bcost
<<
endl
;
cout
<<
" cost x "
<<
nd
<<
endl
;
cout
<<
" e -> "
<<
ae
<<
endl
;
#endif
// cannot do any better, insert the volumes in the tree
if
(
ae
>=
bcost
)
break
;
else
{
auto
lv
=
impl_
.
cost_
(
v
,
_value
(
x
->
left_
));
auto
rv
=
impl_
.
cost_
(
v
,
_value
(
x
->
right_
));
#ifdef DEBUG_TREE
cout
<<
" c left -> "
<<
lv
<<
endl
;
#endif
if
(
ae
+
lv
<=
bcost
)
{
bcost
=
ae
+
lv
;
result
=
_left
(
x
);
#ifdef DEBUG_TREE
cout
<<
" c+e < bcost!!! result set to left "
<<
_value
(
_left
(
x
))
<<
endl
;
#endif
}
#ifdef DEBUG_TREE
cout
<<
" c right -> "
<<
rv
<<
endl
;
#endif
if
(
ae
+
rv
<=
bcost
)
{
bcost
=
ae
+
rv
;
result
=
_right
(
x
);
#ifdef DEBUG_TREE
cout
<<
" c+e < bcost!!! result set to right "
<<
_value
(
_right
(
x
))
<<
endl
;
#endif
}
// if left branch expands less
if
(
lv
-
impl_
.
cost_
(
_value
(
x
->
left_
))
<=
rv
-
impl_
.
cost_
(
_value
(
x
->
right_
)))
{
wv
=
lv
;
x
=
_left
(
x
);
}
else
{
wv
=
rv
;
x
=
_right
(
x
);
}
}
}
// while loop
#ifdef DEBUG_TREE
cout
<<
"best sibling -> "
<<
_value
(
result
)
<<
endl
;
#endif
return
iterator
(
result
);
}
private
:
template
<
class
functor_type
>
void
_execute_at_leaves
(
iterator
x
,
std
::
set
<
base_ptr
>&
visited
,
functor_type
&
fn
)
{
auto
it
=
visited
.
find
(
x
.
node_
);
if
(
it
!=
visited
.
end
())
return
;
visited
.
insert
(
x
.
node_
);
if
(
x
.
is_leaf
())
fn
(
x
);
else
{
if
(
x
.
node_
->
left_
!=
0
)
_execute_at_leaves
(
iterator
(
static_cast
<
link_type
>
(
x
.
node_
->
left_
)),
visited
,
fn
);
if
(
x
.
node_
->
right_
!=
0
)
_execute_at_leaves
(
iterator
(
static_cast
<
link_type
>
(
x
.
node_
->
right_
)),
visited
,
fn
);
}
}
public
:
//! Collect neighbors
/*! This function is used to collect neighbors from a tree given a functor.
* The functor should implement a parameterless and a one-parameter operator() overloads.
* The first load is used as the predicate to finish the search of neighbors, whereas
* the second one is executed at leaves.
*/
template
<
class
functor_type
>
void
collect_neighbors
(
iterator
it
,
functor_type
&
fn
)
{
// check for null ptr
if
(
it
.
node_
==
nullptr
)
return
;
std
::
set
<
base_ptr
>
visited
;
base_ptr
p
=
it
.
node_
;
// execute while predicate is not true
while
(
!
fn
())
{
p
=
p
->
parent_
;
// root node
if
(
p
==
_root
()
->
parent_
)
break
;
_execute_at_leaves
(
iterator
(
static_cast
<
link_type
>
(
p
)),
visited
,
fn
);
}
}
template
<
typename
Arg
>
std
::
pair
<
iterator
,
bool
>
cheap_insert
(
Arg
&&
v
)
{
iterator
it
=
cheap_best_sibling
(
v
);
link_type
r
=
_create_node
(
v
);
return
std
::
pair
<
iterator
,
bool
>
(
_insert
(
it
.
node_
,
r
),
true
);
}
template
<
typename
Arg
>
std
::
pair
<
iterator
,
bool
>
insert
(
Arg
&&
v
)
{
iterator
it
=
best_sibling
(
v
);
link_type
r
=
_create_node
(
v
);
return
std
::
pair
<
iterator
,
bool
>
(
_insert
(
it
.
node_
,
r
),
true
);
}
std
::
pair
<
iterator
,
bool
>
insert
(
link_type
x
)
{
return
insert
(
iterator
(
x
));
}
std
::
pair
<
iterator
,
bool
>
insert
(
iterator
vit
)
{
iterator
it
=
best_sibling
(
_value
(
vit
.
node_
));
return
std
::
pair
<
iterator
,
bool
>
(
_insert
(
it
.
node_
,
vit
.
node_
),
true
);
}
iterator
sibling
(
iterator
it
)
{
base_ptr
x
=
it
.
node_
;
if
(
!
x
)
return
iterator
(
nullptr
);
if
(
x
==
_root
())
return
end
();
base_ptr
p
=
x
->
parent_
;
assert
(
p
!=
0
);
if
(
p
->
left_
==
x
)
return
iterator
(
_right
(
p
));
return
iterator
(
_left
(
p
));
}
public
:
iterator
relocate_parent
(
iterator
it
)
{
#if DEBUG_TREE
if
(
it
.
node_
)
cout
<<
"relocating node "
<<
_value
(
it
.
node_
)
<<
endl
;
#endif
link_type
x
=
static_cast
<
link_type
>
(
it
.
node_
);
// null pointer
if
(
!
x
)
return
end
();
// get parent
link_type
p
=
_parent
(
x
);
// if parent is header return root
if
(
p
==
_end
())
return
iterator
(
_begin
());
// get grand-parent
link_type
gp
=
_parent
(
p
);
// no need to recompute volume as the parent has
// the enclosing volume of its children
// sibling
link_type
s
=
x
==
p
->
left_
?
_right
(
p
)
:
_left
(
p
);
#ifdef DEBUG_TREE
cout
<<
"relocating x -> "
<<
_value
(
x
)
<<
endl
;
cout
<<
"parent of node -> "
<<
_value
(
p
)
<<
endl
;
cout
<<
"sibling -> "
<<
_value
(
s
)
<<
endl
;
#endif
if
(
gp
==
_end
())
{
#ifdef DEBUG_TREE
cout
<<
"*** WARNING *** sibling new parent is the header!"
<<
endl
;
#endif
_root
()
=
s
;
}
else
if
(
gp
->
left_
==
p
)
{
gp
->
left_
=
s
;
#ifdef DEBUG_TREE
cout
<<
"setting parent->parent->left to sibling"
<<
endl
;
#endif
}
else
if
(
gp
->
right_
==
p
)
{
gp
->
right_
=
s
;
#ifdef DEBUG_TREE
cout
<<
"setting parent->parent->right to sibling"
<<
endl
;
#endif
}
else
assert
(
false
);
// set parent of sibling
s
->
parent_
=
p
->
parent_
;
// recursively fix parents
link_type
r
=
_parent
(
s
);
while
(
r
!=
_end
())
{
r
->
value_
=
impl_
.
cost_
(
_value
(
r
->
right_
),
_value
(
r
->
left_
));
r
=
_parent
(
r
);
}
// destroy parent node p and reinsert x into the tree
x
->
parent_
=
0
;
p
->
parent_
=
0
;
p
->
left_
=
0
;
p
->
right_
=
0
;
_erase
(
p
);
// get the best sibling
iterator
bit
=
best_sibling
(
_value
(
x
));
#ifdef DEBUG_TREE
cout
<<
"best sibling for relocation -> "
<<
bit
.
node_
<<
endl
;
if
(
it
.
node_
)
cout
<<
" best sibling value -> "
<<
_value
(
bit
.
node_
)
<<
endl
;
#endif
iterator
result
=
_insert
(
bit
.
node_
,
x
,
false
);
// set leftmost and rightmost
base_ptr
lt
=
_root
();
while
(
lt
->
left_
!=
0
)
lt
=
lt
->
left_
;
_leftmost
()
=
lt
;
base_ptr
rt
=
_root
();
while
(
rt
->
right_
!=
0
)
rt
=
rt
->
right_
;
_rightmost
()
=
rt
;
return
result
;
}
iterator
erase
(
iterator
it
)
{
link_type
x
=
static_cast
<
link_type
>
(
it
.
node_
);
// null pointer
if
(
!
x
)
return
end
();
// root node
else
if
(
x
==
_root
())
{
clear
();
return
end
();
}
link_type
p
=
_parent
(
x
);
link_type
s
;
// sibling
if
(
x
==
p
->
left_
)
{
s
=
_right
(
p
);
p
->
right_
=
0
;
// set to zero to use erase
}
else
{
s
=
_left
(
p
);
p
->
left_
=
0
;
}
#ifdef DEBUG_TREE
cout
<<
"erasing x -> "
<<
_value
(
x
)
<<
endl
;
cout
<<
"parent of node -> "
<<
_value
(
p
)
<<
endl
;
cout
<<
"sibling -> "
<<
_value
(
s
)
<<
endl
;
#endif
if
(
_leftmost
()
==
x
)
{
base_ptr
l
=
s
;
while
(
l
->
left_
!=
0
)
l
=
l
->
left_
;
_leftmost
()
=
l
;
#ifdef DEBUG_TREE
cout
<<
"x is leftmost, so setting leftmost to "
<<
_value
(
l
)
<<
endl
;
#endif
}
if
(
_rightmost
()
==
x
)
{
base_ptr
r
=
s
;
while
(
r
->
right_
!=
0
)
r
=
r
->
right_
;
_rightmost
()
=
r
;
#ifdef DEBUG_TREE
cout
<<
"x is rightmost, so setting rightmost to "
<<
_value
(
r
)
<<
endl
;
#endif
}
s
->
parent_
=
p
->
parent_
;
if
(
p
->
parent_
==
_end
())
{
#ifdef DEBUG_TREE
cout
<<
"*** WARNING *** sibling new parent is the header!"
<<
endl
;
#endif
_root
()
=
s
;
}
else
if
(
p
->
parent_
->
left_
==
p
)
{
p
->
parent_
->
left_
=
s
;
#ifdef DEBUG_TREE
cout
<<
"setting parent->parent->left to sibling"
<<
endl
;
#endif
}
else
{
p
->
parent_
->
right_
=
s
;
#ifdef DEBUG_TREE
cout
<<
"setting parent->parent->right to sibling"
<<
endl
;
#endif
}
#ifdef DEBUG_TREE
cout
<<
"p right -> "
<<
p
->
right_
<<
endl
;
cout
<<
"p left -> "
<<
p
->
left_
<<
endl
;
if
(
p
->
right_
)
cout
<<
"p right value -> "
<<
_value
(
p
->
right_
)
<<
endl
;
if
(
p
->
left_
)
cout
<<
"p left value -> "
<<
_value
(
p
->
left_
)
<<
endl
;
#endif
// recursively fix parents
link_type
r
=
_parent
(
s
);
while
(
r
!=
_end
())
{
r
->
value_
=
_value
(
r
->
right_
)
+
_value
(
r
->
left_
);
r
=
_parent
(
r
);
}
// erase subtree rooted at p
_erase
(
p
);
return
iterator
(
s
);
}
Real
volume
()
const
{
Real
v
=
0
;
for
(
const_iterator
it
=
begin
();
it
!=
end
();
++
it
)
v
+=
it
->
measure
();
return
v
;
}
friend
std
::
ostream
&
operator
<<
(
std
::
ostream
&
os
,
const
Tree
&
t
)
{
os
<<
"Tree: count "
<<
t
.
impl_
.
node_count_
<<
endl
;
os
<<
" header: "
<<&
t
.
impl_
.
header_
<<
endl
;
if
(
t
.
impl_
.
header_
.
parent_
)
os
<<
" ROOT: "
<<
t
.
impl_
.
header_
.
parent_
<<
", value "
<<
_value
(
t
.
impl_
.
header_
.
parent_
)
<<
endl
;
os
<<
" left: "
<<
t
.
impl_
.
header_
.
left_
<<
endl
;
os
<<
" right: "
<<
t
.
impl_
.
header_
.
right_
<<
endl
;
size_t
c
=
0
;
Real
v
=
0
;
os
<<
endl
;
for
(
Tree
::
const_iterator
it
=
t
.
begin
();
it
!=
t
.
end
();
++
it
,
++
c
)
{
Real
cost
=
t
.
impl_
.
cost_
(
*
it
);
if
(
it
.
node_
==
t
.
impl_
.
header_
.
parent_
)
{
os
<<
" ROOT "
<<
it
.
node_
;
if
(
it
.
node_
==
t
.
_leftmost
())
os
<<
" [LEFTMOST]"
;
if
(
it
.
node_
==
t
.
_rightmost
())
os
<<
" [RIGHTMOST]"
;
os
<<
"
\n
value: "
<<*
it
<<
endl
;
os
<<
" parent: "
<<
it
.
node_
->
parent_
<<
endl
;
}
else
{
os
<<
" pointer "
<<
it
.
node_
;
if
(
it
.
node_
==
t
.
_leftmost
())
os
<<
" [LEFTMOST]"
;
if
(
it
.
node_
==
t
.
_rightmost
())
os
<<
" [RIGHTMOST]"
;
os
<<
"
\n
value: "
<<*
it
<<
endl
;
os
<<
" parent: "
<<
it
.
node_
->
parent_
<<
", value "
<<
_value
(
it
.
node_
->
parent_
)
<<
endl
;
}
if
(
it
.
node_
->
left_
)
os
<<
" left: "
<<
it
.
node_
->
left_
<<
", value "
<<
_value
(
it
.
node_
->
left_
)
<<
endl
;
if
(
it
.
node_
->
right_
)
os
<<
" right: "
<<
it
.
node_
->
right_
<<
", value "
<<
_value
(
it
.
node_
->
right_
)
<<
endl
;
if
(
!
it
.
node_
->
left_
&&
!
it
.
node_
->
right_
)
os
<<
" leaf"
<<
endl
;
os
<<
" cost: "
<<
cost
<<
endl
;
os
<<
endl
;
v
+=
cost
;
}
cout
<<
"total cost -> "
<<
v
<<
endl
;
if
(
c
!=
t
.
impl_
.
node_count_
)
cout
<<
"*** WARNING *** Tree node count mismatch "
<<
t
.
impl_
.
node_count_
<<
" != "
<<
c
<<
endl
;
return
os
;
}
template
<
class
functor_type
>
functor_type
execute_at_level
(
size_t
level
,
functor_type
fn
)
{
link_type
x
=
_begin
();
if
(
x
==
nullptr
)
return
fn
;
std
::
queue
<
link_type
>
q
;
_add_level
(
q
,
x
,
0
,
level
);
while
(
!
q
.
empty
())
{
link_type
l
=
q
.
front
();
assert
(
l
!=
0
);
fn
(
iterator
(
l
));
q
.
pop
();
}
return
fn
;
}
};
template
<
class
object_type
>
struct
Cost_functor
{
auto
operator
()(
const
object_type
&
o
)
const
->
decltype
(
o
.
measure
())
{
return
o
.
measure
();
}
auto
operator
()(
const
object_type
&
o1
,
const
object_type
&
o2
)
const
->
decltype
(
o1
+
o2
)
{
return
(
o1
+
o2
);
}
};
template
<
class
link_type
>
struct
Tuple_compare
{
typedef
std
::
tuple
<
link_type
,
link_type
,
Real
>
tuple_type
;
bool
operator
()(
const
tuple_type
&
t1
,
const
tuple_type
&
t2
)
const
{
return
std
::
get
<
2
>
(
t1
)
>
std
::
get
<
2
>
(
t2
);
}
};
// bottom up tree construction
template
<
class
tree_type
,
class
volume_container
>
tree_type
*
construct_tree_bottom_up
(
const
volume_container
&
volumes
)
{
// online tree type definitions
typedef
typename
tree_type
::
value_type
volume_type
;
typedef
typename
tree_type
::
cost_functor
cost_functor
;
typedef
typename
tree_type
::
iterator
iterator_type
;
// queue type definitions
typedef
std
::
tuple
<
iterator_type
,
iterator_type
,
Real
>
tuple_type
;
typedef
typename
std
::
priority_queue
<
tuple_type
,
std
::
vector
<
tuple_type
>
,
Tuple_compare
<
iterator_type
>
>
queue_type
;
// already paired container type definitions
typedef
std
::
set
<
iterator_type
>
paired_set
;
typedef
typename
paired_set
::
iterator
paired_iterator
;
size_t
numVolumes
=
volumes
.
size
();
assert
(
numVolumes
!=
0
);
tree_type
*
tp
=
new
tree_type
();
const
cost_functor
&
cost
=
tp
->
cost
();
tree_type
&
t
=
*
tp
;
queue_type
q
;
paired_set
s
;
std
::
vector
<
iterator_type
>
links
(
numVolumes
);
// insert volumes into online tree
for
(
size_t
i
=
0
;
i
<
numVolumes
;
++
i
)
{
std
::
pair
<
iterator_type
,
bool
>
p
=
t
.
insert
(
volumes
[
i
]);
assert
(
p
.
second
);
links
[
i
]
=
p
.
first
;
}
iterator_type
ii
,
jj
;
for
(
size_t
i
=
0
;
i
<
numVolumes
-
1
;
++
i
)
{
Real
merged
=
std
::
numeric_limits
<
Real
>::
infinity
();
for
(
size_t
j
=
i
+
1
;
j
<
numVolumes
;
++
j
)
{
volume_type
v
=
cost
(
*
links
[
i
],
*
links
[
j
]);
Real
measure
=
cost
(
v
);
if
(
measure
<
merged
)
{
ii
=
links
[
i
];
jj
=
links
[
j
];
merged
=
measure
;
}
}
q
.
push
(
std
::
make_tuple
(
ii
,
jj
,
merged
));
}
while
(
!
q
.
empty
())
{
// best candidate
auto
tuple
=
q
.
top
();
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
q
.
pop
();
paired_iterator
it
=
s
.
find
(
node
);
if
(
it
!=
s
.
end
())
continue
;
it
=
s
.
find
(
pair
);
if
(
it
!=
s
.
end
())
continue
;
#if DEBUG_TREE
cout
<<
t
<<
endl
;
cout
<<
"node -> "
<<
node
.
node_
<<
endl
;
cout
<<
"node value -> "
<<*
node
<<
endl
;
cout
<<
"pair -> "
<<
pair
.
node_
<<
endl
;
cout
<<
"pair value -> "
<<*
pair
<<
endl
;
cout
<<
"volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
// obtain best pair from online tree
iterator_type
best
=
t
.
sibling
(
node
);
#if DEBUG_TREE
cout
<<
"best sibling -> "
<<*
best
<<
endl
;
#endif
if
(
pair
==
best
)
{
iterator_type
parent
=
t
.
relocate_parent
(
node
);
assert
(
parent
!=
t
.
end
());
#if DEBUG_TREE
cout
<<
"BEST SIBLING MATCHES! relocating..."
<<
endl
;
cout
<<
" parent -> "
<<*
parent
<<
endl
;
#endif
// add paired nodes to container
s
.
insert
(
node
);
s
.
insert
(
pair
);
// compute best pair for the parent
best
=
t
.
sibling
(
parent
);
if
(
best
!=
t
.
end
())
{
tuple_type
tuple
=
std
::
make_tuple
(
parent
,
best
,
cost
(
cost
(
*
parent
,
*
best
)));
q
.
push
(
tuple
);
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
#if DEBUG_TREE
cout
<<
" pushing new tuple "
<<
endl
;
cout
<<
" node -> "
<<*
node
<<
endl
;
cout
<<
" pair -> "
<<*
pair
<<
endl
;
cout
<<
" volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
}
}
// else enqueue new pair
else
{
if
(
best
!=
t
.
end
())
{
tuple_type
tuple
=
std
::
make_tuple
(
node
,
best
,
cost
(
cost
(
*
node
,
*
best
)));
q
.
push
(
tuple
);
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
#if DEBUG_TREE
cout
<<
"BEST SIBLING DOES NOT MATCH!"
<<
endl
;
cout
<<
" pushing new tuple "
<<
endl
;
cout
<<
" node -> "
<<*
node
<<
endl
;
cout
<<
" pair -> "
<<*
pair
<<
endl
;
cout
<<
" volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
}
}
}
return
tp
;
}
template
<
class
volume_type
>
class
Volume_creator
;
template
<
int
d
>
struct
Volume_creator
<
Ball
<
d
>
>
{
typedef
typename
Ball
<
d
>::
point_type
point_type
;
template
<
class
coord_array
>
static
Ball
<
d
>
create
(
const
coord_array
&
coord
)
{
std
::
vector
<
point_type
>
pts
;
size_t
nnodes
=
coord
.
size
();
pts
.
reserve
(
nnodes
);
for
(
size_t
i
=
0
;
i
<
nnodes
;
++
i
)
pts
.
push_back
(
point_type
(
coord
[
i
]));
return
bounding_ball
<
d
>
(
pts
);
}
};
template
<
int
d
>
struct
Volume_creator
<
BoundingBox
<
d
>
>
{
typedef
typename
BoundingBox
<
d
>::
point_type
point_type
;
template
<
class
coord_array
>
static
Sphere
create
(
const
coord_array
&
coord
)
{
std
::
vector
<
point_type
>
pts
;
size_t
nnodes
=
coord
.
size
();
pts
.
reserve
(
nnodes
);
for
(
size_t
i
=
0
;
i
<
nnodes
;
++
i
)
pts
.
push_back
(
point_type
(
coord
[
i
]));
return
BoundingBox
<
d
>
(
pts
.
begin
(),
pts
.
end
());
}
};
// bottom up tree construction
template
<
class
tree_type
,
class
model_type
,
class
element_type
>
tree_type
*
construct_tree_bottom_up
(
model_type
&
model
)
{
// online tree type definitions
typedef
typename
tree_type
::
value_type
volume_type
;
typedef
typename
tree_type
::
cost_functor
cost_functor
;
typedef
typename
tree_type
::
iterator
iterator_type
;
// queue type definitions
typedef
std
::
tuple
<
iterator_type
,
iterator_type
,
Real
>
tuple_type
;
typedef
typename
std
::
priority_queue
<
tuple_type
,
std
::
vector
<
tuple_type
>
,
Tuple_compare
<
iterator_type
>
>
queue_type
;
// already paired container type definitions
typedef
std
::
set
<
iterator_type
>
paired_set
;
typedef
typename
paired_set
::
iterator
paired_iterator
;
tree_type
*
tp
=
new
tree_type
();
tree_type
&
t
=
*
tp
;
const
cost_functor
&
cost
=
t
.
cost
();
std
::
vector
<
iterator_type
>
links
;
typedef
typename
model_type
::
mesh_type
mesh_type
;
mesh_type
&
mesh
=
model
.
getMesh
();
int
dim
=
mesh
.
getSpatialDimension
();
// iterate over elements of lower dimension
typename
mesh_type
::
type_iterator
it
=
mesh
.
firstType
(
dim
-
1
);
typename
mesh_type
::
type_iterator
end
=
mesh
.
lastType
(
dim
-
1
);
size_t
numVolumes
=
0
;
for
(;
it
!=
end
;
++
it
)
{
// add elements to corresponding surface
for
(
UInt
e
=
0
;
e
<
mesh
.
getNbElement
(
*
it
);
++
e
)
{
// create solid mechanics element
element_type
el
(
model
,
*
it
,
e
);
// vector of coordinates for update
std
::
vector
<
const
Real
*>
coord
=
el
.
coordinates
();
// create leaf volume
volume_type
v
=
Volume_creator
<
volume_type
>::
create
(
coord
);
// do not add zero measure volumes
if
(
v
.
measure
()
==
0
&&
dim
!=
1
)
continue
;
std
::
pair
<
iterator_type
,
bool
>
p
=
t
.
insert
(
v
);
assert
(
p
.
second
);
links
.
push_back
(
p
.
first
);
++
numVolumes
;
// save leaf data
if
(
!
t
.
add_data
(
p
.
first
,
el
))
{
cout
<<
"*** ERROR *** Could not add data. Aborting..."
<<
endl
;
exit
(
1
);
}
}
// loop over elements
}
// loop over types of element
if
(
numVolumes
==
0
)
{
cout
<<
"*** ERROR *** No volumes were created. Aborting..."
<<
endl
;
exit
(
1
);
}
queue_type
q
;
paired_set
s
;
iterator_type
ii
,
jj
;
for
(
size_t
i
=
0
;
i
<
numVolumes
-
1
;
++
i
)
{
Real
merged
=
std
::
numeric_limits
<
Real
>::
infinity
();
for
(
size_t
j
=
i
+
1
;
j
<
numVolumes
;
++
j
)
{
volume_type
v
=
cost
(
*
links
[
i
],
*
links
[
j
]);
Real
measure
=
v
.
measure
();
if
(
measure
<
merged
)
{
ii
=
links
[
i
];
jj
=
links
[
j
];
merged
=
measure
;
}
}
q
.
push
(
std
::
make_tuple
(
ii
,
jj
,
merged
));
}
while
(
!
q
.
empty
())
{
// best candidate
auto
tuple
=
q
.
top
();
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
q
.
pop
();
paired_iterator
it
=
s
.
find
(
node
);
if
(
it
!=
s
.
end
())
continue
;
it
=
s
.
find
(
pair
);
if
(
it
!=
s
.
end
())
continue
;
#if DEBUG_TREE
cout
<<
t
<<
endl
;
cout
<<
"node -> "
<<
node
.
node_
<<
endl
;
cout
<<
"node value -> "
<<*
node
<<
endl
;
cout
<<
"pair -> "
<<
pair
.
node_
<<
endl
;
cout
<<
"pair value -> "
<<*
pair
<<
endl
;
cout
<<
"volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
// obtain best pair from online tree
iterator_type
best
=
t
.
sibling
(
node
);
#if DEBUG_TREE
cout
<<
"best sibling -> "
<<*
best
<<
endl
;
#endif
if
(
pair
==
best
)
{
iterator_type
parent
=
t
.
relocate_parent
(
node
);
assert
(
parent
!=
t
.
end
());
#if DEBUG_TREE
cout
<<
"BEST SIBLING MATCHES! relocating..."
<<
endl
;
cout
<<
" parent -> "
<<*
parent
<<
endl
;
#endif
// add paired nodes to container
s
.
insert
(
node
);
s
.
insert
(
pair
);
// compute best pair for the parent
best
=
t
.
sibling
(
parent
);
if
(
best
!=
t
.
end
())
{
tuple_type
tuple
=
std
::
make_tuple
(
parent
,
best
,
cost
(
cost
(
*
parent
,
*
best
)));
q
.
push
(
tuple
);
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
#if DEBUG_TREE
cout
<<
" pushing new tuple "
<<
endl
;
cout
<<
" node -> "
<<*
node
<<
endl
;
cout
<<
" pair -> "
<<*
pair
<<
endl
;
cout
<<
" volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
}
}
// else enqueue new pair
else
{
if
(
best
!=
t
.
end
())
{
tuple_type
tuple
=
std
::
make_tuple
(
node
,
best
,
cost
(
cost
(
*
node
,
*
best
)));
q
.
push
(
tuple
);
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
#if DEBUG_TREE
cout
<<
"BEST SIBLING DOES NOT MATCH!"
<<
endl
;
cout
<<
" pushing new tuple "
<<
endl
;
cout
<<
" node -> "
<<*
node
<<
endl
;
cout
<<
" pair -> "
<<*
pair
<<
endl
;
cout
<<
" volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
}
}
}
return
tp
;
}
// bottom up tree construction
template
<
class
tree_type
,
class
element_container
>
tree_type
*
construct_tree_bottom_up
(
element_container
&
elems
)
{
// element type
typedef
typename
element_container
::
value_type
element_type
;
// online tree type definitions
typedef
typename
tree_type
::
value_type
volume_type
;
typedef
typename
tree_type
::
cost_functor
cost_functor
;
typedef
typename
tree_type
::
iterator
iterator_type
;
// queue type definitions
typedef
std
::
tuple
<
iterator_type
,
iterator_type
,
Real
>
tuple_type
;
typedef
typename
std
::
priority_queue
<
tuple_type
,
std
::
vector
<
tuple_type
>
,
Tuple_compare
<
iterator_type
>
>
queue_type
;
// already paired container type definitions
typedef
std
::
set
<
iterator_type
>
paired_set
;
typedef
typename
paired_set
::
iterator
paired_iterator
;
tree_type
*
tp
=
new
tree_type
();
tree_type
&
t
=
*
tp
;
const
cost_functor
&
cost
=
t
.
cost
();
std
::
vector
<
iterator_type
>
links
;
size_t
numVolumes
=
0
;
for
(
typename
element_container
::
iterator
it
=
elems
.
begin
();
it
!=
elems
.
end
();
++
it
)
{
element_type
&
el
=
*
it
;
// vector of coordinates for update
std
::
vector
<
const
Real
*>
coord
=
el
.
coordinates
();
// create leaf volume
volume_type
v
=
Volume_creator
<
volume_type
>::
create
(
coord
);
// do not add zero measure volumes
if
(
v
.
measure
()
==
0
)
continue
;
std
::
pair
<
iterator_type
,
bool
>
p
=
t
.
insert
(
v
);
assert
(
p
.
second
);
links
.
push_back
(
p
.
first
);
++
numVolumes
;
// save leaf data
if
(
!
t
.
add_data
(
p
.
first
,
el
))
{
cout
<<
"*** ERROR *** Could not add data. Aborting..."
<<
endl
;
exit
(
1
);
}
}
// loop over elements in container
if
(
numVolumes
==
0
)
{
cout
<<
"*** ERROR *** No volumes were created. Aborting..."
<<
endl
;
exit
(
1
);
}
queue_type
q
;
paired_set
s
;
iterator_type
ii
,
jj
;
for
(
size_t
i
=
0
;
i
<
numVolumes
-
1
;
++
i
)
{
Real
merged
=
std
::
numeric_limits
<
Real
>::
infinity
();
for
(
size_t
j
=
i
+
1
;
j
<
numVolumes
;
++
j
)
{
volume_type
v
=
cost
(
*
links
[
i
],
*
links
[
j
]);
Real
measure
=
v
.
measure
();
if
(
measure
<
merged
)
{
ii
=
links
[
i
];
jj
=
links
[
j
];
merged
=
measure
;
}
}
q
.
push
(
std
::
make_tuple
(
ii
,
jj
,
merged
));
}
while
(
!
q
.
empty
())
{
// best candidate
auto
tuple
=
q
.
top
();
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
q
.
pop
();
paired_iterator
it
=
s
.
find
(
node
);
if
(
it
!=
s
.
end
())
continue
;
it
=
s
.
find
(
pair
);
if
(
it
!=
s
.
end
())
continue
;
#if DEBUG_TREE
cout
<<
t
<<
endl
;
cout
<<
"node -> "
<<
node
.
node_
<<
endl
;
cout
<<
"node value -> "
<<*
node
<<
endl
;
cout
<<
"pair -> "
<<
pair
.
node_
<<
endl
;
cout
<<
"pair value -> "
<<*
pair
<<
endl
;
cout
<<
"volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
// obtain best pair from online tree
iterator_type
best
=
t
.
sibling
(
node
);
#if DEBUG_TREE
cout
<<
"best sibling -> "
<<*
best
<<
endl
;
#endif
if
(
pair
==
best
)
{
iterator_type
parent
=
t
.
relocate_parent
(
node
);
assert
(
parent
!=
t
.
end
());
#if DEBUG_TREE
cout
<<
"BEST SIBLING MATCHES! relocating..."
<<
endl
;
cout
<<
" parent -> "
<<*
parent
<<
endl
;
#endif
// add paired nodes to container
s
.
insert
(
node
);
s
.
insert
(
pair
);
// compute best pair for the parent
best
=
t
.
sibling
(
parent
);
if
(
best
!=
t
.
end
())
{
tuple_type
tuple
=
std
::
make_tuple
(
parent
,
best
,
cost
(
cost
(
*
parent
,
*
best
)));
q
.
push
(
tuple
);
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
#if DEBUG_TREE
cout
<<
" pushing new tuple "
<<
endl
;
cout
<<
" node -> "
<<*
node
<<
endl
;
cout
<<
" pair -> "
<<*
pair
<<
endl
;
cout
<<
" volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
}
}
// else enqueue new pair
else
{
if
(
best
!=
t
.
end
())
{
tuple_type
tuple
=
std
::
make_tuple
(
node
,
best
,
cost
(
cost
(
*
node
,
*
best
)));
q
.
push
(
tuple
);
iterator_type
node
=
std
::
get
<
0
>
(
tuple
);
iterator_type
pair
=
std
::
get
<
1
>
(
tuple
);
#if DEBUG_TREE
cout
<<
"BEST SIBLING DOES NOT MATCH!"
<<
endl
;
cout
<<
" pushing new tuple "
<<
endl
;
cout
<<
" node -> "
<<*
node
<<
endl
;
cout
<<
" pair -> "
<<*
pair
<<
endl
;
cout
<<
" volume -> "
<<
std
::
get
<
2
>
(
tuple
)
<<
endl
;
#endif
}
}
}
return
tp
;
}
template
<
class
tree_type
>
void
print_mathematica
(
tree_type
&
t
)
{
typedef
typename
tree_type
::
value_type
volume_type
;
int
d
=
volume_type
::
dim
();
cout
<<
std
::
fixed
;
cout
.
precision
(
2
);
if
(
d
==
2
)
cout
<<
"Graphics[{"
;
else
cout
<<
"Graphics3D[{"
;
for
(
typename
tree_type
::
const_leaf_iterator
it
=
t
.
leaves_begin
();
it
!=
t
.
leaves_end
();
++
it
)
cout
<<*
it
<<
", "
;
cout
<<
"}];"
<<
endl
;
}
template
<
typename
T
>
std
::
string
stringify
(
const
T
&
x
)
{
std
::
stringstream
o
;
if
(
!
(
o
<<
x
))
{
cout
<<
"*** ERROR *** Bad argument to stringity function"
<<
endl
;
exit
(
1
);
}
return
o
.
str
();
}
template
<
class
tree
>
void
export_video
(
tree
&
t
,
Real
duration
,
Real
min_opacity
,
std
::
string
pre
=
""
,
std
::
string
post
=
""
)
{
typedef
typename
tree
::
value_type
volume_type
;
typedef
typename
volume_type
::
aabb_type
aabb_type
;
typedef
typename
aabb_type
::
point_type
point_type
;
typedef
typename
point_type
::
value_type
value_type
;
typedef
typename
tree
::
iterator
iterator
;
int
d
=
volume_type
::
dim
();
cout
<<
std
::
fixed
;
cout
.
precision
(
2
);
std
::
tuple
<
size_t
,
size_t
,
size_t
>
h
=
t
.
height
();
typename
tree
::
iterator
it
=
t
.
begin
();
aabb_type
bb
=
it
->
bounding_box
();
// get bounding box
for
(;
it
!=
t
.
end
();
++
it
)
bb
+=
it
->
bounding_box
();
std
::
string
figs
;
int
H
=
std
::
get
<
2
>
(
h
);
int
k
=
0
;
for
(
int
l
=
H
;
l
>=
0
;
--
l
)
{
std
::
string
g
=
"g"
;
g
+=
stringify
(
k
);
++
k
;
// compute opacity for figure
Real
opacity
=
(
1
-
min_opacity
)
*
static_cast
<
double
>
(
l
)
/
H
+
min_opacity
;
if
(
d
==
2
)
cout
<<
g
<<
" = Graphics[{Opacity["
<<
stringify
(
opacity
)
<<
"],"
<<
pre
;
else
cout
<<
g
<<
" = Graphics3D[{Opacity["
<<
stringify
(
opacity
)
<<
"],"
<<
pre
;
t
.
execute_at_level
(
l
,
[](
iterator
it
){
cout
<<*
it
<<
", "
;});
figs
+=
figs
.
empty
()
?
g
:
(
','
+
g
);
cout
<<
"}];
\n
Show["
<<
figs
<<
", PlotRange-> {{"
;
const
point_type
&
m
=
bb
.
min
();
const
point_type
&
M
=
bb
.
max
();
for
(
int
i
=
0
;
i
<
d
;
++
i
)
{
value_type
l
=
0.05
*
(
M
[
i
]
-
m
[
i
]);
cout
<<
(
m
[
i
]
-
l
)
<<
','
<<
(
M
[
i
]
+
l
)
<<
(
i
<
d
-
1
?
"},{"
:
"}}"
);
}
cout
<<
post
<<
"];
\n
"
;
cout
<<
"Export[
\"
"
<<
g
<<
".png
\"
, %, ImageResolution -> 300];"
<<
endl
;
}
cout
<<
"files = Last /@ Sort[{Characters@#, #} & /@ FileNames[
\"
*.png
\"
]]"
<<
endl
;
cout
<<
"images = Map[Import, files];"
<<
endl
;
cout
<<
"Export[
\"
video.mov
\"
, images,
\"
FrameRate
\"
-> "
<<
stringify
(
static_cast
<
double
>
(
k
)
/
duration
)
<<
"];"
<<
endl
;
}
//// bottom up tree construction
//template <class volume_container>
//Tree<typename volume_container::value_type, Cost_functor<typename volume_container::value_type> >
//construct_tree_bottom_up2(const volume_container& volumes)
//{
//
// typedef typename volume_container::value_type volume_type;
//
// // online tree type definitions
// typedef Tree<volume_type, Cost_functor<volume_type> > tree_type;
//
// typedef Tree_node<volume_type> node_type;
// typedef typename tree_type::link_type link_type;
//
// size_t numVolumes = volumes.size();
// assert(numVolumes != 0);
//
// // allocate leafs of the tree
// link_type* leafs = new link_type[numVolumes];
//
// for (size_t i=0; i<numVolumes; ++i)
// leafs[i] = new node_type(volumes[i]);
//
// while (numVolumes > 1) {
//
// // find indices of the two "nearest" nodes, based on some criterion
// size_t ii,jj;
// Real merged = std::numeric_limits<Real>::infinity();
// for (size_t i=0; i<numVolumes; ++i)
// for (size_t j=i+1; j<numVolumes; ++j) {
//
// volume_type v = leafs[i]->value_ + leafs[j]->value_;
// if (v.measure() < merged) {
// ii = i;
// jj = j;
// merged = v.measure();
// }
// }
//
// volume_type v = leafs[ii]->value_ + leafs[jj]->value_;
// link_type parent = new node_type(v);
//
//#if DEBUG_TREE
// cout<<"best volume found -> "<<v<<endl;
// cout<<"measure -> "<<v.measure()<<endl;
// cout<<"parent -> "<<parent->value_<<endl;
// cout<<"left -> "<<leafs[ii]->value_<<endl;
// cout<<"right -> "<<leafs[jj]->value_<<endl;
//#endif
//
// parent->left_ = leafs[ii];
// parent->right_ = leafs[jj];
// leafs[ii]->parent_ = parent;
// leafs[jj]->parent_ = parent;
//
// // remove the two nodes from the active set and add in the new node.
// leafs[ii] = parent;
// leafs[jj] = leafs[numVolumes - 1];
// --numVolumes;
// }
//
// link_type root = leafs[0];
//
// tree_type t(root);
//
// delete leafs;
//
// return t;
//}
__END_AKANTU__
#endif
/* __AKANTU_TREE_HH__ */
Event Timeline
Log In to Comment