# 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