Project

General

Profile

Codemonkeys Solutions » codemonkeys_v05.txt

Codemonkeys Solutions - Version 5 (Text only) - Fabian Damken, 2017-06-06 23:47

 
1

    
2

    
3

    
4

    
5
# Array List
6

    
7

    
8

    
9
## Contains
10

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

    
23

    
24

    
25
## Remove
26

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

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

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

    
54

    
55

    
56

    
57
# Priority Queue
58

    
59

    
60

    
61
## Peek
62

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

    
67

    
68

    
69
## Push
70

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

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

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

    
87
        return true;
88
    }
89

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

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

    
103

    
104

    
105
## Pop
106

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

    
116

    
117

    
118

    
119
# Array
120

    
121

    
122

    
123
## Array is Sorted
124

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

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

    
140

    
141

    
142
## Insert
143

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

    
170

    
171

    
172
## Insert at Index
173

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

    
201

    
202

    
203
## Remove
204

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

    
217

    
218

    
219
## Search second largest Element
220

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

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

    
243

    
244

    
245
## Sort $O(n^2)$ Iterative
246

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

    
258
    return inputdata;
259
}
260

    
261

    
262

    
263
## Duplicate every second Element
264

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

    
277

    
278

    
279
## Linear Search
280

    
281
{
282
    if (getElem() == null) {
283
        return -1;
284
    }
285

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

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

    
298

    
299

    
300
## Merge
301

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

    
328

    
329

    
330
## Rotate Pairs
331

    
332
{
333
    if (list == null) {
334
        throw new NullPointerException();
335
    }
336

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

    
343
    return list;
344
}
345

    
346

    
347

    
348
## Rotate successive Tripels
349

    
350
{
351
    if (a < 0 || b < 0 || c < 0) {
352
        throw new IndexOutOfBoundsException();
353
    }
354
    if (a >= array.length || b >= array.length || c >= array.length) {
355
        return false;
356
    }
357

    
358
    final Listobject<T> aElem = array[a];
359
    final Listobject<T> bElem = array[b];
360
    final Listobject<T> cElem = array[c];
361
    array[a] = cElem;
362
    array[b] = aElem;
363
    array[c] = bElem;
364

    
365
    return true;
366
}
367

    
368

    
369

    
370
## Rotate Triples
371

    
372
{
373
    if (a < 0 || b < 0 || c < 0) {
374
        throw new IndexOutOfBoundsException();
375
    }
376
    if (a >= array.length || b >= array.length || c >= array.length) {
377
        return false;
378
    }
379

    
380
    final Listobject<T> aElem = array[a];
381
    final Listobject<T> bElem = array[b];
382
    final Listobject<T> cElem = array[c];
383
    array[a] = cElem;
384
    array[b] = aElem;
385
    array[c] = bElem;
386

    
387
    return true;
388
}
389

    
390

    
391

    
392
## Selection-Sort Iterative
393

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

    
403
        if (array[m].compareTo(array[i]) > 0) {
404
            Listobject<T> tmp = array[i];
405
            array[i] = array[m];
406
            array[m] = tmp;
407
        }
408
    }
409
    return array;
