diff options
author | Zandr Martin <zandrmartin+git@gmail.com> | 2016-06-02 15:48:14 -0500 |
---|---|---|
committer | Zandr Martin <zandrmartin+git@gmail.com> | 2016-06-02 15:48:14 -0500 |
commit | 9ccc92705ef428d6486fd9173e5029c594798919 (patch) | |
tree | 6ccc4143129cdfe354aa01f80c80deff1cca4ca4 /common | |
parent | Merge pull request #691 from thuck/floating_size_conf (diff) | |
download | sway-9ccc92705ef428d6486fd9173e5029c594798919.tar.gz sway-9ccc92705ef428d6486fd9173e5029c594798919.tar.zst sway-9ccc92705ef428d6486fd9173e5029c594798919.zip |
implement stable sort for lists
also change sort_workspaces() to use it
Diffstat (limited to 'common')
-rw-r--r-- | common/list.c | 59 |
1 files changed, 58 insertions, 1 deletions
diff --git a/common/list.c b/common/list.c index a7585a31..d57234e3 100644 --- a/common/list.c +++ b/common/list.c | |||
@@ -59,7 +59,7 @@ void list_cat(list_t *list, list_t *source) { | |||
59 | } | 59 | } |
60 | } | 60 | } |
61 | 61 | ||
62 | void list_qsort(list_t* list, int compare(const void *left, const void *right)) { | 62 | void list_qsort(list_t *list, int compare(const void *left, const void *right)) { |
63 | qsort(list->items, list->length, sizeof(void *), compare); | 63 | qsort(list->items, list->length, sizeof(void *), compare); |
64 | } | 64 | } |
65 | 65 | ||
@@ -72,3 +72,60 @@ int list_seq_find(list_t *list, int compare(const void *item, const void *data), | |||
72 | } | 72 | } |
73 | return -1; | 73 | return -1; |
74 | } | 74 | } |
75 | |||
76 | static void list_swap(list_t *list, int src, int dest) { | ||
77 | void *tmp = list->items[src]; | ||
78 | list->items[src] = list->items[dest]; | ||
79 | list->items[dest] = tmp; | ||
80 | } | ||
81 | |||
82 | static void list_rotate(list_t *list, int from, int to) { | ||
83 | void *tmp = list->items[to]; | ||
84 | |||
85 | while (to > from) { | ||
86 | list->items[to] = list->items[to - 1]; | ||
87 | to--; | ||
88 | } | ||
89 | |||
90 | list->items[from] = tmp; | ||
91 | } | ||
92 | |||
93 | static void list_inplace_merge(list_t *list, int left, int last, int mid, int compare(const void *a, const void *b)) { | ||
94 | int right = mid + 1; | ||
95 | |||
96 | if (compare(&list->items[mid], &list->items[right]) <= 0) { | ||
97 | return; | ||
98 | } | ||
99 | |||
100 | while (left <= mid && right <= last) { | ||
101 | if (compare(&list->items[left], &list->items[right]) <= 0) { | ||
102 | left++; | ||
103 | } else { | ||
104 | list_rotate(list, left, right); | ||
105 | left++; | ||
106 | mid++; | ||
107 | right++; | ||
108 | } | ||
109 | } | ||
110 | } | ||
111 | |||
112 | static void list_inplace_sort(list_t *list, int first, int last, int compare(const void *a, const void *b)) { | ||
113 | if (first >= last) { | ||
114 | return; | ||
115 | } else if ((last - first) == 1) { | ||
116 | if (compare(&list->items[first], &list->items[last]) > 0) { | ||
117 | list_swap(list, first, last); | ||
118 | } | ||
119 | } else { | ||
120 | int mid = (int)((last + first) / 2); | ||
121 | list_inplace_sort(list, first, mid, compare); | ||
122 | list_inplace_sort(list, mid + 1, last, compare); | ||
123 | list_inplace_merge(list, first, last, mid, compare); | ||
124 | } | ||
125 | } | ||
126 | |||
127 | void list_stable_sort(list_t *list, int compare(const void *a, const void *b)) { | ||
128 | if (list->length > 1) { | ||
129 | list_inplace_sort(list, 0, list->length - 1, compare); | ||
130 | } | ||
131 | } | ||