Sort records with the library
In this lesson we use sorting to solve problems: we process events in time order, replace large values by small ranks, and find one value of the sorted order without sorting the rest. We begin by reviewing how to tell the library sort which order we want, using a list of records.
Consider the scoreboard of a small contest. Each row has a name, the number of problems solved and a time penalty:
name solved penaltyana 3 250bo 4 310cy 3 190di 4 280In the standings, the row with more problems solved comes first, and between two rows with the same count the lower penalty comes first.
In Python an order is described by a key, a function that is called once on each row, and the rows are sorted by the values it returns. Tuples are compared by their first elements, and by their second elements only when the first are equal, so a key that returns (-row[1], row[2]), the negated solved count and then the penalty, expresses both rules of the standings. The minus sign makes larger counts come first.
The scoreboard sorted in two ways
rows = [("ana", 3, 250), ("bo", 4, 310), ("cy", 3, 190), ("di", 4, 280)]
by_solved = sorted(rows, key=lambda row: row[1])
print([row[0] for row in by_solved])
standings = sorted(rows, key=lambda row: (-row[1], row[2]))
print([row[0] for row in standings])Prints ['ana', 'cy', 'bo', 'di'], then ['di', 'bo', 'cy', 'ana'].
The first sort uses the solved count alone, so ana ties with cy and bo with di. Python's sort is stable, which means that rows with equal keys keep their input order: ana stays ahead of cy, and bo ahead of di.
In the standings the penalty decides both ties: di is ahead of bo, and cy ahead of ana.
A library sort makes about comparisons, which is about for 200,000 rows. Roughly simple steps fit in one second, so a solution can sort its input first at little cost, and most solutions in this lesson begin that way.
Deeper read: library sorts and counting sort
Python's sort is a merge sort that first looks for stretches of the input that are already in order and merges those. On a list that is already sorted it finds a single stretch and makes only comparisons.
Sorts like these are comparison sorts: everything they learn about the values comes from asking whether one goes before another. For every comparison sort there are inputs of values that force about comparisons. To see why, fix the sort and the number , and give it different values. Its first comparison is always between the same two positions, and it has two possible outcomes. Which pair the sort compares next may depend on that outcome, the third comparison on the first two, and so on. So the possible runs of the sort form a binary tree, with a comparison at each branching and a finished run at each leaf.
The values can arrive in different orders, and each order needs a different rearrangement to become sorted. If two orders reached the same leaf, they would get the same rearrangement and one of them would come out unsorted, so the tree has at least leaves. A binary tree with no leaf deeper than levels has at most leaves, so some leaf lies at least levels down, and the input that leads there costs that many comparisons. For 200,000 values is about , close to .
When the values are small whole numbers, we can sort without comparing any two of them. Counting sort keeps one counter for each possible value and counts how often each value occurs. For [2, 0, 2, 1], with values from 0 to 2, the counters end as [1, 1, 2]: one 0, one 1 and two 2s. Writing each value as many times as its counter says gives [0, 1, 2, 2].
For values between 0 and this takes steps to count and counters to read, so time. That can be far less than without contradicting the argument above, because counting sort never compares two values: the step count[x] += 1 picks one of counters at once, where a comparison has only two outcomes. It works only while is small enough for the counters to fit in memory. Values up to would need a billion counters. Coordinate compression, later in this lesson, makes such values small.
Order items by comparing two at a time
A key gives every item a value of its own, and the order follows from those values. For some orders such a value is hard to find, and it is easier to compare two items directly. The next problem is an example.
You get a list of nonnegative integers. Write all of them side by side in some order so that the digits form the largest possible number, and return that number as a string.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [10,2]
Output
"210"
Sample 2 · Input
nums = [3,30,34,5,9]
Output
"9534330"
The answer to the second sample uses the order 9, 5, 34, 3, 30. Sorting the numbers from largest to smallest does not find it: that order is 34, 30, 9, 5, 3, which gives 3430953. Sorting them as text from largest to smallest compares the first digits first and gives 9, 5, 34, 30, 3, which is 9534303. This is correct except for the last two numbers. As text "30" is larger than "3", but 3 has to come before 30.
Two numbers can be written side by side in only two ways, so we can try both. "3" + "30" is "330" and "30" + "3" is "303". The first is larger, so 3 goes before 30. The same test works for any two numbers and written as strings: goes before when is larger than . The two joined strings have the same length, so comparing them as text is the same as comparing them as numbers.
A function that takes two items and says which of them goes first is a comparator. Python's sort accepts only a key, and functools.cmp_to_key turns a comparator into one. The comparator returns a negative number when a goes first, a positive number when b goes first, and 0 when the order of the two makes no difference.
Largest Number in code
def largest_number(nums):
parts = [str(x) for x in nums]
def order(a, b):
if a + b > b + a:
return -1
if a + b < b + a:
return 1
return 0
parts.sort(key=cmp_to_key(order))
if parts[0] == "0":
return "0"
return "".join(parts)
print(largest_number([10, 2]))
print(largest_number([3, 30, 34, 5, 9]))Prints 210 and 9534330, the two samples.
The check on parts[0] handles an input of only zeros. After the sort, the first string is "0" only when every number is 0, because any other number would be placed ahead of the zeros, and the answer is then "0" and not "00".
Rules for a comparator
A sort compares only some pairs of items and works out the rest of the order from the answers. This is correct only if the comparator behaves like < on numbers, and in particular follows two rules. First, the comparator never puts before and also before . For two equal items it must say that neither goes first. Second, if it puts before and before , it also puts before .
A key cannot break these rules, because the sort compares the ordinary values that the key returns. A comparator written by hand can, and it can also get its return values wrong. Returning a + b > b + a is such a mistake. cmp_to_key takes only a negative result to mean that a goes first, and True and False are 1 and 0. This comparator never says that a goes first, so the sort treats every pair as tied and leaves the list in its input order: ["10", "2"] gives "102".
The joining test follows both rules, and the Deeper read below shows why. The sorted order gives the largest number, because in any order that is not sorted by the test, some two neighbours fail it: comes just before although is larger than . Swapping them makes the number larger, because only the digits of that pair change, from to , which has the same length.
Deeper read: the joining test and the second rule
Write for the number of digits of . Joining and then gives the number , so goes first when . Moving the terms with to the left and the terms with to the right, and then dividing by the two positive factors, gives
So every number has a fixed value of its own, , and the test sorts by that value from largest to smallest. Sorting by a fixed value always behaves like > on numbers. In the second sample, 34 has the value , 3 has and 30 has , which is the order 34, 3, 30.
Replay events in sorted order
So far the sorted order itself was the answer. From here on, we sort as the first step of a solution. Our first problem is about customers who come and go at different times.
A restaurant had customers. You know when each one arrived and when each one left. Find the largest number of customers that were in the restaurant at the same moment.
The first input line holds . Each of the next lines holds a customer's arrival time and leaving time . All arrival and leaving times are distinct. Print one integer: the largest number of customers present at once.
Constraints
Sample · Input
3 5 8 2 4 3 9
Output
2
In the sample the visits are (5, 8), (2, 4) and (3, 9). Let us number the customers 0, 1 and 2 in this order. Customers 1 and 2 are both inside between times 3 and 4, and customers 0 and 2 between times 5 and 8. Customers 0 and 1 are never inside together, so the answer is 2.
The number of customers inside can reach a new maximum only when somebody arrives. So a simple solution takes each arrival time and counts the customers who are inside at that moment. There are arrival times and customers to check at each. For this is
which takes about 400 seconds at steps a second. Keeping a counter for every unit of time, the number of customers inside at that time, is no better, because times go up to and the list would need a billion counters.
However, the number of customers inside changes only when somebody arrives or leaves, and each time it changes by 1. We call each arrival and each departure an event. We make a list of the events and sort it by time. Then we go through the list once and keep a count: an arrival adds 1 and a departure subtracts 1. The largest value of the count is the answer.
The six events of the sample
| Time | What happens | Change | Inside |
|---|---|---|---|
| 2 | customer 1 arrives | 1 | |
| 3 | customer 2 arrives | 2 | |
| 4 | customer 1 leaves | 1 | |
| 5 | customer 0 arrives | 2 | |
| 8 | customer 0 leaves | 1 | |
| 9 | customer 2 leaves | 0 |
The count reaches 2 twice and never 3. Processing events in sorted order like this is known as an event sweep. The sweep skips the times between two events, where the count stays the same.
The sweep in code
In the program an event is a pair (time, change), where the change is or . Pairs are compared by their first elements, so sorting the list puts the events in time order.
def maximum_guests(visits):
events = []
for arrive, leave in visits:
events.append((arrive, 1))
events.append((leave, -1))
events.sort()
current = 0
best = 0
for time, change in events:
current += change
best = max(best, current)
return best
data = sys.stdin.read().split()
n = int(data[0])
visits = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]
print(maximum_guests(visits))On the sample input the program prints 2.
For 200,000 customers the program sorts 400,000 events, which takes about
and then reads the sorted list once. The time is , and the event list is the only extra memory.
Events at the same time
In the restaurant problem all times are different. When two events have the same time, the sort also decides which of them is processed first, and the answer may depend on it. Consider five visits to a café, in minutes after opening:
guest 0 1 2 3 4arrives 2 6 1 4 3leaves 6 9 4 7 5Just before minute 4, guests 0, 2 and 4 are inside. At minute 4, guest 2 leaves and guest 3 arrives. If the sweep processes the departure first, the count goes from 3 to 2 and back to 3. If it processes the arrival first, the count goes from 3 to 4, and the sweep reports four guests at once, although guest 2 had left when guest 3 arrived.
The correct order depends on what the times mean. Here a guest who leaves at minute 4 is no longer inside at minute 4, so departures come first. The sweep program already orders them this way: two pairs with the same time are compared by their second elements, and is smaller than .
If a guest who leaves at minute 4 still counted as inside at minute 4, arrivals would have to come first. In that case we store an arrival as (time, 0) and a departure as (time, 1), and add or subtract 1 according to the second element.
Step through the café log
The widget processes the ten events of the café log. When Departures first at equal times is switched off, the count is 4 at minute 4 and the final answer is wrong. The other switch, Compress coordinates, draws the events on ranks, which the next part explains.
Worked example
Run the sweep on other visits
The trace runs the sweep, with departures first, on other lists of visits.
5 visits become 10 events: +1 at each arrival, -1 at each departure. Sort them by time; at equal times the departure comes first, because a guest leaving at t is gone before a guest arriving at t sits down.
Change the example input
Current result: 3
Coordinate compression
Some algorithms need a list indexed by value, such as one counter for each time in the restaurant problem. With times up to that list has a billion entries, although 200,000 customers have at most 400,000 different times.
We can make the values small by renumbering them. We sort the distinct values and replace each value by its position in the sorted list, its rank. This technique is coordinate compression. For example, the values 7, 42, 500 and get the ranks 1, 2, 3 and 4:
The largest rank is the number of distinct values, so ranks can be used as list indices. Ranks also keep the order of the values: a smaller value has a smaller rank, and equal values have the same rank. So an algorithm that only compares values gives the same result on the ranks. Ranks do not keep distances, since 500 and are one rank apart. If the original values are needed later, we keep the sorted list of distinct values, where the value with rank is at index .
Compute the ranks
In the following problem the ranks themselves are the answer:
Replace every value in an array with its rank. The smallest value gets rank 1, equal values get the same rank, and ranks are as small as possible: a larger value gets the next rank up.
Constraints
-
arr.length -
arr[i]
Sample 1 · Input
arr = [40,10,20,30]
Output
[4,1,2,3]
Sample 2 · Input
arr = [100,100,100]
Output
[1,1,1]
Sample 3 · Input
arr = [37,12,28,9,100,56,80,5,12]
Output
[5,3,4,2,8,6,7,1,3]
In the third sample the distinct values in sorted order are 5, 9, 12, 28, 37, 56, 80 and 100. So 5 gets rank 1, both 12s get rank 3, and 100 gets rank 8.
The program removes the repeated values with set, sorts the distinct values, and stores each value's index plus 1 in a dictionary. Then it looks up every value of the input.
Rank transform in code
def array_rank_transform(arr):
xs = sorted(set(arr))
rank = {v: i + 1 for i, v in enumerate(xs)}
return [rank[v] for v in arr]
print(array_rank_transform([37, 12, 28, 9, 100, 56, 80, 5, 12]))Prints the third sample's answer.
The sort is the only step that takes more than linear time: it makes about comparisons for values. After it the program does one lookup per value.
Find one value of the sorted order
In a sorted list the smallest value is first, the largest is last, and the th smallest is at index . Some problems ask for only one of these values.
You get an array of integers and a number . Return the th largest value in sorted order. Repeats count separately, so in [5, 5, 4] the second largest is 5. The problem asks whether you can solve it without sorting.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [3,2,1,5,6,4], k = 2
Output
5
Sample 2 · Input
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output
4
The second sample in sorted order is [1, 2, 2, 3, 3, 4, 5, 5, 6]. Its 4th largest value is 4, which is also its 6th smallest. In general the th largest of values is the th smallest, so from now on we look for the th smallest.
Sorting the array and reading one index takes time, about comparisons for values, which is fast enough here. But the sort also orders all the other values, and the problem asks whether we can do without that. Finding the th smallest value without sorting the rest is known as selection, and it can be done in time on average.
Split around a pivot and keep one group
The algorithm is called quickselect. We pick one value of the list, the pivot, and split the list into three groups: the values smaller than the pivot, the values equal to it, and the values larger than it. In sorted order the three groups follow one another, so their sizes show which group contains the th smallest value:
- If is at most the size of the smaller group, the answer is the th smallest value of that group.
- Otherwise, if is at most the size of the smaller and equal groups together, the answer is the pivot.
- Otherwise the answer is in the larger group. We subtract the size of the other two groups from and look for the th smallest value there.
In the first and third cases we repeat the same step on that group alone.
For example, let us find the 6th smallest value of [3, 2, 3, 1, 2, 4, 5, 5, 6] with the pivot 3. The smaller group is [2, 1, 2], two values equal 3, and the larger group is [4, 5, 5, 6]. The three smallest values are in the smaller group and the 4th and 5th smallest are the two 3s, so the 6th smallest is the smallest value of the larger group. With the pivot 5, that group splits into [4], two 5s and [6]. Its smallest value is in [4], so the answer is 4.
Quickselect with a random pivot
def kth_smallest(nums, k):
while True:
pivot = random.choice(nums)
lower = [x for x in nums if x < pivot]
higher = [x for x in nums if x > pivot]
same = len(nums) - len(lower) - len(higher)
if k <= len(lower):
nums = lower
elif k <= len(lower) + same:
return pivot
else:
k -= len(lower) + same
nums = higher
def find_kth_largest(nums, k):
return kth_smallest(nums, len(nums) - k + 1)
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))Prints 5 and 4, the two samples.
Any pivot gives the right answer, because each round keeps the group that holds it. The pivots decide only the speed. The work of a round is proportional to the length of its list, so the running time is proportional to the total length of the lists. If every pivot is near the middle of the sorted order, the group we keep is about half as long as the list, and the lengths add up to less than :
The worst case is a pivot at the edge. If every pivot is the smallest value of its list and we are looking for the largest value, each round removes only the pivot, and the lengths add up to
A fixed rule, such as always taking the first value as the pivot, meets this case on a sorted list. The program above chooses its pivots at random instead. Then no input is bad every time, because the pivots are drawn while the program runs, after the input is fixed.
A pivot from the middle half of the sorted order is good enough: it leaves neither the smaller nor the larger group with more than three quarters of the list. If every round did that, the lengths would add up to less than :
Half of the values lie in the middle half, so a random pivot does this every second round on average. Each shrink to three quarters then takes two rounds on average, which at most doubles the sum above, to below . In 200 runs that looked for the middle of 100,000 different values, it averaged about .
Partition inside the array
The program above copies values into new lists in every round. The split can also be made inside the array by swapping values, with no extra list. This in-place split is a partition. It makes two groups: values that are at most the pivot go to the left, larger values go to the right, and the pivot ends up between them.
The partition comes from quicksort, which, unlike merge sort, does its work before its recursive calls. It partitions the array and then sorts the two sides the same way, and the sorted sides need no merging, because every value on the left is already at most every value on the right.
The partition uses the last value of the range as the pivot and reads the other values from left to right with an index read. A second index, write, is the position just after the left group. Whenever the value at read is at most the pivot, it is swapped to position write, and write moves one step to the right. Finally the pivot is swapped to position write. Now everything to its left is at most the pivot and everything to its right is larger, so the pivot is at its position in sorted order.
The three regions of a partition
Consider the first partition of [5, 2, 8, 4, 1, 9, 3, 7], where the pivot is 7. After six reads, the values before write are at most 7, the values from write up to just before read are larger, and the value at read has not been read yet.
write. The final swap puts the pivot at position 5.Every read keeps these three regions. A value larger than the pivot stays where it is, and the region of larger values grows by one. A value at most the pivot is swapped with the first of the larger values, the one at write, so the region of small values grows by one and the region of larger values moves one step to the right. When every value has been read, the last swap puts the pivot between the two regions.
Step through quickselect with this partition
The widget finds the 4th smallest of the same eight values, which belongs at position 3. It marks write as i and read as j. After each partition it discards the pivot and the side that cannot contain position 3, and it finds the answer, 4, after three partitions and comparisons.
Deeper read: quickselect in place
In the code, quickselect maintains the range from left to right that contains position , and partition returns the position of the pivot.
def partition(nums, left, right):
pivot = nums[right]
write = left
for read in range(left, right):
if nums[read] <= pivot:
nums[write], nums[read] = nums[read], nums[write]
write += 1
nums[write], nums[right] = nums[right], nums[write]
return write
def quickselect(nums, k):
if not 1 <= k <= len(nums):
raise ValueError("k must be between 1 and len(nums)")
target = k - 1
left, right = 0, len(nums) - 1
while left <= right:
pivot_index = partition(nums, left, right)
if pivot_index == target:
return nums[pivot_index]
if target < pivot_index:
right = pivot_index - 1
else:
left = pivot_index + 1
print(quickselect([5, 2, 8, 4, 1, 9, 3, 7], 4))Prints 4, the widget's answer.
Each round removes at least the pivot from the range, so the loop ends. On a sorted list, however, the last value is the largest, so a partition removes only the pivot, and finding the smallest value takes partitions before the range is down to that one value. This is the worst case of the previous part. Swapping a random value into the last position before each partition avoids it. The listing follows the widget and leaves that swap out.
A list of equal values is slow even with random pivots, because every value is at most the pivot and the pivot always lands at the right end. Finding the smallest of 100,000 equal values takes 4,999,950,000 comparisons. The limits of Kth Largest allow such a list, and the three-group program finishes it in one round.
For this reason the three-group program is the one to submit.
Count pairs during a merge
Quickselect uses one step of a sorting algorithm for a new purpose. The merge step of merge sort can be used in the same way: while it merges two sorted halves, it can count pairs of values that are in the wrong order, as in the following problem.
You get an array of integers. For each position, count how many values to its right are smaller than the value there, and return the counts as an array.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [5,2,6,1]
Output
[2,1,1,0]
Sample 2 · Input
nums = [-1]
Output
[0]
Sample 3 · Input
nums = [-1,-1]
Output
[0,0]
In the first sample, 2 and 1 are to the right of 5 and smaller, so the count for 5 is 2. Checking every pair of positions is too slow, because 100,000 positions form 4,999,950,000 pairs.
Merge sort can count these pairs while it sorts. Take two positions . Each call splits its positions into a left half and a right half. As long as and fall in the same half, they go down to the same recursive call, and the first call that puts them in different halves has in its left half and in its right half. So every pair is separated by exactly one call, and that call can count it.
When a call merges, a value from the right half is placed before a value from the left half only if it is smaller, and because both halves are sorted, it goes ahead of every left-half value it is smaller than. So at the moment the merge places a value from the left half, the right-half values already placed are exactly the right-half values smaller than it, all from positions to its right, and we add their number to its count.
Merge sort on the first sample
Deeper read: the counting merge in code
Consider the top call in the figure. Its left half holds the values 2 and 5 (positions 1 and 0) and its right half the values 1 and 6 (positions 3 and 2), and each half is sorted. The merge places 1 first. Then it places 2, when one right-half value has been placed, so the count of position 1 grows by 1. Then it places 5, still with one right-half value placed, so the count of position 0 grows by 1. The 6 is placed last. The two smaller calls had already added 1 for the pair and 1 for the pair , so the counts are [2, 1, 1, 0].
The counts belong to positions of the input, but sorting moves the values. For this reason the program sorts a list of positions, compares two positions by their values, and adds to counts[i] when it places position i.
def count_smaller(nums):
counts = [0] * len(nums)
def sort_positions(idx):
if len(idx) <= 1:
return idx
mid = len(idx) // 2
left = sort_positions(idx[:mid])
right = sort_positions(idx[mid:])
out = []
j = 0
for i in left:
while j < len(right) and nums[right[j]] < nums[i]:
out.append(right[j])
j += 1
counts[i] += j
out.append(i)
out.extend(right[j:])
return out
sort_positions(list(range(len(nums))))
return counts
print(count_smaller([5, 2, 6, 1]))
print(count_smaller([-1, -1]))Prints [2, 1, 1, 0] and [0, 0].
The inner loop places a right-half position first only while its value is strictly smaller. With <= an equal value would be counted too, and the third sample [-1, -1] would give [1, 0]. The running time is that of merge sort, about steps for 100,000 values.
Common mistakes with sorting
Processing arrivals before departures at the same time.
- Where it breaks
- For the visits (1, 3) and (3, 5), where a guest who leaves at time 3 is no longer inside at time 3, the count goes 1, 2, 1. The sweep answers 2, although the two guests never meet.
- The fix
- Put departures first at equal times. The pairs
(time, -1)and(time, 1)sort that way.
Compressing without removing repeated values.
- Where it breaks
- Numbering the sorted list
[5, 5, 9]by index plus 1 gives 5 the ranks 1 and 2, and 9 the rank 3. A dictionary keeps the later rank, so[5, 5, 9]becomes[2, 2, 3]and not[1, 1, 2]. - The fix
- Remove the repeated values before numbering.
Recall A problem gives 100,000 scores and asks 1,000 times for the kth smallest score, each time with a different k. Should each question be answered with quickselect?
No. For a value of near the middle, one run of quickselect goes through about values, which is 340,000 here, so 1,000 such runs go through about 340 million. Sorting once takes about comparisons, and after that every question is answered by reading one index.
Further reading
- Python documentationSorting Techniques(opens in a new tab)
Key functions, the
operatorhelpers, stability and sorting by several keys in passes, comparison functions withcmp_to_key, and partial sorts. - USACO Guide, SilverCustom Comparators and Coordinate Compression(opens in a new tab)
Key functions and comparators in C++, Java and Python, descending and multi-criteria sorts, and coordinate compression with practice problems.
- cppreferenceC++ named requirements: Compare(opens in a new tab)
The strict weak ordering that
std::sortassumes: irreflexive, transitive, and with ties that behave like equality. A<=comparator breaks the first rule. - cp-algorithmsKth order statistic in O(N)(opens in a new tab)
A non-recursive quickselect in C++, with a note on why a random pivot or a shuffle is needed for the expected linear time.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Chapter 3: Sorting(opens in a new tab)
Pages 25 to 34: bubble sort and inversions, merge sort, why sorting by comparisons needs comparisons, counting sort, C++ comparison functions, then binary search.
- OI Wiki, in Chinese快速排序 (Quicksort)(opens in a new tab)
Three-way partitioning, introsort, linear-time selection of the th smallest, and the median-of-medians method with its proof.
- Jeff Erickson (PDF)Algorithms, Chapter 1: Recursion(opens in a new tab)
Mergesort and quicksort with their correctness proofs and recurrences, then quickselect, why good pivots give linear time, and the median-of-medians pivot. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- Pat MorinOpen Data Structures, Chapter 11: Sorting Algorithms(opens in a new tab)
Merge-sort, quicksort and heap-sort, the comparison-tree argument that every comparison sort needs about comparisons, and counting sort and radix sort, which escape that bound by indexing an array. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.