Программы, написанные в рамках курса Software Design

2006 год

  1. The Knots
  2. Библиотека для работы с PostScript-файлами
  3. Ребусы
  4. File Manager
  5. JBookReader
  6. Редактор блок-схем
  7. Index Fabric
  8. XMLIndex
  9. Индексатор XML документов и процессор регулярных XPath запросов
  10. File Manager
  11. FB2Reader
  12. TheGames
  13. Файловый менеджер
  1. The Knots

    Автор: Юлия Беляева.

    Узел – это замкнутая линия в пространстве без самопересечений. Зацепление – несколько таких линий.

    Программа The Knots позволяет

    • вводить и редактировать диаграммы узлов и зацеплений;
    • сохранять диаграммы в виде XML-файла;
    • вычислять полином Джонса для узлов и зацеплений.

    Программа (jar-файл).

    Исходный код.

    Примеры узлов.

  2. Библиотека для работы с PostScript-файлами

    Автор: Игорь Синев

    В этой библиотеке реализован набор классов для работы с файлами в формате PostScript (PS). Этот формат часто используется для переносимого представления документов, однако на самом деле является интерпретируемым языком программирования. (Интерпретация PS-файла состоит в последовательном исполнении операторов и, возможно, вызове макросов. Операторы обрабатывают входную информацию, осуществляют вывод в выходной поток, читая и записывая локальные данные в специальный стек.)

    Библиотека позволяет построить в памяти модель PS-документа, подходящую для эффективного выполнения различных операций. В этой модели создается структура связей между операторами с проверкой соответствия синтаксису, что позволяет анализировать содержимое файла и вносить в него локальные изменения. Поддерживается возможность частичной интерпретации документа, для выполнения которой необходимо реализовать вычисляющие методы для соответствующих операторов.

    Использовать библиотеку можно, почитав документацию к классам (javadoc-комментарии в исходных текстах), либо посмотрев на примеры программ и тесты.

    Исходный код.

  3. Ребусы

    Автор: Ольга Большакова

    Программа предназначена для решения “числовых ребусов”.

    Она позволяет:

    • ввести ребус произвольного вида;
    • сохранить ребус на диске (созданные файлы по умолчанию сохраняются в домашнем каталоге пользователя в папке “rebuses”);
    • решить ребус.

    Если программа будет развиваться, предполагается добавить возможность решения ребусов с операциями неравенства и возведения в степень, а также типовые шаблоны для быстрого создания наиболее распространенных видов ребусов.

    Примеры ребусов:

    1. SIX * TWO = TWELVE
    2. СОРОК * 5 = ДВЕСТИ
    3.  ОДИН
      +ОДИН
      -----
      МНОГО
    4. АБ + 8 = 3В
      -    -    -
      ГД + В = ГВ
      =    =    =
      ГБ + 3 = АД
    5. *****|**
      ***  |---
      ---  |*8*
       ***
        **
       ---
        ***
        ***
        ---
          0
    6.   1995
       x ***
       -----
       *****
      *ГОД
      ------
      СВИНЬИ

    Программа.

    Исходный код.

    Примеры ребусов.

  4. File Manager

    Автор: Петр Аверьянов.

    Эта программа позволяет просматривать файлы на диске и перемещаться по каталогам при помощи мыши или клавиатуры. Есть возможность создания и удаления файла или каталога. (При удалении файлы реально удаляются с диска.) Программа умеет определять тип файла по расширению и по первым байтам, данные о типах загружаются из filetypes.xml и при желании могут быть изменены. Для всех файлов одного типа может быть задана открывающая программа и иконка. Настройки (такие как текущий каталог, команды для файлов, размер окна и некоторые другие) сохраняются каждый раз после окончания работы менеджера и восстанавливаются при следующем запуске. Программа не обновляет данные о файловой системе, если изменения были внесены посторонними приложениями.

    Программа.

    Исходный код.

  5. JBookReader

    Автор: Дмитрий Барышков

    Программа JBookReader предназначена для чтения книг в формате FictionBook2.

    Текущая версия программы позволяет просматривать книги, редактировать настройки внешнего вида книги. Позиция в книге сохраняется между запусками программы. В этой версии программа не поддерживает гиперссылки, таблицы, варианты начертания текста.

    При развитии программы планируется добавить поддержку остальных тегов формата fb2, тонкую настройку визуального представления книги.

    Программа.

    Исходный код.

  6. Редактор блок-схем

    Автор: Юлия Астахова

    Программа позволяет создавать и редактировать блок-схемы алгоритмов. Диаграммы сохраняются в XML-файле. Есть возможность экспорта блок-схемы в формат jpeg. Работа с буфером обмена ограничена возможностью помещения в него части изображения диаграммы.

    Программа.

    Исходный код.

  7. Index Fabric

    Автор: Максим Подколзин

    Index Fabric – это механизм быстрого поиска ключа в неструктурированных данных. Примером неструктурированного документа является XML-документ без схемы, определяющей его структуру. Основу Index Fabric составляет Patricia trie. (Подробно про Patricia Trie можно почитать, например, в “Donald Knuth. The Art of Computer Programming, Vol. III, Sorting and Searching, Third Edition”.)

    Patricia trie - это дерево (бор) с помеченными вершинами и рёбрами. Именно, в вершинах записываются целые числа, называемые глубиной вершины, а на рёбрах - символы некоторого алфавита. Пример trie, содержащего 3 строки “cash”, “cat” и “fast”, представлен на рисунке:

    С помощью такого представления легко осуществляется поиск строки среди заданного набора. Просто, начиная с корня, сравниваются символы ключа на соответствующей позиции и символы на рёбрах.

    Идея Index Fabric состоит в том, чтобы представить слабоструктурированный документ в виде набора строк. Например, XML документ - это множество строк, кодирующих пути от корня до листьев. Сначала, все строки добавляются в Patricia trie, после чего trie позволяет быстро отвечать на запросы вида “есть ли заданный ключ x1x2...xn в trie или нет”.

    В нашей реализации Index Fabric, для каждого тэга (элемента) XML, для каждого атрибута и символа текста создаётся определённый символ алфавита, который и будет использоваться при построении и поиске в Patricia trie. С точки зрения Patricia trie, он оперирует с произвольными символами (у нас это интерфейс ISymbol), а уже Index Fabric подразделяет символы на tag, attribute или text.

    Описание библиотеки:

    • Класс XMLBuilder предоставляет интерфейс добавления в Index Fabric новых XML документов.
    • Класс XMLRetriever позволяет искать в построенном Index Fabric.
    • Классы IndexFabricSerializer и IndexFabricDeserializer сохраняют и поднимают Index Fabric соответственно.

    Patricia trie реализован независимо от Index Fabric. Предоставляется набор интерфейсов:

    • Интерфейс IPatriciaTrie – бор, использующийся только для чтения (поиск заданной строки символов). Его наследник IWritablePatriciaTrie позволяет добавлять новые строки.
    • Интерфейс ISymbol – символы на рёбрах.
    • Интерфейс INode – вершина (узел) бора, использующаяся только для чтения (взятие предка, сыновей, глубины вершины). Наследник IwritableNode содержит методы для изменения всех данных узла.
    • Интерфейс IReference означает ссылку на документ. Узел бора может иметь ссылку на тот документ, из которого был добавлен (обычно ссылки содержат листья бора).

    Реализация интерфейсов, а также другие необходимые классы находятся в под-package’е impl.

    Patricia trie может быть сериализован, причем в несколько файлов, содержащих отдельные поддеревья исходного. Это позволяет не держать в оперативной памяти весь бор целиком и подгружать отдельные блоки по необходимости.

    Проводилось тестирование Index Fabric на XML-документах разных размеров. Самый большой файл содержал 1 000 000 тэгов (из них 10 000 различных) и ˜200 000 атрибутов. JVM запускалась с ключами -Xmx500M –ea; общее время работы теста (добавление вместе с проверкой) ˜30 минут. Index Fabric был сериализован в ˜18 000 файлов, общий объём составил ˜75 Mb.

    Замечания:

    • Библиотека реализует некоторые интерфейсы из проекта XAnswer. Их можно скачать с сайта этого проекта, либо взять в виде отдельного zip-файла на этой странице.
    • Использовалась стандартная базовая java-сериализация (классов Symbol, Node, Block, и др.). Для оптимизации занимаемого места на диске рекомендуется использовать свою сериализацию.
    • В данной версии Index Fabric не поддерживается разбиение на слои.
    • Класс XMLBuilder имеет опции добавления XML документов: игнорирование пробелов и добавление всех префиксов ключа. Первая опция реагирует (или не реагирует) на переводы строк и пробельные символы между тэгами. Включение опции сокращает размер структуры на 10-20%. Вторая опция позволяет добавлять все пути от корня до каждой вершины в XML (а не только до листьев). Отключение второй опции сокращает дерево в 1.5-2 раза.
    • Для работы с файловой системой использовался класс NativeSystem. Все потоки ввода-вывода открываются из файла и в файл. Возможно редактирование этого класса для работы с сетью или базами данных.

    Для демонстрации работы Index Fabric созданы классы DemoBuilder и DemoRetriever. Первый позволяет строить Index Fabric из указанных XML файлов, второй - искать в существующем Index Fabric заданную последовательность тэгов (заметим, что это не единственное возможное использование класса XMLRetriever).

    Исходный код.

    Необходимые классы из проекта XAnswer.

  8. XMLIndex

    Автор: Виктор Кропп

    Эта библиотека позволяет индексировать XML-файлы для ускорения XPath-запросов к ним. Зачем это нужно рассказывается на сайте проекта XAnswer.

    Библиотека предназначена для ускроения выборки по осям XPath. В ней реализованы структура данных и алгоритм, описанные в этой статье. Для хранения индекса используется B+ дерево, реализованное в библиотеке org.exist из проекта XAnswer. Библиотека позволяет создавать индекс, сохранять его на диске, искать в нем. Кроме этого, реализована обработка некоторого подмножества XPath-запросов.

    Примеры использования библиотеки можно найти в пакете org.kropp.examples, а также в JUnit-тестах в пакете org.kropp.tests.

    Исходный код.

    Необходимые файлы из проекта XAnswer.

  9. 
  10. Индексатор XML документов и процессор регулярных XPath запросов

    Автор: Евгений Кирпичев

    Реализована библиотека, позволяющая индексировать XML документы, хранить индексы на диске и выполнять на них регулярные XPath запросы либо низкоуровневые запросы, представленные последовательностью специфических операций. В программе используется индексная структура XISS, основанная на B+ деревьях, и исполнение запросов при помощи низкоуровневых операций XISS.

    В настоящий момент в программе применяется неоптимальный способ хранения части индекса – индекса структуры (при открытом индексе он целиком хранится в памяти). В программе присутствует большая часть необходимого для исполнения любых регулярных XPath запросов, но синтаксически поддерживается лишь достаточно малое (и, к тому же, измененное) подмножество языка. (Сам по себе язык XPath не является языком регулярных выражений и не существует стандарта регулярного XPath.)

    К библиотеке прилагается 3 примера – утилиты командной строки:

    • индексатор – строит индекс одного XML документа и сохраняет его на диске;
    • процессор запросов – выполняет один регулярный XPath запрос к сохраненному на диске индексу;
    • пример исполнения низкоуровневого запроса – выполняет один конкретный простой низкоуровневый запрос, построенный напрямую в виде последовательности операций.

    Для работы с B+ деревьями используется библиотека eXist из проекта XAnswer.

    Исходный код.

    Необходимые классы из проекта XAnswer.

    Исходные тексты классов из XAnswer.

  11. File Manager

    Автор: Александр Ильин.

    Программа предназначена для просмотра файлов и каталогов на жестком диске. Файлы (каталоги) можно создавать, удалять и переименовывать. Программа определяет тип файла по первым байтам или по расширению. Для каждого типа файлов можно указать внешнюю программу для их просмотра. Реализованы два различных интерфейса: один — в стиле Norton Commander'а, другой — в стиле Explorer'а.

    Программа.

    Исходный код.

  12. FB2Reader

    Автор: Сергей Скроботов

    Программа предназначена для чтения книг в формате FB2.

    Представленная версия программы реализует следующую функциональность:

    • просмотр текста в формате fb2 :);
    • сохранение текущей позиции между запусками программы;
    • панель оглавления с поддержкой навигации и отображением текущей главы;
    • отображение текущей позиции во всей книге;
    • настройка свойств отображения текста (цвет, размер, выравнивание, отступы и др.);
    • сохранение списка просмотренных документов;
    • сохранение истории навигации.

    В текущей версии поддержаны не все теги fb2, что может привести к некорректному отображению некоторых документов.

    Инсталлятор.

    Исходный код.

    Исходный код инсталлятора.

  13. TheGames

    Автор: Антон Ланцов

    Программа TheGames предназначена для быстрого создания простых логических игр. Поддерживаются только игры для двух игроков на прямоугольной доске с фишками двух цветов одного типа. Например реверси, крестики-нолики, уголки, attax.

    Для создания новой игры нужно реализовать два интерфейса: IGame (правила игры) и Intellect (искусственный интеллект). Программа включает три готовые игры.

    Программа.

    Исходный код.

  14. Файловый менеджер

    Автор: Руслан Исакиев

    Программа поддерживает два сменных интерфейса, т.е. в зависимости от желания пользователя может выглядеть как Norton Commander или как Explorer.

    Реализованы следующие возможности:

    • определение по содержимому файла форматов GIF, BMP, JPEG, PNG, TIFF, MP3, WAV, EXE, ZIP, RAR, class-файов Java;
    • просмотр содержимого ZIP-архивов;
    • просмотр изображений GIF, JPEG, PNG;
    • запуск исполняемых файлов;
    • синхронизация с изменениями, сделанными в файловой системе извне;
    • копирование, перемещение, переименование, удаление файлов и каталогов (для интерфейса в стиле NC);
    • сохранение текущего состояния программы (текущий интерфейс, выбранные элементы, размеры и положение окна) в XML-документ и загрузка этого состояния при следующем запуске;
    • создание log-файла, содержащего подробную информацию о работе программы в формате HTML.

    В качестве дальнейшего направления развития программы предполагается:

    • открытие файлов с помощью внешних программ; создание и редактирование списка ассоциаций типов файлов с открывающими программами;
    • определение текстовых файлов по содержимому;
    • поддержка командной строки для обоих интерфейсов;
    • возможность изменения визуальных настроек программы (шрифт текста, цвета);
    • воспроизведение музыки;
    • просмотр class-файлов.

    Программа.

    Исходный код.