[systemd-devel] [PATCH 03/14] systemadm: display dependencies sorted

[Zbigniew Jędrzejewski-Szmek]

On 09/19/2011 07:34 PM, Maciej Marcin Piechotka wrote:
> On Mon, 2011-09-19 at 13:24 +0200, Zbigniew Jędrzejewski-Szmek wrote:
>> Maybe there's an easier way to sort strings in vala...
>
> In libgee the code would be:
>
> List<string>  sorted = new ArrayList<string>();
> sorted.add_all (dependencies);
> sorted.sort ();
>
> Or:
>
> Collection<string>  sorted = new TreeSet<string>();
> sorted.add_all (dependencies);

Hi,

thanks for the review! Indeed using gee makes this a bit simpler and
O(n log n), which should be OK, since n is on the order of tens.
Unfortunately the source (dependencies) is an array, not a Collection,
so add_all does not accept it and explicit looping is necessary.

An improved patch is below. I'll also push the changed version to my repo.

Best,
Zbyszek

---
  src/systemadm.vala |    6 +++++-
  1 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/src/systemadm.vala b/src/systemadm.vala
index c893da0..088ba26 100644
--- src/systemadm.vala
+++ src/systemadm.vala
@@ -458,6 +458,10 @@ public class MainWindow : Window {
          }

          public string make_dependency_string(string? prefix, string 
word, string[] dependencies) {
+                Gee.Collection<unowned string> sorted = new 
Gee.TreeSet<string>();
+                foreach (string i in dependencies)
+                        sorted.add(i);
+
                  bool first = true;
                  string r;

@@ -466,7 +470,7 @@ public class MainWindow : Window {
                  else
                          r = prefix;

-                foreach (string i in dependencies) {
+                foreach (string i in sorted) {
                          if (r != "")
                                  r += first ? "\n" : ",";

-- 
1.7.6




>> I admit
>> that this patch is not very pretty.
>> ---
>>   src/systemadm.vala |    7 ++++++-
>>   1 files changed, 6 insertions(+), 1 deletions(-)
>>
>> diff --git a/src/systemadm.vala b/src/systemadm.vala
>> index 21177bf..9861ae4 100644
>> --- a/src/systemadm.vala
>> +++ b/src/systemadm.vala
>> @@ -442,6 +442,11 @@ public class MainWindow : Window {
>>           }
>>
>>           public string make_dependency_string(string? prefix, string word, string[] dependencies) {
>> +                List<string>  sorted = new List<string>();
>> +                foreach (string i in dependencies)
>> +                        sorted.append(i);
>> +                sorted.sort(strcmp);
>> +
>
> The above code have O(n^2) complexity (each append have O(n) and there
> is O(n) appends) and IIRC[1] list should start by NULL:
>
> List<string>? sorted = NULL;
> foreach (string i in dependencies)
>      sorted.prepend(i);
> sorted.reverse();
> sorted.sort(strcmp);
>
> or even better if dependencies is List:
>
> List<unowned string>? sorted = dependencies.copy();
> sorted.sort(strcmp);
>
> [1] "There is no function to create a GList. NULL is considered to be
> the empty list so you simply set a GList* to NULL." from
> http://developer.gnome.org/glib/2.28/glib-Doubly-Linked-Lists.html
>
>
>>                   bool first = true;
>>                   string r;
>>
>> @@ -450,7 +455,7 @@ public class MainWindow : Window {
>>                   else
>>                           r = prefix;
>>
>> -                foreach (string i in dependencies) {
>> +                foreach (string i in sorted) {
>>                           if (r != "")
>>                                   r += first ? "\n" : ",";
>>
>
> Regards