#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include "ppport.h"
#define isPenalty(sv) (SvROK(sv) && sv_derived_from(sv, "Text::KnuthPlass::Penalty"))
#define ivHash(hv, key) (IV)SvIV(*hv_fetch((HV*)hv, key, strlen(key), TRUE))
#define nvHash(hv, key) (NV)SvNVx(*hv_fetch((HV*)hv, key, strlen(key), TRUE))
#define debug(x)
typedef
SV * Text_KnuthPlass;
struct
Breakpoint_s {
struct
Breakpoint_s * prev;
struct
Breakpoint_s * next;
struct
Breakpoint_s * previous;
struct
Breakpoint_s * active;
NV demerits;
NV ratio;
IV line;
IV position;
IV fitness_class;
HV* totals;
};
typedef
struct
Breakpoint_s Breakpoint;
typedef
struct
LinkedList_s {
Breakpoint* head;
Breakpoint* tail;
IV list_size;
AV* to_free;
} LinkedList;
NV _compute_cost(Text_KnuthPlass self, IV start, IV end, Breakpoint* a,
IV current_line, AV* nodes) {
IV infinity = ivHash(self,
"infinity"
);
HV* sum = (HV*)SvRV(*hv_fetch((HV*)self,
"sum"
, 3, FALSE));
HV* totals = a->totals;
NV width = nvHash(sum,
"width"
) - nvHash(totals,
"width"
);
AV* linelengths = (AV*)SvRV(*hv_fetch((HV*)self,
"linelengths"
, 11, FALSE));
I32 ll = av_len(linelengths);
NV stretch = 0;
NV shrink = 0;
NV linelength = SvNV(*av_fetch(linelengths, current_line <= ll ? current_line-1 : ll, 0));
debug(warn(
"Computing cost from %i to %i\n"
, start, end));
debug(warn(
"Sum width: %f\n"
, nvHash(sum,
"width"
)));
debug(warn(
"Total width: %f\n"
, nvHash(totals,
"width"
)));
if
(isPenalty(*av_fetch(nodes, end, 0))) {
debug(warn(
"Adding penalty width\n"
));
width += nvHash(SvRV(*av_fetch(nodes,end, 0)),
"width"
);
}
debug(warn(
"Width %f, linelength %f\n"
, width, linelength));
if
(width < linelength) {
stretch = nvHash(sum,
"stretch"
) - nvHash(totals,
"stretch"
);
debug(warn(
"Stretch %f\n"
, stretch));
if
(stretch > 0) {
return
(linelength - width) / stretch;
}
else
{
return
infinity;
}
}
else
if
(width > linelength) {
debug(warn(
"Shrink %f\n"
, shrink));
shrink = nvHash(sum,
"shrink"
) - nvHash(totals,
"shrink"
);
if
(shrink > 0) {
return
(linelength - width) / shrink;
}
else
{
return
infinity;
}
}
else
{
return
0; }
}
HV* _compute_sum(Text_KnuthPlass self, IV index, AV* nodes) {
HV* result = newHV();
HV* sum = (HV*)SvRV(*hv_fetch((HV*)self,
"sum"
, 3, FALSE));
IV infinity = ivHash(self,
"infinity"
);
NV width = nvHash(sum,
"width"
);
NV stretch = nvHash(sum,
"stretch"
);
NV shrink = nvHash(sum,
"shrink"
);
I32 len = av_len(nodes);
I32 i = index;
while
(i < len) {
SV* e = *av_fetch(nodes, i, 0);
if
(sv_derived_from(e,
"Text::KnuthPlass::Glue"
)) {
width += nvHash(SvRV(e),
"width"
);
stretch += nvHash(SvRV(e),
"stretch"
);
shrink += nvHash(SvRV(e),
"shrink"
);
}
else
if
(sv_derived_from(e,
"Text::KnuthPlass::Box"
) ||
(isPenalty(e) && ivHash(SvRV(e),
"penalty"
) == -infinity
&& i > index)) {
break
;
}
i++;
}
hv_stores(result,
"width"
, newSVnv(width));
hv_stores(result,
"stretch"
, newSVnv(stretch));
hv_stores(result,
"shrink"
, newSVnv(shrink));
return
result;
}
Breakpoint* _new_breakpoint (
void
) {
Breakpoint* dummy;
HV* totals = newHV();
Newxz(dummy, 1, Breakpoint);
dummy->prev = dummy->next = dummy->previous = dummy->active = NULL;
dummy->demerits = dummy->ratio = 0;
dummy->line = dummy->position = dummy->fitness_class = 0;
hv_stores(totals,
"width"
, newSVnv(0));
hv_stores(totals,
"stretch"
, newSVnv(0));
hv_stores(totals,
"shrink"
, newSVnv(0));
dummy->totals = totals;
return
dummy;
}
void
free_breakpoint(Breakpoint* b) {
while
(b) {
Breakpoint* p = b->previous;
if
(SvROK(b->totals)) {
sv_free((SV*)b->totals);
Safefree(b);
}
b = p;
}
if
(b && b->totals) sv_free((SV*)b->totals);
if
(b) Safefree(b);
}
void
_unlinkKP(LinkedList* list, Breakpoint* a) {
if
(!a->prev) { list->head = a->next; }
else
{ a->prev->next = a->next; }
if
(!a->next) { list->tail = a->prev; }
else
{ a->next->prev = a->prev; }
list->list_size--;
av_push(list->to_free, newSViv((IV)a));
}
MODULE = Text::KnuthPlass PACKAGE = Text::KnuthPlass
void
_init_nodelist(self)
Text_KnuthPlass self
CODE:
LinkedList* activelist;
Newxz(activelist, 1, LinkedList);
activelist->head = activelist->tail = _new_breakpoint();
activelist->list_size = 1;
activelist->to_free = newAV();
hv_stores((HV*)self,
"activeNodes"
, ((IV)activelist));
void
_active_to_breaks(self)
Text_KnuthPlass self
PREINIT:
LinkedList* activelist;
Breakpoint* b;
Breakpoint* best = NULL;
PPCODE:
activelist = (LinkedList*)(*hv_fetch((HV*)self,
"activeNodes"
, 11, FALSE));
for
(b = activelist->head; b; b = b->next) {
if
(!best || b->demerits < best->demerits) best = b;
}
while
(best) {
HV* posnode = newHV();
hv_stores(posnode,
"position"
, newSViv(best->position));
hv_stores(posnode,
"ratio"
, newSVnv(best->ratio));
XPUSHs(sv_2mortal(newRV((SV*)posnode)));
best = best->previous;
}
void
_cleanup(self)
Text_KnuthPlass self
CODE:
Breakpoint* b;
LinkedList* activelist;
activelist = (LinkedList*)(*hv_fetch((HV*)self,
"activeNodes"
, 11, FALSE));
return
;
b = activelist->head;
while
(b) {
Breakpoint* n = b->next;
free_breakpoint(b);
b = n;
}
while
(av_len(activelist->to_free)) {
SV* pointer = av_shift(activelist->to_free);
if
((Breakpoint*)SvIV(pointer))
free_breakpoint((Breakpoint*)SvIV(pointer));
sv_free(pointer);
}
sv_free((SV*)activelist->to_free);
void
_mainloop(self, node, index, nodes)
Text_KnuthPlass self
SV* node
IV index
AV* nodes
CODE:
LinkedList* activelist = (LinkedList*)(*hv_fetch((HV*)self,
"activeNodes"
, 11, FALSE));
IV tolerance = ivHash(self,
"tolerance"
);
IV infinity = ivHash(self,
"infinity"
);
SV* demerits_r = *hv_fetch((HV*)self,
"demerits"
, 8, FALSE);
NV ratio = 0;
IV nodepenalty = 0;
NV demerits = 0;
IV linedemerits = 0, flaggeddemerits = 0, fitnessdemerits = 0;
Breakpoint* candidates[4];
NV badness;
IV current_line = 0;
HV* tmpsum;
IV current_class = 0;
Breakpoint* active = activelist->head;
Breakpoint* next;
if
(demerits_r && SvRV(demerits_r)) {
linedemerits = ivHash(SvRV(demerits_r),
"line"
);
flaggeddemerits = ivHash(SvRV(demerits_r),
"flagged"
);
fitnessdemerits = ivHash(SvRV(demerits_r),
"fitness"
);
}
else
{
croak(
"Demerits hash not properly set!"
);
}
if
(isPenalty(node)) {
nodepenalty = SvIV(*hv_fetch((HV*)SvRV(node),
"penalty"
, 7, TRUE));
}
while
(active) {
int
t;
candidates[0] = NULL; candidates[1] = NULL;
candidates[2] = NULL; candidates[3] = NULL;
debug(warn(
"Outer\n"
));
while
(active) {
next = active->next;
IV position = active->position;
debug(warn(
"Inner loop\n"
));
current_line = 1+ active->line;
ratio = _compute_cost(self, position, index, active, current_line, nodes);
debug(warn(
"Got a ratio of %f\n"
, ratio));
if
(ratio < 1 || (isPenalty(node) && nodepenalty == -infinity))
_unlinkKP(activelist, active);
if
(-1 <= ratio && ratio <= tolerance) {
SV* nodeAtPos = *av_fetch(nodes, position, FALSE);
badness = 100 * ratio * ratio * ratio;
debug(warn(
"Badness is %f\n"
, badness));
if
(isPenalty(node) && nodepenalty > 0) {
demerits = linedemerits + badness + nodepenalty;
}
else
if
(isPenalty(node) && nodepenalty != -infinity) {
demerits = linedemerits + badness - nodepenalty;
}
else
{
demerits = linedemerits + badness;
}
demerits = demerits * demerits;
if
(isPenalty(node) && isPenalty(SvRV(nodeAtPos))) {
demerits = demerits + (flaggeddemerits *
ivHash(node,
"flagged"
) *
ivHash(SvRV(nodeAtPos),
"flagged"
));
}
if
(ratio < -0.5) current_class = 0;
else
if
(ratio <= 0.5) current_class = 1;
else
if
(ratio <= 1) current_class = 2;
else
current_class = 3;
if
(
abs
(current_class - active->fitness_class) > 1)
demerits += fitnessdemerits;
demerits += active->demerits;
if
(!candidates[current_class] ||
demerits < candidates[current_class]->demerits) {
debug(warn(
"Setting c %i\n"
, current_class));
if
(!candidates[current_class])
candidates[current_class] = _new_breakpoint();
candidates[current_class]->active = active;
candidates[current_class]->demerits = demerits;
candidates[current_class]->ratio = ratio;
}
}
active = next;
if
(!active || active->line >= current_line)
break
;
}
debug(warn(
"Post inner loop\n"
));
for
(t = 0; t <= 3; t++) {
if
(candidates[t]) {
Breakpoint* newnode = _new_breakpoint();
HV* tmpsum = _compute_sum(self, index, nodes);
newnode->position = index;
newnode->fitness_class = t;
newnode->totals = tmpsum;
debug(warn(
"Setting previous to %p\n"
, candidates[t]->active));
newnode->previous = candidates[t]->active;
newnode->demerits = candidates[t]->demerits;
newnode->ratio = candidates[t]->ratio;
newnode->line = candidates[t]->line + 1;
if
(active) {
debug(warn(
"Before\n"
));
newnode->prev = active->prev;
newnode->next = active;
if
(!active->prev) { activelist->head = newnode; }
else
{ active->prev->next = newnode; }
active->prev = newnode;
activelist->list_size++;
}
else
{
debug(warn(
"After\n"
));
if
(!activelist->head) {
activelist->head = activelist->tail = newnode;
newnode->prev = newnode->next = NULL;
}
else
{
newnode->prev = activelist->tail;
newnode->next = NULL;
activelist->tail->next = newnode;
activelist->tail = newnode;
activelist->list_size++;
}
}
sv_free((SV*)candidates[t]->totals);
Safefree(candidates[t]);
}
}
}