class IntCell { private int value ; int getvalue() {return value; private IntCell next; IntCell next() {return next; IntCell(int value) {this.value =

Size: px

Start display at page:

Download "class IntCell { private int value ; int getvalue() {return value; private IntCell next; IntCell next() {return next; IntCell(int value) {this.value ="

しげのぶありの
7 years ago
Views:

1 Part2-1-3 Java (*) (*).class Java public static final 1

2 class IntCell { private int value ; int getvalue() {return value; private IntCell next; IntCell next() {return next; IntCell(int value) {this.value = value; IntCell(int value, IntCell cell) { this.value = value; next = cell; void showvalue() {System.out.print(value+" "); class IntList { private int size = 0; private IntCell firstcell = null; void tail() {// firstcell = firstcell.next(); size--; /* IntList IntCell IntCell so, polymorphism */ 2

4 Therefore, java.util 4

5 Heap: O(log n) 5

6 = (*) interface ObjectWithLessThan { boolean lessthan(objectwithlessthan y); void show(); // lessthan // lessthan // public int x ObjectWithLessThan x (x < y) x.lessthan(y) boolean lessthan(objectwithlessthan) (*) Java 6

7 class ClassName implements Interface1,Interface2,... implements public class Student implements ObjectWithLessThan{ private String name; private int score, code; public boolean lessthan(objectwithlessthan y) {// Student yrec = (Student)y; // /* y objectwithlessthan y Student y.name() yrec.name() Student */ return name.compareto(yrec.name) < 0; // return code < yrec.code; // // return score > yrec.score; // score public void show() { System.out.print(" "+name+","+score+" "); 7

8 class ζ {... σ method (τ 1 x 1,..., τ n x n ) { : ζ,, σ j,... : f : ζ, τ 1,..., τ n σ (ζ : self, this ) σ method (τ 1,..., τ n ) Java τ method (τ 1,..., τ n ) 1. (overload) 2., override 8

9 Interface z; z = (C)x; x C ow. : double z = 1.0; int x = (int)z; 9

10 class Heap { private ObjectWithLessThan[] heap; ObjectWithLessThan get(int index) {return heap[index]; private int size = 0; public int size() {return size; void reset() {size=0; private int capacity; Heap(int capacity) {// heap = new ObjectWithLessThan[capacity]; size = 0; this.capacity=capacity; private static int CAPACITY = 10000;// Heap() {// capacity = CAPACITY; heap = new ObjectWithLessThan[capacity]; size = 0; private void swap(int pt1, int pt2) { ObjectWithLessThan tmp; tmp=heap[pt1]; heap[pt1]=heap[pt2]; heap[pt2]=tmp; private boolean nonroot(int pt) {return pt > 0; // private int parent(int pt) {return (pt-1)/2; private int succ(int pt) { return 2*pt+1; private void insert(objectwithlessthan element){ if (++size > capacity) { System.out.println("*** "); System.exit(1); int pt, parent; heap[(pt=size-1)]=element; while(nonroot(pt) && heap[pt].lessthan(heap[(parent=parent(pt))])) { swap(pt,parent); pt = parent; ; void formheap(objectwithlessthan[] elements) { for (int i=0;i<elements.length;i++) insert(elements[i]); void showintheorder() { ObjectWithLessThan element; while ( (element=deletemin())!= null) element.show(); System.out.println(); 10

11 private ObjectWithLessThan deletemin(){ if (size==0) return null; ObjectWithLessThan min = heap[0]; heap[0] = heap[--size]; int pt = 0, branch; while((branch=succ(pt)) < size) { if (branch+1 < size && heap[branch+1].lessthan(heap[branch])) branch = branch+1; //take min among left and right childs if (!heap[branch].lessthan(heap[pt])) break; swap(branch,pt); pt = branch; ; return min; interface Show {// void show(); interface ObjectWithLessThan extends Show { boolean lessthan(objectwithlessthan y); class Teacher implements ObjectWithLessThan{ private int salary; private String name, division; Teacher(String name, String div, int salary) { this.salary=salary; this.name=name; division=div; public void show() { System.out.print("<"+name+","+division+","+salary+">, "); public boolean lessthan(objectwithlessthan y) { return salary < ((Teacher)y).salary; // class Student implements ObjectWithLessThan{ private String name; private int score; Student(String name, int score) {this.name=name; this.score=score; // public boolean lessthan(objectwithlessthan y) { return name.compareto(((student)y).name) < 0;//name public void show() {System.out.print("<"+name+","+score+">, "); 11

12 class MyInt implements ObjectWithLessThan{ private int value; MyInt(int i) {value = i; public boolean lessthan(objectwithlessthan y) { return value > ((MyInt)y).value; // public void show() {System.out.print("<"+value+">, "); class test { public static void main(string args[]){ Student[] ss = { new Student("mh",10), new Student("keiko",50), new Student("kenichi",100), new Student("taro",70) ; Teacher[] ts = {new Teacher("mh", "cs",400), new Teacher("sarah","physics",1000); MyInt[] is = {new MyInt(100), new MyInt(300), new MyInt(200); ObjectWithLessThan[][] testdata = {ss, ts, is;// Heap heap = new Heap(); for (int i=0;i<testdata.length;i++) { // heap.reset(); // heap heap.formheap(testdata[i]); System.out.print("+++ "+i+"-th sorted data: "); heap.showintheorder(); // heap ; ObjectWithLessThan[] objs = {new Student("satoshi",70), new MyInt(60); for (int i=0;i<objs.length;i++) objs[i].show(); System.out.println(); heap.formheap(objs);// c:\users\makoto\home\lecture\pl\resume>javac heap.java c:\users\makoto\home\lecture\pl\resume>java test th sorted data: <keiko,50>, <kenichi,100>, <mh,10>, <taro,70>, th sorted data: <mh,cs,400>, <sarah,physics,1000>, th sorted data: 300, 200, 100, <satoshi,70>, <60>, // Exception in thread "main" java.lang.classcastexception: Student cannot be cast to MyInt // lessthan //instanceof // // instancof 12

13 C1 {m11, m12 os1 {m21, m22 os2 13

14 Web Jave C ++ : Java 14

15 ConvexPolygon double boudarylength() (public) ObjectWithLessThan read() { if (size > 0) return deletemin(); else return null; Heap... class Point implements ObjectWithLessThan { private static final double PRECISION = 1.0e-7; // PRECISION private double x, y; double distance(point p) {//pow(x,y)=x^y ( ), sqrt return Math.sqrt(Math.pow(y-p.y,2)+Math.pow(x-p.x,2)); private static Point standardpoint; static void setstandardpoint(point p) { standardpoint=p; boolean eqx(point p) {// X return Math.abs(x - p.x) < PRECISION; public boolean lessthan(objectwithlessthan ap) { Point p = (Point)ap; if (eqx(standardpoint)) if (standardpoint.eqx(p)) return y + PRECISION < p.y; else return false; if (standardpoint.eqx(p)) return true; return slope(standardpoint) > p.slope(standardpoint) + PRECISION ; boolean pointeq(point p) {// return Math.abs(x-p.x) < PRECISION && Math.abs(y-p.y) < PRECISION ; public void show() {System.out.println("x="+x+", y="+y); 15

16 private double slope(point p) { return (y-p.y)/(x-p.x); /* (y-p.y)/(x-p.x) NaN, infinity slope Point private (Point ) lessthan lessthan. */ boolean morelefthigher(point p) { if ( x + PRECISION < p.x (eqx(p) && p.y + PRECISION < y) ) return true; else return false; class ConvexPolygon { private int nofpoints; // private Point[] points; // private Point standardpoint; private void setstandardpoint() { standardpoint = points[0]; for (int i=1;i<nofpoints;i++) if (points[i].morelefthigher(standardpoint)) standardpoint = points[i]; Point.setStandardPoint(standardPoint); private double boundarylength() { Heap heap = new Heap(nofPoints-1); //standardpoint for (int i=0;i<nofpoints;i++) if (!points[i].pointeq(standardpoint)) heap.insert(points[i]); double boundarylength = 0.0; Point presentpoint = standardpoint, nextpoint; while ((nextpoint = (Point)heap.read())!=null) { boundarylength += presentpoint.distance(nextpoint); presentpoint = nextpoint; ; return boundarylength + presentpoint.distance(standardpoint); public static void main(string args[]) { ConvexPolygon cp = new ConvexPolygon(); cp.readdatafromfile(args[0]); // // readdatafromfile points nofpoints cp.setstandardpoint(); System.out.println(" "+cp.boundarylength()); 16

17 1. lessthan Graham Jarvis Quickhull 17

class IntCell { private int value ; int getvalue() {return value; private IntCell next; IntCell next() {return next; IntCell(int value) {this.value =

Part2-1-3 Java (*) (*).class Java public static final 1 class IntCell { private int value ; int getvalue() {return value; private IntCell next; IntCell next() {return next; IntCell(int value) {this.value