Здравствуйте, greenpci, Вы писали:
К>>"Выпуклая оболочка", дорогой Ватсон!
G>да, правильно. Я представлял что выпуклый корпус (hull — the body or frame of a ship, most of which goes under the water (Cambridge Dictionary), но оболочка гораздо лучше.
Это не просто гораздо лучше, это соответствует общепринятой русской терминологии.
G>...
К>>Есть ряд моментов, которые стоит отшлифовать.
К>>1. Странное разбиение на файлы:
К>>- исключение в common.h, почему бы не в ch_exception.h?
К>>- SharedPoint опять в common.h, тогда как PointVector и SharedPointVector — в point.h, а PointList и SharedPointList — в convex_hull.h
G>Принимаю. Вспоминаю, сам чувствовал вину, когда разместил в common.h вместо отдельного файла. В C# обычно правила жесткие — каждый клас, интерфейс, даже нестед в отдельный файл. В си плюс плюс также надо похоже.
Можно и в общую кучу, но со смыслом. Point и ChException не имеют ничего общего, используются в разных местах программы.
Либо всё в один заголовок положить — для такой маленькой программы это вполне реально.
G>Я использовал инкрементальный алгоритм, как ты говорил ниже. Мотивация моя была в следующем: меньше памяти (ведь точек может быть очень много) и не надо делать два прохода: сохранить точки в векторе, пройтись по ним для нахождения выпуклой оболочки. Я 1*N сэкономил этим, не считая расширения вектора при вставке (чтобы обойти расширение, мне бы пришлось объявлять вектор на все точки — увеличить потребление памяти в два раза).
G>Ты тоже упоминаешь инкрементальный алгоритм ниже, тольео у тебя "Push", а у меня "Pull". Сказались годы работы на шарпе с его IEnumerable. Ты считаешь этот интерфейс (см ниже) перебор с абстрагированием? Хм... Возможно. Я просто думал, как же си шарпный IEnumerable<Point> на плюсах сделать. Ничего лучшего чем это не придумал.
G>G>class PointQueue
G>{
G>public:
G> SharedPoint NextPoint()
G> {
G> return NextPointInternal();
G> }
G>};
G>
В отличие от шарпа, в плюсах нет особой нужды делать ООП-интерфейс итератора. Вот это и есть излишнее абстрагирование. Можно ведь передать итератор (готового контейнера) как параметр шаблона — ничего руками не придётся писать.
При этом абстрагировании, кстати говоря, теряется
Инкрементный алгоритм может быть построен 3 способами:
— когда активным является источник данных, а вычислитель — подобие последовательного вывода
class AlgoServer
{
public:
void init();
void step(Point);
void done();
void somehow_utilize_results(.....);
};
void algo_client()
{
AlgoServer a;
a.init();
while(!end_of_file) { a.step(read_point()); }
// на деле, там может быть вот такое
for(current_point.x = ....) for(current_point.y = ......)
{
if(color(current_point) == what_we_need)
a.step(current_point);
}
a.done();
a.somehow_utilize_results(.....);
}
— когда активным является вычислитель, а источник данных — подобие последовательного ввода
class AlgoClient
{
bool eof() const;
Point read();
};
void algo_server(AlgoClient& client)
{
my_init();
while(!client.eof()) my_step(client.read());
// здесь сложно представить, что цикл будет затейливым (в отличие от предыдущего)
// но может оказаться наоборот: что он банальный - например, просто прочитать точки во внутренний контейнер,
// а вся жирная логика переедет в my_done()
my_done();
somehow_utilize_results();
}
— наконец, когда источник и вычислитель пассивны, а отдельно существует инфраструктура, реализующая весь этот конвеер
void algo_conveyor(SourceOfPoints& src, Algorithm& alg, DestinationOfPoints& dst)
{
alg.init();
while(!src.eof()) alg.write(src.read());
alg.done();
Algorithm::Result res = alg.result();
while(!res.eof()) dst.write(res.read());
}
Я, понятное дело, в этих эскизах никак не раскрываю деталей.
(Кстати, сейчас пришла в голову мысль, что на сопрограммах это было бы изящно. Но сопрограммы, особенно в С++, — излишество).
G>Прибитые гвоздями — это похоже про shared_ptr. Обосную ниже.
Это про shared_ptr<vector> и shared_ptr<list>.
К>>// для тех, кому нравится работать с произвольными контейнерами:
К>>template<class InIter, class OutIter>
К>>OutIter convex_hull(InIter begin, InIter end, OutIter dst)
К>>{
К>> std::vector<Point> points(begin, end);
К>> do_convex_hull(points);
К>> std::copy(points.begin(), points.end(), dst);
К>>}
G>Хороший интерфейс, а ля STL. Только слишком много N добавляет. Два копирования. Кстати в моей первой версии кода я тоже передавал vector. Потом поменял на "Pull-IEnumerable" при мыслях о производительности и памяти.
Этот алгоритм изначально не инкрементный, поскольку ниже говорилось: "отсортировать все точки по полярным координатам"...
Так что, если бы был выбран он, то ничего поделать нельзя.
Но можно же напрямую вызвать нешаблонную функцию do_convex_hull, тогда никаких лишних копирований.
К>>// нешаблонная функция — реализацию можно вынести в отдельный .cpp
К>>// тип рабочего контейнера зафиксирован — vector<Point>
К>>// (в будущем можно сделать произвольным — например, vector<void*>
К>>// плюс передавать стратегию для работы с точками: функции
К>>// get_x(void const*), get_y(void const*), remove(void*)
К>>// )
К>>void do_convex_hull(std::vector<Point>& points)
К>>{
К>> // отсортировать в полярных координатах
К>> // удалить точки, образующие вогнутые углы
К>>}
К>>[/c]
G>По поводу void* тут сразу два нарушения:
G>C++ Coding Standards 101 Rules by Alexandresku and Sutter
G>90. Avoid type switching; prefer polymorphism
G>92. Avoid using reinterpret_cast
G>Я думаю все плюсники эту книжку должны любить пламенной любовью. 
Расскажи это разработчикам boost::shared_ptr, boost::any и boost::function.
Никаких type switching, и даже никаких reinterpret_cast. Это эзотерическая техника неинтрузивных виртуальных функций. Она и в сях используется (qsort), и в плюсах (shared_ptr), а уж как она используется в хаскелле... но это уже дело хаскельного компилятора, пользователь о ней не думает.
G>Хотя с другой стороны в дот нете WPF постоянно Object грызет. Не type safe нифига.
Тут фокус в том, чтобы не отпускать объекты со стёртым типом в свободное плаванье.
Т.е. никаких vector<void*>, а только vector<void*> + IPointTypeTraits*
G>Это твой "Push" как я понимаю. То есть код, читающий точки, должен будет получить ConvexHullBuilder. Тебе не кажется, что это нарушение Rule Of Demeter (Least knowledge) и Separation of Concern. Получается, что тот код будет tightly coupled с конвекс халом. А что если я захочу просто точки получить для чего-нибудь другого, применяя тот же клас? Смысл моих абстракций вверху был "разлучить" код читающий точки и код делающий оболочку. Чтобы они были независимыми.
Для разлучения — нужна инфраструктура конвеера, см. выше.
К>>4. shared_ptr'ы нигде не нужны. Откройте для себя передачу аргументов по ссылке
G>C++ Coding Standards 101 Rules by Alexandresku and Sutter
G>79. Store only values and smart pointers in containers
G>Я не хотел передавать Point по значению, потому, что мой поинт был с двумя double — 16 байт. Копировать их при передаче значения было бы долго. Использовать референсы можно было бы, но у меня они уже должны были быть обернутыми в shared_ptr, из-за Александреску с его правилами (см. выше)
Александреску — очень плохой кумир для фанатизма.
Тем более, посчитай, сколько стоит копировать два дабла, и сколько — играть с подсчётом ссылок (он потокобезопасный, атомарный, и поэтому создаёт барьеры), а также — какие накладные расходы на блоки памяти.
G>Еще вот это
G>virtual SharedPoint NextPointInternal() = 0;
G>не понятно как сделать без SharedPoint.
Очень просто: virtual Point NextPointInternal().
И помолись о том, что компилятор умеет делать RVO (а компилятор умеет).
А если нет веры в RVO, то сделать out-параметр, как в старом злобром OLE/COM.
virtual bool NextPointInternal(Point& dst);
Кстати, если речь о том, чтобы возвращать значение или признак конца, так для этого есть много подходов:
— зарезервировать особое "сигнальное" значение, например, Point(NaN,NaN) или Inf,Inf
— возвращать обёртку — не обязательно shared_ptr, но можно boost::optional<Point> или std::pair<bool,Point>
— возвращать bool (или int) и out-параметр, как это делается во всех файловых функциях — int fread(void*dst,.....)
— вместо одного метода Read ввести два: Point Get()const и bool Next(), а то и три метода — void Next(), bool Eof()const — это стиль стльных итераторов
— кидать исключение, как это делает питон
G>Ты в своем void add(Point pt) вообще копируешь по значению. Я кстати оставил double на будущее. Вдруг захотят дробные на вход подять.
Ну и что в этом ужасного? Чай, не строка
Опять же, это эскиз. Можно переделать на Point const& pt.
К>>То есть, моё мнение: код нужно переделать вдребезги пополам
G>блин, ты бы видел какой пишут код тут у нас. Поубивал бы. 
G>По поводу книжки. Ищите в гугле:
G>C++ Coding Standards: 101 Rules, Guidelines, and Best Practices
G>By Herb Sutter, Andrei Alexandrescu
Дело не в том, чтобы следовать гайдлайнам кодирования. А в том, чтобы трезво отнестись к архитектуре программы, и затем закодировать её так, чтоб она была видна.
Но по архитектуре я не знаю, какую книгу предложить. Явно же не Банду Четырёх или Гради Буча?
Тем более, что и банда, и Буч — приверженцы ООП, а мне кажется, что здесь больше ФП и юникс-вей подойдёт.
(Но если в команде разработчиков практикуется ООП, то нужно помнить, что ФП — это ООП для бедных, и делать ООП, ибо есть такой принцип — "наименьшего удивления").
Перекуём баги на фичи!
