LZP - metoda kompresji

Jeśli kiedyś będziecie potrzebowali wiedzieć jak działa algorytm LZP, to na coraz bardziej niezawodnej Wikipedii znajdziecie. Dla stron polskich G**gle zwraca 10 stron na krzyż.

Bylejakość

Na pewnej popularnej stronie dla programistów czytamy (przez litość nie podaję linku):

Krzywa Beziera to krzywa wielomianowa trzeciego stopnia, czyli taka która może być definiowana za pomocą trzech wielomianów (odpowiednio dla współrzędnych x, y i z) z pewnym parametrem t.

Ludzie, co za kosmiczne bzdury! Wielomianowa krzywa Beziera nie ma ograniczonego stopnia, stopień wielomianów może być dowolny. Sama zaś krzywa Beziera jest krzywą parametryczną.

Z tego tekstu wynika, że liczba wielomianów potrzebnych do określenia krzywej jest równa stopniu wielomianu -- tak oczywiście nie jest. Liczba wielomianów zależy od liczby wymiarów przestrzeni w której określana jest krzywa, wielomiany mogą być dowolnego stopnia; np. można mieć krzywą przestrzenną (czyli 3 wielomiany) ale wielomiany stopnia 125.

Dalej, co to znaczy "wielomiany z pewnym parametrem"? Ja pamiętam jeszcze ze szkoły średniej zadania w rodzaju "dla jakiego parametru c wielomian jakiśtam nie ma pierwiastków", ale tutaj rzecz jasna nie chodzi o to. Mowa oczywiście o wielomianach jednej zmiennej, zwyczajowo argument jest tutaj oznaczany literką 't', a nie 'x' jak się przyzwyczailiśmy.

Dalej jest jeszcze jeden cymes:

Krzywe trzeciego stopnia są również krzywymi najniższego stopnia, które nie leżą w jednej płaszczyźnie w 3D.

Czyli, że co -- nie można określić w przestrzeni krzywej trzeciego stopnia, która leżałaby na płaszczyźnie? (Odpowiedź brzmi oczywiście: nie, na całe szczęście można). A poza tym "w jednej płaszczyźnie" -- ale z czym? Bez sensu kompletnie. O co więc chodzi: krzywa 3-stopnia opisywana jest 4 punktami kontrolnymi, i taka liczba punktów może być niewspółpłaszczyznowa, a co za tym idzie krzywa nie będzie płaska.

Dlaczego o tym piszę? Bo razi mnie taka bylejakość, a poza tym lubię się czasem przypieprzyć; na Wikipedii taki tekst by chyba na pewno nie przeszedł (z resztą mamy na wiki całkiem nieźle opracowany temat krzywych i powierzchni Beziera).

27.08.2008 - dwie drobne poprawki

Wrap me!

Inheritance is fundamental way of creating new types in OOP. Apart of this, there is another important technique: composition, using many object to create higher level objects that provide interface to selected members of component objects. Inheritance is supported by many languages at syntax level, composition -- not!

Consider simple (real-world) example: we have GUI objects -- static label, and list box, we want another widget, labeled list box, a composition of these two simple widgets. We have to write tons of wrappers, that just call label or list methods. Here is example (C++):

class Label {
 public:
  void set_text(string s);
  string get_text();
};


class ListBox {
 public:
  void   clear();
  int    add_item(string s, bool uppercase);
  string get_item(int index);
};


class LabeledListBox {
 public:
  void   set_label(string s) {label.set_text(s);}
  string get_label() {return label.get_text();}

  void   clear() {box.clear();}
  int    add_item(string s) {return box.add_item(s, false);}
  int    add_item_uppercase(string s) {return box.add_item(s, true);}
  string get_item(int index) {return box.get_item(inex);}
 private:
  Label label;
  ListBox box;

};

Of course C++ compiler is able to inline LabeledListBox methods, but programmer have to write many lines of code that merely call another methods. He must know types of arguments, returned values and other. And if some class is changed, he must update classes that use this one. He must maintain all these stupid wrappers. Wrappers are evil.

