Hello all, I have just seen this message, having come back from annual leave. I have tried reading the generated PDF with xpdf and re-generated it from the LaTeX source and (again) reading it with xpdf , without seeing anything that indicates a broken PDF (that is, what I see displayed as the document matches what I expect). I have attached the PDF I just generated. If that, too, is broken, I am more than happy trying to figure out a solution. On Thu, Nov 22, 2012 at 8:12 PM, Pascal Costanza <pc@p-cos.net> wrote:

Hi Ingvar,

I got a report that the PDF you provided is broken. This is indeed the case. If I try to regenerate the PDF from the TeX source, I still get a broken output. Could you try to fix this?

Thanks, Pascal

On 22 Nov 2012, at 17:34, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

...

Hi

The PDF is broken.

We need a fixed spec to properly discuss it.

MA

On Nov 20, 2012, at 20:55 , Pascal Costanza <pc@p-cos.net> wrote:

...

The document "Generic extendable heaps for Common Lisp" has been submitted by Ingvar Mattsson and has been accepted as CDR document 12. According to the CDR process, this document is now in its initial stage and will be finalized on January 1, 2012, unless withdrawn by the author beforehand. See http://cdr.eurolisp.org/document/12/ for the details of this document.

-- Pascal Costanza

_______________________________________________ cdr-announce mailing list cdr-announce@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-announce

-- Marco Antoniotti

_______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Pascal Costanza

Ok. Seen the mishap. You have \subsubsection(MACRO declare-heap) Instead of \subsubsection{MACRO declare-heap} The '>' in TeX text mode are still broken. MA On Dec 3, 2012, at 16:43 , Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

Hi

the PDF is still broken. In general it fumbles on the usual suspects '>' etc. and is becomes seriously confused at "MACRO declare-heap".

Cheers -- MA

On Dec 3, 2012, at 10:59 , Ingvar Mattsson <ingvar@google.com> wrote:

...

Hello all,

I have just seen this message, having come back from annual leave. I have tried reading the generated PDF with xpdf and re-generated it from the LaTeX source and (again) reading it with xpdf , without seeing anything that indicates a broken PDF (that is, what I see displayed as the document matches what I expect).

I have attached the PDF I just generated. If that, too, is broken, I am more than happy trying to figure out a solution.

On Thu, Nov 22, 2012 at 8:12 PM, Pascal Costanza <pc@p-cos.net> wrote: Hi Ingvar,

I got a report that the PDF you provided is broken. This is indeed the case. If I try to regenerate the PDF from the TeX source, I still get a broken output. Could you try to fix this?

Thanks, Pascal

On 22 Nov 2012, at 17:34, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

...

Hi

The PDF is broken.

We need a fixed spec to properly discuss it.

MA

On Nov 20, 2012, at 20:55 , Pascal Costanza <pc@p-cos.net> wrote:

...

The document "Generic extendable heaps for Common Lisp" has been submitted by Ingvar Mattsson and has been accepted as CDR document 12. According to the CDR process, this document is now in its initial stage and will be finalized on January 1, 2012, unless withdrawn by the author beforehand. See http://cdr.eurolisp.org/document/12/ for the details of this document.

-- Pascal Costanza

_______________________________________________ cdr-announce mailing list cdr-announce@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-announce

-- Marco Antoniotti

_______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Pascal Costanza

<cl-genheap.pdf>

-- Marco Antoniotti

-- Marco Antoniotti

Hi, Thanks a lot for the fix. I have uploaded the new version to the CDR repository. Pascal On 3 Dec 2012, at 16:59, Ingvar Mattsson <ingvar@google.com> wrote:

Ah. When I saw "broken PDF", I was thinking a PDF that wasn't machine-readable, rather than human-readable. I am sorry about the confusion.

Fixed source doc and PDF attached.

On Mon, Dec 3, 2012 at 3:48 PM, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote: Ok. Seen the mishap.

You have

\subsubsection(MACRO declare-heap)

Instead of

\subsubsection{MACRO declare-heap}

The '>' in TeX text mode are still broken.

MA

On Dec 3, 2012, at 16:43 , Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

...

Hi

the PDF is still broken. In general it fumbles on the usual suspects '>' etc. and is becomes seriously confused at "MACRO declare-heap".

Cheers -- MA

