implent class Trip Planner with locate$\_$all, plan$\_$route, and find$\_$nearby in dssl$2$ given these directions:

locate$-$all Takes a point$-$of$-$interest category; returns the positions of all points$-$

order you want, but the result should not include duplicates.

plan$-$route Takes a starting position $($latitude and longitude$)$ and the name of

a point$-$of$-$interest; returns a shortest path from the starting position to

the named point$-$of$-$interest. You can assume the starting position is at a

road segment endpoint. Returns the empty list if the destination does not

exist or is unreachable.

find$-$nearby Takes a starting position $($latitude and longitude$),$ a point$-$of$-$

interest category, and a limit n; returns the $($up to$)$ n points$-$of$-$interest

in the given category nearest the starting position. You can assume the

starting position is at a road segment endpoint. Resolve ties however you

want, and order points$-$of$-$interest within the list in any order you want.

#lang dssl$2$

# Final project: Trip Planner

import cons

### Basic Types ###

# $-$ Latitudes and longitudes are numbers:

let Lat? $=$ num?

let Lon? $=$ num?

# $-$ Point$-$of$-$interest categories and names are strings:

let Cat? $=$ str$?$

let Name? $=$ str$?$

# $-$ Raw positions are $2-$element vectors with a latitude and a longitude

let RawPos? $=$ TupC$[$Lat$?,$ Lon?$]$

# $-$ Raw road segments are $4-$element vectors with the latitude and

# longitude of their first endpoint, then the latitude and longitude

# of their second endpoint

let RawSeg? $=$ TupC$[$Lat$?,$ Lon?, Lat?, Lon?$]$

# $-$ Raw points$-$of$-$interest are $4-$element vectors with a latitude, a

# longitude, a point$-$of$-$interest category, and a name

let RawPOI? $=$ TupC$[$Lat$?,$ Lon?, Cat?, Name?$]$

### Contract Helpers ###

# ListC$[$T$]$ is a list of $`$T$`$s $($linear time$)$:

let ListC $=$ Cons.ListC

# List of unspecified element type $($constant time$)$:

let List? $=$ Cons.list?

interface TRIP$\_$PLANNER:

# Returns the positions of all the points$-$of$-$interest that belong to

# the given category.

def locate$\_$all$($

self,

dst$\_$cat: Cat? # point$-$of$-$interest category

$)->$ ListC$[$RawPos$?]$ # positions of the POIs

# Returns the shortest route, if any, from the given source position

# to the point$-$of$-$interest with the given name.

def plan$\_$route$($

self,

src$\_$lat: Lat?, # starting latitude

src$\_$lon: Lon?, # starting longitude

dst$\_$name: Name? # name of goal

$)->$ ListC$[$RawPos$?]$ # path to goal

# Finds no more than $`$n$`$ points$-$of$-$interest of the given category

# nearest to the source position.

def find$\_$nearby$($

self,

src$\_$lat: Lat?, # starting latitude

src$\_$lon: Lon?, # starting longitude

dst$\_$cat: Cat?, # point$-$of$-$interest category

n: nat? # maximum number of results

$)->$ ListC$[$RawPOI$?]$ # list of nearby POIs

class TripPlanner $($TRIP$\_$PLANNER$)$:

pass

# $^$ YOUR PART GOES HERE

def my$\_$first$\_$example$()$:

return TripPlanner$([[0,0,0,1],[0,0,1,0]],$

$[[0,0,$ "bar", "The Empty Bottle"$],$

$[0,1,$ "food", "Pierogi"$]])$

test $\text{'}$My first locate$\_$all test':

assert my$\_$first$\_$example$().$locate$\_$all$("$food$")==\backslash$

cons$([0,1],$ None$)$

test $\text{'}$My first plan$\_$route test':

assert my$\_$first$\_$example$().$plan$\_$route$(0,0,$ "Pierogi"$)==\backslash$

cons$([0,0],$ cons$([0,1],$ None$))$

test $\text{'}$My first find$\_$nearby test':

assert my$\_$first$\_$example$().$find$\_$nearby$(0,0,$ "food", $1)==\backslash$

cons$([0,1,$ "food", "Pierogi"$],$ None$)$