Mercurial > repos > tabletprog
comparison modules/array.tp @ 322:fb54a3af9c86
Add sort method to arrays
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Sun, 22 Mar 2015 22:06:50 -0700 |
parents | bb4723fec05e |
children | eb5f1fca9b78 |
comparison
equal
deleted
inserted
replaced
321:3edd0169311a | 322:fb54a3af9c86 |
---|---|
127 idx <- l | 127 idx <- l |
128 } | 128 } |
129 } | 129 } |
130 ret | 130 ret |
131 } | 131 } |
132 | |
133 sort <- { | |
134 n <- length | |
135 tmp <- #[] | |
136 tmp resize: n | |
137 while: { (tmp length) < n} do: { | |
138 tmp append: false | |
139 } | |
140 src <- self | |
141 dst <- tmp | |
142 | |
143 merge <- :lStart rStart rEnd { | |
144 dstIdx <- lStart | |
145 left <- lStart | |
146 right <- rStart | |
147 | |
148 while: { dstIdx < rEnd } do: { | |
149 if: left < rStart && (right >= rEnd || (src get: left) <= (src get: right)) { | |
150 dst set: dstIdx (src get: left) | |
151 left <- left + 1 | |
152 } else: { | |
153 dst set: dstIdx (src get: right) | |
154 right <- right + 1 | |
155 } | |
156 dstIdx <- dstIdx + 1 | |
157 } | |
158 } | |
159 | |
160 needsCopy? <- false | |
161 subSize <- 1 | |
162 while: { subSize < n} do: { | |
163 group <- subSize * 2 | |
164 i <- 0 | |
165 while: { i < n} do: { | |
166 right <- i + subSize | |
167 end <- i + group | |
168 if: right > n { | |
169 right <- n | |
170 end <- n | |
171 } else: { | |
172 if: end > n { | |
173 end <- n | |
174 } | |
175 } | |
176 merge: i right end | |
177 i <- i + group | |
178 } | |
179 tmp <- dst | |
180 dst <- src | |
181 src <- tmp | |
182 needsCopy? <- not: needsCopy? | |
183 | |
184 subSize <- subSize + subSize | |
185 } | |
186 if: needsCopy? { | |
187 foreach: src :index val { | |
188 self set: index val | |
189 } | |
190 } | |
191 } | |
132 | 192 |
133 join <- :sep { | 193 join <- :sep { |
134 if: length > 0 { | 194 if: length > 0 { |
135 str <- string: (get: 0) | 195 str <- string: (get: 0) |
136 idx <- 1 | 196 idx <- 1 |