On Dec 3, 2012, at 10:59 , Ingvar Mattsson <ingvar@google.com> wrote:

...

Hello all,

I have just seen this message, having come back from annual leave. I have tried reading the generated PDF with xpdf and re-generated it from the LaTeX source and (again) reading it with xpdf , without seeing anything that indicates a broken PDF (that is, what I see displayed as the document matches what I expect).

I have attached the PDF I just generated. If that, too, is broken, I am more than happy trying to figure out a solution.

On Thu, Nov 22, 2012 at 8:12 PM, Pascal Costanza <pc@p-cos.net> wrote: Hi Ingvar,

I got a report that the PDF you provided is broken. This is indeed the case. If I try to regenerate the PDF from the TeX source, I still get a broken output. Could you try to fix this?

Thanks, Pascal

On 22 Nov 2012, at 17:34, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

...

Hi

The PDF is broken.

We need a fixed spec to properly discuss it.

MA

On Nov 20, 2012, at 20:55 , Pascal Costanza <pc@p-cos.net> wrote:

...

The document "Generic extendable heaps for Common Lisp" has been submitted by Ingvar Mattsson and has been accepted as CDR document 12. According to the CDR process, this document is now in its initial stage and will be finalized on January 1, 2012, unless withdrawn by the author beforehand. See http://cdr.eurolisp.org/document/12/ for the details of this document.

-- Pascal Costanza

_______________________________________________ cdr-announce mailing list cdr-announce@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-announce

-- Marco Antoniotti

_______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Pascal Costanza

<cl-genheap.pdf>

-- Marco Antoniotti

-- Marco Antoniotti

<cl-genheap.pdf><cl-genheap.tex>_______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Pascal Costanza

On Dec 9, 2012, at 21:31 , Nick Levine <ndl@ravenbrook.com> wrote:

1. Typo "devbelopers" for "developers".

2. Maybe I'm just dim, but I really don't understand what this is about. The functional interface looks like that of a queue (or a stack, depending on whether insert and remove work on the same end as each other or not). Can you explain? give a couple of examples?

A "Heap" is also known as a "Priority Queue". So the interface must be similar. I have nothing against this (*), although the spec leaves out a few corner cases. E.g., what happens when the keys are equal, but the values/content associated are not? Apart from that, I do not understand the use of DECLARE-HEAP and I believe that there should be no provisions to define a package for these sort of data structures. Or better: I believe a discussion about how to structure packages and libraries should be started. But this is an old pet peeve of mine. Finally, and maybe much more critical, a key operation on Heaps is REDUCE-KEY (to use the now standard CLR terminology). Without it you cannot implement Dijkstra SSSP algorithm. Problem is, this operation assumes the presence of "fingers" (read: "pointers") in the heap, not an easy thing to "librarize". all the best -- Marco Antoniotti (*) Full disclosure: a priority queue implementation by yours truly has been floating around for about 20 years now :)

Dear all, I believe that the document as it is is insufficient as a specification for a HEAP/PRIORITY-QUEUE data structure in CL. I have several suggestions about how to proceed and change it. If Ingvar agrees I can just go ahead and make the changes to the main LaTeX. All the best -- MA On Dec 10, 2012, at 13:55 , Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

On Dec 10, 2012, at 11:49 , Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

...

On Dec 9, 2012, at 21:31 , Nick Levine <ndl@ravenbrook.com> wrote:

...

1. Typo "devbelopers" for "developers".

2. Maybe I'm just dim, but I really don't understand what this is about. The functional interface looks like that of a queue (or a stack, depending on whether insert and remove work on the same end as each other or not). Can you explain? give a couple of examples?

A "Heap" is also known as a "Priority Queue". So the interface must be similar.

I have nothing against this (*), although the spec leaves out a few corner cases. E.g., what happens when the keys are equal, but the values/content associated are not?

Apart from that, I do not understand the use of DECLARE-HEAP and I believe that there should be no provisions to define a package for these sort of data structures. Or better: I believe a discussion about how to structure packages and libraries should be started. But this is an old pet peeve of mine.

Finally, and maybe much more critical, a key operation on Heaps is REDUCE-KEY (to use the now standard CLR terminology). Without it you cannot implement Dijkstra SSSP algorithm. Problem is, this operation assumes the presence of "fingers" (read: "pointers") in the heap, not an easy thing to "libraries".

