Help with arrays and sorting


#1

I have a situation that my rudimentary JS skills haven’t been able to solve. I have drafts of addresses in this format:

Street Name
1234 Optional Notes...
1248
1274
1301
1344 Optional Notes...

Another Street Name
13838
13842
[...]

What I’d like to be able to do is create an action that will let me sort the addresses between the street names, and as an option, to sort even and odd separately. I can sort the numbers easily enough, but I can’t quite figure out how to keep the structure in place with the street name headings. Any ideas?

Thanks!
Nick


#2

This script is not optimised at all, but it works.

var contents = draft.content.split("\n\n");
var newContent = "";

//ask you to choose your sort preference
var p = Prompt.create();
p.title = "Sort preference";
p.addButton("Sort low to high");
p.addButton("Seperate odd and even");
var didSelect = p.show();
//if you pressed cancel, stop
if (didSelect === false) {
	context.cancel("User cancelled action");
}

//go through the street groupings
for (var street in contents) {
	var details = contents[street].split("\n");
	//add the street name to the newContent and remove it from the array
	newContent += details[0] + "\n";
	delete details[0];
	//if you wanted to sort odd and even seperately do that, otherwise just ascending order
	if (p.buttonPressed == "Seperate odd and even") {
		details.sort(function(a, b) {
		//look specifically for the numbers here
     		return a.match(/[0-9]+/g) % 2 - b.match(/[0-9]+/g) % 2 || a - b;
		});
	} else {
		details.sort();	
	}
	newContent += details.join("\n");
	newContent += "\n";
}

editor.setText(newContent);

If you have any questions then let me know! Hopefully the comments will help you figure it out though :slight_smile:


#3

That describes 98% of my code :slight_smile:


#4

For sorting on multiple keys (primary sort, secondary sort, etc), (for example, sorting the numbers first by their evenness, and then by their numeric order), you can get a combined sort function for Array.sort() by using:

// mappendComparing :: [(a -> b)] -> (a -> a -> Ordering)
const mappendComparing = fs =>
    (x, y) => fs.reduce(
        (ordr, f) => ordr || compare(f(x), f(y)),
        0
    );

The compare(f(x), f(y)) part uses a particular function to compare two houses etc, so for a simple sort on house numbers

houses.sort(comparing(houseNumber))

where houseNumber is extracting the numeric rather than string value of the number, in case some numbers have many digits, and others fewer. (For street numbers, we probably want a numeric order rather than a lexical order – the default xs.sort() applied to numbers as strings might complicate the life of a travelling salesman):

['1','2', '10', '20', '100', '200', '1000', '2000'].sort()

--> [
  "1",
  "10",
  "100",
  "1000",
  "2",
  "20",
  "200",
  "2000"
]

So we derive the numeric value rather than the lexical number string:

const
    rgxNum = /(^\d+)/,
    houseNumber = s => {
        const m = rgxNum.exec(s);
        return Boolean(m) ? parseInt(m[1], 10) : 0;
    };

mappendComparing takes a list of functions that just extract some property from an item (like houseNumber above, or even below)

// even :: Int -> Bool
const even = n => n % 2 === 0;

