task we will be investigating is when a user clicks the mouse on the screen, determining which window and which part of the window they have clicked on. We will simplify this task by assuming every component of a window is a rectangle

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Assignment:  7

Overview

A windowing environment in computer science is the software that manages different parts of the display. In Windows 10 it is called the Desktop Window Manager and in macOS it is called Quartz Compositor.

Both of these environments implement the WIMP (windows, icons, menus, pointer) paradigm. An additional complexity that both of these operating systems support is allowing for multiple programs to run (or appear to run) at the same time, so the windowing system must manage multiple (possibly overlapping) windows.

Our Goal

The task we will be investigating is when a user clicks the mouse on the screen, determining which window and which part of the window they have clicked on. We will simplify this task by assuming every component of a window is a rectangle (which includes squares).

A Window can have many components such as a Menu Bar (a rectangular area) that can be further subdivided into Menu Items (which are smaller rectangles), a maximize button, a minimize button and a close button. We will use symbols to identify each of these components, e.g. ’Close, ’Maximize, and ’Minimize. We will use the symbol ’None to identify the region outside of a window; i.e. a rectangle is inside a window if and only if it is not associated with the label ’None.

Our Approach

We will start with some simple tasks (which will be in 1 dimension) and then work our way up to identifying which part of a window a user has clicked on (which will be in 2 dimensions).

1. An Augmented Binary Search Tree Dictionary (BSTD) [25% Correctness]

For this question we will be using the following data definition for a binary search tree dictionary which associates Natural numbers to Symbols.

(define-struct node (key val left right))

;; A Node is a (make-node Nat Sym BSTD BSTD)

;; requires: key > every key in left BSTD

;;  key < every key in right BSTD

;; A binary search tree dictionary (BSTD) is one of:

;; * empty

;; * Node

• A range search in a BSTD considers all the keys within a First create a function that produces the number of keys in the given range.

;; (range-count dict low high) produces the number of keys that

;; are >= low and < high in dict.

;; range-count: BSTD Nat Nat -> Nat

;; requires: low < high

 

For example in the BSTD illustrated in Figure 1, we would have the following.

(check-expect(range-count root1 20 30) 0)

(check-expect(range-count root1 10 12) 0)

(check-expect(range-count root1 10 13) 1)

(check-expect(range-count root1 12 13) 1)

(check-expect(range-count root1  4  8) 4)

(check-expect(range-count root1  0 15) 9)

• Now create a function that produces a list of all the corresponding values in that range ordered from the value with the lowest key to the value highest Hint: carefully consider the order that the recursion is done. You may reorder the sequence of recursive calls in the template as long as the base case is always first.

You may use the list function append for this question but you cannot use reverse.

;; (range-query dict low high) produces a list of values whose

;; keys in the dict are in the range >= low and < high. The

;; list of values produced are in ascending order by their key.

;; range-query: BSTD Nat Nat -> (listof Sym)

;; requires: low < high

For example, in the BSTD illustrated in Figure 1, we would have the following.

(check-expect(range-query root1 20 30) ’() )

(check-expect(range-query root1 10 12) ’() )

(check-expect(range-query root1 10 13) ’(y))

(check-expect(range-query root1 12 13) ’(y)) (check-expect(range-query root1         4  8) ’(g o o d))

(check-expect(range-query root1  0 15) ’(a b g o o d x y z))

The data definitions, the example in Figure 1, the function purposes and contracts will be provided in a starter file that you can download, called bstd.rkt. Add your code to this file and submit it as your solution to Q1.

2. Interval Trees (ITrees) [10% Correctness]

For this question we are breaking up the natural numbers into intervals. Each interval will have a symbol associated with it. Consuming a Natural number n, use a binary search tree to find which interval n is in and produce the symbol associated with that interval.

We will call this an ITree (for interval tree). The interior nodes will be called BNode (for boundary nodes). The leaves are symbols.

(define-struct bnode (val left right))

;; A BNode is a (make-bnode Nat ITree ITree)

;; requires: val > every val in left ITree

;;           val < every val in right ITree

;; An ITree (Interval Tree) is one of:

;; * a Sym (a leaf)

;; * a BNode (a boundary node)

 

Given a natural number n and a BNode with value v

• if n < v, then the interval occurs in the left subtree;

• if n ≤ v, then the interval occurs in the right

When a leaf is reached, produce the symbol that is associated with that leaf. For example, for the ITree in Figure 2, consuming

• 0, 1 or 2 will produce ’None

• 3, 4 or 5 will produce ’a

• 6 or 7 will produce ’b

• 8 will produce ’c

• 9, 10, ... will produce ’None

 

Create a function called it-lookup (which consumes an ITree and a Nat) that produces the symbol associated with the interval that the Nat is found in.

;; (it-lookup it n) produces the symbol from the it

;; that is associated with the interval that contains n

;; it-lookup: ITree Nat -> Sym

For example, for the ITree in Figure 2 the following should all pass.

(check-expect (it-lookup n6 0) ’None) (check-expect (it-lookup n6 2) ’None) (check-expect (it-lookup n6 3) ’a) (check-expect (it-lookup n6 5) ’a) (check-expect (it-lookup n6 6) ’b) (check-expect (it-lookup n6 7) ’b) (check-expect (it-lookup n6 8) ’c) (check-expect (it-lookup n6 9) ’None) (check-expect (it-lookup n6 10) ’None

The data definitions, example from Figure 2, function purposes and contracts will be provided in a starter file that you can download, called itree.rkt. Add your code to this file and submit it as your solution to Q2.

3. Finding Rectangles in a Window (RTree) [45% Correctness]

For this question we will be moving from 1 dimension to 2 dimensions, breaking up the XY plane (pixels on a screen) into different rectangles. Each rectangle will have a symbol

associated with it. Consuming a posn (position on the screen) you will use a binary search tree to find which rectangle the posn is in and what symbol is associated with that rectangle. We will call this an RTree (for rectangle tree).

There will be two types of interior nodes in this tree. One type is called an XNode which will divide the window into two parts, one with x values less than the XNode value (left) and one with x values greater than or equal to the XNode value (right). Similarly, a YNode will divide the window into two parts: those with y values less than the YNode value (below) and those with y values greater than or equal to the YNode value (above). Again, the leaves are symbols, which represent different rectangles that make up the window.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of