Pseudo code for 1D Range search You will implement 1D range tree first, and then

Question

Pseudo code for 1D Range search

You will implement 1D range tree first, and then generalized it to 2D.

///////////////////////////////////////////    RangeTree1D.java//////////////////////////////////////////////////////////////////////////////////

import java.util.Comparator;

// There are 3 Tasks in this file

public class RangeTree1D<T>
{
//Task 1: this is Build1DRangeTree(P) (20 pts)
public Node<T> build( T [] data_array)
{
    //your code here.

    return null;
}

//Task #2: FindSplitNode(x, x')
//Method to find the split node.
protected Node<T> FindSplitNode( Range range)
{
    return null;
}

//Method to make range and call search.
//Do NOT CHANGE THIS FUNCTION
public IterableLinkedList<T> Search1D(T min, T max)
{
    IterableLinkedList<T> l = new IterableLinkedList<T>();
    Search1D(new Range(min, max), l);
    return l;
}

//
// Task #3: RangeSearch_1D(x,x') (25 pts)
// Note 1: Store results in "l"
// Note 2: Use reportSubTree method below
//
public void Search1D(Range query, IterableLinkedList<T> l)
{
    //your code here
}

//change this function to test your 1D range search locally
//make sure you have this class working before moving to RangeTree2D
public static void main(String [] args)
{
    //your test code here
    class NC implements Comparator<Double> {
      public int compare(Double o1, Double o2){
        Double r=o1-o2;
        if(r>0) return 1;
        else if(r<0) return -1;
        else return 0;
      }
    }

    //
    RangeTree1D<Double> RT1D=new RangeTree1D<>(new NC());
    Double [] data={2.0,7.0,3.0,4.0,5.0,6.0,1.0,8.0,9.0,10.0};
    RT1D.build(data);
    Double min=3.5, max=7.99;
    IterableLinkedList<Double> result=RT1D.Search1D(min, max);
    result.sort(new NC());
    System.out.println("Query: "+min+" "+max+" Results=");
    for(Double v : result)
    {
      System.out.println(v);
    }
}

//
// !!! DO NOT CHANGE ANYTHING BELOW !!!
//

protected Comparator<T> comp;

public RangeTree1D(Comparator<T> _comp)
{
    this.comp=_comp;
}

public class Range
{
    public T min, max;

    public Range(T _min, T _max)
    {
      this.min=_min; this.max=_max;
    }

    public boolean is_inside(T p)
    {
        return (comp.compare(p,min) >= 0 && comp.compare(max,p) >= 0);
    }
}

public class Node<T>
{
    public Node<T> left, right;
    RangeTree1D<T> next_level;
    public T data;

    public boolean is_leaf(){ return left == null && right == null; }
    public boolean has_next_level(){ return next_level!=null; }
}

protected Node<T> root;

//Method to report subtree
protected void reportSubTree(Node<T> n,IterableLinkedList<T> l)
{
    if(n.right == null && n.left == null){
      l.add(n.data);
    }
    else{
      reportSubTree(n.left,l);
      reportSubTree(n.right,l);
    }
}

}

*****************************************************************************************************************************************************************************************************************

Explanation / Answer

RangeTree1D.java

import java.util.Comparator;

// There are 3 Tasks in this file

public class RangeTree1D<T>