and builds a composite function which compares the values of any two items, using each of the supplied property-extraction functions in turn (e.g. on even, then on houseNumber) until one of the comparisons results in something other than 0 (i.e. LT (-1) or GT (+1), rather than EQ (0).

So testing the basic pattern with randomly generated addresses, and

  1. Sorting the streets AZ by their names
  2. Sorting the houses in each street on first on evenness of number (primary sort key), and then on numeric (non-string) value of number (secondary sort key):
(() => {
    'use strict';

    /* 1. Generating a random list of streets and numbers, and then
       2. SORTING:
            Streets A-Z by name,
            houses first by evenness of number,
            and then by numeric (rather than string) order of number.
    */
    const main = () => {

        // SAMPLE TEST DATA
        const strList = randomStreetList();

        const
            rgxNum = /(^\d+)/,
            houseNumber = s => {
                const m = rgxNum.exec(s);
                return Boolean(m) ? parseInt(m[1], 10) : 0;
            };
        return strList.split('\n\n')
            .map(strLines => {
                const xs = strLines.split('\n');
                return xs[0] + '\n' + xs.slice(1)
                    .sort(
                        mappendComparing(
                            [ // Primary sort on evenness of house number,
                                // secondary on numeric value of house number
                                // (not on string value – lengths may differ)
                                x => even(houseNumber(x)),
                                houseNumber
                            ]
                        )
                    )
                    .join('\n');
            })
            .sort() // If we want to sort the streets by name as well
            .join('\n\n');
    };

    // RANDOM TEST DATA

    const randomStreetList = () => ['alpha', 'beta', 'gamma', 'delta',
        'epsilon', 'zeta', 'eta', 'theta', 'iota', 'kappa',
        'lambda', 'mu'
    ].map(
        x => {
            const intFrom = randomRInt(1, 10000);
            return x.charAt(0).toUpperCase() +
                x.slice(1) + ' Street\n' +
                enumFromTo(intFrom, intFrom + randomRInt(5, 10))
                .map(
                    n => n.toString() + (Boolean(randomRInt(0, 1)) ? (
                        ' notes...'
                    ) : '')
                )
                .join('\n');
        }
    ).join('\n\n');


    // GENERIC FUNCTIONS --------------------------------------

    // compare :: a -> a -> Ordering
    const compare = (a, b) => a < b ? -1 : (a > b ? 1 : 0);

    // enumFromToInt :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        n >= m ? (
            iterateUntil(x => x >= n, x => 1 + x, m)
        ) : [];

    // even :: Int -> Bool
    const even = n => n % 2 === 0;

    // iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
    const iterateUntil = (p, f, x) => {
        let vs = [x],
            h = x;
        while (!p(h))(h = f(h), vs.push(h));
        return vs;
    };

    // mappendComparing :: [(a -> b)] -> (a -> a -> Ordering)
    const mappendComparing = fs =>
        (x, y) => fs.reduce(
            (ordr, f) => ordr || compare(f(x), f(y)),
            0
        );

    // randomRInt :: Int -> Int -> Int
    const randomRInt = (low, high) =>
        low + Math.floor(
            (Math.random() * ((high - low) + 1))
        );

    // MAIN ---------------------------------------------------
    const strSorted = main();

    return strSorted;
})();


#5

And if you want to mix ascending and descending orders within your multiple sort keys, for example keeping the numbers ascending, but listing the even numbers before the odd ones (where after is the default):

.sort(
    mappendComparing_(
        [
            // DESCENDING
            [x => even(houseNumber(x)), false],

            // ASCENDING
            [houseNumber, true]
        ]
    )
)

Then we can use a variant of mappendComparing which takes a list of property-extraction functions in which each function is paired with either:

  • true (for ascending sort with that key), or
  • false (for descending sort with that key)
// mappendComparing_ :: [((a -> b), Bool)] -> (a -> a -> Ordering)
const mappendComparing_ = fboolPairs =>
    (x, y) => fboolPairs.reduce(
        (ordr, fb) => {
            const f = fb[0];
            return ordr !== 0 ? (
                ordr
            ) : fb[1] ? (
                compare(f(x), f(y))
            ) : compare(f(y), f(x));
        }, 0
    );

So, for street listings in which the even numbers precede the odd numbers (descending order), but the numbers within evenness groups are still in ascending sequence:

(() => {
    'use strict';

    /* 1. Generating a random list of streets and numbers, and then
       2. SORTING:
            Streets A-Z by name,
            houses first by evenness of number, (EVEN THEN ODD)
            and then by numeric (rather than string) order of number. (0-9)
    */
    const main = () => {

        // SAMPLE TEST DATA
        const strList = randomStreetList();

        const
            rgxNum = /(^\d+)/,
            houseNumber = s => {
                const m = rgxNum.exec(s);
                return Boolean(m) ? parseInt(m[1], 10) : 0;
            };
        return strList.split('\n\n')
            .map(strLines => {
                const xs = strLines.split('\n');
                return xs[0] + '\n' + xs.slice(1)
                    .sort(
                        mappendComparing_(
                            [
                                // DESCENDING (EVENS BEFORE ODDS)
                                [x => even(houseNumber(x)), false],

                                // ASCENDING
                                [houseNumber, true]
                            ]
                        )
                    )
                    .join('\n');
            })
            .sort() // If we want to sort the streets by name as well
            .join('\n\n');
    };

    // RANDOM TEST DATA

    const randomStreetList = () => ['alpha', 'beta', 'gamma', 'delta',
        'epsilon', 'zeta', 'eta', 'theta', 'iota', 'kappa',
        'lambda', 'mu'
    ].map(
        x => {
            const intFrom = randomRInt(1, 10000);
            return x.charAt(0).toUpperCase() +
                x.slice(1) + ' Street\n' +
                enumFromTo(intFrom, intFrom + randomRInt(5, 10))
                .map(
                    n => n.toString() + (Boolean(randomRInt(0, 1)) ? (
                        ' notes...'
                    ) : '')
                )
                .join('\n');
        }
    ).join('\n\n');


    // GENERIC FUNCTIONS --------------------------------------

    // compare :: a -> a -> Ordering
    const compare = (a, b) => a < b ? -1 : (a > b ? 1 : 0);

    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        n >= m ? (
            iterateUntil(x => x >= n, x => 1 + x, m)
        ) : [];

    // even :: Int -> Bool
    const even = n => n % 2 === 0;

    // iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
    const iterateUntil = (p, f, x) => {
        let vs = [x],
            h = x;
        while (!p(h))(h = f(h), vs.push(h));
        return vs;
    };

    // mappendComparing_ :: [((a -> b), Bool)] -> (a -> a -> Ordering)
    const mappendComparing_ = fboolPairs =>
        (x, y) => fboolPairs.reduce(
            (ordr, fb) => {
                const f = fb[0];
                return ordr !== 0 ? (
                    ordr
                ) : fb[1] ? (
                    compare(f(x), f(y))
                ) : compare(f(y), f(x));
            }, 0
        );

    // randomRInt :: Int -> Int -> Int
    const randomRInt = (low, high) =>
        low + Math.floor(
            (Math.random() * ((high - low) + 1))
        );

    // MAIN ---------------------------------------------------
    const strSorted = main();

    return strSorted;
})();


