high-cities-sorted.taq

$ java -jar taq.jar high-cities-sorted

Running query high_cities in global scope 
high_cities(name=denver, altitude=5280)
high_cities(name=flagstaff, altitude=6970)
high_cities(name=addis ababa, altitude=8000)
high_cities(name=leadville, altitude=10200)

Description

high-cities-sorted.taq shows a non-trivial loop with 2 exit criteria. The loop performs an insert sort on a list of cities so they are ordered by ascending altitude. The start of the loop is marked by this comment

// Shuffle list until sort order restored

Early exit from the loop is triggered by sort order being achieved. Another exit occurs when there are no more cities to sort. The loop contains a shuffle step which moves a city one place down the list

high_cities[i + 1] = high_cities[i]

The last city is detected by loop variable ‘i’ decrementing to zero.


axiom list city (name, altitude)
{"bilene", 1718}
{"addis ababa", 8000}
{"denver", 5280}
{"flagstaff", 6970}
{"jacksonville", 8}
{"leadville", 10200}
{"madrid", 1305}
{"richmond",19}
{"spokane", 1909}
{"wichita", 1305}

// Performs insert sort on high_cities
flow insert_sort
{ export list<axiom> high_cities }
(
// Filter out cities below 5,000 feet
altitude? > 5000,
// Append next city from source
high_cities += axiom high_city { name, altitude },
// Top index
top = high_cities.size() - 1,
// Skip first time when only one item in list
?: top == 0,
// Save axiom to swap
inserted = high_cities[top--],
// i is the loop variable
i = top,
// Shuffle list until sort order restored
{
? altitude < high_cities[i]->altitude,
high_cities[i + 1] = high_cities[i],
? --i >= 0
},
// All done if inserted city was in sort order
?: i == top,
// Place latest city in correct position
high_cities[i + 1] = inserted
)

query high_cities (city : insert_sort)