[an error occurred while processing this directive]
[an error occurred while processing this directive]

Quadtree Node

Requirements

In this sub-project, you will implement two classes:

  1. Quadtrees: Quadtree, and
  2. Quadtree Nodes: Quadtree_nod.

This quadtree node is used by the quadtree class to store pairs of elements. There are four sub-trees which are denoted as north-west, north-east, south-west, and south-east. In a binary search tree, all values less than the current element are stored in the left sub-tree while all values greater than the current element are stored in the right sub-tree. This is a generalization of that concept; however, now we are storing pairs of numbers and we must be more careful:

  • Given a pair (x, y) and the current pair (x0, y0), if x ≥ x0, the pair (x, y) must be stored in one of the east sub-trees; otherwise the pair (x, y) must be stored in one of the west sub-trees.
  • Given a pair (x, y) and the current pair (x0, y0), if y ≥ y0, the pair (x, y) must be stored in one of the north sub-trees; otherwise the pair (x, y) must be stored in one of the south sub-trees.

For example, if the root node is (5, 5); pairs such as (7, 7), (5, 7), and (7, 5) must be stored in the north-east sub-tree, pairs such as (3, 7) and (3, 5) are stored in the north-west sub-tree, pairs such as (7, 3) and (5, 3) are stored in the south-east sub-tree, and pairs such as (3, 3) are stored in the south-east sub-tree. This is shown in Figure 1 where the axes are grouped according to where the values are stored.

Figure 1. Ordering of which sub-trees values are stored in.

None of the descendants of this node will have the same pair (x, y) stored in this node.

Class Specification

UML Class Diagram

Quadtree_node
- x_value:Type
- y_value:Type
- north_west:Quadtree_node
- north_east:Quadtree_node
- south_west:Quadtree_node
- south_east:Quadtree_node
+ create():Quadtree_node
+ retrieve_x():Type
+ retrieve_y():Type
+ nw():Quadtree_node
+ ne():Quadtree_node
+ sw():Quadtree_node
+ se():Quadtree_node
+ min_x():Type
+ min_y():Type
+ max_x():Type
+ max_y():Type
+ sum_x():Type
+ sum_y():Type
+ member( in x:Type, in y:Type ):Boolean
+ insert( in x:Type, in y:Type ):Boolean
+ clear()
+ destroy()


Description

This class stores a pair of values (x, y) and pointers to four possible sub-trees. The values stored in the sub-trees satisfy the requirements stated above. The value of n in the run times refers to the number of descendants of the current node.

Member Variables

The six member variables are:

  • Two Types, referred to as the x and y values of the node, and
  • Four pointers to Quadtree_nodes, which are referred to as north-west, north-east, south-west and south-east.

Member Functions

Constructors

Quadtree_node( Type const &x, Type const &y )

This constructor sets the x and y values to the arguments, respectively, and sets all the sub-trees to 0. (O(1))

Destructor

The destructor must call clear on the four sub-trees and delete those nodes. (O(n))

Accessors

This class has thirteen accessors:

Type retrieve_x() const;
Type retrieve_y() const;
Returns the x and y values of the current node, respectively. (O(1))
Quadtree_node *nw() const
Quadtree_node *ne() const;
Quadtree_node *sw() const;
Quadtree_node *se() const;
Returns the north-west, north-east, south-west, and south-east pointers, respectively. (O(1))
Type min_x() const;
Type min_y() const;
Type max_x() const;
Type max_y() const;
Returns the minimum-or-maximum x-or-y value within the quadtree. (O(n) but O(√n) if balanced)
Type sum_x() const;
Type sum_y() const;
Returns the sum of the x and y values within the quadtree, respectively (O(n))
bool member( Type const &x, Type const &y ) const;
Returns true if the pair (x,y) is stored in one of the nodes of the quadtree and false otherwise. (O(n) but O(ln(n)) if balanced)

NOTE: the O(√n) run times are the natural run times of a balanced quadtree: the minimum x value is the minimum x value of the current node and the minimum x values of the two west sub trees. You do not have to implement special code to achieve the required run time.

Mutators

This class has two mutators:

bool insert( Type const &x, Type const &y );
If the pair (x,y) equals the pair stored in the current node, return false; otherwise, insert the pair into the appropriate sub-tree either by creating a new node and returning true or recursively calling insert and returning that call's return value. (O(n) but O(ln(n)) if balanced)
void clear();
On any non-zero sub-tree, call clear, and then delete that node. (O(n))
[an error occurred while processing this directive]