#6

Finally, Rosemary mentioned optimisation, which, of course, in some contexts means saving minutes or hours of coding time, and in others means saving milliseconds or seconds of run time.

My guess is that the latter kind of optimisation doesn’t arise all that much as a priority for light personal scripting on Drafts, but if:

  • lists were really long and disordered, or
  • one or more of the accessor functions (like houseNumber, even etc) were expensive (involved significant processing to obtain a property, every time two values were compared in a sort, or
  • the action was used very frequently by many, then …

The main point to notice is that any given item in a list may be involved in multiple comparisons during a sort, and if a property accessor function like houseNumber does involves some work to derive, then it it would be good to rearrange things so that each property is obtained only once per item per sort key.

A classic way to do that is a decorate-sort-undecorate pattern, bundled below in the generic and reusable sortOn function, which in this case seems to run c. 15-20% faster than the method above, i.e. probably not really worth it here, but in case it’s of any interest to anyone, here is how it works.

(PS in this case, because both sort keys use the houseNumber function, a hand-written version of the decorate-sort-undecorate process, in which houseNumber is called once only for each item), and the result reused for the even key, might speed it up another 5-10% beyond sortOn at a first guess, so still not worth it for the extra coding time :slight_smile: )

(Javascript is very fast anyway …)

(() => {
    'use strict';

    /* 1. Generating a random list of streets and numbers, and then
       2. SORTING:
            Streets A-Z by name,
            houses first by evenness of number, (EVEN THEN ODD)
            and then by numeric (rather than string) order of number. (0-9)
    */
    const main = () => {

        // SAMPLE TEST DATA
        const strList = randomStreetList();

        const
            rgxNum = /(^\d+)/,
            houseNumber = s => {
                const m = rgxNum.exec(s);
                return Boolean(m) ? parseInt(m[1], 10) : 0;
            };

        return strList.split('\n\n')
            .map(strLines => {
                const xs = strLines.split('\n');
                return xs[0] + '\n' +
                    sortOn(
                        mappendComparing_(
                            [
                                // DESCENDING (EVENS BEFORE ODDS)
                                [x => even(houseNumber(x)), false],

                                // ASCENDING
                                [houseNumber, true]
                            ]
                        ),
                        xs.slice(1)
                    ).join('\n');
            })
            .sort() // If we want to sort the streets by name as well
            .join('\n\n');
    };

    // RANDOM TEST DATA

    const randomStreetList = () => ['alpha', 'beta', 'gamma', 'delta',
        'epsilon', 'zeta', 'eta', 'theta', 'iota', 'kappa',
        'lambda', 'mu'
    ].map(
        x => {
            const intFrom = randomRInt(1, 10000);
            return x.charAt(0).toUpperCase() +
                x.slice(1) + ' Street\n' +
                enumFromTo(intFrom, intFrom + randomRInt(5, 10))
                .map(
                    n => n.toString() + (Boolean(randomRInt(0, 1)) ? (
                        ' notes...'
                    ) : '')
                )
                .join('\n');
        }
    ).join('\n\n');


    // GENERIC FUNCTIONS --------------------------------------

    // Tuple (,) :: a -> b -> (a, b)
    const Tuple = (a, b) => ({
        type: 'Tuple',
        '0': a,
        '1': b,
        length: 2
    });

    // compare :: a -> a -> Ordering
    const compare = (a, b) => a < b ? -1 : (a > b ? 1 : 0);

    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        n >= m ? (
            iterateUntil(x => x >= n, x => 1 + x, m)
        ) : [];

    // even :: Int -> Bool
    const even = n => n % 2 === 0;

    // flatten :: NestedList a -> [a]
    const flatten = t =>
        Array.isArray(t) ? (
            [].concat.apply([], t.map(flatten))
        ) : t;

    // iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
    const iterateUntil = (p, f, x) => {
        let vs = [x],
            h = x;
        while (!p(h))(h = f(h), vs.push(h));
        return vs;
    };

    // mappendComparing_ :: [((a -> b), Bool)] -> (a -> a -> Ordering)
    const mappendComparing_ = fboolPairs =>
        (x, y) => fboolPairs.reduce(
            (ordr, fb) => {
                const f = fb[0];
                return ordr !== 0 ? (
                    ordr
                ) : fb[1] ? (
                    compare(f(x), f(y))
                ) : compare(f(y), f(x));
            }, 0
        );

    // randomRInt :: Int -> Int -> Int
    const randomRInt = (low, high) =>
        low + Math.floor(
            (Math.random() * ((high - low) + 1))
        );

    // sortBy :: (a -> a -> Ordering) -> [a] -> [a]
    const sortBy = (f, xs) =>
        xs.slice()
        .sort(f);

    // Sort a list by comparing the results of a key function applied to each
    // element. sortOn f is equivalent to sortBy (comparing f), but has the
    // performance advantage of only evaluating f once for each element in
    // the input list. This is called the decorate-sort-undecorate paradigm,
    // or Schwartzian transform.
    // Elements are arranged from from lowest to highest.
    // sortOn :: Ord b => (a -> b) -> [a] -> [a]
    // sortOn :: Ord b => [((a -> b), Bool)]  -> [a] -> [a]
    const sortOn = (f, xs) => {
        // Functions and matching bools derived from argument f
        // which may be a single key function, or a list of key functions
        // each of which may or may not be followed by a direction bool.
        const fsbs = unzip(
                flatten([f])
                .reduceRight((a, x) =>
                    typeof x === 'boolean' ? {
                        asc: x,
                        fbs: a.fbs
                    } : {
                        asc: true,
                        fbs: [
                            [x, a.asc]
                        ].concat(a.fbs)
                    }, {
                        asc: true,
                        fbs: []
                    })
                .fbs
            ),
            [fs, bs] = [fsbs[0], fsbs[1]],
            iLast = fs.length;

        // decorate-sort-undecorate
        return sortBy(mappendComparing_(
                // functions that access pre-calculated values
                // by position in the decorated ('Schwartzian')
                // version of xs
                zip(fs.map((_, i) => x => x[i]), bs)
            ), xs.map( // xs decorated with precalculated values
                x => fs.reduceRight(
                    (a, g) => [g(x)].concat(a), [
                        x
                    ])))
            .map(x => x[iLast]); // undecorated version of data, post sort.
    };

    // unzip :: [(a,b)] -> ([a],[b])
    const unzip = xys =>
        xys.reduce(
            (a, x) => Tuple.apply(null, [0, 1].map(
                i => a[i].concat(x[i])
            )),
            Tuple([], [])
        );

    // zip :: [a] -> [b] -> [(a, b)]
    const zip = (xs, ys) =>
        xs.slice(0, Math.min(xs.length, ys.length))
        .map((x, i) => Tuple(x, ys[i]));

    // MAIN ---------------------------------------------------
    const strSorted = main();

    return strSorted;
})();