{

//Task 1: this is Build1DRangeTree(P) (20 pts)

public Node<T> build( T [] data_array)

{

//your code here.

return null;

}

//Task #2: FindSplitNode(x, x')

//Method to find the split node.

protected Node<T> FindSplitNode( Range range)

{

return null;

}

//Method to make range and call search.

//Do NOT CHANGE THIS FUNCTION

public IterableLinkedList<T> Search1D(T min, T max)

{

IterableLinkedList<T> l = new IterableLinkedList<T>();

Search1D(new Range(min, max), l);

return l;

}

//

// Task #3: RangeSearch_1D(x,x') (25 pts)

// Note 1: Store results in "l"

// Note 2: Use reportSubTree method below

//

public void Search1D(Range query, IterableLinkedList<T> l)

{

//your code here

}

//change this function to test your 1D range search locally

//make sure you have this class working before moving to RangeTree2D

public static void main(String [] args)

{

//your test code here

class NC implements Comparator<Double> {

public int compare(Double o1, Double o2){

Double r=o1-o2;

if(r>0) return 1;

else if(r<0) return -1;

else return 0;

}

}

//

RangeTree1D<Double> RT1D=new RangeTree1D<>(new NC());

Double [] data={2.0,7.0,3.0,4.0,5.0,6.0,1.0,8.0,9.0,10.0};

RT1D.build(data);

Double min=3.5, max=7.99;

IterableLinkedList<Double> result=RT1D.Search1D(min, max);

result.sort(new NC());

System.out.println("Query: "+min+" "+max+" Results=");

for(Double v : result)

{

System.out.println(v);

}

}

//

// !!! DO NOT CHANGE ANYTHING BELOW !!!

//

protected Comparator<T> comp;

public RangeTree1D(Comparator<T> _comp)

{

this.comp=_comp;

}

public class Range

{

public T min, max;

public Range(T _min, T _max)

{

this.min=_min; this.max=_max;

}

public boolean is_inside(T p)

{

return (comp.compare(p,min) >= 0 && comp.compare(max,p) >= 0);

}

}

public class Node<T>

{

public Node<T> left, right;

RangeTree1D<T> next_level;

public T data;

public boolean is_leaf(){ return left == null && right == null; }

public boolean has_next_level(){ return next_level!=null; }

}

protected Node<T> root;

//Method to report subtree

protected void reportSubTree(Node<T> n,IterableLinkedList<T> l)

{

if(n==null) return; //do nothing

if(n.right == null && n.left == null){

l.add(n.data);

}

else{

reportSubTree(n.left,l);

reportSubTree(n.right,l);

}

}

}

RangeTree2D.java

import java.util.Comparator;

// There are 2 Tasks in this file

public class RangeTree2D<T> extends RangeTree1D<T>

{

// Task #4: this is Build2DRangeTree(P)

// Build 2D Range Tree (15 pts)

public Node<T> build( T [] data_array)

{

return null;

}

// Task #5: this is RangeSearch_2D(x,x', y, y') (25 pts)

public void Search2D(Range query, IterableLinkedList<T> l)

{

//Your code here

}

//!!! Do NOT CHANGE BELOW !!!

public IterableLinkedList<T> Search2D(T min, T max)

{

IterableLinkedList<T> l = new IterableLinkedList<T>();

Search2D(new Range(min, max), l);

return l;

}

Comparator<T> comp_next_level;

RangeTree2D(Comparator<T> _comp_x, Comparator<T> _comp_y)

{

super(_comp_x); //comparator for X tree

this.comp_next_level=_comp_y; //comparator for Y tree

}

}

cs310pa2.java

import java.util.Scanner;

import java.io.File;

import java.io.IOException;

import java.io.FileWriter;

import java.io.FileNotFoundException;

import java.util.Comparator;

public class cs310pa2