410
}
411

    
412

    
413

    
414
## Ehift elements left
415

    
416
{
417
    if (list == null) {
418
        return null;
419
    }
420
    if (list.length == 0) {
421
        return list;
422
    }
423

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

    
430
    return list;
431
}
432

    
433

    
434

    
435
## Shift elements right
436

    
437
{
438
    if (list == null) {
439
        return null;
440
    }
441

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

    
451

    
452

    
453

    
454
# Baum
455

    
456

    
457

    
458
## Binary Search Tree: Traverse
459

    
460

    
461
### getElements
462

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

    
471

    
472
### getElementsRec
473

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

    
486

    
487

    
488

    
489
# Graph
490

    
491

    
492

    
493
## Add Edge
494

    
495

    
496
### Methode 1
497

    
498
{
499
    if (from == null || to == null || data == null) {
500
        throw new IllegalArgumentException();
501
    }
502
    if (getFanOutMax() < from.getFanOut().size() + 1 || getFanInMax() < to.getFanIn().size() + 1) {
503
        throw new FanOverflowException("");
504
    }
505

    
506
    final Edge<N, E> edge = new Edge(from, to, data);
507
    from.getFanOut().add(edge);
508
    to.getFanIn().add(edge);
509
    final ArrayList<Edge<N, E>> edges = getEdgeList();
510
    edges.add(edge);
511
    setEdgeList(edges);
512
}
513

    
514

    
515
### Methode 2
516

    
517
{
518
    if (from == null || to == null || data == null) {
519
        throw new IllegalArgumentException();
520
    }
521
    if (getFanOutMax() <= from.getFanOut().size() + 1 || getFanInMax() <= to.getFanIn().size() + 1) {
522
        throw new FanOverflowException("");
523
    }
524

    
525
    final Edge<N, E> edge = new Edge(from, to, data);
526
    from.getFanOut().add(edge);
527
    to.getFanIn().add(edge);
528
    final ArrayList<Edge<N, E>> edges = getEdgeList();
529
    edges.add(edge);
530
    setEdgeList(edges);
531
}
532

    
533

    
534

    
535
## Add Node
536

    
537
{
538
    if (data == null) {
539
        return null;
540
    }
541

    
542
    final Node<N, E> node = new Node(getIdGen(), data);
543
    final ArrayList<Node<N, E>> nodes = getNodeList();
544
    nodes.add(node);
545
    setNodeList(nodes);
546
    return node;
547
}
548

    
549

    
550

    
551
## Count Edges
552

    
553

    
554
### countEdgesRec
555

    
556
{
557
    if (!nodeSet.add(node)) {
558
        return;
559
    }
560

    
561
    for (final Edge<N, E> edge : node.getFanOut()) {
562
        edgeSet.add(edge);
563

    
564
        countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
565
    }
566
    for (final Edge<N, E> edge : node.getFanIn()) {
567
        edgeSet.add(edge);
568

    
569
        countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
570
    }
571
}
572

    
573

    
574
### countEdgesInConnectedGraph
575

    
576
{
577
    if (node == null || !contains(node)) {
578
        return -1;
579
    }
580

    
581
    final HashSet<Edge<N, E>> edges = new HashSet<>();
582
    final HashSet<Node<N, E>> nodes = new HashSet<>();
583
    countEdgesRec(node, edges, nodes);
584
    return edges.size();
585
}
586

    
587

    
588

    
589
## Find Node
590

    
591
{
592
    if (startNode == null || data == null || !contains(startNode)) {
593
        return null;
594
    }
595

    
596
    final HashSet<Node<N, E>> processed = new HashSet<>();
597
    final ArrayDeque<Node<N, E>> stack = new ArrayDeque<>();
598
    stack.push(startNode);
599
    while (!stack.isEmpty()) {
600
        final Node<N, E> node = stack.pop();
601

    
602
        if (processed.contains(node)) {
603
            continue;
604
        }
605

    
606
        processed.add(node);
607
        for (final Edge<N, E> edge : node.getFanOut()) {
608
            stack.push(edge.getTargetNode());
609
        }
610

    
611
        if (objectEquals(node.getData(), data)) {
612
            return node;
613
        }
614
    }
615
    return null;
616
}
617

    
618

    
619

    
620
## Remove Edge
621

    
622
{
623
    if (edge == null || !getEdgeList().contains(edge)) {
624
        return false;
625
    }
626

    
627
    final ArrayList<Edge<N, E>> edges = getEdgeList();
628
    edges.remove(edge);
629
    setEdgeList(edges);
630

    
631
    edge.removeFromNodes();
632

    
633
    return true;
634
}
635

    
636

    
637

    
638
## Remove Node
639

    
640
{
641
    if (node == null || !contains(node)) {
642
        return false;
643
    }
644

    
645
    final ArrayList<Node<N, E>> nodes = getNodeList();
646
    nodes.remove(node);
647
    setNodeList(nodes);
648

    
649
    final ArrayList<Edge<N, E>> edges = getEdgeList();
650
    edges.removeAll(node.getFanOut());
651
    edges.removeAll(node.getFanIn());
652
    setEdgeList(edges);
653

    
654
    for (final Edge<N, E> edge : node.getFanOut()) {
655
        edge.removeFromNodes();
656
    }
657
    for (final Edge<N, E> edge : node.getFanIn()) {
658
        edge.removeFromNodes();
659
    }
660

    
661
    return true;
662
}
663

    
664

    
665

    
666

    
667
# Iterativ
668

    
669

    
670

    
671
## Palindrome Check
672

    
673
{
674
    if (s == null) {
675
        throw new NullPointerException();
676
    }
677
    if (StringHelper.isEmpty(s)) {
678
        return false;
679
    }
680

    
681
    final String lower = s.toLowerCase();
682
    for (int i = 0; i < StringHelper.length(lower) / 2; i++) {
683
        if (lower.charAt(i) != lower.charAt(s.length() - i - 1)) {
684
            return false;
685
        }
686
    }
687
    return true;
688
}
689

    
690

    
691

    
692
## Fibonacci
693

    
694
{
695
    if (n < 0) {
696
        throw new IllegalArgumentException();
697
    }
698

    
699
    if (n == 0) {
700
        return 0;
701
    }
702

    
703
    int prev = 0;
704
    int result = 1;
705
    for (int i = 1; i < n; i++) {
706
        result = prev + (prev = result);
707
    }
708
    return result;
709
}
710

    
711

    
712

    
713
## Multiple Palindrome Check
714

    
715
{
716
    if (a == null) {
717
        throw new NullPointerException();
718
    }
719
    if (a.length <= 0) {
720
        return null;
721
    }
722

    
723
    final boolean[] result = new boolean[a.length];
724
    for (int i = 0; i < a.length; i++) {
725
        final String s = a[i].toLowerCase();
726
        boolean palindrome = true;
727
        for (int j = 0; j < StringHelper.length(s) / 2; j++) {
728
            if (s.charAt(j) != s.charAt(s.length() - j - 1)) {
729
                palindrome = false;
730
                break;
731
            }
732
        }
733
        result[i] = palindrome;
734
    }
735
    return result;
736
}
737

    
738

    
739

    
740

    
741
# MIPS
742

    
743

    
744

    
745

    
746
# Rekursiv
747

    
748

    
749

    
750
## Approximate Square Root
751

    
752
{
753
    if (x < 0 || g < 0 || tolerance < 0) {
754
        throw new IllegalArgumentException();
755
    }
756

    
757
    if (Math.abs((x / g) - g) < tolerance) {
758
        return g;
759
    }
760

    
761
    return proxRootRec(x, ((x / g) + g) / 2, tolerance);
762
}
763

    
764

    
765

    
766
## Fibonacci
767

    
768
{
769
    if (i <= 0) {
770
        return 0;
771
    }
772
    if (i == 1) {
773
        return 1;
774
    }
775
    return fibRec(i - 1) + fibRec(i - 2);
776
}
777

    
778

    
779

    
780

    
781
# Single Linked List
782

    
783

    
784

    
785
## Insert First (single)
786

    
787
{
788
    if (el == null || getFirst() == el) {
789
        return false;
790
    }
791

    
792
    if (getFirst() == null) {
793
        setLast(el);
794
    }
795
    el.setNext(getFirst());
796
    setFirst(el);
797
    setSize(size() + 1);
798

    
799
    return true;
800
}
801

    
802

    
803

    
804
## Insert Last (single)
805

    
806
{
807
    if (el == null || getLast() == el) {
808
        return false;
809
    }
810

    
811
    if (getFirst() == null) {
812
        setFirst(el);
813
    } else {
814
        getLast().setNext(el);
815
    }
816
    setLast(el);
817
    el.setNext(null);
818

    
819
    setSize(size() + 1);
820

    
821
    return true;
822
}
823

    
824

    
825

    
826
## Clone Elements
827

    
828
{
829
    if (el == null) {
830
        throw new NullPointerException();
831
    }
832

    
833
    final ListElement<T> head = new ListElement<T>(el.getData());
834
    ListElement<T> clone = head;
835
    for (ListElement<T> orig = el.next();
836
            orig != null; orig = orig.next()) {
837
        final ListElement<T> elem = new ListElement<T>(orig.getData());
838
        clone.setNext(elem);
839
        clone = elem;
840
    }
841
    return head;
842
}
843

    
844

    
845

    
846
## Clone List
847

    
848
{
849
    if (list == null) {
850
        throw new NullPointerException();
851
    }
852
    if (list.isEmpty()) {
853
        return new LinkedList<T>();
854
    }
855

    
856
    final ListElement<T> head = list.getFirst();
857
    final LinkedList<T> result = new LinkedList<T>();
858
    ListElement<T> clone = new ListElement<T>(head.getData());
859
    result.setFirst(clone);
860
    int count = 1;
861
    for (ListElement<T> el = head.next(); el != null; el = el.next()) {
862
        final ListElement<T> elem = new ListElement<T>(el.getData());
863
        clone.setNext(elem);
864
        clone = elem;
865
        count++;
866
    }
867
    result.setSize(count);
868
    result.setLast(clone);
869
    return result;
870
}
871

    
872

    
873

    
874
## Duplicate every second Element
875

    
876
{
877
    boolean duplicate = true;
878
    for (MListElement<T> el = head; el != null; el = el.getNext()) {
879
        if (duplicate) {
880
            final MListElement<T> dupl = new MListElement<T>(el.getKey());
881
            dupl.setNext(el.getNext());
882
            el.setNext(dupl);
883
            el = dupl;
884
        }
885

    
886
        duplicate = !duplicate;
887
    }
888

    
889
    return head;
890
}
891

    
892

    
893

    
894
## Get at Index
895

    
896
{
897
    int i = 0;
898
    for (ListElement<T> el = getFirst(); el != null; el = el.next(), i++) {
899
        if (i == idx) {
900
            return el;
901
        }
902
    }
903
    return null;
904
}
905

    
906

    
907

    
908
## Insert First
909

    
910
{
911
    if (el == null) {
912
        return false;
913
    }
914
    // Loop detection using Floyd's circle-finding algorithm.
915
    boolean run = true;
916
    for (ListElement<T> i = el, j = el; run;) {
917
        if (i.hasNext()) {
918
            i = i.next();
919
        } else {
920
            run = false;
921
            break;
922
        }
923
        if (j.hasNext() && j.next().hasNext()) {
924
            j = j.next().next();
925
        } else {
926
            run = false;
927
            break;
928
        }
929

    
930
        if (i == j) {
931
            return false;
932
        }
933
    }
934

    
935
    ListElement<T> last = null;
936
    int count = 0;
937
    for (ListElement<T> elem = el; elem != null;
938
            elem = elem.next(), count++) {
939
        if (contains(elem)) {
940
            return false;
941
        }
942
        if (!elem.hasNext()) {
943
            last = elem;
944
        }
945
    }
946
    setSize(size() + count);
947
    last.setNext(getFirst());
948
    setFirst(el);
949
    if (getLast() == null) {
950
        setLast(last);
951
    }
952

    
953
    return true;
954
}
955

    
956

    
957

    
958
## Insert Last
959

    
960
{
961
    if (el == null) {
962
        return false;
963
    }
964
    // Loop detection using Floyd's circle-finding algorithm.
965
    boolean run = true;
966
    for (ListElement<T> i = el, j = el; run;) {
967
        if (i.hasNext()) {
968
            i = i.next();
969
        } else {
970
            run = false;
971
            break;
972
        }
973
        if (j.hasNext() && j.next().hasNext()) {
974
            j = j.next().next();
975
        } else {
976
            run = false;
977
            break;
978
        }
979

    
980
        if (i == j) {
981
            return false;
982
        }
983
    }
984

    
985
    ListElement<T> last = null;
986
    int count = 0;
987
    for (ListElement<T> elem = el;
988
            elem != null; elem = elem.next(), count++) {
989
        if (contains(elem)) {
990
            return false;
991
        }
992
        if (!elem.hasNext()) {
993
            last = elem;
994
        }
995
    }
996
    setSize(size() + count);
997
    if (getLast() == null) {
998
        setFirst(el);
999
    } else {
1000
        getLast().setNext(el);
1001
    }
1002
    setLast(last);
1003

    
1004
    return true;
1005
}
1006

    
1007

    
1008

    
1009
## Insert (single)
1010

    
1011
{
1012
    if (el == null || idx < 0 || idx > size() || contains(el)) {
1013
        return false;
1014
    }
1015

    
1016
    el.setNext(null);
1017

    
1018
    if (idx == 0) {
1019
        el.setNext(getFirst());
1020
        setFirst(el);
1021
        if (getLast() == null) {
1022
            setLast(el);
1023
        }
1024
    } else if (idx == size()) {
1025
        if (getLast() == null) {
1026
            setFirst(el);
1027
            setLast(el);
1028
        } else {
1029
            getLast().setNext(el);
1030
            setLast(el);
1031
        }
1032
    } else {
1033
        int i = 1;
1034
        for (ListElement<T> elem = getFirst();
1035
                elem != null; elem = elem.next(), i++) {
1036
            if (i == idx) {
1037
                el.setNext(elem.next());
1038
                elem.setNext(el);
1039
                break;
1040
            }
1041
        }
1042
    }
1043
    setSize(size() + 1);
1044
    return true;
1045
}
1046

    
1047

    
1048

    
1049
## Invert
1050

    
1051
{
1052
    if (head == null) {
1053
        return null;
1054
    }
1055

    
1056
    ListElement<T> next = null;
1057
    ListElement<T> cur = head;
1058
    for (ListElement<T> el = head.next(); el != null; el = next) {
1059
        next = el.next();
1060

    
1061
        el.setNext(cur);
1062
        cur = el;
1063
    }
1064
    head.setNext(null);
1065
    return cur;
1066
}
1067

    
1068

    
1069

    
1070
## Merge Linked Lists
1071

    
1072
{
1073
    if (left == null || right == null || comp == null) {
1074
        throw new IllegalArgumentException();
1075
    }
1076

    
1077
    MListElement<T> result = null;
1078
    for (MListElement<T> i = left, j = right, merged = null;
1079
            i != null || j != null; ) {
1080
        final MListElement<T> use;
1081
        if (i == null) {
1082
            use = j;
1083
            j = j.getNext();
1084
        } else if (j == null) {
1085
            use = i;
1086
            i = i.getNext();
1087
        } else if (comp.compare(i.getKey(), j.getKey()) < 0) {
1088
            use = i;
1089
            i = i.getNext();
1090
        } else {
1091
            use = j;
1092
            j = j.getNext();
1093
        }
1094

    
1095
        if (merged != null) {
1096
            merged.setNext(use);
1097
        }
1098
        merged = use;
1099
        if (result == null) {
1100
            result = merged;
1101
        }
1102
    }
1103

    
1104
    return result;
1105
}
1106

    
1107

    
1108

    
1109
## Remove First
1110

    
1111
{
1112
    final ListElement<T> first = getFirst();
1113
    if (first != null) {
1114
        setFirst(first.next());
1115
        setSize(size() - 1);
1116
        if (size() == 0) {
1117
            setLast(null);
1118
        }
1119
    }
1120
    return first;
1121
}
1122

    
1123

    
1124

    
1125
## Remove Last
1126

    
1127
{
1128
    if (getFirst() == null) {
1129
        return null;
1130
    }
1131

    
1132
    final ListElement<T> result = getLast();
1133
    if (getFirst() == getLast()) {
1134
        setFirst(null);
1135
        setLast(null);
1136
    } else {
1137
        ListElement<T> secondLast = getFirst();
1138
        while (secondLast.next() != getLast()) {
1139
            secondLast = secondLast.next();
1140
        }
1141

    
1142
        secondLast.setNext(null);
1143
        setLast(secondLast);
1144
    }
1145
    setSize(size() - 1);
1146
    return result;
1147
}
1148

    
1149

    
1150

    
1151
## Remove duplicated Elements
1152

    
1153
{
1154
    if (head == null) {
1155
        return null;
1156
    }
1157

    
1158
    ListElement<T> prev = head;
1159
    for (ListElement<T> el = head.next(); el != null; el = el.next()) {
1160
        if (comp.compare(prev.getData(), el.getData()) == 0) {
1161
            prev.setNext(el.next());
1162
        } else {
1163
            prev = el;
1164
        }
1165
    }
1166
    return head;
1167
}
1168

    
1169

    
1170

    
1171

    
1172
# String Operations
1173

    
1174

    
1175

    
1176
## Prefix Check
1177

    
1178
{
1179
    if (a == null || b == null) {
1180
        return false;
1181
    }
1182

    
1183
    final String lowerA = a.toLowerCase();
1184
    final String lowerB = b.toLowerCase();
1185
    for (int i = 0; i < lowerA.length(); i++) {
1186
        if (i >= lowerB.length() || lowerA.charAt(i) != lowerB.charAt(i)) {
1187
            return false;
1188
        }
1189
    }
1190
    return true;
1191
}
1192

    
1193

    
1194

    
1195
## Simple String Matcher
1196

    
1197
{
1198
    if (S == null || T == null) {
1199
        throw new IllegalArgumentException();
1200
    }
1201

    
1202
    final String haystack = S.toLowerCase();
1203
    final String needle = T.toLowerCase();
1204

    
1205
    final ArrayList<int[]> tupels = new ArrayList<int[]>();
1206
    final ArrayList<Integer> result = new ArrayList<Integer>();
1207
    for (int i = 0; i < haystack.length(); i++) {
1208
        tupels.add(new int[] { i + 1, -1 } );
1209

    
1210
        final java.util.Iterator<int[]> it = tupels.iterator();
1211
        while (it.hasNext()) {
1212
            final int[] tupel = it.next();
1213
            tupel[1] += 1;
1214
            if (haystack.charAt(i) != needle.charAt(tupel[1])) {
1215
                it.remove();
1216
            } else if (tupel[1] == needle.length() - 1) {
1217
                it.remove();
1218
                result.add(tupel[0]);
1219
            }
1220
        }
1221
    }
1222
    return result;
1223
}
1224

    
1225

    
1226

    
1227

    
1228
# Lambda
1229

    
1230

    
1231

    
1232
## Lambda Expressions/Strategy Pattern
1233

    
1234

    
1235
### doArrayWork
1236

    
1237
{
1238
    final Integer[] result = new Integer[array.length];
1239
    for (int i = 0; i < array.length; i++) {
1240
        result[i] = array[i];
1241
    }
1242
    for (int i = 0; i < ops.length; i++) {
1243
        getOperations()[ops[i]].doSomeThingOnArrays(result);
1244
    }
1245
    return result;
1246
}
1247

    
1248

    
1249
### makeOperations
1250

    
1251
{
1252
    getOperations()[0] = arr -> {
1253
        for (int i = 0; i < arr.length; i++) {
1254
            arr[i] = arr[i] * arr[i];
1255
        }
1256
        return arr;
1257
    };
1258
    getOperations()[1] = arr -> {
1259
        for (int i = 0; i < arr.length; i++) {
1260
            arr[i] = arr[i] * 2;
1261
        }
1262
        return arr;
1263
    };
1264
    getOperations()[2] = arr -> {
1265
        for (int i = 0; i < arr.length; i++) {
1266
            arr[i] = arr[i] + 2;
1267
        }
1268
        return arr;
1269
    };
1270
}
(6-6/10) Go to top