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 = 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
1. 2. 3. 1. 2. 3. 3
Therefore, parent = (child-1)/2 java.util 4
Heap: O(log n) 5
= (*) 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
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
class ζ {... σ method (τ 1 x 1,..., τ n x n ) {...... : ζ,, σ j,... : f : ζ, τ 1,..., τ n σ (ζ : self, this ) σ method (τ 1,..., τ n ) Java τ method (τ 1,..., τ n ) 1. 2. 8
Interface z; z = (C)x; x C ow. : double z = 1.0; int x = (int)z; 9
class Heap { private ObjectWithLessThan[] heap; ObjectWithLessThan get(int index) {return heap[index]; private int size; int size() {return size; private int capacity; Heap(int capacity) { heap = new ObjectWithLessThan[capacity]; size = 0; this.capacity=capacity; 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; // left successor (child) // right succ+1 void insert(objectwithlessthan element){ if (++size > capacity) { System.out.println(" Heap: sorry, no space any more"); return; ; int pt, parent; heap[(pt=size-1)]=element; while(nonroot(pt) && heap[pt].lessthan(heap[(parent=parent(pt))])) { swap(pt,parent); pt = parent; ; private ObjectWithLessThan deletemin(){ 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 children if (!heap[branch].lessthan(heap[pt])) break; swap(branch,pt); pt = branch; ; return min; void showintheorder() { while (size > 0) deletemin().show(); System.out.println(); 10
interface ObjectWithLessThan { boolean lessthan(objectwithlessthan y); // //, public void show(); 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 score < ((Student)y).score; // // Student lessthan Student // so, Student score // y Student public void show() { System.out.print(" "+name+","+score+" "); public static void main(string args[]){ Student[] records = { new Student("mh",10), new Student("keiko",50), new Student("kenichi",100), new Student("taro",70) ; Heap heap = new Heap(records.length); for (int i=0; i<records.length; i++) heap.insert(records[i]); heap.showintheorder(); 11
C1 {m11, m12 os1 {m21, m22 os2 12
Web Java 13
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); 14
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()); 15
1. lessthan 2.... Graham Jarvis Quickhull 16