I'm looking for an algorithm that converts a list of integers (for instance of pages to be printed) from this form:
I'm looking for an algorithm that converts a list of integers (for instance of pages to be printed) from this form:
1,2,3,4,6,7,8,13,14
into
1-4,6-8,13-14
and back.
My Google foo fails me as I get to way too complex stuff like http://stackoverflow.com/questions/283299/best-compression-algorithm-for-a-sequence-of-integers
Anybody having something like this lying around?
http://stackoverflow.com/questions/283299/best-compression-algorithm-for-a-sequence-of-integers
1,2,3,4,6,7,8,13,14
into
1-4,6-8,13-14
and back.
My Google foo fails me as I get to way too complex stuff like http://stackoverflow.com/questions/283299/best-compression-algorithm-for-a-sequence-of-integers
Anybody having something like this lying around?
http://stackoverflow.com/questions/283299/best-compression-algorithm-for-a-sequence-of-integers
Don't have it right now, but you can just sort the integers and iterate to "compress", should be a matter of two nested loops.
ReplyDeleteFor the reverse, parse and add the ranges (one loop with two PosEx) , then sort and remove duplicates (assuming there is user input, so ranges may not be in order and may overlap, and you don't want that).
http://Tastings.DelimitedTextand
See e.g. function GetBitCSV() and SetBitCSV() in github.com - mORMot or the CleverReadInteger() and the associated compression techniques in the same unit. For instance, a .map file is read and highly compressed in memory thanks to those "clever' encoding.
ReplyDeleteBecause it's friday, here's my most inefficient version: http://paste.ie/view/7698f058
ReplyDeleteThis is probably you are looking for:
ReplyDeleteType
TRangeElment = record
StartRange, CloseRange: Integer;
end;
function Compress(const Data: TArray): TArray;
Var
Range: TRangeElment;
i : Integer;
procedure CloseRange(Value: Integer);
begin
SetLength(Result, Length(Result) + 1);
Range.CloseRange := Value;
Result[Length(Result) - 1] := Range;
end;
begin
for i := 0 to Length(Data) - 1 do begin
if (i = 0) then begin
Range.StartRange := Data[i];
end else if Data[i] > (Data[i-1] + 1) then begin
CloseRange(Data[i-1]);
Range.StartRange := Data[i];
end;
end;
CloseRange(Data[Length(Data)-1]);
end;
What is actually a problem here? Just write the code ... it is trivial.
ReplyDeleteDidn't think about user input in the round-trip stage... so, because this is saturday, an even more inefficient, but more flexible, version: http://paste.ie/view/db4c0678
ReplyDeletePrimož Gabrijelčič That's not the Stack Overflow spirit!
ReplyDeleteIIRC what I have somewhere (can check Monday) some of the SO answers are a bit on the over-engineered side if you just want to go between string and array/list of integers.
ReplyDeleteAs Primož Gabrijelčič hints, this is a matter of a handful of lines of code (unless you have a hidden difficulty Jeroen Wiert Pluimers, like the full Int32 or Int64 range? Or some other memory/streaming considerations?)
ReplyDeleteEric Grange basically parsing/generating the page ranges in a printing dialog.
Asbjørn Heid thanks a lot, I think that's exactly what I wanted.
I might add the `3` and `3` options later (so people can omit the first and large page number) later.
Need to pack for a marching band event in Belgium. If anyone is near to "De Panne": it's gonna be nice weather tomorrow (: http://www.dekust.be/nl/agenda/taptoe-de-panne-0
Jeroen Wiert Pluimers Should be easy enough, just modify the Range.FromString.
ReplyDeleteSince the input is from a user, I can easily imagine issues which make clean handling non-trivial. It's not rocket science, but needs some care to handle the things a user can do to you.
ReplyDeleteFor a starter: the input field will only allow digits, comma's and hyphens.
ReplyDeleteJeroen Wiert Pluimers Which means, I assume, that unlike the example, the input may contain ranges, as well.
ReplyDeleterosettacode.org - Range extraction - Rosetta Code
ReplyDeleteBill Meyer The first list is what the program has internally (a list of pages to print), the second list is what's presented to the user and which can be edited by the user.
ReplyDeleteJeroen Wiert Pluimers then I guess you mostly have to constraint the range expansion to the valid page ranges, just to avoid embarrassment if someone's fingers slip like in "1-999999999" :)
ReplyDeleteAsbjørn Heid Thanks again for all your work. I've cleaned it up a bit, split it in two units and wrote unit tests. It won't work with Int64 or UInt64 (compiler bug) and for negative Integer values I've some unit tests that fail and I will make working one day, but in short: it's great code.
ReplyDeleteI am intrigued by the "Functional = record" type, especially about the _1 and _2 parameters of type BindArg1 and BindArg2. My feeling is that they are from a bigger piece as right now you can just do without them.
Care to elaborate a bit?
As soon as I've done some more cleanup I'll get it online in my bitbucket repository. Link will follow later.
Jeroen Wiert Pluimers I use the _1 but not the _2. You're correct that it was copypasta'd from my library code.
ReplyDeleteThe idea behind Bind is to transform a function f with M parameters to a function g with N parameters, where N < M, by supplying fixed values for M-N parameters of f.
In the sample code I posted, I use it to turn the function ReplaceStr into a new function which only takes a single parameter that replaces all spaces with an empty string. The new function does so by passing the (remaining) parameter to ReplaceStr, and by fixing the "old pattern" and "new pattern" parameters to space and empty string respectively.
In order to do this in general, I need to know which parameters that one wants to fix, and which ones should remain as regular parameters.
The idea is that the BindArg1 and BindArg2 types are used with overloading to select which permutation to use. Since _1 is of type BindArg1 and _2 is of type BindArg2, they can be used to perform this selection. They then act as placeholders to indicate which parameter is passed on to which parameter in the bound function. So _1 represents the first parameter of the new function (our "g"), and _2 the second. Where they're put in the Bind() call dictates how they're passed to the original function (our "f"). This allows you to reverse the parameter order for example and similar.
In my library code, I have all possible permutations, but I ripped them out for the sample here, and I forgot to remove _2 which is not used.
It is directly inspired by Boost.Bind[1], which turned into std::bind().
Yes it's overkill but since it was weekend I just wanted to show off a slightly different style of coding than what many Delphi folks may be used to.
[1]: http://www.boost.org/doc/libs/1_62_0/libs/bind/doc/html/bind.html
Jeroen Wiert Pluimers So just to be clear, everything above "type Range = record" is trimmed pasta from my library :)
ReplyDeleteAsbjørn Heid Thanks for the explanation. You've a remarkable library!
ReplyDeleteJeroen Wiert Pluimers Thanks, it's just something I cobble together trying to make my life easier at work :)
ReplyDeleteAsbjørn Heid
ReplyDelete"The idea behind Bind is to transform a function f with M parameters to a function g with N parameters, where N < M, by supplying fixed values for M-N parameters of f."
I believe in functional programming they call this "partial functions". It can be very useful when you've got functions you're calling with the same parameters over and over again.
It's on my (long) list of things the Delphi standard library needs to make people's lives easier.
Joseph Mitzen Asbjørn Heid it would be cool if someone could contribute something like this to Spring4D.
ReplyDeleteJoseph Mitzen Ah yes. I've never really learned functional programming in a FP language, but I do like many of the concepts when using them in C++ or Python.
ReplyDeleteJeroen Wiert Pluimers I could provide a pull request if Stefan Glienke feels it fits.
ReplyDeleteAsbjørn Heid the commit with unit tests, support for negative numbers and all integral number types (except Int64/UInt64: those two only for 10.1 Berlin): https://bitbucket.org/jeroenp/besharp.net/commits/7205b070a4e6457675a083b78d26659da506fc08
ReplyDeleteJeroen Wiert Pluimers Cool, I'll check it out.
ReplyDeleteAsbjørn Heid Python is where I first saw partial functions. They go really well with named/optional parameters, which is on my Top 5 list of small things that could be added to the language that would really make it cleaner / easier to use. I brought up named parameters a few days ago on the EMBT forum but so far I've been too scared to go back there and read what the old guard had to say in response. :-(
ReplyDeleteBy the way, fantastic job implementing something like this in Delphi!