Java Program to Implement Interval Tree

Code:

import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;

class Interval implements Comparable>
{

    private long start;
    private long end;
    private Type data;

    public Interval(long start, long end, Type data)
    {
        this.start = start;
        this.end = end;
        this.data = data;
    }

    public long getStart()
    {
        return start;
    }

    public void setStart(long start)
    {
        this.start = start;
    }

    public long getEnd()
    {
        return end;
    }

    public void setEnd(long end)
    {
        this.end = end;
    }

    public Type getData()
    {
        return data;
    }

    public void setData(Type data)
    {
        this.data = data;
    }

    public boolean contains(long time)
    {
        return time < end && time > start;
    }

    public boolean intersects(Interval other)
    {
        return other.getEnd() > start && other.getStart() < end;
    }

    public int compareTo(Interval other)
    {
        if (start < other.getStart())
            return -1;
        else if (start > other.getStart())
            return 1;
        else if (end < other.getEnd())
            return -1;
        else if (end > other.getEnd())
            return 1;
        else
            return 0;
    }

}

class IntervalNode
{

    private SortedMap, List>> intervals;
    private long                                            center;
    private IntervalNode                              leftNode;
    private IntervalNode                              rightNode;

    public IntervalNode()
    {
        intervals = new TreeMap, List>>();
        center = 0;
        leftNode = null;
        rightNode = null;
    }

    public IntervalNode(List> intervalList)
    {

        intervals = new TreeMap, List>>();

        SortedSet endpoints = new TreeSet();

        for (Interval interval : intervalList)
        {
            endpoints.add(interval.getStart());
            endpoints.add(interval.getEnd());
        }

        long median = getMedian(endpoints);
        center = median;

        List> left = new ArrayList>();
        List> right = new ArrayList>();

        for (Interval interval : intervalList)
        {
            if (interval.getEnd() < median)
                left.add(interval);
            else if (interval.getStart() > median)
                right.add(interval);
            else
            {
                List> posting = intervals.get(interval);
                if (posting == null)
                {
                    posting = new ArrayList>();
                    intervals.put(interval, posting);
                }
                posting.add(interval);
            }
        }

        if (left.size() > 0)
            leftNode = new IntervalNode(left);
        if (right.size() > 0)
            rightNode = new IntervalNode(right);
    }

    public List> stab(long time)
    {
        List> result = new ArrayList>();

        for (Entry, List>> entry : intervals
                .entrySet())
        {
            if (entry.getKey().contains(time))
                for (Interval interval : entry.getValue())
                    result.add(interval);
            else if (entry.getKey().getStart() > time)
                break;
        }

        if (time < center && leftNode != null)
            result.addAll(leftNode.stab(time));
        else if (time > center && rightNode != null)
            result.addAll(rightNode.stab(time));
        return result;
    }

    public List> query(Interval target)
    {
        List> result = new ArrayList>();

        for (Entry, List>> entry : intervals
                .entrySet())
        {
            if (entry.getKey().intersects(target))
                for (Interval interval : entry.getValue())
                    result.add(interval);
            else if (entry.getKey().getStart() > target.getEnd())
                break;
        }

        if (target.getStart() < center && leftNode != null)
            result.addAll(leftNode.query(target));
        if (target.getEnd() > center && rightNode != null)
            result.addAll(rightNode.query(target));
        return result;
    }

    public long getCenter()
    {
        return center;
    }

    public void setCenter(long center)
    {
        this.center = center;
    }

    public IntervalNode getLeft()
    {
        return leftNode;
    }

    public void setLeft(IntervalNode left)
    {
        this.leftNode = left;
    }

    public IntervalNode getRight()
    {
        return rightNode;
    }

    public void setRight(IntervalNode right)
    {
        this.rightNode = right;
    }

    private Long getMedian(SortedSet set)
    {
        int i = 0;
        int middle = set.size() / 2;
        for (Long point : set)
        {
            if (i == middle)
                return point;
            i++;
        }
        return null;
    }