Of course, I wrote the above just before double checking the last CLR edition. :) The operation in question is INCREASE-KEY (depends on whether you have a MAX or MIN Heap); DECREASE-KEY is instead mentioned in the chapter about SSSP problems. :)

Oh well.

-- Marco Antoniotti

_______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Marco Antoniotti

Hi, If you indeed intend to withdraw the submission, you have to tell me in time. The default is to finalize the document if I don't hear otherwise… Best, Pascal On 14 Dec 2012, at 11:19, Ingvar Mattsson <ingvar@google.com> wrote:

On Mon, Dec 10, 2012 at 10:49 AM, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

On Dec 9, 2012, at 21:31 , Nick Levine <ndl@ravenbrook.com> wrote:

...

1. Typo "devbelopers" for "developers".

2. Maybe I'm just dim, but I really don't understand what this is about. The functional interface looks like that of a queue (or a stack, depending on whether insert and remove work on the same end as each other or not). Can you explain? give a couple of examples?

A "Heap" is also known as a "Priority Queue". So the interface must be similar.

I have nothing against this (*), although the spec leaves out a few corner cases. E.g., what happens when the keys are equal, but the values/content associated are not?

That is unclear in the specification. The example implementations would do different things depending on if you use something that is (essentially) "less than" or "less than or equal" (in the former case, they'd not re-order the equal values whenever there's an operation on the queue, in the latter case, they would).

Apart from that, I do not understand the use of DECLARE-HEAP and I believe that there should be no provisions to define a package for these sort of data structures. Or better: I believe a discussion about how to structure packages and libraries should be started. But this is an old pet peeve of mine.

That is definitely something that is worth discussing. The main reason fro submitting GENHEAP is that I didn't see anything similar and, well, I did submit GENHASH back in the early days of CDRs. If people are, generally, hesitant, I am more than happy to withdraw the submission.

The main reason for DECLARE-HEAP is to allow for the example implementation that defines all underlying operations in terms of methods on a specialized class to be easily created on "this is the type of heap I want" rather than on the first creation. _______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Pascal Costanza

OK, I will change the state to "withdrawn." Thanks, Pascal On 27 Dec 2012, at 09:00, Ingvar Mattsson <ingvar@google.com> wrote:

I think withdrawing the proposal, for now, pending time to augment it with Marco's suggestions.

On Mon, Dec 24, 2012 at 7:31 PM, Pascal Costanza <pc@p-cos.net> wrote: Hi,

If you indeed intend to withdraw the submission, you have to tell me in time. The default is to finalize the document if I don't hear otherwise…

Best, Pascal

On 14 Dec 2012, at 11:19, Ingvar Mattsson <ingvar@google.com> wrote:

...

On Mon, Dec 10, 2012 at 10:49 AM, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

On Dec 9, 2012, at 21:31 , Nick Levine <ndl@ravenbrook.com> wrote:

...

1. Typo "devbelopers" for "developers".

2. Maybe I'm just dim, but I really don't understand what this is about. The functional interface looks like that of a queue (or a stack, depending on whether insert and remove work on the same end as each other or not). Can you explain? give a couple of examples?

A "Heap" is also known as a "Priority Queue". So the interface must be similar.

I have nothing against this (*), although the spec leaves out a few corner cases. E.g., what happens when the keys are equal, but the values/content associated are not?

That is unclear in the specification. The example implementations would do different things depending on if you use something that is (essentially) "less than" or "less than or equal" (in the former case, they'd not re-order the equal values whenever there's an operation on the queue, in the latter case, they would).

Apart from that, I do not understand the use of DECLARE-HEAP and I believe that there should be no provisions to define a package for these sort of data structures. Or better: I believe a discussion about how to structure packages and libraries should be started. But this is an old pet peeve of mine.

That is definitely something that is worth discussing. The main reason fro submitting GENHEAP is that I didn't see anything similar and, well, I did submit GENHASH back in the early days of CDRs. If people are, generally, hesitant, I am more than happy to withdraw the submission.

The main reason for DECLARE-HEAP is to allow for the example implementation that defines all underlying operations in terms of methods on a specialized class to be easily created on "this is the type of heap I want" rather than on the first creation. _______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Pascal Costanza

_______________________________________________ cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

-- Pascal Costanza