#7

Here is the hand-written decorate-sort-undecorate using sortBy, rather than sortOn.

Still not worth the extra coding time – it runs only about 30%-35% faster than the more quickly written first draft. Sounds significant, but in fact completely subliminal, and the script is probably not the main bottle-neck anyway :slight_smile:

(() => {
    'use strict';

    /* 1. Generating a random list of streets and numbers, and then
       2. SORTING:
            Streets A-Z by name,
            houses first by evenness of number, (EVEN THEN ODD)
            and then by numeric (rather than string) order of number. (0-9)
    */
    const main = () => {

        // SAMPLE TEST DATA
        const strList = randomStreetList();

        const
            rgxNum = /(^\d+)/,
            houseNumber = s => {
                const m = rgxNum.exec(s);
                return Boolean(m) ? parseInt(m[1], 10) : 0;
            };

        return strList.split('\n\n')
            .map(strLines => {
                const xs = strLines.split('\n');
                return xs[0] + '\n' +
                    sortBy(
                        mappendComparing_(
                            [
                                // DESCENDING (EVENS BEFORE ODDS)
                                [x => x.even, false],

                                // ASCENDING
                                [x => x.houseNumber, true]
                            ]
                        ),
                        // SORTING A DECORATED VERSION OF THE LIST
                        xs.slice(1).map(x => {
                            const n = houseNumber(x);
                            return {
                                item: x,
                                houseNumber: n,
                                even: even(n)
                            }
                        })
                    )
                    // SHEDDING THE DECORATION
                    .map(x => x.item)
                    .join('\n');
            })
            .sort() // If we want to sort the streets by name as well
            .join('\n\n');
    };

    // RANDOM TEST DATA

    const randomStreetList = () => ['alpha', 'beta', 'gamma', 'delta',
        'epsilon', 'zeta', 'eta', 'theta', 'iota', 'kappa',
        'lambda', 'mu'
    ].map(
        x => {
            const intFrom = randomRInt(1, 10000);
            return x.charAt(0).toUpperCase() +
                x.slice(1) + ' Street\n' +
                enumFromTo(intFrom, intFrom + randomRInt(5, 10))
                .map(
                    n => n.toString() + (Boolean(randomRInt(0, 1)) ? (
                        ' notes...'
                    ) : '')
                )
                .join('\n');
        }
    ).join('\n\n');


    // GENERIC FUNCTIONS --------------------------------------

    // Tuple (,) :: a -> b -> (a, b)
    const Tuple = (a, b) => ({
        type: 'Tuple',
        '0': a,
        '1': b,
        length: 2
    });

    // compare :: a -> a -> Ordering
    const compare = (a, b) => a < b ? -1 : (a > b ? 1 : 0);

    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        n >= m ? (
            iterateUntil(x => x >= n, x => 1 + x, m)
        ) : [];

    // even :: Int -> Bool
    const even = n => n % 2 === 0;

    // iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
    const iterateUntil = (p, f, x) => {
        let vs = [x],
            h = x;
        while (!p(h))(h = f(h), vs.push(h));
        return vs;
    };

    // mappendComparing_ :: [((a -> b), Bool)] -> (a -> a -> Ordering)
    const mappendComparing_ = fboolPairs =>
        (x, y) => fboolPairs.reduce(
            (ordr, fb) => {
                const f = fb[0];
                return ordr !== 0 ? (
                    ordr
                ) : fb[1] ? (
                    compare(f(x), f(y))
                ) : compare(f(y), f(x));
            }, 0
        );

    // randomRInt :: Int -> Int -> Int
    const randomRInt = (low, high) =>
        low + Math.floor(
            (Math.random() * ((high - low) + 1))
        );

    // sortBy :: (a -> a -> Ordering) -> [a] -> [a]
    const sortBy = (f, xs) =>
        xs.slice()
        .sort(f);

    // MAIN ---------------------------------------------------
    const strSorted = main();

    return strSorted;
})();


#8

Thank you both!!! It looks like I have all of the elements here to accomplish what I need. I like the prompts from Rosemary’s script and I’ll combine that with the functions draft8 provided. Preliminary tests show that it works as expected.

I may try my hand at putting those “generic functions” into a library that I can use within other scripts. I’ve been keeping my scripts in drafts and using eval() inside the script editor, which has been working fabulously.

Thanks again for all of your help!
Nick


#9

So I have a new question related to this. I have a script working pretty well, but I’m thinking about changing the format a little bit in order to add flexibility. Any idea of how I can keep the sorting intact if I have an optional line, below the house number, containing notes? For example:

Smith Street
3388
3900
4100
4101
    - Note attached to 4101
4102
4103
    - Note attached to 4103
4104
etc...

Any ideas?


#12

This actually made me laugh out loud. :wink:


#14

Thank you! I think this gets me started in the right direction. It wasn’t working at first with my test data, but when I used @draft8’s “show invisibles” action, It helped me see that I had two spaces after one of the address blocks. Once I removed those, it worked perfectly.

Thanks again, I will keep working on this until I get a workflow that I like.

Nick