Wrappers are so frequently used in programming, that I'm still don't know why syntax of popular languages do not reflect this state. This is my view of syntax, but I hope shows the intention -- simple things should remain simple on screen:

class LabeledListBox {
 public:
  method set_label is label.set_text; // rename
  method get_label is label.get_text; // rename

  method clear, get_item from box; // publish two methods of box object
  method add_item is box.add_item with uppercase=false;  // create simple wrappers
  method add_item_upperacase is box.add_item with uppercase=true; // with default arguments set to const

 private:
  Label label;
  ListBox box;
};

Coroutines in C++

What a surprise, there is a portable library for coroutines written 9 years ago by Keld Helsgaun.

Today I compiled some examples using gcc (MinGW) and seems to work! Great! I will try to explore this library and show some additional examples.

More constraints, please

In C++ classes have public, protected and private members. Variable member can be also declared as const or static const and it make such member read-only.

But it would be really great if we can select level of protection, and declare that some variable is const only when accessed at public or protected level. Here is a sample:

class C1 { // C++ - present
 public:
  void foo_x() { /* do some magic with x */ x = 5; }
  int get_x() const { return x;}

 private:
  int x;
};

class C2 { // C++ - future?
 public:
  void foo_x() { /* do some magic with x */ x = 5; }
 
 public const:
  int x;
}

Member x can be freely read/write within C2 member functions, but when accessed from outside, x is read only.

This is not as powerful as Borland's extension __property, which allow to declare property as alias for member variable, or setup getter/setter for a property. However I think proposed extension wouldn't bring much work for compilers authors.

With C++

C++ has lack of everything useful, you won't find local functions for example. But I really miss Pascal with statement. I know people say that would confuse programmer or even compiler. Wait! Pascal programmers were not confused, Pascal compilers were able to deal with this. Moreover, C++ programmers are not confused with tons of nested name spaces, crazy visibility rules and other odds.

Here is a snippet from my program:

for (unsigned i=0; i < data.measure_dist.size(); i++)
  if (data.measure_dist[i].active)
     find_crosspoints(
         data.measure_dist[i].point_1,
         data.measure_dist[i].point_2,
         outline,
         data.measure_dist[i].crosspoints
     );

Using with would make this much clearer:

for (unsigned i=0; i < data.measure_dist.size(); i++)
  with (data.measure_dist[i]) {
     if (active)
         find_crosspoints(point_1, point_2, outline, crosspoints);
  }

Does anybody confused about this code? Does anybody don't know what above code do? I don't think so.

Lets continue. With could also accept more complex syntax and allow temporary rename different entities. This (inefficient!) code finds all intersection between two sets of segments:

double u, v; // parameters, lerp(A, B, u) = A + u*(B-A)
for (int i=0; i < data.points.inner.size() - 1; i++)
  for (int j=0; j < data.points.outer.size() - 1; j++) {
      bool b = intersection(
          data.outline.inner[i],
          data.outline.inner[i+1],
          data.outline.outer[j],
          data.outline.outer[j+1],
          u, v);

      if (b)
          crosspoints.add(lerp(data.outline.inner[i], data.outline.inner[i+1], u));
  }

Now compare with following code:

double u, v;
with (data.points) {
  with (inner as A, outer as B) {
      for (int i=0; i < A.size() - 1; i++)
          for (int j=0; j < B.size() - 1; j++)
              if (intersection(A[i], A[i+1], B[i], B[i+1]))
                  crosspoints.add(lerp(A[i], A[i+1], u));
      }
}

Code is easier, cleaner, compacted. In next posts I will show some other ideas.

demoscene.tv

For a years I was big fan of demoscene. When I was young, demos and intros (some watched over and over, like "Jizz" by TBL) pushed me to learn many new things; moreover I still like to listen demoscene music; for example tracks from music disc "Ambrozia" released by group Pulse around 10 years ago still sound nice.

Now youtube is full of old and new demos uploaded by Good People. But on the net there are Much Better Good People, who created http://demoscene.tv - you can watch demos in high quality, yeah. BTW I love "Photon" by Purple.