Somedude 
Posted in reply to Andrej Mitrovic
| Le 16/04/2012 21:51, Andrej Mitrovic a écrit :
> On 4/16/12, Somedude <lovelydear@mailmetrash.com> wrote:
>> OPTLINK : Warning 134: No Start Address
>
> This means you're missing a void main or int main function. You can pass --main to rdmd to add it automatically (useful when e.g. unittesting).
All right, now I have a bunch of questions.
Sorry, D newcomer here.
I hate to do this, but I'll simply dump the full code, it should save me a lot of questions.
/++
Xinok Sort for the D Programming Language
Written and tested for DMD 2.055 and Phobos
Authors: Xinok
Date: November 2011
License: Public Domain
Web: $(LINK http://www.sourceforge.net/projects/xinoksort)
Todo:
Parallelization - Write a separate function which runs xinok sort in
multiple threads
Support for CTFE - Sorting arrays at compile time
Unittest for ranges - Test implementation of xinok sort using range
primitives
In / Out conditions and asserts
++/
module xinoksort;
import std.range;
import std.functional : binaryFun, not;
import std.algorithm : swap, swapRanges, copy, reverse, isSorted;
import std.traits : isCallable;
import core.exception : OutOfMemoryError;
/++
This function will sort an array or range in-place,
optionally using a custom predicate.
Returns: Sorted input as SortedRange
Throws: OutOfMemoryError if memory allocation fails
Predicate:
The predicate can be a string, function, or delegate.
A string should represent the two elements to compare
using the characters 'a' and 'b'.
A function or delegate should take two arguments of the
same type and return a bool.
The default predicate for sorting is "a < b".
Examples:
---
int[] arr = [20, 40, 60, 10, 30, 50];
xinokSort(arr);
// Sort in reverse order
xinokSort!("a > b")(arr);
// Use a function or delegate as predicate
bool comp(int a, int b){ return a < b; }
xinokSort!(comp)(arr);
// Sort an array of strings, case insensitive
string[] list;
xinokSort!("icmp(a, b) < 0")(list);
---
++/
SortedRange!(Range, pred) xinokSort(alias pred = "a < b", Range)(Range arr){
typeof(Range[0])[] temp;
if(!__ctfe){ // Allocate temporary memory
size_t len = arr.length >= 1024*64 ? arr.length / 1024 : 64;
while(temp is null){
try temp.length = len;
catch(OutOfMemoryError err){ // Reduce memory usage and try again
len /= 2;
if(len >= 8) continue;
else throw err;
}
}
}
else temp.length = 1024;
XinokSortImpl!(pred, Range).findRuns(arr, arr.length, temp);
return assumeSorted!(pred, Range)(arr);
}
/++ Generate compare functions from predicate
Example:
---
mixin Compares!("a > b");
---
++/
template Compares(alias pred){
static if(is(typeof(pred) : string)){
alias binaryFun!(pred) less;
alias binaryFun!(pred, "b", "a") greater;
alias not!(binaryFun!(pred)) greaterEqual;
alias not!(binaryFun!(pred, "b", "a")) lessEqual;
}
else static if(isCallable!pred){
alias pred less;
auto greater(T)(T a, T b){ return pred(b, a); }
auto greaterEqual(T)(T a, T b){ return !pred(a, b); }
auto lessEqual(T)(T a, T b){ return !pred(b, a); }
}
else static assert(false, "Invalid predicate");
}
/// Implementation of xinok sort for ranges
template XinokSortImpl(alias pred, Range){
static assert(isRandomAccessRange!Range && isBidirectionalRange!Range
&& hasSlicing!Range, Range.toString ~ " is incompatible with xinok sort");
alias typeof(Range[0]) T;
mixin Compares!pred;
/// Find runs in ascending or descending order and merge them
size_t findRuns(Range arr, size_t t, T[] temp){
enum min_run = 8;
if(arr.length <= min_run){
insertSort(arr);
return arr.length;
}
if(t > arr.length) t = arr.length;
// Find first run
size_t lef = 2;
if(lessEqual(arr[0], arr[1])){ // Ascending order
while(lef < arr.length && lessEqual(arr[lef-1], arr[lef])) ++lef;
}
else{ // Descending order
while(lef < arr.length && greater(arr[lef-1], arr[lef])) ++lef;
// reverse(arr[0..lef]);
auto tmp = arr[0..lef];
while(tmp.length >= 2){
swap(tmp.front, tmp.back);
tmp = tmp[1..$-1];
}
}
if(lef < min_run){ // Build run of min length
insertSort(arr[0..min_run]);
lef = min_run;
}
while(lef < t){ // Build run of length t
size_t rig = findRuns(arr[lef..$], lef, temp) + lef;
mergeRuns(arr[0..rig], arr[0..lef], arr[lef..rig], temp);
lef = rig;
}
return lef;
}
/// Merge together two sorted runs
void mergeRuns(Range arr, Range lef, Range rig, T[] temp){
assert(arr.length == lef.length + rig.length);
if(lef.length <= rig.length){
if(lef.length == 0) return; // Nothing to do
if(lef.length <= temp.length){ // Merge left to right
copy(lef, temp[0..lef.length]);
lef = temp[0..lef.length];
foreach(ref v; arr){
if(lessEqual(lef.front, rig.front)){
v = lef.front;
lef.popFront();
if(lef.empty) break;
}
else{
v = rig.front;
rig.popFront();
if(rig.empty) break;
}
}
if(!lef.empty) copy(lef, arr[$-lef.length .. $]);
}
else{ // Range Swap
if(lessEqual(lef.back, rig.front)) return; // Nothing to swap
size_t c;
{
// Binary search
size_t l = 0, u = lef.length - 1;
immutable off = lef.length - 1;
while(u - l > 1){
c = (u - l) / 2 + l;
if(greater(lef[c], rig[off-c])) u = c;
else l = c;
}
c = greater(lef[l], rig[off-l]) ? l : u;
// swapRanges(lef[c..$], rig[0..off-c+1]);
foreach(i, ref v; lef[c..$]) swap(v, rig[i]);
}
mergeRuns(lef, lef[0..c], lef[c..$], temp);
return mergeRuns(rig, rig[0..lef.length-c], rig[lef.length-c..$], temp);
}
}
else{
if(rig.length == 0) return; // Nothing to do
if(rig.length <= temp.length){ // Merge right to left
copy(rig, temp[0..rig.length]);
rig = temp[0..rig.length];
foreach_reverse(ref v; arr){
if(greaterEqual(rig.back, lef.back)){
v = rig.back;
rig.popBack();
if(rig.empty) break;
}
else{
v = lef.back;
lef.popBack();
if(lef.empty) break;
}
}
if(!rig.empty) copy(rig, arr[0..rig.length]);
}
else{ // Range Swap
if(lessEqual(lef.back, rig.front)) return; // Nothing to swap
size_t c;
{
// Binary search
size_t l = 0, u = rig.length - 1;
immutable off = lef.length - 1;
while(u - l > 1){
c = (u - l) / 2 + l;
if(less(rig[c], lef[off-c])) l = c;
else u = c;
}
c = less(rig[u], lef[off-u]) ? u : l;
// swapRanges(lef[off-c..$], rig[0..c+1]);
foreach(i, ref v; lef[off-c..$]) swap(v, rig[i]);
}
mergeRuns(rig, rig[0..c + 1], rig[c + 1..$], temp);
return mergeRuns(lef, lef[0..$-1-c], lef[$-1-c..$], temp);
}
}
}
/// A simple insert sort used for obtaining min_run
void insertSort(Range arr){
T o; size_t j;
for(size_t i = 1; i < arr.length; ++i) if(less(arr[i], arr[i-1])){
j = i; o = arr[j];
do{
arr[j] = arr[j-1];
--j;
} while(j >= 1 && less(o, arr[j-1]));
arr[j] = o;
}
}
}
/// Implementation of xinok sort for arrays
template XinokSortImpl(alias pred, T : T[]){
alias T[] Range;
mixin Compares!pred;
/// Find runs in ascending or descending order and merge them
size_t findRuns(Range arr, size_t t, T[] temp){
enum min_run = 8;
if(arr.length <= min_run){
insertSort(arr);
return arr.length;
}
if(t > arr.length) t = arr.length;
// Find first run
size_t lef = 2;
if(lessEqual(arr[0], arr[1])){ // Ascending order
auto p = arr.ptr + 2, e = arr.ptr + arr.length;
while(p < e && lessEqual(p[-1], *p)) ++p;
lef = p - arr.ptr;
}
else{ // Descending order
auto p = arr.ptr + 2, e = arr.ptr + arr.length;
while(p < e && greater(p[-1], *p)) ++p;
lef = p - arr.ptr;
// Reverse elements
e = arr.ptr; --p;
while(e < p) swap(*e++, *p--);
}
if(lef < min_run){ // Build run of min length
insertSort(arr[0..min_run]);
lef = min_run;
}
while(lef < t){ // Build run of length t
size_t rig = findRuns(arr[lef..$], lef, temp) + lef;
mergeRuns(arr[0..rig], arr[0..lef], arr[lef..rig], temp);
lef = rig;
}
return lef;
}
/// Merge together two sorted runs
void mergeRuns(Range arr, Range lef, Range rig, T[] temp){
assert(arr.length == lef.length + rig.length);
if(lef.length <= rig.length){
if(lef.length == 0) return; // Nothing to do
if(lef.length <= temp.length){ // Merge left to right
// copy(lef, temp[0..lef.length]);
temp[0..lef.length] = lef[];
T* p = arr.ptr;
T* l = temp.ptr, l_end = temp.ptr + lef.length;
T* r = rig.ptr, r_end = rig.ptr + rig.length;
while(true){
if(lessEqual(*l, *r)){
*p++ = *l++;
if(l >= l_end) break;
}
else{
*p++ = *r++;
if(r >= r_end) break;
}
}
while(l < l_end) *p++ = *l++;
}
else{ // Range Swap
if(lessEqual(lef[$-1], rig[0])) return; // Nothing to swap
size_t c;
{
// Binary search
size_t l = 0, u = lef.length - 1;
immutable off = lef.length - 1;
while(u - l > 1){
c = (u - l) / 2 + l;
if(greater(lef[c], rig[off-c])) u = c;
else l = c;
}
c = greater(lef[l], rig[off-l]) ? l : u;
// Swap elements
T* lp = lef.ptr + lef.length - 1;
T* rp = rig.ptr + (off - c);
T o;
while(rp >= rig.ptr){
o = *lp;
*lp = *rp;
*rp = o;
--lp; --rp;
}
}
mergeRuns(lef, lef[0..c], lef[c..$], temp);
return mergeRuns(rig, rig[0..lef.length-c], rig[lef.length-c..$], temp);
}
}
else{
if(rig.length == 0) return; // Nothing to do
if(rig.length <= temp.length){ // Merge right to left
// copy(rig, temp[0..rig.length]);
temp[0..rig.length] = rig[];
T* p = arr.ptr + arr.length - 1, l = lef.ptr + lef.length - 1, r =
temp.ptr + rig.length - 1;
while(true){
if(greaterEqual(*r, *l)){
*p-- = *r--;
if(r < temp.ptr) break;
}
else{
*p-- = *l--;
if(l < lef.ptr) break;
}
}
while(r >= temp.ptr) *p-- = *r--;
}
else{ // Range Swap
if(lessEqual(lef[$-1], rig[0])) return; // Nothing to swap
size_t c;
{
// Binary search
size_t l = 0, u = rig.length - 1;
immutable off = lef.length - 1;
while(u - l > 1){
c = (u - l) / 2 + l;
if(less(rig[c], lef[off-c])) l = c;
else u = c;
}
c = less(rig[u], lef[off-u]) ? u : l;
// Swap elements
T* lp = lef.ptr + lef.length - 1;
T* rp = rig.ptr + c;
T o;
while(rp >= rig.ptr){
o = *lp;
*lp = *rp;
*rp = o;
--lp; --rp;
}
}
mergeRuns(rig, rig[0..c + 1], rig[c + 1..$], temp);
return mergeRuns(lef, lef[0..$-1-c], lef[$-1-c..$], temp);
}
}
}
/// A simple insert sort used for obtaining min_run
void insertSort(Range arr){
T o; T* p;
foreach(c; arr.ptr + 1 .. arr.ptr + arr.length) if(less(*c, c[-1])){
p = c; o = *p;
do{
*p = p[-1];
--p;
} while(p > arr.ptr && less(o, p[-1]));
*p = o;
}
}
}
unittest{
// Predicate test
bool comp(uint a, uint b){ return a < b; }
with(Compares!comp){
assert(less(10, 20));
assert(lessEqual(10, 20));
assert(!greater(10, 20));
assert(!greaterEqual(10, 20));
assert(greater(20, 10));
assert(greaterEqual(20, 10));
assert(!less(20, 10));
assert(!lessEqual(20, 10));
assert(!less(10, 10));
assert(!greater(10, 10));
assert(lessEqual(10, 10));
assert(greaterEqual(10, 10));
}
}
unittest{
// Sort test
int[] arr = [2, 5, 8, 1, 4, 7, 3, 6, 9];
xinokSort(arr);
assert(arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]);
arr = [2, 5, 8, 1, 4, 7, 3, 6, 9];
xinokSort!("a > b")(arr);
assert(arr == [9, 8, 7, 6, 5, 4, 3, 2, 1]);
bool comp(int a, int b){ return a > b; }
arr = [2, 5, 8, 1, 4, 7, 3, 6, 9];
xinokSort!(comp)(arr);
assert(arr == [9, 8, 7, 6, 5, 4, 3, 2, 1]);
// Stability test
bool icmp(ubyte a, ubyte b){
if(a >= 'a') a -= 'a' - 'A';
if(b >= 'a') b -= 'a' - 'A';
return a < b;
}
ubyte[] str =
cast(ubyte[])"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".dup;
xinokSort!(icmp)(str);
assert(str == "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");
// CTFE test
int[] foo(){
int[] tmp = [20, 40, 60, 80, 10, 30, 50, 70, 90];
xinokSort(tmp);
return tmp;
}
//@ static assert(foo() == [10, 20, 30, 40, 50, 60, 70, 80, 90]);
}
All I want is compile and run this.
Everything is there, the unit test included. I thought that should have
been sufficient to be a runnable program.
Basically, if I type
PS E:\DigitalMars\dmd2\samples> rdmd --main xinoksort.d
Now it compiles and links without warning, and I get:
-a--- 16/04/2012 08:55 12600 xinoksort.d -a--- 16/04/2012 22:34 3621 xinoksort.d.deps -a--- 16/04/2012 22:34 13264 xinoksort.exe -a--- 16/04/2012 22:34 38763 xinoksort.obj
But running the exe crashes immediately at execution with "unauthorized instruction". Why ? Shouldn't it run, do nothing and quit nicely ?
And how do I execute the unit test ?
I'm sorry for all these questions, but it appears to be hard to find
these simple infos in the wiki and main website. I guess I'll update the
wiki to make it convenient to find them.
|
Permalink
Reply
