// /*-------------------------------------------------------------------*\
// | Concrete Template : Partial_Map_Kernel_5
// \*-------------------------------------------------------------------*/
#ifndef CT_PARTIAL_MAP_KERNEL_5
#define CT_PARTIAL_MAP_KERNEL_5
///---------------------------------------------------------------------
/// Global Context -----------------------------------------------------
///---------------------------------------------------------------------
#include "AT/Partial_Map/Kernel.h"
/*!
#include "AT/General/Is_Equal_To.h"
#include "AT/General/Are_In_Order.h"
!*/
#include "CT/Binary_Tree/Kernel_1a.h"
#include "CT/Binary_Tree/Symmetric_Compose_2.h"
///---------------------------------------------------------------------
/// Interface ----------------------------------------------------------
///---------------------------------------------------------------------
concrete_template <
concrete_instance class D_Item,
/*!
implements
abstract_instance General_Is_Equal_To <D_Item,
D_Item>
!*/
concrete_instance class R_Item,
concrete_instance utility_class D_Item_Are_In_Order,
/*!
implements
abstract_instance General_Are_In_Order <D_Item>
!*/
concrete_instance class D_R_Pair =
Record <
D_Item,
R_Item
>,
concrete_instance class Binary_Tree_Of_D_R_Pair =
Binary_Tree_Symmetric_Compose_2 <
D_R_Pair,
Binary_Tree_Kernel_1a <D_R_Pair>
>,
/*
Note: The details of this implementation are not shown
here because they are very similar to a course
laboratory assignment. Even so, you can write a program
that uses Partial_Map_Kernel_5 because the compiler has
access to the implementation. It is advantageous to use
Partial_Map_Kernel_5 because its worst-case run-time
performance is excellent as long as you leave this
default template parameter, Binary_Tree_Of_D_R_Pair,
alone so that it still refers to
Binary_Tree_Symmetric_Compose_2.
*/
concrete_instance class Rep =
Representation <
D_R_Pair,
Boolean,
Binary_Tree_Of_D_R_Pair
>
>
class Partial_Map_Kernel_5 :
implements
abstract_instance Partial_Map_Kernel <
D_Item,
R_Item
>,
encapsulates
concrete_instance Rep
{
private:
rep_field_name (Rep, 0, D_R_Pair, cache);
rep_field_name (Rep, 1, Boolean, cache_is_full);
rep_field_name (Rep, 2, Binary_Tree_Of_D_R_Pair,tree_of_pairs);
field_name (D_R_Pair, 0, D_Item, d_item);
field_name (D_R_Pair, 1, R_Item, r_item);
/*!
math subtype TREE_ITEM is (
d_item: D_Item,
r_item: R_Item
)
math operation ELEMENTS (
t: binary tree of TREE_ITEM
): set of TREE_ITEM
implicit definition
if t = empty_tree
then ELEMENTS (t) = empty_set
else there exists root: TREE_ITEM
left, right: binary tree of TREE_ITEM
(t = compose (root, left, right) and
ELEMENTS (t) = {root} union
ELEMENTS (left) union
ELEMENTS (right))
math operation D_OCCURS_COUNT (
t: binary tree of TREE_ITEM,
d: D_Item
): integer
implicit definition
if t = empty_tree
then D_OCCURS_COUNT (t, d) = 0
else there exists root: TREE_ITEM
left, right: binary tree of TREE_ITEM
(t = compose (root, left, right) and
(if d = root.d_item
then D_OCCURS_COUNT (t, d) =
1 + D_OCCURS_COUNT(left, d) +
D_OCCURS_COUNT (right, d)
else D_OCCURS_COUNT (t, d) =
D_OCCURS_COUNT (left,d) +
D_OCCURS_COUNT(right, d)))
math operation D_VALUES_ARE_UNIQUE (
t : binary tree of TREE_ITEM
): boolean
explicit definition
for all d: D_Item (D_OCCURS_COUNT (t, d) <= 1)
math operation IS_BST_ORDERED (
t: binary tree of TREE_ITEM
): boolean
implicit definition
if t = empty_tree
then IS_BST_ORDERED (t) = true
else there exists root: TREE_ITEM
left, right: binary tree of TREE_ITEM
(t = compose (root, left, right) and
IS_BST_ORDERED (t) =
IS_BST_ORDERED (left) and
IS_BST_ORDERED (right) and
for all d: D_Item
where (D_OCCURS_COUNT(left, d) > 0)
(not ARE_IN_ORDER(root.d_item, d)) and
for all d: D_Item
where (D_OCCURS_COUNT(right, d) > 0)
(ARE_IN_ORDER(root.d_item, d)))
math operation TREE_CONV (
t: binary tree of TREE_ITEM
): boolean
explicit definition
IS_BST_ORDERED (t) and
D_VALUES_ARE_UNIQUE (t)
math operation CONV (
c: TREE_ITEM,
c_full: boolean,
t: binary tree of TREE_ITEM
): boolean
explicit definition
TREE_CONV (t) and
(if c_full = true
then D_OCCURS_COUNT (t, c.d_item) = 0)
math operation CORR (
c: TREE_ITEM,
c_full: boolean,
t: binary tree of TREE_ITEM
): set of TREE_ITEM
implicit definition
if c_full = true
then CORR (c, c_full, t) = ELEMENTS (t) union {c}
else CORR (c, c_full, t) = ELEMENTS (t)
convention
CONV (self.cache, self.cache_is_full, self.tree_of_pairs)
correspondence
self = CORR (self.cache,
self.cache_is_full, self.tree_of_pairs)
!*/
// Students to add private operations as needed--these operations
// will have some type of binary tree among their arguments.
// Use local_procedure_body or local_function_body as the keyword
// to start each operation.
public:
standard_concrete_operations (Partial_Map_Kernel_5);
procedure Define (
consumes D_Item& d,
consumes R_Item& r
)
{
// Students to fill this in
}
procedure Undefine (
preserves D_Item& d,
produces D_Item& d_copy,
produces R_Item& r
)
{
// Students to fill this in
}
procedure Undefine_Any (
produces D_Item& d,
produces R_Item& r
)
{
// Students to fill this in
}
function Boolean Is_Defined (
preserves D_Item& d
)
{
// Students to fill this in
}
function R_Item& operator [] (
preserves D_Item& d
)
{
// Students to fill this in
}
function Integer Size ()
{
// Students to fill this in
}
};
#endif // CT_PARTIAL_MAP_KERNEL_5
Last modified: Wed Nov 14 09:36:56 EST 2007
