Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * ====================================================================
   * Copyright (c) 2004-2006 TMate Software Ltd.  All rights reserved.
   *
   * This software is licensed as described in the file COPYING, which
   * you should have received as part of this distribution.  The terms
   * are also available at http://svnkit.com/license.html
   * If newer versions of this license are posted there, you may use a
   * newer version instead, at your option.
  * ====================================================================
  */
 package org.tmatesoft.svn.core.internal.delta;



Author(s):
TMate Software Ltd.
Version:
1.1.0
 
 public class SVNRangeTree {
     
     private SVNRangeTreeNode myRoot = null;
     
     private SVNRangeTreeNode myFreeTreeNodes;
     private SVNRangeListNode myFreeListNodes;
     
     public static class SVNRangeTreeNode {
         
         public SVNRangeTreeNode(int offsetint limitint target) {
             this. = offset;
             this. = limit;
             this. = target;
         }
         
         public String toString() {
             String str =  + ":" +  + ":" + ;
             return str;
         }
         
         public int offset;
         public int limit;
         public int targetOffset;
         
         public SVNRangeTreeNode left;
         public SVNRangeTreeNode right;
         public SVNRangeTreeNode prev;
         public SVNRangeTreeNode next;
         
         public SVNRangeTreeNode nextFree;
     }
     
     private SVNRangeTreeNode allocateTreeNode(int offsetint limitint target) {
         if ( == null) {
             SVNRangeTreeNode node = new SVNRangeTreeNode(offsetlimittarget);
             node.nextFree = ;
              = node;
             return node;
         }
         SVNRangeTreeNode node = ;
          = node.nextFree;
         node.left = node.right = node.next = node.prev = null;
         node.offset = offset;
         node.limit = limit;
         node.targetOffset = target;
         
         // make it head of the allocated list.
         node.nextFree = ;
          = node;
         return node;
     }
 
     private void freeTreeNode(SVNRangeTreeNode node) {
         if (node.next != null) {
             node.next.prev = node.prev;
             node.next = null;
         }
         if (node.prev != null) {
             node.prev.next = node.next;
             node.prev = null;
         }
         // remove if from the allocated list, it has to be there.
         if ( == node) {
         } else {
             SVNRangeTreeNode allocated = ;
             while(allocated.nextFree != node) {
                 allocated = allocated.nextFree;
             }
             allocated.nextFree = node.nextFree;
         }
         // make it head of the free nodes list.
         node.nextFree = ;
          = node;
     }
 
     private SVNRangeListNode allocateListNode(int kindint offsetint limitint target) {
         if ( == null) {
             return new SVNRangeListNode(kindoffsetlimittarget);
        }
        SVNRangeListNode node = ;
         = node.next;
        node.offset = offset;
        node.limit = limit;
        node.targetOffset = target;
        node.kind = kind;
        node.prev = node.next = null;
        node.head = node;
        return node;
    }
    
    public void disposeList(SVNRangeListNode head) {
        SVNRangeListNode n = head;
        while(head.next != null) {
            head = head.next;
        }
        head.next = ;
         = n;
    }
    
    public void dispose() {
        SVNRangeTreeNode node = ;
        if (node == null) {
             = ;
        } else {
            while(node.nextFree != null) {
                node = node.nextFree;
            }
            node.nextFree = ;
        }
         = null;
         = null;
    }
    public static class SVNRangeListNode {
        
        public static int FROM_SOURCE = 0;
        public static int FROM_TARGET = 1;
        
        public SVNRangeListNode(int kindint offsetint limitint target) {
            this. = kind;
            this. = offset;
            this. = limit;
            this. = target;
            this. = this;
        }
        
        public SVNRangeListNode append(SVNRangeListNode node) {
            this. = node;
            node.prev = this;
            node.head = this.;
            return node;
        }
        public int kind;
        public int offset;
        public int limit;
        public int targetOffset;
        
        public SVNRangeListNode prev;
        public SVNRangeListNode next;
        public SVNRangeListNode head;
    }
    
    public SVNRangeListNode buildRangeList(int offsetint limit) {
        SVNRangeListNode tail = null;
        SVNRangeTreeNode node = ;
        
        while(offset < limit) {
            if (node == null) {
                return appendToRangeList(.offsetlimit, 0, tail);
            }
            if (offset < node.offset) {
                if (limit <= node.offset) {
                    return appendToRangeList(.offsetlimit, 0, tail);
                }
                tail = appendToRangeList(.offsetnode.offset, 0, tail);
                offset = node.offset;
            } else {
                if (offset >= node.limit) {
                    node = node.next;
                } else {
                    int targetOffset = offset - node.offset + node.targetOffset;
                    if (limit <= node.limit) {
                        return appendToRangeList(.offsetlimittargetOffsettail);
                    }
                    tail = appendToRangeList(.offsetnode.limittargetOffsettail);
                    offset = node.limit;
                    node = node.next;
                }
            }
        }
        SVNDeltaCombiner.assertCondition(false"assert #6");
        return tail;
    }
    private SVNRangeListNode appendToRangeList(int kindint offsetint limitint tOffsetSVNRangeListNode tail) {
        if (tail == null) {
            return allocateListNode(kindoffsetlimittOffset);
        }
        return tail.append(allocateListNode(kindoffsetlimittOffset));
    }
    
    private SVNRangeTreeNode myScratchNode = new SVNRangeTreeNode(0,0,0); 
    
    public void splay(int offset) {
        if ( == null) {
            return;
        }
        SVNRangeTreeNode root = ;
        SVNRangeTreeNode scratch = ;
        scratch.left = scratch.right = null;
        SVNRangeTreeNode left = scratch;
        SVNRangeTreeNode right = scratch;
        while(true) {
            if (offset < root.offset) {
                if (root.left == null) {
                    break;
                }
                if (offset < root.left.offset) {
                    SVNRangeTreeNode node = root.left;
                    root.left = node.right;
                    node.right = root;
                    root = node;
                    if (root.left == null) {
                        break;
                    }
                }
                right.left = root;
                right = root;
                root = root.left;
            } else if (offset > root.offset) {
                if (root.right == null) {
                    break;
                }
                if (offset > root.right.offset) {
                    SVNRangeTreeNode node = root.right;
                    root.right = node.left;
                    node.left = root;
                    root = node;
                    if (root.right == null) {
                        break;
                    }
                }
                left.right = root;
                left = root;
                root = root.right;
            } else {
                break;
            }
        }
        left.right = root.left;
        right.left = root.right;
        root.left = scratch.right;
        root.right = scratch.left;
        
        if (offset < root.offset && root.left != null) {
            if (root.left.right == null) {
                SVNRangeTreeNode node = root.left;
                root.left = node.right;
                SVNDeltaCombiner.assertCondition(root.left == null"not null I");
                node.right = root;
                root = node;
            } else {
                SVNRangeTreeNode node = root.left;
                SVNRangeTreeNode prevNode = node;
                while(node.right != null) {
                    prevNode = node;
                    node = node.right;
                }
                // node should now become root.
                right = root;
                left = root.left;
                root = node;
                //node = root.left;
                prevNode.right = null;
                right.left = null;
                root.left = left;
                root.right = right;
            }
        }
         = root;
        SVNDeltaCombiner.assertCondition((offset >= root.offset) || (root.left == null && root.prev == null), "assert #4");
    }
    
    public void insert(int offsetint limitint targetOffset) {
        if ( == null) {
             = allocateTreeNode(offsetlimittargetOffset);
            return;
        }
        if (offset == . && limit > .) {
            . = limit;
            . = targetOffset;
            cleanTree(limit);
        } else if (offset > . && limit > .) {
            boolean haveToInsertRange = . == null ||
                    . < .. ||
                    limit > ..;
            if (haveToInsertRange) {
                if (. != null && .. > offset) {
                    . = offset;
                    . = limit;
                    . = targetOffset;
                } else {
                    SVNRangeTreeNode node = allocateTreeNode(offsetlimittargetOffset);
                    node.next = .;
                    if (node.next != null) {
                        node.next.prev = node;
                    }
                    . = node;
                    node.prev = ;
                    node.right = .;
                    . = null;
                    node.left = ;
                     = node;
                }
                cleanTree(limit);
            }   
        } else if (offset < .) {
            SVNDeltaCombiner.assertCondition(. == null"assert #5");
            SVNRangeTreeNode node = allocateTreeNode(offsetlimittargetOffset);
            
            node.left = node.prev = null;
            node.right = node.next = ;
             = node.next.prev = node;
            cleanTree(limit);
        }
    }
    
    private void cleanTree(int limit) {
        int topOffset = limit + 1;
        SVNRangeTreeNode parent = ;
        SVNRangeTreeNode node = .;
        while(node != null) {
            int offset = node.right != null && node.right.offset < topOffset ? node.right.offset : topOffset;
            if (node.limit <= limit || (node.offset < limit && offset < limit)) {
                parent.right = null;
                parent = node;
                deleteSubtree(node);
                node = null;
            } else {
                topOffset = node.offset;
                node = node.left;
            }
        }
    }
    
    private void deleteSubtree(SVNRangeTreeNode node) {
        if (node != null) {
            deleteSubtree(node.left);
            deleteSubtree(node.right);
            freeTreeNode(node);
        }
    }
New to GrepCode? Check out our FAQ X