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 sense, operation should use data of the origin tree as much as possible, and add/remove/change elements only where needed.

Working branch of the task is ​http://www.sophie2.org/trac/browser/branches/second_resource_refactoring

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 arbitrary 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

The working repository and module for the hierarchy of the classes is ​http://www.sophie2.org/trac/browser/branches/second_resource_refactoring/sophie2-platform/modules/org.sophie2.base.commons/src/main/java/org/sophie2/base/commons/structures?rev=5622

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

Class ImmDosTree will be the implementation of Red-Black indexed tree following methods will be introduced (only description in logical sense):

• add element
  • addCase1
  • addCase2

• set element

• remove element
  • removeCase1
  • removeCase2
  • removeCase3
  • removeCase4
  • removeCase5

ImmDosTree's extension - ImmHashingTree contains hashable Nodes. ImmHashingTree contains static method getHash, which in itself invokes a public method in the inner class HashingNode, which calculates :

public static Hash getHash(ImmCollection<?> col, int begin, int end) {
		if(!(col instanceof ImmTreeCollection<?>)) {
			throw new IllegalArgumentException("Non Hashable Collection - cannot get Hash!");
		}
		
		ImmTreeCollection<?> treeCol = (ImmTreeCollection<?>)col;
		
		if(!(treeCol.getTree().getRoot() instanceof HashingNode<?>)) {
			throw new IllegalArgumentException("Non Hashable Tree - cannot get Hash!");
		}
		
		HashingNode<?> node = (HashingNode<?>)treeCol.getTree().getRoot();
		
		Hasher res = new Hasher();
		int count = end - begin;
		
		node.getHash(res, begin + treeCol.getTreeBegin(), count);
		return res.toHash();
	}

• List interface should be implemented for the ImmTreeList class. ​http://www.sophie2.org/trac/attachment/wiki/IMMUTABLE_TREE_R0/ImmList.java
• Set interface should be implemented for the ImmTreeSet class. ​http://www.sophie2.org/trac/attachment/wiki/IMMUTABLE_TREE_R0/ImmSet.java
• Map interface should be implemented for the ImmTreeMap class. ​http://www.sophie2.org/trac/attachment/wiki/IMMUTABLE_TREE_R0/ImmMap.java

Tests: [5399]

Implementation

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

Testing

Tests: [5412]

Comments

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