-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcode.html
More file actions
952 lines (880 loc) · 35.7 KB
/
code.html
File metadata and controls
952 lines (880 loc) · 35.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
<!DOCTYPE html>
<html lang="en-us">
<head>
<meta charset="utf-8">
<title>BuiltByCooper - Code Samples</title>
<link rel="stylesheet" href="css/style.css" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata" rel="stylesheet">
<link href="https://fonts.googleapis.com/css?family=Josefin+Sans" rel="stylesheet">
<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js?lang=java&skin=desert"></script>
<link rel="stylesheet" href="https://ajax.googleapis.com/ajax/libs/jqueryui/1.12.1/themes/smoothness/jquery-ui.css">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link href="data:image/x-icon;base64,AAABAAEAEBAAAAEAIABoBAAAFgAAACgAAAAQAAAAIAAAAAEAIAAAAAAAAAQAABILAAASCwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAsAAAAAAAAARwAAADkAAAAAAAAAAAAAAAAAAAALAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABwAAAHYAAAC9AAAAAAAAAGMAAAC8AAAAAAAAAAAAAAAAAAAAvgAAAHkAAAAIAAAAAAAAAAAAAAABAAAATQAAANoAAAD+AAAAmAAAAAAAAAAVAAAA9gAAABUAAAAAAAAAAAAAAJEAAAD9AAAA3gAAAFQAAAABAAAArAAAAP8AAADJAAAARAAAAAAAAAAAAAAAAAAAALsAAABlAAAAAAAAAAAAAAAAAAAAMgAAALQAAAD/AAAAuAAAALgAAAD/AAAAtAAAADIAAAAAAAAAAAAAAAAAAABoAAAAuQAAAAAAAAAAAAAAAAAAAEQAAADJAAAA/wAAAKwAAAABAAAAVAAAAN4AAAD9AAAAkQAAAAAAAAAAAAAAFwAAAPYAAAAUAAAAAAAAAJkAAAD+AAAA2gAAAE0AAAABAAAAAAAAAAAAAAAIAAAAeQAAAL4AAAAAAAAAAAAAAAAAAADAAAAAYgAAAAAAAAC9AAAAdgAAAAcAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAALAAAAAAAAAAAAAAAAAAAAOwAAAEcAAAAAAAAACwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA//8AAP//AAD//wAA//8AAPTvAADE4wAABGAAAARgAAAGIAAABiAAAMcjAAD3LwAA//8AAP//AAD//wAA//8AAA==" rel="icon" type="image/x-icon">
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-92893041-1', 'auto');
ga('send', 'pageview');
</script>
</head>
<body>
<div class="container-fluid"><!-- begin Container -->
<div class="right-side"> <!-- begin right side container -->
<div class="hero-right"><!-- begin hero right -->
<div id="dynamic-runtime"><!-- begin dynamic runtime environment -->
<h1>Start Here!</h1>
<p>
Welcome to your interactive code viewer. Access code snippets via the terminal below by clicking next to the carat below "java links".
Type "run" and a list of commands will appear. Press enter (or click) to select a command, then again to run it. </br></br> Code snippets are displayed in the other terminal and code notes will appear right here.
All code comes from work done at UMass Boston (under Professor Iyer), and utilizes the great work and libraries of the Princeton University CS department.
</p>
</div><!-- end dynamic runtime environment -->
</div><!--end hero right -->
<div id="terminal"> <!-- here is the "terminal" -->
<p id="cursor">> java links</p><br/>
<span id="cursor"> => ["<a href="index.html">home</a>",
"<a href="websamples.html">web samples</a>", <a href="http://www.blog.builtbycooper.com">problem solving blog</a>"]<br/></span></br>
<p id="cursor">><input type="textarea" id="code-input" value=""></p>
</div><!-- end the Terminal -->
</div><!-- end right side -->
<div class="left-side"><!-- begin left side container-->
<div class="hero-left"><!-- begin hero left -->
<div class="code-block"><!-- begin code block div -->
<code id="dynamic-code"> <!-- this is the dynamic code block-->
<!--
CAUTION: If you are looking at this section, don't judge me. Code gets ugly from here on out because <pre> blocks display in relation to their whitespace
in html. To get left aligned text, I had to slam the html up against the left side and it looks terrible. These don't display on the site unless they are
called via the terminal. This ends my caution.
-->
<pre class="prettyprint" id="kdTrees">
import edu.princeton.cs.algs4.MaxPQ;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class KdTreePointST<Value> implements PointST<Value> {
private Node root; // root of the KdTree
private int N; // number of nodes in the KdTree
// 2d-tree (generalization of a BST in 2d) representation.
private class Node {
private Point2D p; // the point
private Value val; // the symbol table maps the point to this value
private RectHV rect; // the axis-aligned rectangle corresponding to
// this node
private Node lb; // the left/bottom subtree
private Node rt; // the right/top subtree
// Construct a node given the point, the associated value, and the
// axis-aligned rectangle corresponding to the node.
Node(Point2D p, Value val, RectHV rect) {
//instantiate the node
this.p = p;
this.val = val;
this.rect = rect;
//set rb and lb to null, will populate later
this.lb = null;
this.rt = null;
}
}
// Construct an empty symbol table of points.
public KdTreePointST() {
this.N = 0;
this.root = null;
}
// Is the symbol table empty?
public boolean isEmpty() {
return N == 0;
}
// Number of points in the symbol table.
public int size() {
return N;
}
// Associate the value val with point p.
public void put(Point2D p, Value val) {
if (val == null || p == null) {
throw new IllegalArgumentException("first arg is null");
}
//set a rect to base values for use in put
RectHV rect = new RectHV(0, 0, 1, 1);
//root equals call to put, starting with a true flag
root = put(root, p, val, rect, true);
}
// Helper for put(Point2D p, Value val).
private Node put(Node x, Point2D p, Value val, RectHV rect, boolean lr) {
if (x == null) { //if no node then create one
N++;
return new Node(p, val, rect);
}
if (x.p.equals(p)) { // if the keys are the same then return the node
x.val = val;
return x;
}
//if lr is true, compare the x values to place the new node
if (lr) {
//if new point has smaller x, recursive call to put in left branch
if (p.x() < x.p.x()) {
//new rect is put to begin at limits of parent rect
RectHV rect1 = new RectHV(rect.xmin(), rect.ymin(),
x.p.x(), rect.ymax());
//recursive call to left branch with new rectangle
x.lb = put(x.lb, p, val, rect1, !lr);
}
//if new point has greater x, call to put in right branch
else if (p.x() >= x.p.x()) {
//new rect begins at the limits of parent rect
RectHV rect1 = new RectHV(x.p.x(), rect.ymin(),
rect.xmax(), rect.ymax());
//recursive call to right tree with new rectangle
x.rt = put(x.rt, p, val, rect1, !lr);
}
}
//if lr is false, only compare the y values to place node
if (!lr) {
//if new point has smaller y, make call to put in left branch
if (p.y() < x.p.y()) {
//set the rect to begin at limits of parent
RectHV rect1 = new RectHV(rect.xmin(), rect.ymin(),
rect.xmax(), x.p.y());
//put in left branch with recursive call
x.lb = put(x.lb, p, val, rect1, !lr);
}
//if new point has larger y, put in right tree
else if (p.y() >= x.p.y()) {
//rect begins at parents limits
RectHV rect1 = new RectHV(rect.xmin(), x.p.y(),
rect.xmax(), rect.ymax());
//put in the right tree with recursive call
x.rt = put(x.rt, p, val, rect1, !lr);
}
}
return x; //return node x
}
// Value associated with point p.
public Value get(Point2D p) {
return get(root, p, true);
}
// Helper for get(Point2D p).
private Value get(Node x, Point2D p, boolean lr) {
//if no node, return null
if (x == null) {
return null;
}
//if asking for the current nodes point, return that
if (x.p.equals(p)) {
return x.val;
}
//if true, compare to x values to find the correct branch
if (lr) {
//if x is smaller, prune right branch
if (p.x() < x.p.x()) {
return get(x.lb, p, !lr);
}
//if x is larger, prune left branch
if (p.x() >= x.p.x()) {
return get(x.rt, p, !lr);
}
}
//if false, compare to y values to find right branch
if (!lr) {
//if y is smaller, prune right branch
if (p.y() < x.p.y()) {
return get(x.lb, p, !lr);
}
//if x is small, prune left branch
if (p.y() >= x.p.y()) {
return get(x.rt, p, !lr);
}
}
return x.val;
}
// Does the symbol table contain the point p?
public boolean contains(Point2D p) {
if (p == null) {
throw new IllegalArgumentException("argument is null");
}
return get(p) != null;
}
// All points in the symbol table, in level order.
public Iterable<Point2D> points() {
//create a queue to hold nodes, one for points
Queue<Point2D> keys = new Queue<Point2D>();
Queue<Node> queue = new Queue<Node>();
//begin with the root
queue.enqueue(root);
//while the node queue has something in it...
while (!queue.isEmpty()) {
//set the temp node x
Node x = queue.dequeue();
//if its null, get out of there!
if (x == null) continue;
//enqueue the temps point values
keys.enqueue(x.p);
//enqueue the right and left child nodes to begin again
queue.enqueue(x.lb);
queue.enqueue(x.rt);
}
//return the keys
return keys;
}
// All points in the symbol table that are inside the rectangle rect.
public Iterable<Point2D> range(RectHV rect) {
//create the queue
Queue<Point2D> results = new Queue<Point2D>();
if (!isEmpty()) {
//make call to helper function
range(root, rect, results);
}
return results;
}
// Helper for public range(RectHV rect).
private void range(Node x, RectHV rect, Queue<Point2D> q) {
//base case using rect api
if (rect.contains(x.p)) {
q.enqueue(x.p);
}
//if left branch exists and the rectangles overlap,
//search within the left branch for points
if (x.lb != null) {
if (rect.intersects(x.lb.rect)) {
range(x.lb, rect, q);
}
}
//if the right branch exists and the rectangles overlap,
//search within the right branch
if (x.rt != null) {
if (rect.intersects(x.rt.rect)) {
range(x.rt, rect, q);
}
}
}
// A nearest neighbor to point p; null if the symbol table is empty.
public Point2D nearest(Point2D p) {
if (isEmpty()) {
return null;
}
//set values to pass to the helper fucntion
return nearest(root, p, null, 0.0, true);
}
// Helper for public nearest(Point2D p).
private Point2D nearest(Node x, Point2D p, Point2D nearest,
double nearestDistance, boolean lr) {
//set the current nearest
Point2D currentNearest = nearest;
//base case 1, if no x, return last nearest
if (x == null) {
return nearest;
}
//second basecase. Currentnearest null checks for empty branches
//if new nearest is farther away, and the distance isnt zero
//which ensures you dont return the searching point,
//then return the x.p
if ((currentNearest == null)
|| (currentNearest.distanceSquaredTo(p)
> x.p.distanceSquaredTo(p))
&& x.p.distanceSquaredTo(p) != 0) {
currentNearest = x.p;
}
//set up stand ins for the rt and lb.
Node first, second;
//if true, compare with x values to determine branch order
if (lr) {
//sets normal order branches for recursive searching
if (p.x() < x.p.x()) {
first = x.lb;
second = x.rt;
}
//sets opposite order branches for recursive searching
else {
first = x.rt;
second = x.lb;
}
}
//if false, compare y values to determine branch order
else {
//sets normal order branches for recursive searching
if (p.y() < x.p.y()) {
first = x.lb;
second = x.rt;
}
//sets opposite order branches for recursive searching
else {
first = x.rt;
second = x.lb;
}
}
//if the branch exists, and the distance is greater
//go down the smaller valued branch
if (first != null) {
if (currentNearest.distanceSquaredTo(p)
> first.rect.distanceSquaredTo(p)) {
currentNearest = nearest(first, p, currentNearest,
first.rect.distanceSquaredTo(p), !lr);
}
}
//if the branch exists, and the distance is greater
//go down the smaller valued branch
if (second != null) {
if (currentNearest.distanceSquaredTo(p)
> second.rect.distanceSquaredTo(p)) {
currentNearest = nearest(second, p, currentNearest,
second.rect.distanceSquaredTo(p), !lr);
}
}
return currentNearest;
}
// k points that are closest to point p.
public Iterable<Point2D> nearest(Point2D p, int k) {
//create all values for helper function
MaxPQ<Point2D> pq = new MaxPQ<Point2D>(p.distanceToOrder());
nearest(root, p, k, pq, true);
return pq;
}
// Helper for public nearest(Point2D p, int k).
private void nearest(Node x, Point2D p, int k, MaxPQ<Point2D> pq,
boolean lr) {
//if no null or k, return
if (x == null || k == 0) {
return;
}
//if the pq is too large, delete some!
if (pq.size() > k) {
pq.delMax();
}
//if the size is big and the top is closer, its all wrong
if (pq.size() >= k && pq.max().distanceSquaredTo(p)
<= x.rect.distanceSquaredTo(p)) {
return;
}
//as long as the point isnt the search point, insert!
if (!x.p.equals(p)) {
pq.insert(x.p);
}
//recursive calls to check the branches
nearest(x.lb, p, k, pq, !lr);
nearest(x.rt, p, k, pq, !lr);
}
</pre>
<pre class="prettyprint" id="seamCarver">
import java.awt.Color;
import edu.princeton.cs.algs4.Picture;
public class SeamCarver {
private Picture picture; // current picture.
private double[][] energyTracker;
private int[][] positionTracker;
/*
* To implement my seam carver, I created three new helper methods
* that were not in the original file. I did this to create more
* compact and modular code. The three methods were all related
* to energy. I made yColor and xColor methods in order to modularize
* finding the delta x of color at a given x. I did the same with y
*
* The other method is relax edge. I made this because it would need
* to be called many times, and making it into a method seemed like the
* most efficient approach.
*/
// Create a seam carver object based on the given picture, making a
// defensive copy of picture.
public SeamCarver(Picture picture) {
this.picture = new Picture(picture);
}
// Current picture.
public Picture picture() {
return this.picture;
}
// Width of current picture.
public int width() {
return picture.width();
}
// Height of current picture.
public int height() {
return picture.height();
}
// Energy of pixel at column x and row y.
public double energy(int x, int y) {
//handle the obvious exception cases
if (x < 0 || x >= width()) {
throw new IndexOutOfBoundsException();
}
if (y < 0 || y >= height()) {
throw new IndexOutOfBoundsException();
}
//returns the sum of the delta y values and delta x values
//surrounding the given pixel
return xColor(x, y) + yColor(x, y);
}
private double xColor(int x, int y) {
//returns difference between adjancent x pixel color values squared
//helper values to allow for varibale x positions
int c1x = x-1;
int c2x = x+1;
//if x is first x, c1 uses last x for its adjacent x-1
if (x == 0) {
c1x = width() -1;
c2x = x+1;
}
//if x is last value, c2 uses first x for its adjacent x+1
else if (x == width()-1) {
c1x = x-1;
c2x = 0;
}
//get the color values of adjacent x pixels
Color c1 = picture.get(c1x, y);
Color c2 = picture.get(c2x, y);
//find the deltas in each color group
int deltaRed = Math.abs(c2.getRed() - c1.getRed());
int deltaBlue = Math.abs(c2.getBlue() - c1.getBlue());
int deltaGreen = Math.abs(c2.getGreen() - c1.getGreen());
//find the delta squared, done separately for speed
int redSquare = deltaRed * deltaRed;
int blueSquare = deltaBlue * deltaBlue;
int greenSquare = deltaGreen * deltaGreen;
//return the sum of the squares for energy
return redSquare + blueSquare + greenSquare;
}
private double yColor(int x, int y) {
//returns difference between adjancent y pixel color values squared
//helper values to allow for varibale y positions
int c1y = y-1;
int c2y = y+1;
//if y is first y, c1 uses last y for its adjacent y-1
if (y == 0) {
c1y = height()-1;
c2y = y+1;
}
//if y is last value, c2 uses first y for its adjacent y+1
else if (y == height()-1) {
c1y = y-1;
c2y = 0;
}
//else use normal y+1, y-1 for adjacents
Color c1 = picture.get(x, c1y);
Color c2 = picture.get(x, c2y);
//find the deltas in each color group
int deltaRed = Math.abs(c1.getRed() - c2.getRed());
int deltaBlue = Math.abs(c1.getBlue() - c2.getBlue());
int deltaGreen = Math.abs(c1.getGreen() - c2.getGreen());
//find the delta squared, done separately for speed
int redSquare = deltaRed * deltaRed;
int blueSquare = deltaBlue * deltaBlue;
int greenSquare = deltaGreen * deltaGreen;
//return the sum of the squares for energy
return redSquare + blueSquare + greenSquare;
}
// Sequence of indices for horizontal seam.
public int[] findHorizontalSeam() {
/*
*horizontal seam leans on the vertical seam method
*we simply transpose the image to reverse x and y, then
*remove the vertical seam, then transpose back.
*/
//create our picture objects for manipulation
Picture original = picture;
//tranpose the image
Picture transposed = transpose(original);
//set the object image as the transposed image
this.picture = transposed;
//identify the vertical seam in tranposed picture
int[] seam = findVerticalSeam();
//return to original orientation
this.picture = original;
//return the found seam
return seam;
}
// Sequence of indices for vertical seam.
public int[] findVerticalSeam() {
//init two 2D arrays
//energy tracker hold energy values at given pixels
energyTracker = new double[width()][height()];
//positionTracker used to ID seams
positionTracker = new int[width()][height()];
//init all energies to inifinity
for (int x = 0; x < width(); x++) {
for (int y = 0; y < height(); y++) {
energyTracker[x][y] = Double.POSITIVE_INFINITY;
}
}
//init top row to proper energy vlaues
for (int x = 0; x < width(); x++) {
energyTracker[x][0] = energy(x, 0);
}
//Call the relax mehtod on every pixel in the image
//making sure only to call on legal pixels
for (int y = 0; y < height() - 1; y++) {
for (int x = 0; x < width(); x++) {
if (x > 0) {
relaxEdge(x, y, x - 1, y + 1);
}
relaxEdge(x, y, x, y + 1);
if (x < width() - 1) {
relaxEdge(x, y, x + 1, y + 1);
}
}
}
// find minimum energy path
double minEnergy = Double.POSITIVE_INFINITY;
//lowest energy pixel tracks where the seam will be
int lowestEnergyPixel = 0;
//for every pixel across the last line of pixels
for (int w = 0; w < width(); w++) {
//find the lowest energy position and store that
if (energyTracker[w][height() - 1] < minEnergy) {
lowestEnergyPixel = w;
minEnergy = energyTracker[w][height() - 1];
}
}
//create the seam array
int[] seam = new int[height()];
//the last pixel is the lowest energy position in the last row
seam[height() - 1] = lowestEnergyPixel;
//next pixel beings at the lowest energy pixel
int nextPixel = positionTracker[lowestEnergyPixel][height() - 1];
//starting at second to last row, transfer values from positon
//tracker into the seam array, finding the lowest energy path
//REMEMBER ***positionTracker is updated in the relax method***
for (int h = height() - 2; h >= 0; h--) {
seam[h] = nextPixel;
nextPixel = positionTracker[nextPixel][h];
}
return seam;
}
/*
* Relax edge does the main work of finding the lowest energy seam by
* updating energy values based on the lowest energy path in the adjacent
* pixels. Once found, it updates the position tracker to reflect the lowest
* energy positon at that juncture
*/
private void relaxEdge(int x1, int y1, int x2, int y2) {
if (energyTracker[x2][y2] > energyTracker[x1][y1] + energy(x2, y2)) {
energyTracker[x2][y2] = energyTracker[x1][y1] + energy(x2, y2);
positionTracker[x2][y2] = x1;
}
}
// Remove horizontal seam from current picture.
public void removeHorizontalSeam(int[] seam) {
//leans on vertical seam removal and transposing
//Set picture objects for manipulation
Picture original = picture();
//change the orientation of the picture
Picture transposed = transpose(original);
//set the object picture as the newly tranposed image
this.picture = transposed;
//remove the vertical seam
removeVerticalSeam(seam);
//change original to the newly carved image
original = picture();
//tranpose original back to the original orientation
transposed = transpose(original);
//set the object image to the newly carved and tranposed image
this.picture = transposed;
}
// Remove vertical seam from current picture.
public void removeVerticalSeam(int[] seam) {
//Handle basic edge cases
if (seam == null) {
throw new NullPointerException();
}
if (seam.length != height()) {
throw new NullPointerException();
}
//create two picture objects, original and the new image
Picture original = picture();
Picture resized = new Picture(original.width() -1, original.height());
/*
iterate through every row. For each pixel(column) in the row
tranpose the pixel until you reach thr seam. At the seam, skip
the seam pixel and continue transposing
*/
//for every row...
for (int i = 0; i < resized.height(); i++) {
//for every column until the seam...
for (int j = 0; j < seam[i]; j++) {
//tanspose pixels
resized.set(j, i, original.get(j, i));
}
//for every column after the seam
for (int j = seam[i]; j < resized.width(); j++) {
//transpose pixels
resized.set(j, i, original.get(j+1, i));
}
}
this.picture = resized;
}
// Return y - 1 if x < 0; 0 if x >= y; and x otherwise.
private static int wrap(int x, int y) {
if (x < 0) {
return y - 1;
}
else if (x >= y) {
return 0;
}
return x;
}
/* TRANSPOSE METHOD WAS PROVIDED, I DID NOT WRITE IT! */
// Return a new picture that is a transpose of the given picture.
private static Picture transpose(Picture picture) {
Picture transpose = new Picture(picture.height(), picture.width());
for (int i = 0; i < transpose.width(); i++) {
for (int j = 0; j < transpose.height(); j++) {
transpose.set(i, j, picture.get(j, i));
}
}
return transpose;
}
}
</pre>
<pre class="prettyprint" id="binarySearchDeluxe">
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import java.util.Arrays;
import java.util.Comparator;
// Implements binary search for clients that may want to know the index of
// either the first or last key in a (sorted) collection of keys.
public class BinarySearchDeluxe {
// The index of the first key in a[] that equals the search key,
// or -1 if no such key.
public static <Key> int firstIndexOf(Key[] a, Key key,
Comparator<Key> comparator) {
//error handling per the PDF requirements
if (a == null || key == null || comparator == null) {
throw new java.lang.NullPointerException();
}
//set the low pointer to 0
int low = 0;
//set high pointer to the end
int high = a.length - 1;
//while low is less than high, Search!
while (low + 1 < high) {
//set mid equal to the difference of high and low
int mid = low + (high - low)/2;
//if key is less than or equal to mid indice
if (comparator.compare(key, a[mid]) <= 0) {
//set high to mid, its before mid
high = mid;
}
else {
//else set low to mid, its after mid
low = mid;
}
}
//if the key indice is the low indice, return it
if (comparator.compare(key, a[low]) == 0) {
return low;
}
//if the key indice is the high indice, return it
if (comparator.compare(key, a[high]) == 0) {
return high;
}
//if all else fails, return -1 because the key isnt
//present in the array
return -1;
}
// The index of the last key in a[] that equals the search key,
// or -1 if no such key.
public static <Key> int lastIndexOf(Key[] a, Key key,
Comparator<Key> comparator) {
//exception handling per the PDF
if (a == null || key == null || comparator == null) {
throw new java.lang.NullPointerException();
}
//set low indice to zero
int low = 0;
//set high indice to the end
int high = a.length - 1;
//while low is less than the end, Search!
while (low + 1 < high) {
//set mid equal to differnece between low and high
int mid = low + (high - low)/2;
//if the key is before mid...
if (comparator.compare(key, a[mid]) < 0) {
//set high to mid, its before it
high = mid;
}
else {
//set low to mid, its after it
low = mid;
}
}
//returns the high position first, which should return
//the last position found if more than one exists
if (comparator.compare(key, a[high]) == 0) {
return high;
}
//otherwise returns the low position because it is the
//only one that exists in the array
if (comparator.compare(key, a[low]) == 0) {
return low;
}
//if all else fails, return -1 because it doesnt exist
//in the array
return -1;
}
</pre>
<pre class="prettyprint" id="euclideanEdgeGraph">
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinkedBag;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.SeparateChainingHashST;
import edu.princeton.cs.algs4.StdOut;
public class EuclideanEdgeWeightedGraph {
private int V;
private int E;
private SeparateChainingHashST<Point2D, LinkedBag<EuclideanEdge>> adj;
// Initialize an empty Euclidean edge-weighted graph from an input stream.
public EuclideanEdgeWeightedGraph(In in) {
this.V = in.readInt();
this.E = in.readInt();
this.adj = new SeparateChainingHashST
<Point2D, LinkedBag<EuclideanEdge>>();
if (E < 0) {
throw new IllegalArgumentException(
"Number of edges must be nonnegative");
}
for (int i = 0; i < E; i++) {
Point2D p1 = new Point2D(in.readDouble(), in.readDouble());
Point2D p2 = new Point2D(in.readDouble(), in.readDouble());
EuclideanEdge e = new EuclideanEdge(p1, p2);
addEdge(e);
}
}
// Number of vertices in this Euclidean edge-weighted graph.
public int V() {
return V;
}
// Number of edges in this Euclidean edge-weighted graph.
public int E() {
return E;
}
// Add an undirected edge to this Euclidean edge-weighted graph.
public void addEdge(EuclideanEdge e) {
Point2D v = e.either();
Point2D w = e.other(v);
if (!adj.contains(v)) {
LinkedBag<EuclideanEdge> bag = new LinkedBag<EuclideanEdge>();
bag.add(e);
adj.put(v, bag);
}
else if (adj.contains(v)) {
LinkedBag bag = adj.get(v);
bag.add(e);
}
if (!adj.contains(w)) {
LinkedBag<EuclideanEdge> bag = new LinkedBag<EuclideanEdge>();
bag.add(e);
adj.put(w, bag);
}
else if (adj.contains(w)) {
LinkedBag bag = adj.get(w);
bag.add(e);
}
}
// Edges incident on vertex v.
public Iterable<EuclideanEdge> adj(Point2D v) {
return adj.get(v);
}
// All the edges in this Euclidean edge-weighted graph.
public Iterable<EuclideanEdge> edges() {
LinkedBag<EuclideanEdge> bag = new LinkedBag<EuclideanEdge>();
for (Point2D v : adj.keys()) {
int selfLoops = 0;
for (EuclideanEdge e : adj(v)) {
if (e.other(v).hashCode() > v.hashCode()) {
bag.add(e);
}
else if (e.other(v).equals(v)) {
if (selfLoops % 2 == 0) bag.add(e);
selfLoops++;
}
}
}
return bag;
}
// A string representation of this Euclidean edge-weighted graph.
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + "\n");
for (Point2D v : adj.keys()) {
s.append(v + ": ");
for (EuclideanEdge e : adj(v)) {
s.append(e + " ");
}
s.append("\n");
}
return s.toString();
}
</pre>
<pre class="prettyprint" id="euclideanEdgeGraphMST">
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinkedQueue;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.SeparateChainingHashST;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.UF;
public class EuclideanKruskalMST {
private double weight;
private LinkedQueue<EuclideanEdge> mst;
// Compute a minimum spanning tree (or forest) of an Euclidean
// edge-weighted graph.
public EuclideanKruskalMST(EuclideanEdgeWeightedGraph G) {
//init the pq for smallest edges first
MinPQ<EuclideanEdge> pq = new MinPQ<EuclideanEdge>();
//init the mst
this.mst = new LinkedQueue<EuclideanEdge>();
//create hast table to assign points integers
SeparateChainingHashST<Point2D, Integer> hasher =
new SeparateChainingHashST<Point2D, Integer>();
//insert all edges into both pq and hash table
for (EuclideanEdge e : G.edges()) {
pq.insert(e);
Point2D v = e.either();
Point2D w = e.other(v);
hasher.put(v, 1);
hasher.put(w, 1);
}
//assign all points integer keys
int i = 0;
for (Point2D v : hasher.keys()) {
hasher.put(v, i);
i++;
}
// run greedy algorithm
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V()-1) {
EuclideanEdge e = pq.delMin();
Point2D v = e.either();
Point2D w = e.other(v);
int vInt = hasher.get(v);
int wInt = hasher.get(w);
if (!uf.connected(vInt, wInt)) { // v-w does not create a cycle
uf.union(vInt, wInt); // merge v and w components
mst.enqueue(e); // add edge e to mst
weight += e.weight();
}
}
StdOut.println();
}
// Edges in a minimum spanning tree (or forest).
public Iterable<EuclideanEdge> edges() {
return mst;
}
// Sum of the edge weights in a minimum spanning tree (or forest).
public double weight() {
return weight;
}
</pre>
<!-- This ends the pre block madness. -->
</div><!-- end code block div -->
</div><!--end hero left-->
</div><!-- end left side -->
</div><!--end container -->
<div id="dialog" title="Overflow!">
<p id="dialog-html"></p>
</div>
</body>
<!-- All my scripts yo -->
<script src="js/jquery.min.js"></script>
<script src="js/jquery-ui.min.js"></script>
<script src="js/app.js"></script>
</html>