Error: Macro BackLinksMenu(None) failed

compressed data is corrupt

Error: Macro TicketQuery(summary=IMMUTABLE_TREE_R0, format=table, col=summary|owner|status|type|component|priority|effort|importance, rows=description|analysis_owners|analysis_reviewers|analysis_score|design_owners|design_reviewers|design_score|implementation_owners|implementation_reviewers|implementation_score|test_owners|test_reviewers|test_score|) failed

current transaction is aborted, commands ignored until end of transaction block

Analysis

Overview

In order that new project's persistence could be implemented, immutable structures are needed - like immutable tree. Immutability requires that every operation delivers reference to a new tree, in which changes (one defined by the operation) are made, in same time not modifying the tree of origin. In that sence, operation should use data of the origin tree as much as possible, and add/remove/change elements only where needed.

Task requirements

Following steps should be fulfilled:

• Tree/Map/Set Interface should be introduced
• Red-Black implementation of a tree (in order to get O(log n) worst case time complexity)
• Test Cases

Task result

Source code that contains working hierarchy of persistence structures with hashing ability.

Implementation idea

Simple implementation hierarchy and name convention:

• Collection
  • List
  • Set
  • Map
• Tree
  • Hashing Tree

For the hashing purposes, several already existing classes are introduced (like Hash, Hasher...). Good idea for the names of the classes and methods is to add "imm" prefix to classes that contain structures and are used to store persistent data.

Related

^{(Add links to related tasks that could be useful or helpful.)}

How to demo

Result of the time-capacity performance of the Red-Black tree.

Design

Following UML class diagram describes the class hierarchy that should be implemented:

Class ImmDosTree will be the implementation of Red-Black indexed tree. It's extension - ImmHashingTree contains hashable Nodes, so, itself is a hashable tree.

Tests: [5399]

Implementation

^{(Describe and link the implementation results here (from the wiki or the repository).)}

Testing

Tests: [5399]

Comments

^{(Write comments for this or later revisions here.)}