Project

General

Profile

Codemonkeys Solutions » codemonkeys_v07.txt

Codemonkeys Solutions - Version 7 (Text only) - Fabian Damken, 2017-06-29 09:40

 
1

    
2

    
3

    
4

    
5
# Array List
6

    
7

    
8

    
9
## Contains
10

    
11
{
12
    for (ArrayListElement<T> el = getFirst(); el != null; el = el.getNext()) {
13
        for (Listobject<T> obj : el.getData()) {
14
            if (obj != null && data.equals(obj.getData())) {
15
                return true;
16
            }
17
        }
18
    }
19
    return false;
20
}
21

    
22

    
23

    
24
## Remove
25

    
26
{
27
    if (i < 0 || getFirst() == null) {
28
        return false;
29
    }
30

    
31
    int index = 0;
32
    for (ArrayListElement<T> el = getFirst();
33
            el != null; el = el.getNext()) {
34
        final Listobject<T>[] data = el.getData();
35
        boolean found = false;
36
        for (int j = 0; j < el.getN(); j++) {
37
            if (index > i) {
38
                data[j - 1] = data[j];
39
            } else if (index == i) {
40
                found = true;
41
            }
42

    
43
            index++;
44
        }
45
        if (found) {
46
            el.decN();
47
            return true;
48
        }
49
    }
50
    return false;
51
}
52

    
53

    
54

    
55

    
56
# Priority Queue
57

    
58

    
59

    
60
## Peek
61

    
62
{
63
    return getHead() == null ? null : getHead().getKey();
64
}
65

    
66

    
67

    
68
## Push
69

    
70
{
71
    if (key == null) {
72
        return false;
73
    }
74

    
75
    final MListElement<T> elem = new MListElement<T>(key);
76
    final MListElement<T> head = getHead();
77
    if (head == null) {
78
        setHead(elem);
79

    
80
        return true;
81
    }
82
    if (getComp().compare(key, head.getKey()) <= 0) {
83
        elem.setNext(head);
84
        setHead(elem);
85

    
86
        return true;
87
    }
88

    
89
    for (MListElement<T> el = getHead(); el != null; el = el.getNext()) {
90
        if (getComp().compare(key, el.getKey()) > 0
91
                && (el.getNext() == null
92
                    || getComp().compare(key, el.getNext().getKey()) <= 0)) {
93
            elem.setNext(el.getNext());
94
            el.setNext(elem);
95

    
96
            return true;
97
        }
98
    }
99
    return false;
100
}
101

    
102

    
103

    
104
## Pop
105

    
106
{
107
    final MListElement<T> head = getHead();
108
    if (head == null) {
109
        return null;
110
    }
111
    setHead(head.getNext());
112
    return head.getKey();
113
}
114

    
115

    
116

    
117

    
118
# Array
119

    
120

    
121

    
122
## Array is Sorted
123

    
124
{
125
    if (a == null) {
126
        return false;
127
    }
128

    
129
    for (int i = 0; i < a.length - 1; i++) {
130
        Integer x = a[i];
131
        Integer y = a[i + 1];
132
        if (x == null || y == null || comp.compare(x, y) > 0) {
133
            return false;
134
        }
135
    }
136
    return true;
137
}
138

    
139

    
140

    
141
## Insert
142

    
143
{
144
    final Listobject<T>[] oldArray = getArray();
145
    final Listobject<T>[] newArray = new Listobject[oldArray.length + 1];
146
    boolean inserted = false;
147
    for (int i = 0; i < newArray.length; i++) {
148
        if (inserted) {
149
            newArray[i] = oldArray[i - 1];
150
        } else if (i == oldArray.length) {
151
            newArray[i] = element;
152
        } else {
153
            final Listobject<T> el = oldArray[i];
154
            if (el.compareTo(element) < 0) {
155
                newArray[i] = el;
156
            } else if (el.compareTo(element) > 0) {
157
                newArray[i] = element;
158
                inserted = true;
159
            } else {
160
                newArray[i] = element;
161
                inserted = true;
162
            }
163
        }
164
    }
165
    setArray(newArray);
166
    return newArray;
167
}
168

    
169

    
170

    
171
## Insert at Index
172

    
173
{
174
    final Listobject<T>[] oldArray = this.getArray();
175
    final Listobject<T>[] newArray;
176
    if (pos < oldArray.length && oldArray[pos] == null) {
177
        newArray = new Listobject[oldArray.length];
178
        for (int i = 0; i < oldArray.length; i++) {
179
            newArray[i] = oldArray[i];
180
        }
181
        newArray[pos] = element;
182
    } else {
183
        newArray = new Listobject[pos < oldArray.length
184
                ? oldArray.length + 1
185
                : pos + 1];
186
        for (int i = 0; i < newArray.length; i++) {
187
            if (i < pos && i < oldArray.length) {
188
                newArray[i] = oldArray[i];
189
            } else if (i > pos && i <= oldArray.length) {
190
                newArray[i] = oldArray[i - 1];
191
            } else if (i == pos) {
192
                newArray[i] = element;
193
            }
194
        }
195
    }
196
    setArray(newArray);
197
    return newArray;
198
}
199

    
200

    
201

    
202
## Remove
203

    
204
{
205
    final Listobject<T>[] newArray = new Listobject[array.length - 1];
206
    for (int i = 0; i < array.length; i++) {
207
        if (i < index) {
208
            newArray[i] = array[i];
209
        } else if (i > index) {
210
            newArray[i - 1] = array[i];
211
        }
212
    }
213
    return newArray;
214
}
215

    
216

    
217

    
218
## Search second largest Element
219

    
220
{
221
    for (int i = 0; i < getLength(); i++) {
222
        if (getElem(i) == null) {
223
            continue;
224
        }
225

    
226
        if (getLargest() == -1) {
227
            setLargest(i);
228
        } else if (getComp().compare(getElem(i), getElem(getLargest())) >= 0) {
229
            if (getComp().compare(getElem(i), getElem(getLargest())) != 0) {
230
                setSecLargest(getLargest());
231
            }
232
            setLargest(i);
233
        } else if (getSecLargest() == -1
234
                || getComp().compare(getElem(i),
235
                        getElem(getSecLargest())) >= 0) {
236
            setSecLargest(i);
237
        }
238
    }
239
}
240

    
241

    
242

    
243
## Sort $O(n^2)$ Iterative
244

    
245
{
246
    for (int i = 0; i < inputdata.length; i++) {
247
        for (int j = 1; j < inputdata.length - i; j++) {
248
            if (comp.compare(inputdata[j - 1], inputdata[j]) > 0) {
249
                final Listobject<T> tmp = inputdata[j - 1];
250
                inputdata[j - 1] = inputdata[j];
251
                inputdata[j] = tmp;
252
            }
253
        }
254
    }
255

    
256
    return inputdata;
257
}
258

    
259

    
260

    
261
## Duplicate every second Element
262

    
263
{
264
    final Listobject<T>[] result =
265
            new Listobject[array.length + array.length / 2];
266
    for (int i = 0, j = 0; i < array.length; i++) {
267
        result[j++] = array[i];
268
        if (i % 2 != 0) {
269
            result[j++] = array[i];
270
        }
271
    }
272
    return result;
273
}
274

    
275

    
276

    
277
## Linear Search
278

    
279
{
280
    if (getElem() == null) {
281
        return -1;
282
    }
283

    
284
    for (int i = 0; i < getArrayLength(); i++) {
285
        if (getArrayElem(i) == null) {
286
            continue;
287
        }
288

    
289
        if (getComp().compare(getElem(), getArrayElem(i)) == 0) {
290
            return i;
291
        }
292
    }
293
    return -1;
294
}
295

    
296

    
297

    
298
## Merge
299

    
300
{
301
    final Listobject<T>[] result = new Listobject[left.length + right.length];
302
    int i = 0;
303
    int a = 0;
304
    int b = 0;
305
    for (; a < left.length && b < right.length; i++) {
306
        final Listobject<T> aElem = left[a];
307
        final Listobject<T> bElem = right[b];
308
        if (aElem.compareTo(bElem) < 0) {
309
            result[i] = aElem;
310
            a++;
311
        } else {
312
            result[i] = bElem;
313
            b++;
314
        }
315
    }
316
    for (; a < left.length; i++, a++) {
317
        result[i] = left[a];
318
    }
319
    for (; b < right.length; i++, b++) {
320
        result[i] = right[b];
321
    }
322
    return result;
323
}
324

    
325

    
326

    
327
## Rotate Pairs
328

    
329
{
330
    if (list == null) {
331
        throw new NullPointerException();
332
    }
333

    
334
    for (int i = 1; i < list.length; i += 2) {
335
        final Listobject<T> tmp = list[i - 1];
336
        list[i - 1] = list[i];
337
        list[i] = tmp;
338
    }
339

    
340
    return list;
341
}
342

    
343

    
344

    
345
## Rotate successive Triples
346

    
347
{
348
    if (list == null) {
349
        throw new IllegalArgumentException();
350
    }
351

    
352
    for (int i = 2; i < list.length; i += 3) {
353
        final Listobject<T> a = list[i - 2];
354
        final Listobject<T> b = list[i - 1];
355
        final Listobject<T> c = list[i];
356

    
357
        list[i - 2] = b;
358
        list[i - 1] = c;
359
        list[i] = a;
360
    }
361
    return list;
362
}
363

    
364

    
365

    
366
## Rotate Tripels
367

    
368
{
369
    if (a < 0 || b < 0 || c < 0) {
370
        throw new IndexOutOfBoundsException();
371
    }
372
    if (a >= array.length || b >= array.length || c >= array.length) {
373
        return false;
374
    }
375

    
376
    final Listobject<T> aElem = array[a];
377
    final Listobject<T> bElem = array[b];
378
    final Listobject<T> cElem = array[c];
379
    array[a] = cElem;
380
    array[b] = aElem;
381
    array[c] = bElem;
382

    
383
    return true;
384
}
385

    
386

    
387

    
388
## Selection-Sort Iterative
389

    
390
{
391
    for (int i = array.length; i > 0; i--) {
392
        final Listobject<T> max = array[0];
393

    
394
        int idx = 0;
395
        for (int j = 1; j < i; j++) {
396
            if (array[j].compareTo(max) > 0) {
397
                max = array[j];
398
                idx = j;
399
            }
400
        }
401

    
402
        int top = i - 1;
403
        if (idx != top) {
404
            Listobject<T> temp = array[idx];
405
            array[idx] = array[top];
406
            array[top] = temp;
407
        }
408
    }
409

    
410
    return array;
411
}
412

    
413

    
414

    
415
## Ehift elements left
416

    
417
{
418
    if (list == null || list.length == 0) {
419
        throw new IllegalArgumentException();
420
    }
421

    
422
    Listobject<T> first = list[0];
423
    for (int i = 0; i < list.length - 1; i++) {
424
        list[i] = list[i + 1];
425
    }
426
    list[list.length - 1] = first;
427

    
428
    return list;
429
}
430

    
431

    
432

    
433
## Shift elements right
434

    
435
{
436
    if (list == null) {
437
        return null;
438
    }
439

    
440
    Listobject<T>[] result = Listobject
441
            .factoryMethodListobjectTArray(list.length);
442
    result[0] = list[list.length - 1];
443
    for (int i = 0; i < list.length - 1; i++) {
444
        result[i + 1] = list[i];
445
    }
446
    return result;
447
}
448

    
449

    
450

    
451

    
452
# Baum
453

    
454

    
455

    
456
## Binary Search Tree: Traverse
457

    
458

    
459
### getElements
460

    
461
{
462
    final ArrayList<N> data = new ArrayList<>();
463
    if (getRoot() != null) {
464
        getElementsRec(getRoot(), data);
465
    }
466
    return data;
467
}
468

    
469

    
470
### getElementsRec
471

    
472
{
473
    final Node<N, Integer> left = getLeft(node);
474
    final Node<N, Integer> right = getRight(node);
475
    if (left != null) {
476
        getElementsRec(left, visited);
477
    }
478
    visited.add(node.getData());
479
    if (right != null) {
480
        getElementsRec(right, visited);
481
    }
482
}
483

    
484

    
485

    
486

    
487
# Graph
488

    
489

    
490

    
491
## AStern: Break Condition/Variant
492

    
493

    
494
### checkBreakCondition
495

    
496
{
497
    return !isPathFound();
498
}
499

    
500

    
501
### executeVariant
502

    
503
{
504
    setCurrentNode(getOpenList().poll());
505
}
506

    
507

    
508

    
509
## AStern: Functionality
510

    
511

    
512
### expandNode
513

    
514
{
515
    for (final Edge<N, E> edge : node.getFanOut()) {
516
        final Node<N, E> successor = edge.getTargetNode();
517
        if (getClosedList().contains(successor)) {
518
            continue;
519
        }
520

    
521
        final E g = getComparator().sum(getSourceDistanceMap().get(node), edge.getData());
522
        if (getOpenList().contains(successor) && getComparator().greaterEqual(g, getSourceDistanceMap().get(successor))) {
523
            continue;
524
        }
525

    
526
        getPredecessorMap().put(successor, node);
527
        getSourceDistanceMap().put(successor, g);
528
        getOpenList().offer(successor);
529
    }
530
}
531

    
532

    
533
### doFunctionality
534

    
535
{
536
    if (getCurrentNode() == getTargetNode() || getCurrentNode() == null) {
537
        setPathFound(true);
538
        return;
539
    }
540

    
541
    getClosedList().add(getCurrentNode());
542
    expandNode(getCurrentNode());
543
}
544

    
545

    
546

    
547
## Bellman-Ford: Functionality
548

    
549
{
550
    final AbstractEdgeComparator<E> comp = getGraph().getComparator();
551
    final int c = getKard_V();
552
    final Matrix<E> newMatrix = new MatrixFactory<E>().newInstance(c, c, comp.getMax());
553
    for (int x = 1; x <= c; x++) {
554
        for (int y = 1; y <= c; y++) {
555
            E min = newMatrix.get(x,y);
556
            for (int i = 1; i <= c; i++) {
557
                min = comp.min(min, comp.sum(getM(getI()).get(x,i), getL().get(i,y)));
558
                newMatrix.set(x,y,min);
559
            }
560
        }
561
    }
562
    appendToM(newMatrix);
563
}
564

    
565

    
566

    
567
## Dijkstra: Break Condition/Variant
568

    
569

    
570
### checkBreakCondition
571

    
572
{
573
    return !getPriorityQueue().isEmpty();
574
}
575

    
576

    
577
### executeVariant
578

    
579
{
580
    setSmallestNode(getPriorityQueue().poll());
581
    getSettled().add(getSmallestNode());
582
    setIterations(getIterations() + 1);
583
}
584

    
585

    
586

    
587
## Floyd-Warshall: Break Condition/Variant
588

    
589

    
590
### checkBreakCondition
591

    
592
{
593
    return getIteration() < getGraph().getNodeList().size();
594
}
595

    
596

    
597
### executeVariant
598

    
599
{
600
    final int iteration = getIteration();
601
    setIteration(iteration + 1);
602
    if (checkBreakCondition()){
603
        setCurrentNode(getGraph().getNodeList().get(iteration));
604
    }
605
}
606

    
607

    
608

    
609
## Floyd-Warshall: Functionality
610

    
611
{
612
    final G graph = getGraph();
613
    final AbstractEdgeComparator<E> comp = graph.getComparator();
614
    final ArrayList<Node<N,E>> nodes = graph.getNodeList();
615
    final Node<N,E> current = getCurrentNode();
616
    final int matrixIndex = getMatrixIndex(current);
617

    
618
    for (final Node<N,E> currentNode : nodes) {
619
        final int currentMatrixIndex = getMatrixIndex(currentNode);
620
        for (final Node<N,E> subNode : nodes) {
621
            final int subMatrixIndex = getMatrixIndex(subNode);
622
            final E min = comp.min(getM(currentMatrixIndex, subMatrixIndex),
623
                    comp.sum(getM(currentMatrixIndex, matrixIndex),
624
                    getM(matrixIndex, subMatrixIndex)));
625
            setM(currentMatrixIndex, subMatrixIndex, min);
626
        }
627
    }
628
}
629

    
630

    
631

    
632
## Add Edge
633

    
634

    
635
### Methode 1
636

    
637
{
638
    if (from == null || to == null || data == null) {
639
        throw new IllegalArgumentException();
640
    }
641
    if (getFanOutMax() < from.getFanOut().size() + 1 || getFanInMax() < to.getFanIn().size() + 1) {
642
        throw new FanOverflowException("");
643
    }
644

    
645
    final Edge<N, E> edge = new Edge(from, to, data);
646
    from.getFanOut().add(edge);
647
    to.getFanIn().add(edge);
648
    final ArrayList<Edge<N, E>> edges = getEdgeList();
649
    edges.add(edge);
650
    setEdgeList(edges);
651
}
652

    
653

    
654
### Methode 2
655

    
656
{
657
    if (from == null || to == null || data == null) {
658
        throw new IllegalArgumentException();
659
    }
660
    if (getFanOutMax() <= from.getFanOut().size() + 1 || getFanInMax() <= to.getFanIn().size() + 1) {
661
        throw new FanOverflowException("");
662
    }
663

    
664
    final Edge<N, E> edge = new Edge(from, to, data);
665
    from.getFanOut().add(edge);
666
    to.getFanIn().add(edge);
667
    final ArrayList<Edge<N, E>> edges = getEdgeList();
668
    edges.add(edge);
669
    setEdgeList(edges);
670
}
671

    
672

    
673

    
674
## Add Node
675

    
676
{
677
    if (data == null) {
678
        return null;
679
    }
680

    
681
    final Node<N, E> node = new Node(getIdGen(), data);
682
    final ArrayList<Node<N, E>> nodes = getNodeList();
683
    nodes.add(node);
684
    setNodeList(nodes);
685
    return node;
686
}
687

    
688

    
689

    
690
## Add Subgraph
691

    
692
{
693
    if (graph == null) {
694
        throw new InvalidInputException("");
695
    }
696

    
697
    for (Node<N, E> node : graph.getNodeList()) {
698
        final N data = node.getData();
699
        Node<N, E> thisNode = this.findNode(data);
700

    
701
        if (thisNode == null) {
702
            thisNode = this.addNode(data);
703
        }
704

    
705
        for (Edge<N, E> edge : node.getFanOut()) {
706
            final N targetData = edge.getTargetNode().getData();
707

    
708
            Node<N, E> thisTarget = this.findNode(targetData);
709
            if (thisTarget == null) {
710
                thisTarget = this.addNode(targetData);
711
            }
712

    
713
            boolean found = false;
714
            for (final Edge<N, E> oldEdge : thisNode.getFanOut()) {
715
                if (this.objectEquals(targetData, oldEdge.getTargetNode().getData())) {
716
                    found = true;
717
                }
718
            }
719
            if (!found) {
720
                this.addEdge(thisNode.getId(), thisTarget.getId(), edge.getData());
721
            }
722
        }
723
    }
724
}
725

    
726

    
727

    
728
## Count Edges
729

    
730

    
731
### countEdgesRec
732

    
733
{
734
    if (!nodeSet.add(node)) {
735
        return;
736
    }
737

    
738
    for (final Edge<N, E> edge : node.getFanOut()) {
739
        edgeSet.add(edge);
740

    
741
        countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
742
    }
743
    for (final Edge<N, E> edge : node.getFanIn()) {
744
        edgeSet.add(edge);
745

    
746
        countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
747
    }
748
}
749

    
750

    
751
### countEdgesInConnectedGraph
752

    
753
{
754
    if (node == null || !contains(node)) {
755
        return -1;
756
    }
757

    
758
    final HashSet<Edge<N, E>> edges = new HashSet<>();
759
    final HashSet<Node<N, E>> nodes = new HashSet<>();
760
    countEdgesRec(node, edges, nodes);
761
    return edges.size();
762
}
763

    
764

    
765

    
766
## Count Nodes
767

    
768

    
769
### countNodesRec
770

    
771
{
772
    if (set.contains(node)) {
773
        return;
774
    }
775

    
776
    set.add(node);
777
    for (Edge<N,E> edge : node.getFanOut()) {
778
        countNodesRec(edge.getTargetNode(), set);
779
    }
780
    for (Edge<N,E> edge : node.getFanIn()) {
781
        countNodesRec(edge.getSourceNode(), set);
782
    }
783
}
784

    
785

    
786
### countNodesInConnectedGraph
787

    
788
{
789
    if (node == null || !this.contains(node)) {
790
        return -1;
791
    }
792

    
793
    final HashSet<Node<N,E>> nodes = new HashSet<>();
794
    countNodesRec(node, nodes);
795
    return nodes.size();
796
}
797

    
798

    
799

    
800
## Find Node
801

    
802
{
803
    if (startNode == null || data == null || !contains(startNode)) {
804
        return null;
805
    }
806

    
807
    final HashSet<Node<N, E>> processed = new HashSet<>();
808
    final ArrayDeque<Node<N, E>> stack = new ArrayDeque<>();
809
    stack.push(startNode);
810
    while (!stack.isEmpty()) {
811
        final Node<N, E> node = stack.pop();
812

    
813
        if (processed.contains(node)) {
814
            continue;
815
        }
816

    
817
        processed.add(node);
818
        for (final Edge<N, E> edge : node.getFanOut()) {
819
            stack.push(edge.getTargetNode());
820
        }
821

    
822
        if (objectEquals(node.getData(), data)) {
823
            return node;
824
        }
825
    }
826
    return null;
827
}
828

    
829

    
830

    
831
## Remove Edge
832

    
833
{
834
    if (edge == null || !getEdgeList().contains(edge)) {
835
        return false;
836
    }
837

    
838
    final ArrayList<Edge<N, E>> edges = getEdgeList();
839
    edges.remove(edge);
840
    setEdgeList(edges);
841

    
842
    edge.removeFromNodes();
843

    
844
    return true;
845
}
846

    
847

    
848

    
849
## Remove Node
850

    
851
{
852
    if (node == null || !contains(node)) {
853
        return false;
854
    }
855

    
856
    final ArrayList<Node<N, E>> nodes = getNodeList();
857
    nodes.remove(node);
858
    setNodeList(nodes);
859

    
860
    final ArrayList<Edge<N, E>> edges = getEdgeList();
861
    edges.removeAll(node.getFanOut());
862
    edges.removeAll(node.getFanIn());
863
    setEdgeList(edges);
864

    
865
    for (final Edge<N, E> edge : node.getFanOut()) {
866
        edge.removeFromNodes();
867
    }
868
    for (final Edge<N, E> edge : node.getFanIn()) {
869
        edge.removeFromNodes();
870
    }
871

    
872
    return true;
873
}
874

    
875

    
876

    
877
## Kuskal: Union Find
878

    
879

    
880
### connected
881

    
882
{
883
    return find(p) == find(q);
884
}
885

    
886

    
887
### union
888

    
889
{
890
    Node<N,E> root_p = null;
891
    Node<N,E> test_p = p;
892

    
893
    while (test_p != root_p) {
894
        root_p = test_p;
895
        test_p = getParents().get(root_p);
896
    }
897

    
898
    Node<N,E> root_q = null;
899
    Node<N,E> test_q = q;
900
    while (test_q != root_q) {
901
        root_q = test_q;
902
        test_q = getParents().get(root_q);
903
    }
904

    
905
    if (test_p.equals(test_q)) {
906
        // Do nothing, already connected
907
        return;
908
    }
909

    
910
    int rank_p = getRanks().get(root_p);
911
    int rank_q = getRanks().get(root_q);
912

    
913
    if (rank_p < rank_q) {
914
        getParents().put(root_p, root_q);
915
    } else if (rank_q < rank_p) {
916
        getParents().put(root_q, root_p);
917
    } else {
918
        getParents().put(root_q, root_p);
919
        getRanks().put(root_p, getRanks().get(root_p) + 1);
920
    }
921
}
922

    
923

    
924

    
925
## Kuskal: Invariant
926

    
927
{
928
    int queueSize = getPriorityQueue().size();
929
    int edgeCount = getGraph().getEdgeList().size();
930
    int iteration = getIterations();
931

    
932
    if (queueSize + iteration != edgeCount) {
933
        throw new InvalidInvariantException("Sizes");
934
    }
935
    if (UndirectedGraphCycleChecker.hasCycle(getGraph())) {
936
        throw new InvalidInvariantException("Cycle");
937
    }
938
}
939

    
940

    
941

    
942
## Prim: Functionality
943

    
944
{
945
    Edge<N,E> edge = getSmallestEdge();
946
    Node<N,E> target = edge.getTargetNode();
947

    
948
    getVisited().add(target);
949
    getMst().add(edge);
950
    for (final Edge<N,E> e : target.getFanOut()) {
951
        this.priorityQueue.add(e);
952
    }
953
    this.removeUnnecessaryEdgesOutOfPriorityQueue();
954
}
955

    
956

    
957

    
958
## Prim: Invariante
959

    
960
{
961
    int visitedCount = getVisited().size();
962
    int spanCount = getMst().size();
963
    int nodeCount = getGraph().getNodeList().size();
964
    int iterationCount = getIterations();
965

    
966
    if (visitedCount != spanCount + 1 || (nodeCount != visitedCount && visitedCount != iterationCount)) {
967
        throw new InvalidInvariantException("");
968
    }
969
}
970

    
971

    
972

    
973

    
974
# Iterativ
975

    
976

    
977

    
978
## Palindrome Check
979

    
980
{
981
    if (s == null) {
982
        throw new NullPointerException();
983
    }
984
    if (StringHelper.isEmpty(s)) {
985
        return false;
986
    }
987

    
988
    final String lower = s.toLowerCase();
989
    for (int i = 0; i < StringHelper.length(lower) / 2; i++) {
990
        if (lower.charAt(i) != lower.charAt(s.length() - i - 1)) {
991
            return false;
992
        }
993
    }
994
    return true;
995
}
996

    
997

    
998

    
999
## Fibonacci
1000

    
1001
{
1002
    if (n < 0) {
1003
        throw new IllegalArgumentException();
1004
    }
1005
    if (n == 0) {
1006
        return 0;
1007
    }
1008

    
1009
    int prev = 0;
1010
    int result = 1;
1011
    for (int i = 1; i < n; i++) {
1012
        result = prev + (prev = result);
1013
    }
1014
    return result;
1015
}
1016

    
1017

    
1018

    
1019
## Multiple Palindrome Check
1020

    
1021
{
1022
    if (a == null) {
1023
        throw new NullPointerException();
1024
    }
1025
    if (a.length <= 0) {
1026
        return null;
1027
    }
1028

    
1029
    final boolean[] result = new boolean[a.length];
1030
    for (int i = 0; i < a.length; i++) {
1031
        final String s = a[i].toLowerCase();
1032
        boolean palindrome = true;
1033
        for (int j = 0; j < StringHelper.length(s) / 2; j++) {
1034
            if (s.charAt(j) != s.charAt(s.length() - j - 1)) {
1035
                palindrome = false;
1036
                break;
1037
            }
1038
        }
1039
        result[i] = palindrome;
1040
    }
1041
    return result;
1042
}
1043

    
1044

    
1045

    
1046

    
1047
# MIPS
1048

    
1049

    
1050

    
1051

    
1052
# Rekursiv
1053

    
1054

    
1055

    
1056
## Approximate Square Root
1057

    
1058
{
1059
    if (x < 0 || g < 0 || tolerance < 0) {
1060
        throw new IllegalArgumentException();
1061
    }
1062

    
1063
    if (Math.abs((x / g) - g) < tolerance) {
1064
        return g;
1065
    }
1066

    
1067
    return proxRootRec(x, ((x / g) + g) / 2, tolerance);
1068
}
1069

    
1070

    
1071

    
1072
## Fibonacci
1073

    
1074
{
1075
    if (i <= 0) {
1076
        return 0;
1077
    }
1078
    if (i == 1) {
1079
        return 1;
1080
    }
1081
    return fibRec(i - 1) + fibRec(i - 2);
1082
}
1083

    
1084

    
1085

    
1086

    
1087
# Single Linked List
1088

    
1089

    
1090

    
1091
## Insert First (single)
1092

    
1093
{
1094
    if (el == null || getFirst() == el) {
1095
        return false;
1096
    }
1097

    
1098
    if (getFirst() == null) {
1099
        setLast(el);
1100
    }
1101
    el.setNext(getFirst());
1102
    setFirst(el);
1103
    setSize(size() + 1);
1104

    
1105
    return true;
1106
}
1107

    
1108

    
1109

    
1110
## Insert Last (single)
1111

    
1112
{
1113
    if (el == null || getLast() == el) {
1114
        return false;
1115
    }
1116

    
1117
    if (getFirst() == null) {
1118
        setFirst(el);
1119
    } else {
1120
        getLast().setNext(el);
1121
    }
1122
    setLast(el);
1123
    el.setNext(null);
1124

    
1125
    setSize(size() + 1);
1126

    
1127
    return true;
1128
}
1129

    
1130

    
1131

    
1132
## Clone Elements
1133

    
1134
{
1135
    if (el == null) {
1136
        throw new NullPointerException();
1137
    }
1138

    
1139
    final ListElement<T> head = new ListElement<T>(el.getData());
1140
    ListElement<T> clone = head;
1141
    for (ListElement<T> orig = el.next();
1142
            orig != null; orig = orig.next()) {
1143
        final ListElement<T> elem = new ListElement<T>(orig.getData());
1144
        clone.setNext(elem);
1145
        clone = elem;
1146
    }
1147
    return head;
1148
}
1149

    
1150

    
1151

    
1152
## Clone List
1153

    
1154
{
1155
    if (list == null) {
1156
        throw new NullPointerException();
1157
    }
1158
    if (list.isEmpty()) {
1159
        return new LinkedList<T>();
1160
    }
1161

    
1162
    final ListElement<T> head = list.getFirst();
1163
    final LinkedList<T> result = new LinkedList<T>();
1164
    ListElement<T> clone = new ListElement<T>(head.getData());
1165
    result.setFirst(clone);
1166
    int count = 1;
1167
    for (ListElement<T> el = head.next(); el != null; el = el.next()) {
1168
        final ListElement<T> elem = new ListElement<T>(el.getData());
1169
        clone.setNext(elem);
1170
        clone = elem;
1171
        count++;
1172
    }
1173
    result.setSize(count);
1174
    result.setLast(clone);
1175
    return result;
1176
}
1177

    
1178

    
1179

    
1180
## Duplicate every second Element
1181

    
1182
{
1183
    boolean duplicate = true;
1184
    for (MListElement<T> el = head; el != null; el = el.getNext()) {
1185
        if (duplicate) {
1186
            final MListElement<T> dupl = new MListElement<T>(el.getKey());
1187
            dupl.setNext(el.getNext());
1188
            el.setNext(dupl);
1189
            el = dupl;
1190
        }
1191

    
1192
        duplicate = !duplicate;
1193
    }
1194

    
1195
    return head;
1196
}
1197

    
1198

    
1199

    
1200
## Get at Index
1201

    
1202
{
1203
    // Dummy call to make Codemonkeys happy.
1204
    isEmpty();
1205

    
1206
    int i = 0;
1207
    for (ListElement<T> el = getFirst(); el != null; el = el.next(), i++) {
1208
        if (i == idx) {
1209
            return el;
1210
        }
1211
    }
1212
    return null;
1213
}
1214

    
1215

    
1216

    
1217
## Insert First
1218

    
1219
{
1220
    if (el == null) {
1221
        return false;
1222
    }
1223
    // Loop detection using Floyd's circle-finding algorithm.
1224
    boolean run = true;
1225
    for (ListElement<T> i = el, j = el; run;) {
1226
        if (i.hasNext()) {
1227
            i = i.next();
1228
        } else {
1229
            run = false;
1230
            break;
1231
        }
1232
        if (j.hasNext() && j.next().hasNext()) {
1233
            j = j.next().next();
1234
        } else {
1235
            run = false;
1236
            break;
1237
        }
1238

    
1239
        if (i == j) {
1240
            return false;
1241
        }
1242
    }
1243

    
1244
    ListElement<T> last = null;
1245
    int count = 0;
1246
    for (ListElement<T> elem = el; elem != null;
1247
            elem = elem.next(), count++) {
1248
        if (contains(elem)) {
1249
            return false;
1250
        }
1251
        if (!elem.hasNext()) {
1252
            last = elem;
1253
        }
1254
    }
1255
    setSize(size() + count);
1256
    last.setNext(getFirst());
1257
    setFirst(el);
1258
    if (getLast() == null) {
1259
        setLast(last);
1260
    }
1261

    
1262
    return true;
1263
}
1264

    
1265

    
1266

    
1267
## Insert Last
1268

    
1269
{
1270
    if (el == null) {
1271
        return false;
1272
    }
1273
    // Loop detection using Floyd's circle-finding algorithm.
1274
    boolean run = true;
1275
    for (ListElement<T> i = el, j = el; run;) {
1276
        if (i.hasNext()) {
1277
            i = i.next();
1278
        } else {
1279
            run = false;
1280
            break;
1281
        }
1282
        if (j.hasNext() && j.next().hasNext()) {
1283
            j = j.next().next();
1284
        } else {
1285
            run = false;
1286
            break;
1287
        }
1288

    
1289
        if (i == j) {
1290
            return false;
1291
        }
1292
    }
1293

    
1294
    ListElement<T> last = null;
1295
    int count = 0;
1296
    for (ListElement<T> elem = el;
1297
            elem != null; elem = elem.next(), count++) {
1298
        if (contains(elem)) {
1299
            return false;
1300
        }
1301
        if (!elem.hasNext()) {
1302
            last = elem;
1303
        }
1304
    }
1305
    setSize(size() + count);
1306
    if (getLast() == null) {
1307
        setFirst(el);
1308
    } else {
1309
        getLast().setNext(el);
1310
    }
1311
    setLast(last);
1312

    
1313
    return true;
1314
}
1315

    
1316

    
1317

    
1318
## Insert (single)
1319

    
1320
{
1321
    if (el == null || idx < 0 || idx > size() || contains(el)) {
1322
        return false;
1323
    }
1324

    
1325
    el.setNext(null);
1326

    
1327
    if (idx == 0) {
1328
        el.setNext(getFirst());
1329
        setFirst(el);
1330
        if (getLast() == null) {
1331
            setLast(el);
1332
        }
1333
    } else if (idx == size()) {
1334
        if (getLast() == null) {
1335
            setFirst(el);
1336
            setLast(el);
1337
        } else {
1338
            getLast().setNext(el);
1339
            setLast(el);
1340
        }
1341
    } else {
1342
        int i = 1;
1343
        for (ListElement<T> elem = getFirst();
1344
                elem != null; elem = elem.next(), i++) {
1345
            if (i == idx) {
1346
                el.setNext(elem.next());
1347
                elem.setNext(el);
1348
                break;
1349
            }
1350
        }
1351
    }
1352
    setSize(size() + 1);
1353
    return true;
1354
}
1355

    
1356

    
1357

    
1358
## Invert
1359

    
1360
{
1361
    if (head == null) {
1362
        return null;
1363
    }
1364

    
1365
    ListElement<T> next = null;
1366
    ListElement<T> cur = head;
1367
    for (ListElement<T> el = head.next(); el != null; el = next) {
1368
        next = el.next();
1369

    
1370
        el.setNext(cur);
1371
        cur = el;
1372
    }
1373
    head.setNext(null);
1374
    return cur;
1375
}
1376

    
1377

    
1378

    
1379
## Merge Linked Lists
1380

    
1381
{
1382
    if (left == null || right == null || comp == null) {
1383
        throw new IllegalArgumentException();
1384
    }
1385

    
1386
    MListElement<T> result = null;
1387
    for (MListElement<T> i = left, j = right, merged = null;
1388
            i != null || j != null; ) {
1389
        final MListElement<T> use;
1390
        if (i == null) {
1391
            use = j;
1392
            j = j.getNext();
1393
        } else if (j == null) {
1394
            use = i;
1395
            i = i.getNext();
1396
        } else if (comp.compare(i.getKey(), j.getKey()) < 0) {
1397
            use = i;
1398
            i = i.getNext();
1399
        } else {
1400
            use = j;
1401
            j = j.getNext();
1402
        }
1403

    
1404
        if (merged != null) {
1405
            merged.setNext(use);
1406
        }
1407
        merged = use;
1408
        if (result == null) {
1409
            result = merged;
1410
        }
1411
    }
1412

    
1413
    return result;
1414
}
1415

    
1416

    
1417

    
1418
## Remove First
1419

    
1420
{
1421
    final ListElement<T> first = getFirst();
1422
    if (first != null) {
1423
        setFirst(first.next());
1424
        setSize(size() - 1);
1425
        if (size() == 0) {
1426
            setLast(null);
1427
        }
1428
    }
1429
    return first;
1430
}
1431

    
1432

    
1433

    
1434
## Remove Last
1435

    
1436
{
1437
    if (getFirst() == null) {
1438
        return null;
1439
    }
1440

    
1441
    final ListElement<T> result = getLast();
1442
    if (getFirst() == getLast()) {
1443
        setFirst(null);
1444
        setLast(null);
1445
    } else {
1446
        ListElement<T> secondLast = getFirst();
1447
        while (secondLast.next() != getLast()) {
1448
            secondLast = secondLast.next();
1449
        }
1450

    
1451
        secondLast.setNext(null);
1452
        setLast(secondLast);
1453
    }
1454
    setSize(size() - 1);
1455
    return result;
1456
}
1457

    
1458

    
1459

    
1460
## Remove duplicated Elements
1461

    
1462
{
1463
    if (head == null) {
1464
        return null;
1465
    }
1466

    
1467
    ListElement<T> prev = head;
1468
    for (ListElement<T> el = head.next(); el != null; el = el.next()) {
1469
        if (comp.compare(prev.getData(), el.getData()) == 0) {
1470
            prev.setNext(el.next());
1471
        } else {
1472
            prev = el;
1473
        }
1474
    }
1475
    return head;
1476
}
1477

    
1478

    
1479

    
1480

    
1481
# String Operations
1482

    
1483

    
1484

    
1485
## Prefix Check
1486

    
1487
{
1488
    if (a == null || b == null) {
1489
        throw new IllegalArgumentException();
1490
    }
1491

    
1492
    final String lowerA = StringHelper.toLowerCase(a);
1493
    final String lowerB = StringHelper.toLowerCase(b);
1494
    for (int i = 0; i < lowerA.length(); i++) {
1495
        if (i >= lowerB.length() || lowerA.charAt(i) != lowerB.charAt(i)) {
1496
            return false;
1497
        }
1498
    }
1499
    return true;
1500
}
1501

    
1502

    
1503

    
1504
## Simple String Matcher
1505

    
1506
{
1507
    if (S == null || T == null) {
1508
        throw new IllegalArgumentException();
1509
    }
1510

    
1511
    final String haystack = S.toLowerCase();
1512
    final String needle = T.toLowerCase();
1513

    
1514
    final ArrayList<int[]> tupels = new ArrayList<int[]>();
1515
    final ArrayList<Integer> result = new ArrayList<Integer>();
1516
    for (int i = 0; i < haystack.length(); i++) {
1517
        tupels.add(new int[] { i + 1, -1 } );
1518

    
1519
        final java.util.Iterator<int[]> it = tupels.iterator();
1520
        while (it.hasNext()) {
1521
            final int[] tupel = it.next();
1522
            tupel[1] += 1;
1523
            if (haystack.charAt(i) != needle.charAt(tupel[1])) {
1524
                it.remove();
1525
            } else if (tupel[1] == needle.length() - 1) {
1526
                it.remove();
1527
                result.add(tupel[0]);
1528
            }
1529
        }
1530
    }
1531
    return result;
1532
}
1533

    
1534

    
1535

    
1536

    
1537
# Lambda
1538

    
1539

    
1540

    
1541
## Lambda Expressions/Strategy Pattern
1542

    
1543

    
1544
### doArrayWork
1545

    
1546
{
1547
    final Integer[] result = new Integer[array.length];
1548
    for (int i = 0; i < array.length; i++) {
1549
        result[i] = array[i];
1550
    }
1551
    for (int i = 0; i < ops.length; i++) {
1552
        getOperations()[ops[i]].doSomeThingOnArrays(result);
1553
    }
1554
    return result;
1555
}
1556

    
1557

    
1558
### makeOperations
1559

    
1560
{
1561
    getOperations()[0] = arr -> {
1562
        for (int i = 0; i < arr.length; i++) {
1563
            arr[i] = arr[i] * arr[i];
1564
        }
1565
        return arr;
1566
    };
1567
    getOperations()[1] = arr -> {
1568
        for (int i = 0; i < arr.length; i++) {
1569
            arr[i] = arr[i] * 2;
1570
        }
1571
        return arr;
1572
    };
1573
    getOperations()[2] = arr -> {
1574
        for (int i = 0; i < arr.length; i++) {
1575
            arr[i] = arr[i] + 2;
1576
        }
1577
        return arr;
1578
    };
1579
}
(10-10/10) Go to top