Sorting Order of Completion Candidates

Sorting Order of Completion Candidates

[Florian Beck]

While writing some code to index my notes I have run into a problem.
I have a carefully crafted list of keywords sorted in order of 
frequency. (When assigning new keywords I want to consider the most 
frequent keywords first.) However

 > (completing-read "Prompt: " '("a" "c" "b"))

gives me

 > Possible completions are:
 > a
 > b
 > c

whereas I want


 > Possible completions are:
 > a
 > c
 > b

If there is no option or hook, if guess I could just modify the 
*Completions* buffer. Any hints how/where it is set up?

Many thanks in advance!

RE: Sorting Order of Completion Candidates

[Drew Adams]

> While writing some code to index my notes I have run into a problem.
> I have a carefully crafted list of keywords sorted in order of 
> frequency. (When assigning new keywords I want to consider the most 
> frequent keywords first.) However
> (completing-read "Prompt: " '("a" "c" "b"))  gives me
> 
>  Possible completions are:
>  a
>  b
>  c
> 
> whereas I want
> 
>  Possible completions are:
>  a
>  c
>  b
> 
> If there is no option or hook, if guess I could just modify the 
> *Completions* buffer. Any hints how/where it is set up?

1. Stefan can probably steer you as to how to do what you want with a recent
version of vanilla Emacs.

2. An alternative is to use Icicles.  Then all you need to do is bind
`icicle-sort-comparer' to nil around the call to `completing-read'.  A nil value
means do not sort.  (You can also customize `icicle-sort-comparer' to use any
default sort order you like.)

You can also change sort orders on the fly anytime during completion, and that
includes turning sorting off: hit `C-,' to cycle to the next sort order for the
current completion type.  (One of the sort orders is unsorted (off).)

Sorting is particularly important for Icicles because it affects the order of
candidate cycling.

http://www.emacswiki.org/emacs/Icicles_-_Sorting_Candidates

Re: Sorting Order of Completion Candidates

[Florian Beck]

On 03/01/2011 02:25 AM, Drew Adams wrote:
>> While writing some code to index my notes I have run into a problem.
>> I have a carefully crafted list of keywords sorted in order of
>> frequency. (When assigning new keywords I want to consider the most
>> frequent keywords first.) However
>> (completing-read "Prompt: " '("a" "c" "b"))  gives me
>>
>>   Possible completions are:
>>   a
>>   b
>>   c
>>
>> whereas I want
>>
>>   Possible completions are:
>>   a
>>   c
>>   b
>>
>> If there is no option or hook, if guess I could just modify the
>> *Completions* buffer. Any hints how/where it is set up?
>
> 1. Stefan can probably steer you as to how to do what you want with a recent
> version of vanilla Emacs.

I ended up modifying `minibuffer-completion-help'. There doesn't seem to 
be a way around that.

> 2. An alternative is to use Icicles.  Then all you need to do is bind
> `icicle-sort-comparer' to nil around the call to `completing-read'.  A nil value
> means do not sort.  (You can also customize `icicle-sort-comparer' to use any
> default sort order you like.)

Thanks, I will look into that. Or do you replace the whole completion 
mechanism?

-- 
Florian Beck

Re: Sorting Order of Completion Candidates

[Stefan Monnier]

> I ended up modifying `minibuffer-completion-help'. There doesn't seem to
> be a way around that.

M-x report-emacs-bug to request the necessary feature.
Tho, IIRC it's already requested.  Just not implemented yet.


        Stefan

Re: Sorting Order of Completion Candidates

[Ted Zlatanov]

On Tue, 01 Mar 2011 09:48:37 -0500 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> I ended up modifying `minibuffer-completion-help'. There doesn't seem to
>> be a way around that.

SM> M-x report-emacs-bug to request the necessary feature.
SM> Tho, IIRC it's already requested.  Just not implemented yet.

Florian: I've proposed a patch to use the string property
:completion-score to attach a numerical score to the completion
candidates.  The discussion so far is in the BBDB mailing list (where we
needed to score completion candidates) but I will propose it on
emacs-devel once Stefan reviews it.

Ted

Re: Sorting Order of Completion Candidates

[Florian Beck]

On 03/01/2011 05:29 PM, Ted Zlatanov wrote:

> Florian: I've proposed a patch to use the string property
> :completion-score to attach a numerical score to the completion
> candidates.  The discussion so far is in the BBDB mailing list (where we
> needed to score completion candidates) but I will propose it on
> emacs-devel once Stefan reviews it.

Nice idea. You mean text properties on the strings?

So I would use something like

(defun string-score-higher (a b)
   (if (> (or (get-text-property 0 :completion-score a) 0)
	 (or (get-text-property 0 :completion-score b) 0))
       a
     (string-lessp a b)))

as a sorting predicate?

Seems to work (so far),

Thanks,

Florian

Re: Sorting Order of Completion Candidates

[Ted Zlatanov]

On Tue, 01 Mar 2011 19:22:47 +0100 Florian Beck <fb@miszellen.de> wrote: 

FB> On 03/01/2011 05:29 PM, Ted Zlatanov wrote:
>> Florian: I've proposed a patch to use the string property
>> :completion-score to attach a numerical score to the completion
>> candidates.  The discussion so far is in the BBDB mailing list (where we
>> needed to score completion candidates) but I will propose it on
>> emacs-devel once Stefan reviews it.

FB> Nice idea. You mean text properties on the strings?

FB> So I would use something like

FB> (defun string-score-higher (a b)
FB>   (if (> (or (get-text-property 0 :completion-score a) 0)
FB> 	 (or (get-text-property 0 :completion-score b) 0))
FB>       a
FB>     (string-lessp a b)))

FB> as a sorting predicate?

FB> Seems to work (so far),

With my proposal it will be built into
`completion-all-sorted-completions':

- if both candidates have a :completion-score, lowest wins

- if only one has :completion-score, it wins

- else we sort by string length (shortest wins)

Thus you don't have to craft custom sort predicates :)

Ted

Re: Sorting Order of Completion Candidates

[Florian Beck]

On 03/01/2011 08:25 PM, Ted Zlatanov wrote:
> On Tue, 01 Mar 2011 19:22:47 +0100 Florian Beck<fb@miszellen.de>  wrote:
>
> FB>  On 03/01/2011 05:29 PM, Ted Zlatanov wrote:
>>> Florian: I've proposed a patch to use the string property
>>> :completion-score to attach a numerical score to the completion
>>> candidates.  The discussion so far is in the BBDB mailing list (where we
>>> needed to score completion candidates) but I will propose it on
>>> emacs-devel once Stefan reviews it.
>
> FB>  Nice idea. You mean text properties on the strings?
>
> FB>  So I would use something like
>
> FB>  (defun string-score-higher (a b)
> FB>    (if (>  (or (get-text-property 0 :completion-score a) 0)
> FB>  	(or (get-text-property 0 :completion-score b) 0))
> FB>        a
> FB>      (string-lessp a b)))
>
> FB>  as a sorting predicate?
>
> FB>  Seems to work (so far),
>
> With my proposal it will be built into
> `completion-all-sorted-completions':
>
> - if both candidates have a :completion-score, lowest wins
>
> - if only one has :completion-score, it wins
>
> - else we sort by string length (shortest wins)
>
> Thus you don't have to craft custom sort predicates :)
>
> Ted
>

Hm, intuitively, I would think higher scored items come first.

Anyway, I tried modifying `completion-all-sorted-completions' but it had 
no effect, because the candidates are sorted in 
`minibuffer-completion-help'. I guess, you will override that -- but why 
sort there in the first place? All sorting should take place is 
`completion-all-sorted-completions', shouldn't it?

Also, both for reasons of performance and convenience, an option not to 
sort candidates at all might be desirable.

-- 
Florian

Re: Sorting Order of Completion Candidates

[Ted Zlatanov]

On Tue, 01 Mar 2011 21:41:11 +0100 Florian Beck <fb@miszellen.de> wrote: 

FB> Hm, intuitively, I would think higher scored items come first.

I mentioned that too but Stefan thought it would be more consistent with
"shorter string first" this way.  We can discuss it, I'm sure.

FB> Anyway, I tried modifying `completion-all-sorted-completions' but it
FB> had no effect, because the candidates are sorted in
FB> `minibuffer-completion-help'. I guess, you will override that -- but
FB> why sort there in the first place? All sorting should take place is
FB> `completion-all-sorted-completions', shouldn't it?

I tested only `completion-all-sorted-completions' so I didn't know about
the other sort site in `minibuffer-completion-help'.  Stefan knows that
code far better than me so I will let him comment.

FB> Also, both for reasons of performance and convenience, an option not
FB> to sort candidates at all might be desirable.

Obviously that doesn't apply to `completion-all-sorted-completions'
whose entire purpose is to sort...  But yeah,
`minibuffer-completion-help' may need that adjustment.

Ted

Re: Sorting Order of Completion Candidates

[Stefan Monnier]

> Florian: I've proposed a patch to use the string property
> :completion-score to attach a numerical score to the completion
> candidates.

Note that there are two forms of sorting: sorting for *Completion*
display, and sorting for cycling.  Currently, these are not sorted
identically (cycling sorts by string length, whereas *Completions*
sorts alphabetically).  I don't think "alphabetical" is useful for
cycling and neither do I think that "shorter first" is useful for
cycling, so I think it's important to keep them separate.


        Stefan

Re: Sorting Order of Completion Candidates

[Ted Zlatanov]

On Thu, 03 Mar 2011 18:29:49 -0500 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> Florian: I've proposed a patch to use the string property
>> :completion-score to attach a numerical score to the completion
>> candidates.

SM> Note that there are two forms of sorting: sorting for *Completion*
SM> display, and sorting for cycling.  Currently, these are not sorted
SM> identically (cycling sorts by string length, whereas *Completions*
SM> sorts alphabetically).  I don't think "alphabetical" is useful for
SM> cycling and neither do I think that "shorter first" is useful for
SM> cycling, so I think it's important to keep them separate.

Do you think *Completion* candidates could also use the
:completion-score property?  It should be easy to add.

Ted

Re: Sorting Order of Completion Candidates

[Stefan Monnier]

> Do you think *Completion* candidates could also use the
> :completion-score property?  It should be easy to add.

No, as my previous message was trying to say, I think the two sort
orders are likely to want to be different, so they need to be specified
differently (or at least it should be possible to specify two different
orderings).


        Stefan

Re: Sorting Order of Completion Candidates

[Ted Zlatanov]

On Fri, 04 Mar 2011 23:48:06 -0500 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> Do you think *Completion* candidates could also use the
>> :completion-score property?  It should be easy to add.

SM> No, as my previous message was trying to say, I think the two sort
SM> orders are likely to want to be different, so they need to be specified
SM> differently (or at least it should be possible to specify two different
SM> orderings).

Maybe :completion-cycling-score and :completion-candidate-score, with
:completion-score as fallback for both?

Ted

Re: Sorting Order of Completion Candidates

[Stefan Monnier]

>>> Do you think *Completion* candidates could also use the
>>> :completion-score property?  It should be easy to add.
SM> No, as my previous message was trying to say, I think the two sort
SM> orders are likely to want to be different, so they need to be specified
SM> differently (or at least it should be possible to specify two different
SM> orderings).
> Maybe :completion-cycling-score and :completion-candidate-score, with
> :completion-score as fallback for both?

Could be, but I'd first like to see what kind of sorting orders are
found to be useful to get a better feel for it.  Until now the only
display-sort option I've seen mentioned is "preserve the order from the
output of all-completions".


        Stefan

Re: Sorting Order of Completion Candidates

[Ted Zlatanov]

On Mon, 07 Mar 2011 23:09:58 -0500 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>>>> Do you think *Completion* candidates could also use the
>>>> :completion-score property?  It should be easy to add.
SM> No, as my previous message was trying to say, I think the two sort
SM> orders are likely to want to be different, so they need to be specified
SM> differently (or at least it should be possible to specify two different
SM> orderings).
>> Maybe :completion-cycling-score and :completion-candidate-score, with
>> :completion-score as fallback for both?

SM> Could be, but I'd first like to see what kind of sorting orders are
SM> found to be useful to get a better feel for it.  Until now the only
SM> display-sort option I've seen mentioned is "preserve the order from the
SM> output of all-completions".

OK.  In that case I'll just propose my :completion-score-penalty patch
for cycling candidates on emacs-devel, and you can decide when and if to
extend it.

Ted