[[BackLinksMenu]]

[[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|)]]

= 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:


[[Image(imm.png)]]


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.)