Программы, написанные в рамках курса Software Design
2006 год
- The Knots
- Библиотека для работы с PostScript-файлами
- Ребусы
- File Manager
- JBookReader
- Редактор блок-схем
- Index Fabric
- XMLIndex
- Индексатор XML документов и процессор регулярных XPath запросов
- File Manager
- FB2Reader
- TheGames
- Файловый менеджер
-
The Knots
Автор: Юлия Беляева.
Узел – это замкнутая линия в пространстве без самопересечений. Зацепление – несколько таких линий.
Программа The Knots позволяет
- вводить и редактировать диаграммы узлов и зацеплений;
- сохранять диаграммы в виде XML-файла;
- вычислять полином Джонса для узлов и зацеплений.
-
Библиотека для работы с PostScript-файлами
Автор: Игорь Синев
В этой библиотеке реализован набор классов для работы с файлами в формате PostScript (PS). Этот формат часто используется для переносимого представления документов, однако на самом деле является интерпретируемым языком программирования. (Интерпретация PS-файла состоит в последовательном исполнении операторов и, возможно, вызове макросов. Операторы обрабатывают входную информацию, осуществляют вывод в выходной поток, читая и записывая локальные данные в специальный стек.)
Библиотека позволяет построить в памяти модель PS-документа, подходящую для эффективного выполнения различных операций. В этой модели создается структура связей между операторами с проверкой соответствия синтаксису, что позволяет анализировать содержимое файла и вносить в него локальные изменения. Поддерживается возможность частичной интерпретации документа, для выполнения которой необходимо реализовать вычисляющие методы для соответствующих операторов.
Использовать библиотеку можно, почитав документацию к классам (javadoc-комментарии в исходных текстах), либо посмотрев на примеры программ и тесты.
-
Ребусы
Автор: Ольга Большакова
Программа предназначена для решения “числовых ребусов”.
Она позволяет:
- ввести ребус произвольного вида;
- сохранить ребус на диске (созданные файлы по умолчанию сохраняются в домашнем каталоге пользователя в папке “rebuses”);
- решить ребус.
Если программа будет развиваться, предполагается добавить возможность решения ребусов с операциями неравенства и возведения в степень, а также типовые шаблоны для быстрого создания наиболее распространенных видов ребусов.
Примеры ребусов:
SIX * TWO = TWELVE
СОРОК * 5 = ДВЕСТИ
ОДИН +ОДИН ----- МНОГО
АБ + 8 = 3В - - - ГД + В = ГВ = = = ГБ + 3 = АД
*****|** *** |--- --- |*8* *** ** --- *** *** --- 01995 x *** ----- ***** *ГОД ------ СВИНЬИ
-
File Manager
Автор: Петр Аверьянов.
Эта программа позволяет просматривать файлы на диске и перемещаться по каталогам при помощи мыши или клавиатуры. Есть возможность создания и удаления файла или каталога. (При удалении файлы реально удаляются с диска.) Программа умеет определять тип файла по расширению и по первым байтам, данные о типах загружаются из filetypes.xml и при желании могут быть изменены. Для всех файлов одного типа может быть задана открывающая программа и иконка. Настройки (такие как текущий каталог, команды для файлов, размер окна и некоторые другие) сохраняются каждый раз после окончания работы менеджера и восстанавливаются при следующем запуске. Программа не обновляет данные о файловой системе, если изменения были внесены посторонними приложениями.
-
JBookReader
Автор: Дмитрий Барышков
Программа JBookReader предназначена для чтения книг в формате FictionBook2.
Текущая версия программы позволяет просматривать книги, редактировать настройки внешнего вида книги. Позиция в книге сохраняется между запусками программы. В этой версии программа не поддерживает гиперссылки, таблицы, варианты начертания текста.
При развитии программы планируется добавить поддержку остальных тегов формата fb2, тонкую настройку визуального представления книги.
-
Редактор блок-схем
Автор: Юлия Астахова
Программа позволяет создавать и редактировать блок-схемы алгоритмов. Диаграммы сохраняются в XML-файле. Есть возможность экспорта блок-схемы в формат jpeg. Работа с буфером обмена ограничена возможностью помещения в него части изображения диаграммы.
-
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).
-
XMLIndex
Автор: Виктор Кропп
Эта библиотека позволяет индексировать XML-файлы для ускорения XPath-запросов к ним. Зачем это нужно рассказывается на сайте проекта XAnswer.
Библиотека предназначена для ускроения выборки по осям XPath. В ней реализованы структура данных и алгоритм, описанные в этой статье. Для хранения индекса используется B+ дерево, реализованное в библиотеке org.exist из проекта XAnswer. Библиотека позволяет создавать индекс, сохранять его на диске, искать в нем. Кроме этого, реализована обработка некоторого подмножества XPath-запросов.
Примеры использования библиотеки можно найти в пакете org.kropp.examples, а также в JUnit-тестах в пакете org.kropp.tests.
-
Индексатор XML документов и процессор регулярных XPath запросов
Автор: Евгений Кирпичев
Реализована библиотека, позволяющая индексировать XML документы, хранить индексы на диске и выполнять на них регулярные XPath запросы либо низкоуровневые запросы, представленные последовательностью специфических операций. В программе используется индексная структура XISS, основанная на B+ деревьях, и исполнение запросов при помощи низкоуровневых операций XISS.
В настоящий момент в программе применяется неоптимальный способ хранения части индекса – индекса структуры (при открытом индексе он целиком хранится в памяти). В программе присутствует большая часть необходимого для исполнения любых регулярных XPath запросов, но синтаксически поддерживается лишь достаточно малое (и, к тому же, измененное) подмножество языка. (Сам по себе язык XPath не является языком регулярных выражений и не существует стандарта регулярного XPath.)
К библиотеке прилагается 3 примера – утилиты командной строки:
- индексатор – строит индекс одного XML документа и сохраняет его на диске;
- процессор запросов – выполняет один регулярный XPath запрос к сохраненному на диске индексу;
- пример исполнения низкоуровневого запроса – выполняет один конкретный простой низкоуровневый запрос, построенный напрямую в виде последовательности операций.
Для работы с B+ деревьями используется библиотека eXist из проекта XAnswer.
-
File Manager
Автор: Александр Ильин.
Программа предназначена для просмотра файлов и каталогов на жестком диске. Файлы (каталоги) можно создавать, удалять и переименовывать. Программа определяет тип файла по первым байтам или по расширению. Для каждого типа файлов можно указать внешнюю программу для их просмотра. Реализованы два различных интерфейса: один — в стиле Norton Commander'а, другой — в стиле Explorer'а.
-
FB2Reader
Автор: Сергей Скроботов
Программа предназначена для чтения книг в формате FB2.
Представленная версия программы реализует следующую функциональность:
- просмотр текста в формате fb2 :);
- сохранение текущей позиции между запусками программы;
- панель оглавления с поддержкой навигации и отображением текущей главы;
- отображение текущей позиции во всей книге;
- настройка свойств отображения текста (цвет, размер, выравнивание, отступы и др.);
- сохранение списка просмотренных документов;
- сохранение истории навигации.
В текущей версии поддержаны не все теги fb2, что может привести к некорректному отображению некоторых документов.
-
TheGames
Автор: Антон Ланцов
Программа TheGames предназначена для быстрого создания простых логических игр. Поддерживаются только игры для двух игроков на прямоугольной доске с фишками двух цветов одного типа. Например реверси, крестики-нолики, уголки, attax.
Для создания новой игры нужно реализовать два интерфейса: IGame (правила игры) и Intellect (искусственный интеллект). Программа включает три готовые игры.
-
Файловый менеджер
Автор: Руслан Исакиев
Программа поддерживает два сменных интерфейса, т.е. в зависимости от желания пользователя может выглядеть как Norton Commander или как Explorer.
Реализованы следующие возможности:
- определение по содержимому файла форматов GIF, BMP, JPEG, PNG, TIFF, MP3, WAV, EXE, ZIP, RAR, class-файов Java;
- просмотр содержимого ZIP-архивов;
- просмотр изображений GIF, JPEG, PNG;
- запуск исполняемых файлов;
- синхронизация с изменениями, сделанными в файловой системе извне;
- копирование, перемещение, переименование, удаление файлов и каталогов (для интерфейса в стиле NC);
- сохранение текущего состояния программы (текущий интерфейс, выбранные элементы, размеры и положение окна) в XML-документ и загрузка этого состояния при следующем запуске;
- создание log-файла, содержащего подробную информацию о работе программы в формате HTML.
В качестве дальнейшего направления развития программы предполагается:
- открытие файлов с помощью внешних программ; создание и редактирование списка ассоциаций типов файлов с открывающими программами;
- определение текстовых файлов по содержимому;
- поддержка командной строки для обоих интерфейсов;
- возможность изменения визуальных настроек программы (шрифт текста, цвета);
- воспроизведение музыки;
- просмотр class-файлов.
Программа (jar-файл)