---
# System prepended metadata

title: Design

---

# Design 

## user interface
VR interface 
Program arrives on stdin, one per line, and response is printed to stdout

## inputs and outputs 
input: 2 floats, longitude and latitude
output: XML-format weather report OR string: "out of bounds"

## functional decomposition into modules
get from NWS
cache results from NWS
main method

## pseudo code for logic/algorithmic flow 
main 
```
init_nws
init cache 
inputLoop
    read from stdin
    extract lat, long
    IF incorrect, print "input error"
    ELSE 
        xml = fetch(lat, long)
        IF XML out of bounds
            print "out of bounds"
        ELSE
            print xml
```
nws
```
init_nws : init module

list_nws: return a list of weather stations and locations
    connect to NWS server
    download list of station code names
    parse the response 
    build and return array of station codes

fetch_nws: fetches xml for a given statino 
    connect to NWS server
    request for given station code
    download & return xml

end_nws: de-init module
```

cache
```
init_cache: init module
    make quadtree
    for each station in list_nws:
        xml = nws_fetch(station)
        add station to quadtree

fetch_cache:
use quadtree to find all points in each quadrant within a certain longitude and latitude
if no such quadrants found:
    return "out of bounds"
find distance between (x,y) and each station in quadtree

if the station is more than 100 miles away:
    return "out of bounds"
    
search the xml for the closest station
	if the xml metadata indicates NWS would likely have posted a newer observation by now:
	    nws_fetch(station) and replace our xml with fresh data
	
	return the xml for this station.
    


end_cache
    de-initialize module
```
## major data structures
cache of xml fetched from NWS
indexed by point (x,y) which correspodns to (latitude, longitude)

## performance 
we need high throughput and low latency 
for high throughput: 
* replicate the service 
* load balancer to split up requests between replicas 
* 
for low latency: 
* periodic cache-update strategy 
    * run as a background thread to update xml within the cache while foreground thread can still serve requests 

## testing plan
#### unit testing
main: Provide "stub" version of nws and cache modules with known behavior and require no network access

nws: Driver that invokes module functions. Explores erroneous and edge cases. 

cache: Driver that that invokes module functions. Explores erroenous and edge cases.

#### integration testing
The complete server will be tested as a system, by driving it with a series of requests on stdin. Two sets of inputs will be crafted, at least: one set of erroneous inputs and one set of valid inputs. The valid inputs shall push on common cases as well as 'edge' cases.

##### should fail
* out of bounds lat/long (either, or, both)
* invalid number of inputs (too many, too few)

##### should pass 
* valid long/lat inputs  

# Implementation 

## data structures
Primary data structure in cache module is implemented by a quadtree. Each tree node is either a leaf or a non-leaf, while every leaf contains one station. 

## control flow for overall flow 
```
nws_init()
cache_init()
while ( not EOF on stdin )
	read one line from stdin
	IF failed in extracting latitude,longitude from line
	THEN print "input error"
	ELSE
		xml = cache_fetch(latitude, longitude)
		IF xml == NULL
		THEN print "out of bounds"
		ELSE print xml
```

## control flow for each of the functions 
`cache_fetch` function: 
```
station_t* s = findStation(cache.tree, lat, long)
if s is not NULL 
    if s->timestamp is not recent
        s -> xml = nws_fetch(s->code)
    return s->xml
return null
```

function `findStation(tree, lat, long)`
```
if tree->station is not NULL
    if distance(tree->station, lat, long) <= 100 miles
        return tree->station
    else
        return null
else
    closest = NULL
    for each non NULL subquadrant q of tree
        if any location in q is <100 miles from (lat, long)
            s = findStation(q, lat, long)
            if closest is NULL || distance(s, lat, long) < distance(closest, lat, long)
                closest = s
    return closest
```

## detailed function prototypes
```
void nws_init(void);
char** nws_list(void); // returns array of string pointers, last one null
char* nws_fetch(const char* stationCode);
void nws_end();
```
```
void cache_init(void);
char* cache_fetch(const float lat, long);
void cache_end(void);
// local helper functions
station_t* findStation(quad_t* tree, const float lat, long);
```
## error handling and recovery 
Implementation uses defensive-programming to catch errors. In the worst case, service craches, and 'watchdog' script re-launches service.

## persistent storage (files, database, etc.)
All data lives in NWS, our server catches the data

## testing plan
test main by giving it fake input
test nws modules by using a driver to try all possible errors and also try to overload it with too many requests