Java Program to Implement Interval Tree

This is a java program to implement Interval Tree. In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree. The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires T(n) time, where n is the number of intervals in the collection.

Here is the source code of the Java Program to Implement Interval Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to implement a interval tree
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. import java.util.Map.Entry;
  5. import java.util.SortedMap;
  6. import java.util.SortedSet;
  7. import java.util.TreeMap;
  8. import java.util.TreeSet;
  9.  
  10. class Interval<Type> implements Comparable<Interval<Type>>
  11. {
  12.  
  13.     private long start;
  14.     private long end;
  15.     private Type data;
  16.  
  17.     public Interval(long start, long end, Type data)
  18.     {
  19.         this.start = start;
  20.         this.end = end;
  21.         this.data = data;
  22.     }
  23.  
  24.     public long getStart()
  25.     {
  26.         return start;
  27.     }
  28.  
  29.     public void setStart(long start)
  30.     {
  31.         this.start = start;
  32.     }
  33.  
  34.     public long getEnd()
  35.     {
  36.         return end;
  37.     }
  38.  
  39.     public void setEnd(long end)
  40.     {
  41.         this.end = end;
  42.     }
  43.  
  44.     public Type getData()
  45.     {
  46.         return data;
  47.     }
  48.  
  49.     public void setData(Type data)
  50.     {
  51.         this.data = data;
  52.     }
  53.  
  54.     public boolean contains(long time)
  55.     {
  56.         return time < end && time > start;
  57.     }
  58.  
  59.     public boolean intersects(Interval<?> other)
  60.     {
  61.         return other.getEnd() > start && other.getStart() < end;
  62.     }
  63.  
  64.     public int compareTo(Interval<Type> other)
  65.     {
  66.         if (start < other.getStart())
  67.             return -1;
  68.         else if (start > other.getStart())
  69.             return 1;
  70.         else if (end < other.getEnd())
  71.             return -1;
  72.         else if (end > other.getEnd())
  73.             return 1;
  74.         else
  75.             return 0;
  76.     }
  77.  
  78. }
  79.  
  80. class IntervalNode<Type>
  81. {
  82.  
  83.     private SortedMap<Interval<Type>, List<Interval<Type>>> intervals;
  84.     private long                                            center;
  85.     private IntervalNode<Type>                              leftNode;
  86.     private IntervalNode<Type>                              rightNode;
  87.  
  88.     public IntervalNode()
  89.     {
  90.         intervals = new TreeMap<Interval<Type>, List<Interval<Type>>>();
  91.         center = 0;
  92.         leftNode = null;
  93.         rightNode = null;
  94.     }
  95.  
  96.     public IntervalNode(List<Interval<Type>> intervalList)
  97.     {
  98.  
  99.         intervals = new TreeMap<Interval<Type>, List<Interval<Type>>>();
  100.  
  101.         SortedSet<Long> endpoints = new TreeSet<Long>();
  102.  
  103.         for (Interval<Type> interval : intervalList)
  104.         {
  105.             endpoints.add(interval.getStart());
  106.             endpoints.add(interval.getEnd());
  107.         }
  108.  
  109.         long median = getMedian(endpoints);
  110.         center = median;
  111.  
  112.         List<Interval<Type>> left = new ArrayList<Interval<Type>>();
  113.         List<Interval<Type>> right = new ArrayList<Interval<Type>>();
  114.  
  115.         for (Interval<Type> interval : intervalList)
  116.         {
  117.             if (interval.getEnd() < median)
  118.                 left.add(interval);
  119.             else if (interval.getStart() > median)
  120.                 right.add(interval);
  121.             else
  122.             {
  123.                 List<Interval<Type>> posting = intervals.get(interval);
  124.                 if (posting == null)
  125.                 {
  126.                     posting = new ArrayList<Interval<Type>>();
  127.                     intervals.put(interval, posting);
  128.                 }
  129.                 posting.add(interval);
  130.             }
  131.         }
  132.  
  133.         if (left.size() > 0)
  134.             leftNode = new IntervalNode<Type>(left);
  135.         if (right.size() > 0)
  136.             rightNode = new IntervalNode<Type>(right);
  137.     }
  138.  
  139.     public List<Interval<Type>> stab(long time)
  140.     {
  141.         List<Interval<Type>> result = new ArrayList<Interval<Type>>();
  142.  
  143.         for (Entry<Interval<Type>, List<Interval<Type>>> entry : intervals
  144.                 .entrySet())
  145.         {
  146.             if (entry.getKey().contains(time))
  147.                 for (Interval<Type> interval : entry.getValue())
  148.                     result.add(interval);
  149.             else if (entry.getKey().getStart() > time)
  150.                 break;
  151.         }
  152.  
  153.         if (time < center && leftNode != null)
  154.             result.addAll(leftNode.stab(time));
  155.         else if (time > center && rightNode != null)
  156.             result.addAll(rightNode.stab(time));
  157.         return result;
  158.     }
  159.  
  160.     public List<Interval<Type>> query(Interval<?> target)
  161.     {
  162.         List<Interval<Type>> result = new ArrayList<Interval<Type>>();
  163.  
  164.         for (Entry<Interval<Type>, List<Interval<Type>>> entry : intervals
  165.                 .entrySet())
  166.         {
  167.             if (entry.getKey().intersects(target))
  168.                 for (Interval<Type> interval : entry.getValue())
  169.                     result.add(interval);
  170.             else if (entry.getKey().getStart() > target.getEnd())
  171.                 break;
  172.         }
  173.  
  174.         if (target.getStart() < center && leftNode != null)
  175.             result.addAll(leftNode.query(target));
  176.         if (target.getEnd() > center && rightNode != null)
  177.             result.addAll(rightNode.query(target));
  178.         return result;
  179.     }
  180.  
  181.     public long getCenter()
  182.     {
  183.         return center;
  184.     }
  185.  
  186.     public void setCenter(long center)
  187.     {
  188.         this.center = center;
  189.     }
  190.  
  191.     public IntervalNode<Type> getLeft()
  192.     {
  193.         return leftNode;
  194.     }
  195.  
  196.     public void setLeft(IntervalNode<Type> left)
  197.     {
  198.         this.leftNode = left;
  199.     }
  200.  
  201.     public IntervalNode<Type> getRight()
  202.     {
  203.         return rightNode;
  204.     }
  205.  
  206.     public void setRight(IntervalNode<Type> right)
  207.     {
  208.         this.rightNode = right;
  209.     }
  210.  
  211.     private Long getMedian(SortedSet<Long> set)
  212.     {
  213.         int i = 0;
  214.         int middle = set.size() / 2;
  215.         for (Long point : set)
  216.         {
  217.             if (i == middle)
  218.                 return point;
  219.             i++;
  220.         }
  221.         return null;
  222.     }
  223.  
  224.     @Override
  225.     public String toString()
  226.     {
  227.         StringBuffer sb = new StringBuffer();
  228.         sb.append(center + ": ");
  229.         for (Entry<Interval<Type>, List<Interval<Type>>> entry : intervals
  230.                 .entrySet())
  231.         {
  232.             sb.append("[" + entry.getKey().getStart() + ","
  233.                     + entry.getKey().getEnd() + "]:{");
  234.             for (Interval<Type> interval : entry.getValue())
  235.             {
  236.                 sb.append("(" + interval.getStart() + "," + interval.getEnd()
  237.                         + "," + interval.getData() + ")");
  238.             }
  239.             sb.append("} ");
  240.         }
  241.         return sb.toString();
  242.     }
  243.  
  244. }
  245.  
  246. class IntervalTree<Type>
  247. {
  248.  
  249.     private IntervalNode<Type>   head;
  250.     private List<Interval<Type>> intervalList;
  251.     private boolean              inSync;
  252.     private int                  size;
  253.  
  254.     public IntervalTree()
  255.     {
  256.         this.head = new IntervalNode<Type>();
  257.         this.intervalList = new ArrayList<Interval<Type>>();
  258.         this.inSync = true;
  259.         this.size = 0;
  260.     }
  261.  
  262.     public IntervalTree(List<Interval<Type>> intervalList)
  263.     {
  264.         this.head = new IntervalNode<Type>(intervalList);
  265.         this.intervalList = new ArrayList<Interval<Type>>();
  266.         this.intervalList.addAll(intervalList);
  267.         this.inSync = true;
  268.         this.size = intervalList.size();
  269.     }
  270.  
  271.     public List<Type> get(long time)
  272.     {
  273.         List<Interval<Type>> intervals = getIntervals(time);
  274.         List<Type> result = new ArrayList<Type>();
  275.         for (Interval<Type> interval : intervals)
  276.             result.add(interval.getData());
  277.         return result;
  278.     }
  279.  
  280.     public List<Interval<Type>> getIntervals(long time)
  281.     {
  282.         build();
  283.         return head.stab(time);
  284.     }
  285.  
  286.     public List<Type> get(long start, long end)
  287.     {
  288.         List<Interval<Type>> intervals = getIntervals(start, end);
  289.         List<Type> result = new ArrayList<Type>();
  290.         for (Interval<Type> interval : intervals)
  291.             result.add(interval.getData());
  292.         return result;
  293.     }
  294.  
  295.     public List<Interval<Type>> getIntervals(long start, long end)
  296.     {
  297.         build();
  298.         return head.query(new Interval<Type>(start, end, null));
  299.     }
  300.  
  301.     public void addInterval(Interval<Type> interval)
  302.     {
  303.         intervalList.add(interval);
  304.         inSync = false;
  305.     }
  306.  
  307.     public void addInterval(long begin, long end, Type data)
  308.     {
  309.         intervalList.add(new Interval<Type>(begin, end, data));
  310.         inSync = false;
  311.     }
  312.  
  313.     public boolean inSync()
  314.     {
  315.         return inSync;
  316.     }
  317.  
  318.     public void build()
  319.     {
  320.         if (!inSync)
  321.         {
  322.             head = new IntervalNode<Type>(intervalList);
  323.             inSync = true;
  324.             size = intervalList.size();
  325.         }
  326.     }
  327.  
  328.     public int currentSize()
  329.     {
  330.         return size;
  331.     }
  332.  
  333.     public int listSize()
  334.     {
  335.         return intervalList.size();
  336.     }
  337.  
  338.     @Override
  339.     public String toString()
  340.     {
  341.         return nodeString(head, 0);
  342.     }
  343.  
  344.     private String nodeString(IntervalNode<Type> node, int level)
  345.     {
  346.         if (node == null)
  347.             return "";
  348.  
  349.         StringBuffer sb = new StringBuffer();
  350.         for (int i = 0; i < level; i++)
  351.             sb.append("\t");
  352.         sb.append(node + "\n");
  353.         sb.append(nodeString(node.getLeft(), level + 1));
  354.         sb.append(nodeString(node.getRight(), level + 1));
  355.         return sb.toString();
  356.     }
  357. }
  358.  
  359. public class IntervalTreeProblem
  360. {
  361.     public static void main(String args[])
  362.     {
  363.         IntervalTree<Integer> it = new IntervalTree<Integer>();
  364.  
  365.         it.addInterval(0L, 10L, 1);
  366.         it.addInterval(20L, 30L, 2);
  367.         it.addInterval(15L, 17L, 3);
  368.         it.addInterval(25L, 35L, 4);
  369.  
  370.         List<Integer> result1 = it.get(5L);
  371.         List<Integer> result2 = it.get(10L);
  372.         List<Integer> result3 = it.get(29L);
  373.         List<Integer> result4 = it.get(5L, 15L);
  374.  
  375.         System.out.print("\nIntervals that contain 5L:");
  376.         for (int r : result1)
  377.             System.out.print(r + " ");
  378.  
  379.         System.out.print("\nIntervals that contain 10L:");
  380.         for (int r : result2)
  381.             System.out.print(r + " ");
  382.  
  383.         System.out.print("\nIntervals that contain 29L:");
  384.         for (int r : result3)
  385.             System.out.print(r + " ");
  386.  
  387.         System.out.print("\nIntervals that intersect (5L,15L):");
  388.         for (int r : result4)
  389.             System.out.print(r + " ");
  390.     }
  391. }

Output:

$ javac IntervalTreeImplementation.java
$ java IntervalTreeImplementation
 
Interval Tree Implementation
 
Intervals that contain 5L:1 
Intervals that contain 10L:
Intervals that contain 29L:2 4 
Intervals that intersect (5L,15L):1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.