Icicles - Sorting Candidates

iciclesimage
Previous: Icicles - IcompletionIciclesIciclesIndexNext: Icicles - A Propos d'Apropos

Sorting Candidates and Removing Duplicates

The current set of completion candidates matching your minibuffer input can be sorted in various ways. The sort order affects not only the display in buffer ‘*Completions*’ but also cycling among candidates. In general, candidate sorting is alphabetical by default, but some commands use different sort orders by default.

Also, duplicate candidates are typically removed as completion choices, by default. But for some commands duplicates are appropriate, so they are not removed. For example, command ‘icicle-search’ (`C-c `’) uses completion to navigate among search hits. Duplicate search hits are retained. Although some search-hit candidates might have the same text, they are located at different buffer positions.

You can interactively control the order of candidates and whether duplicates are removed. Use `C-,’ during completion to choose a different sort order or to turn off sorting altogether (one of the available sort orders is in fact called “turned OFF”). Use `C-$’ to toggle the removal of duplicate candidates.

A few commands, for which sorting is inappropriate, prevent you from sorting. For all other commands, Icicles can automatically turn candidate sorting off and on, depending on the number of completion candidates. This is a performance optimization, for use when the current set of candidates is large.

You can control this behavior by customizing user option `icicle-sorting-max-candidates’. Set it to ‘nil’ to turn off this automatic toggling of sorting. Set it to a larger or smaller maximum number of candidates to reduce or increase its effect.

It is the act of completion that causes Icicles to check the number of candidates against the option value and thus perhaps toggle sorting. This is the case regardless of how completion is initiated: whether manually (‘TAB’ or ‘S-TAB’) or automatically (see Apropos and Prefix Completion).

The available sort orders for `C-,’ are those defined by user option `icicle-sort-orders-alist’ – see Defining New Sort Orders, below. However, some commands adjust this list of possibilities by adding command-relevant sort orders or removing some that might be inappropriate.

The sort order generally remains as you last set it, for subsequent commands. However, if the last order you set is inappropriate for the current command then sorting is turned off. You can then use `C-,’ to choose a sort order appropriate for the current command.

Changing the Sort Order

There are a couple of ways to use `C-,’ (bound to command ‘icicle-change-sort-order’), to change the current sort order. Its behavior depends on the value of user option `icicle-change-sort-order-completion’, which is 7 by default. The option value determines whether `C-,’ lets you use completion to choose a sort order or it just cycles to the next order. The default value of 7 means cycle if there are no more than 7 sort orders for the current command, and complete if there are more than 7.

The option value can be an integer, as described, or it can be ‘nil’, meaning always cycle, or otherwise non-‘nil’ (e.g. ‘t’), meaning always complete.

Whatever the value of ‘icicle-change-sort-order-completion’, a non-numeric prefix argument (e.g., plain `C-u’) flips the behavior defined by the option: if completion would normally be used then `C-u C-,’ cycles to the next sort order. If cycling would normally be used then `C-u C-,’ initiates completion to choose a sort order.

For example, suppose you use the default option value of 7 and there are fewer than 7 sort orders for the completion operation provided by the current command. In this case, `C-,’ cycles to the next order. But if you would like to see what the available orders are, just use `C-u C-,’ and pick one using completion.

A numeric prefix argument (e.g. ‘C-9’) reverses the direction of the current sort order. It invokes command ‘icicle-reverse-sort-order’.

For example, if candidates are currently sorted alphabetically from A to Z, then `C-9 C-,’ flips the sort order, so that from then on sorting is from Z to A. If buffer names are sorted from small to large buffer size, then `C-9 C-,’ sorts large buffers first. This works for all sort orders.

Whenever you change the sort order, the new sort order is echoed, so you can use `C-9 C-,’ twice to just remind yourself of the current sort order.

Note that if sorting has been turned off automatically for the current minibuffer invocation because there are more candidates than `icicle-sorting-max-candidates’, using `C-,’ to choose a new sort order does not turn sorting back on. The newly chosen sort order takes effect only when sorting is turned on again (e.g. because there are fewer candidates).

In addition to the current sort order, which is defined by the value of user option `icicle-sort-comparer’, an alternative sort order is available at all times. It is the value of option `icicle-alternative-sort-comparer’. By default, this sorts candidates into two alphabetical groups: those previously used as accepted input, followed by those not yet used.

Just as you can choose a different current sort order using `C-,’, so you can choose a different alternative sort order using `M-,’. It behaves the same way, including regarding option ‘icicle-change-sort-order-completion’ and a prefix argument.

How do you actually use the alternative sort order? Use `C-M-,’ (command ‘icicle-toggle-alternative-sorting’) to swap the alternative sort for the current sort. This is the quickest way to flip between two sort orders. If, for example, you set your alternative sort order to “turned OFF”, then this is a quick way to toggle sorting on and off.

The first time during a session that you use a command that completes a buffer name or a file name, sorting changes to (that is, ‘icicle-sort-comparer’ is set to) whatever is specified by user option `icicle-buffer-sort’ or `icicle-file-sort’, respectively, provided the option is non-‘nil’. This gives you a way to privilege a particular sorting method for each of these kinds of completion.

Defining New Sort Orders

When you use `C-,’ or `M-,’, the sort orders that you can choose from are those in user option `icicle-sort-orders-alist’. You can customize this option to add or remove available sort orders. A better way to define a new sort order is to use macro ‘icicle-define-sort-command’ in your Emacs init file (~/.emacs). This defines a new Icicles command, named ‘icicle-sort-’ORDER ‘, where ‘ORDER’ is the name of the new sort order. The definition of the alphabetical sort order provides an example:

  (icicle-define-sort-command "alphabetical" icicle-case-string-less-p
    "Sort completion candidates alphabetically.")

The first argument, "alphabetical", is a string naming the new sort order. When you change to this sort order, a message says “Sorting is now alphabetical”. Whatever sort-order name you provide is used in the message.

The second argument is the actual function used for sorting. It can be any function, including a lambda expression. The function takes two string arguments and returns non-‘nil’ if and only if the first string sorts before (is “less than”) the second. In this case, function ‘icicle-case-string-less-p’ is used, which compares its two arguments alphabetically (lexicographically). The third argument is the doc string for the new sorting command.

The result of this definition is:

  1. The creation of command ‘icicle-sort-’alphabetical’.
  2. The addition of an entry for the new sort order in option ‘icicle-sort-orderss-alist’. The entry associates sort order alphabetical with comparison function ‘icicle-case-string-less-p’.

You can invoke the new sorting command any time using ‘M-x’, but you can also change to the new sort order using `C-,’ (or `M-,’) during minibuffer completion.

Different Sorts for Different Sorts of Uses

There are many different uses of completion in Emacs, and this means that sorting candidates needs to be flexible – there cannot be a single sort order, or even a single set of sort orders, that is useful for all purposes. Completion, and therefore also sorting of completion candidates, needs to deal with different types of candidates and different numbers of them, in different contexts.

Icicles predefines many sort functions, and you can easily define more of your own. You can choose a different sort at any time, as mentioned above. A good sort order can be a big help, depending on the context. However, sorting is not free, and it can be helpful to think for a moment about some of the consequences of sorting, in terms of performance.

What does a sort function do? It determines which of two strings should come first, that is, which is “less than” the other. During sorting, pairs of candidates are compared using the sort function. And each time you change your input by typing or deleting a character, the new set of matching candidates is sorted (if ‘icicle-incremental-completion’ is non-‘nil’).

The number of candidates to be sorted depends on the kind of completion and how you use Icicles. Some Icicles users like to use cycling more and completion less, which means sorting more candidates. Other users favor using completion to narrow down the number of matches (which I recommend). Some commands typically have few possible completion candidates; others have many. Buffer-name completion, for example, typically involves relatively few candidates, whereas file-name completion typically involves many.

If there are many candidates matching your input, then many comparisons will be made each time the candidate set is sorted. This means that if your sort function is complex, response can be slow. A complex sort function might be OK for sorting a small or medium set of candidates, but it might not be appropriate for sorting a very large set.

Only you, as a user, can control which sort makes the best sense for you in any given situation. If you are likely to have zillions of candidates in some context, then you probably will want to change to a sort that computes quickly. You can, of course, even choose not to sort at all, but simple sort comparisons do not noticeably impact performance, even for a very large number of candidates.

Icicles could offer a threshold option similar to ‘icicle-incremental-completion-threshold’ (or it could reuse that option), and not bother to sort if the number of candidates passed the threshold, but there can be many sort orders of differing complexity, so a set of thresholds would really be needed, perhaps one per sort order.

Rather than having you try to manage such complexity ahead of time using options, it’s better to just let you manage it at completion time: Choose the sort order with knowledge of the possible candidate set. For example, if the set of candidates to sort will include every file on your file system, then you probably will want to use a simple sort. On the other hand, there are situations where you might nevertheless prefer to wait a few seconds, in order to perform a complex sort that is of particular use.

In sum, Icicles keeps it simple, and leaves it up to you to choose the appropriate sort order for any given context. This design choice is one reason why Icicles makes it easy to choose a sort even while you are completing input – each act of completion is different.

It can help you choose, however, to know which of the predefined Icicles sort orders are more complex, and therefore tend to be slower. Here they are:

Sort OrderSort Function Used
by previous use alphabetically ‘icicle-historical-alphabetic-p’
by last use as input ‘icicle-latest-input-first-p’
by last use ‘icicle-latest-use-first-p’

The reason these sorts are slower is that they check the current minibuffer history, to see whether, and where, each candidate is located in the history list. If you, like I, have very long history lists, then this can take a while. I use histories of virtually unlimited length – I let SaveHist (savehist-20+.el) save all of my histories from one Emacs session to the next.

Here are some of the Icicles sort orders that exist by default:

As you can see, some are appropriate for color-name completion, some for buffer-name completion, and some for file-name completion. Some are general, appropriate for most kinds of completion.

Those in italics can be used only with Emacs 22 or later. Those in boldface are defined using ‘icicle-define-sort-command’, so they correspond to explicit commands whose doc you can examine. The command names in this case are ‘icicle-sort-’ followed by the sort-order names (with hyphens substituted for spaces) – for example, ‘icicle-sort-’by-directories-last’ and ‘icicle-sort-’turned-OFF.

Adding a Saved Sort Order

There are many predefined sort orders (see DifferentSortsForDifferentUses), and you can define your own new sort orders (see DefiningNewSortOrders). This section is about a unique Icicles feature that lets you combine any number of sort orders interactively, melding them together.

You do this as follows:

  1. Start with a given sort order (use `C-,’ to choose one, possibly with a prefix argument).
  2. Save the set of candidates you are interested in, using `C-M->’ (see Saving and Retrieving Completion Candidates). This saves the candidates in their current order at the time of the save: the saved order.
  3. Choose a different sort order (again, `C-,’, possibly with a prefix argument).
  4. Use `C-M-+’ (‘icicle-plus-saved-sort’) to combine the two sort orders, that is, the (new) current order and the saved order.

What ‘icicle-plus-saved-sort’ does is sum, for each completion candidate, its ranks (indexes) in the two sort orders, and then reorder candidates based on the summed ranks.

For example, if a given candidate is the 4th candidate in the current list of candidates, and it is the 7th candidate in the saved list of candidates, then its combined sort rank is 4 + 7 = 11. With a score of 11 it sorts after a candidate whose score is, for example, 6, and before a candidate whose score is, for example, 13.

The candidates are reordered according to the combined sort orders, forming a new current order.

When you use `C-M-+’ it does not matter what order the saved candidates are in or what order you used to sort the current candidates. (But you will generally want to use the same set of candidates.) In particular, after using `C-M-+’ the candidates are typically in an order that corresponds to no predefined sort — that’s OK.

You can use `C-M-+’ again if you like, to add in the saved sort order again with the new current order. This gives the saved order more weight than the original current sort order. Continued repetition of `C-M-+’ gives the saved sort order more and more weight. Eventually a fixed point is reached: `C-M-+’ produces no further change in the order.

For example, consider ‘icicle-read-color-WYSIWYG’. With user option `icicle-WYSIWYG-Completions-flag’ non-‘nil’ (e.g. a string) it lets you see the effect of `C-M-+’ in a striking, graphical way. However, to see the effect you will first want to use ‘S-pause’ (‘icicle-toggle-highlight-saved-candidates’) in the minibuffer to turn off highlighting of the saved candidates, since that highlighting obscures the color highlighting. (You can use ‘C-S-pause’ to toggle option ‘icicle-WYSIWYG-Completions-flag’.)

Sorting by color hue shows essentially a single rainbow of candidates in ‘*Completions*’: pinks, followed by magentas, purples, blues, cyans, greens, yellows, browns, reds, and grays. Sorting by color brightness shows a single value gamut, the brightest colors followed by dimmer and dimmer colors, down to the dimmest (black).

Try ‘M-x icicle-read-color-WYSIWYG’, sorting (`C-,’, possibly with a prefix argument) first by hue. Here is a screenshot:

by-hue

Save the completion candidates (`C-M->’). Now sort by brightness (`C-,’ again, possibly with a prefix argument). A screenshot:

by-brightness

Now use `C-M-+’ to add/merge the two sort orders. You now see essentially a series of rainbows, from brighter to dimmer and dimmer. A screenshot:

by-hue-and-brightness

Use `C-M-+’ again, to give hue more prominence in the merged sort order. And again. Here is a screenshot after a few times of using `C-M-+’, adding more hue influence.

by-hue-hue-hue-brightness

Keep hitting `C-M-+’ until there is no more apparent change in the sort order — at this point you are back to a pure hue sort.

You can also at any time save the candidates again, saving the latest order as the new sort order. Then you can reorder the current candidates using a different sort order (`C-,’). And then use `C-M-+’ again to merge in the newly saved order. You can play this way ad infinitem.

See Also:


Previous: Icicles - IcompletionIciclesIciclesIndexNext: Icicles - A Propos d'Apropos

DrewsElispLibraries referenced here: Lisp:icicles.el

CategoryCommands CategoryCompletion CategoryDocumentation CategoryHelp CategoryProgrammerUtils