{

static public class Point2D

{

Point2D(Double _x, Double _y){x=_x;y=_y;}

public String toString()

{

return x+" "+y;

}

Double x, y;

}

@SuppressWarnings("unchecked")

public static void main(String args[])

{

String filename=null;

boolean savesvg=false;

for(String arg: args)

{

if(arg.compareTo("-svg")==0) savesvg=true;

filename=arg;

}

if(filename==null)

{

System.err.println("Usage: [-svg] cs310pa2 *.txt");

return;

}

// Scanner scanData = new Scanner(System.in);

// int numPoints = scanData.nextInt();

// int count = 0;

// double[] data = new double[numPoints*3];

try

{

Scanner scanner = new Scanner(new File(filename));

Point2D [] data=readPoints(scanner);

System.out.println("Read in "+data.length+" points");

//create the tree

RangeTree2D<Point2D> rt = new RangeTree2D<Point2D>(

new Comparator<Point2D>(){public int compare(Point2D a, Point2D b){ Double r=a.x-b.x; return (r>0)?1:((r<0)?-1:0);}},

new Comparator<Point2D>(){public int compare(Point2D a, Point2D b){ Double r=a.y-b.y; return (r>0)?1:((r<0)?-1:0);}}

);

rt.build(data);

//read query

int query_count=0;

while(scanner.hasNextDouble())

{

Double xMin = scanner.nextDouble();

Double xMax = scanner.nextDouble();

Double yMin = scanner.nextDouble();

Double yMax = scanner.nextDouble();

System.out.println("Query: "+xMin+" "+xMax+" "+yMin+" "+yMax);

//make a query

IterableLinkedList<Point2D> result = rt.Search2D(new Point2D(xMin,yMin), new Point2D(xMax,yMax) );

result.sort(new Comparator<Point2D>(){public int compare(Point2D a, Point2D b){

Double r=a.x-b.x;

if(r==0) r=a.y-b.y;

return (r>0)?1:((r<0)?-1:0);

}});

//print results

System.out.print("Found "+result.size()+" point");

if(result.size()>1) System.out.print("s");

System.out.println(" ");

for(Point2D v : result)

{

System.out.println(v);

}

//save to svg

if(savesvg)

{

String svgfilename="result_"+query_count+".svg";

saveSVG(svgfilename,new Point2D(xMin,yMin), new Point2D(xMax,yMax),data,result);

query_count++;

}

}//end while

//done

System.out.println("Query: exit bye");

}

catch (FileNotFoundException e) {

e.printStackTrace();

}

}//end main

//read a polygon from file

private static Point2D [] readPoints(Scanner scan)

{

try {

int size;

if(scan.hasNextInt()) size=scan.nextInt(); else throw new IOException("size is not given");

Point2D [] data=new Point2D[size];

for(int id=0;id<size;id++)

{

double x, y;

if(scan.hasNextDouble()) x=scan.nextDouble();

else throw new IOException("X value is not given");

if(scan.hasNextDouble()) y=scan.nextDouble();

else throw new IOException("Y value is not given");

data[id]=new Point2D(x,y);

}

return data;

}

catch (IOException e){

e.printStackTrace();

}

return null;

}

static public void saveSVG(String filename, Point2D qmin, Point2D qmax, Point2D [] data, IterableLinkedList<Point2D> result)

{

try

{

FileWriter fileWriter = new FileWriter(new File(filename));

double radius=1;

//write svg header

{

double [] bbox={Double.MAX_VALUE,-Double.MAX_VALUE,Double.MAX_VALUE,-Double.MAX_VALUE};

for(Point2D pt : data)

{

if(pt.x < bbox[0]) bbox[0]=pt.x;

if(pt.x > bbox[1]) bbox[1]=pt.x;

if(pt.y < bbox[2]) bbox[2]=pt.y;

if(pt.y > bbox[3]) bbox[3]=pt.y;

}

//padding

double width=(bbox[1]-bbox[0]);

double height=(bbox[3]-bbox[2]);

double pad=Math.min(width,height)/10;

bbox[0]-=pad; bbox[1]+=pad; bbox[2]-=pad; bbox[3]+=pad;

width=(bbox[1]-bbox[0]);

height=(bbox[3]-bbox[2]);

radius=Math.min(width,height)*1.0/200;

//

String header="<?xml version="1.0" standalone="no" ?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> <svg ";

header+=(" width=""+ 800 +"px""); //let us fix the window size to 800x800

header+=(" height=""+ 800 +"px"");

header+=(" viewBox=""+bbox[0]+" "+bbox[2]+" "+width+" "+height+" "");

header+=(" xmlns="http://www.w3.org/2000/svg"");

header+=(" version="1.1""+"> ");

fileWriter.write(header);

}

//write each point

double R=200.0, G=50.0, B=120.0;

for(Point2D pt : data)

{

fileWriter.write(svgCircle(pt,radius,R,G,B));

}

//write Range

{

R=250.0; G=250.0; B=120.0;

fileWriter.write(svgBox(qmin,qmax,radius,R,G,B));

}

//write points in range

radius*=1.1;

R=50.0; G=250.0; B=120.0;

for(Point2D pt : result)

{

fileWriter.write(svgCircle(pt,radius,R,G,B));

}

//write svg footer

{

String footer="</svg> ";

fileWriter.write(footer);

}

//done

fileWriter.flush();

fileWriter.close();

}

catch (IOException e) {

e.printStackTrace();

}

System.out.println("- Saved results to "+filename);

}

public static String svgCircle(Point2D pt, double radius, double R, double G, double B)

{

double stroke_width=radius/10;

String str="<circle cx=""+pt.x+"" cy=""+pt.y+"" r=""+radius+""";

str+=" fill="rgb("+R+","+G+","+B+")" ";

str+=" stroke-width=""+stroke_width+"" stroke="rgb("+R/3+","+G/3+","+B/3+")" ";

str+="/> ";

return str;

}

public static String svgBox(Point2D qmin, Point2D qmax, double radius, double R, double G, double B)

{

String str="<rect x=""+qmin.x+"" y=""+qmin.y+"" width=""+(qmax.x-qmin.x)+"" height=""+(qmax.y-qmin.y)+""";

str+=" fill="rgb("+R+","+G+","+B+")" fill-opacity="0.4" ";

str+=" stroke-width=""+radius/10+"" stroke="rgb("+R/2+","+G/2+","+B/2+")" ";

str+="/> ";

return str;

}

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.