    @Override
    public String toString()
    {
        StringBuffer sb = new StringBuffer();
        sb.append(center + ": ");
        for (Entry, List>> entry : intervals
                .entrySet())
        {
            sb.append("[" + entry.getKey().getStart() + ","
                    + entry.getKey().getEnd() + "]:{");
            for (Interval interval : entry.getValue())
            {
                sb.append("(" + interval.getStart() + "," + interval.getEnd()
                        + "," + interval.getData() + ")");
            }
            sb.append("} ");
        }
        return sb.toString();
    }

}

class IntervalTree
{

    private IntervalNode   head;
    private List> intervalList;
    private boolean              inSync;
    private int                  size;

    public IntervalTree()
    {
        this.head = new IntervalNode();
        this.intervalList = new ArrayList>();
        this.inSync = true;
        this.size = 0;
    }

    public IntervalTree(List> intervalList)
    {
        this.head = new IntervalNode(intervalList);
        this.intervalList = new ArrayList>();
        this.intervalList.addAll(intervalList);
        this.inSync = true;
        this.size = intervalList.size();
    }

    public List get(long time)
    {
        List> intervals = getIntervals(time);
        List result = new ArrayList();
        for (Interval interval : intervals)
            result.add(interval.getData());
        return result;
    }

    public List> getIntervals(long time)
    {
        build();
        return head.stab(time);
    }

    public List get(long start, long end)
    {
        List> intervals = getIntervals(start, end);
        List result = new ArrayList();
        for (Interval interval : intervals)
            result.add(interval.getData());
        return result;
    }

    public List> getIntervals(long start, long end)
    {
        build();
        return head.query(new Interval(start, end, null));
    }

    public void addInterval(Interval interval)
    {
        intervalList.add(interval);
        inSync = false;
    }

    public void addInterval(long begin, long end, Type data)
    {
        intervalList.add(new Interval(begin, end, data));
        inSync = false;
    }

    public boolean inSync()
    {
        return inSync;
    }

    public void build()
    {
        if (!inSync)
        {
            head = new IntervalNode(intervalList);
            inSync = true;
            size = intervalList.size();
        }
    }

    public int currentSize()
    {
        return size;
    }

    public int listSize()
    {
        return intervalList.size();
    }

    @Override
    public String toString()
    {
        return nodeString(head, 0);
    }

    private String nodeString(IntervalNode node, int level)
    {
        if (node == null)
            return "";

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < level; i++)
            sb.append("\t");
        sb.append(node + "\n");
        sb.append(nodeString(node.getLeft(), level + 1));
        sb.append(nodeString(node.getRight(), level + 1));
        return sb.toString();
    }
}

public class IntervalTreeProblem
{
    public static void main(String args[])
    {
        IntervalTree it = new IntervalTree();

        it.addInterval(0L, 10L, 1);
        it.addInterval(20L, 30L, 2);
        it.addInterval(15L, 17L, 3);
        it.addInterval(25L, 35L, 4);

        List result1 = it.get(5L);
        List result2 = it.get(10L);
        List result3 = it.get(29L);
        List result4 = it.get(5L, 15L);

        System.out.print("\nIntervals that contain 5L:");
        for (int r : result1)
            System.out.print(r + " ");

        System.out.print("\nIntervals that contain 10L:");
        for (int r : result2)
            System.out.print(r + " ");

        System.out.print("\nIntervals that contain 29L:");
        for (int r : result3)
            System.out.print(r + " ");

        System.out.print("\nIntervals that intersect (5L,15L):");
        for (int r : result4)
            System.out.print(r + " ");
    }
}


Output:

Interval Tree Implementation

Intervals that contain 5L:1 
Intervals that contain 10L:
Intervals that contain 29L:2 4 
Intervals that intersect (5L,15L):1



More Java Programs: