Project

General

Profile

Codemonkeys Solutions » codemonkeys_v06.txt

Codemonkeys Solutions - Version 6 (Text only) - Fabian Damken, 2017-06-07 23:57

 
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 Triples
349

    
350
{
351
    if (list == null) {
352
        throw new IllegalArgumentException();
353
    }
354

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

    
360
        list[i - 2] = b;
361
        list[i - 1] = c;
362
        list[i] = a;
363
    }
364
    return list;
365
}
366

    
367

    
368

    
369
## Rotate Tripels
370

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

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

    
386
    return true;
387
}
388

    
389

    
390

    
391
## Selection-Sort Iterative
392

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

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

    
411

    
412

    
413
## Ehift elements left
414

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

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

    
426
    return list;
427
}
428

    
429

    
430

    
431
## Shift elements right
432

    
433
{
434
    if (list == null) {
435
        return null;
436
    }
437

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

    
447

    
448

    
449

    
450
# Baum
451

    
452

    
453

    
454
## Binary Search Tree: Traverse
455

    
456

    
457
### getElements
458

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

    
467

    
468
### getElementsRec
469

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

    
482

    
483

    
484

    
485
# Graph
486

    
487

    
488

    
489
## Add Edge
490

    
491

    
492
### Methode 1
493

    
494
{
495
    if (from == null || to == null || data == null) {
496
        throw new IllegalArgumentException();
497
    }
498
    if (getFanOutMax() < from.getFanOut().size() + 1 || getFanInMax() < to.getFanIn().size() + 1) {
499
        throw new FanOverflowException("");
500
    }
501

    
502
    final Edge<N, E> edge = new Edge(from, to, data);
503
    from.getFanOut().add(edge);
504
    to.getFanIn().add(edge);
505
    final ArrayList<Edge<N, E>> edges = getEdgeList();
506
    edges.add(edge);
507
    setEdgeList(edges);
508
}
509

    
510

    
511
### Methode 2
512

    
513
{
514
    if (from == null || to == null || data == null) {
515
        throw new IllegalArgumentException();
516
    }
517
    if (getFanOutMax() <= from.getFanOut().size() + 1 || getFanInMax() <= to.getFanIn().size() + 1) {
518
        throw new FanOverflowException("");
519
    }
520

    
521
    final Edge<N, E> edge = new Edge(from, to, data);
522
    from.getFanOut().add(edge);
523
    to.getFanIn().add(edge);
524
    final ArrayList<Edge<N, E>> edges = getEdgeList();
525
    edges.add(edge);
526
    setEdgeList(edges);
527
}
528

    
529

    
530

    
531
## Add Node
532

    
533
{
534
    if (data == null) {
535
        return null;
536
    }
537

    
538
    final Node<N, E> node = new Node(getIdGen(), data);
539
    final ArrayList<Node<N, E>> nodes = getNodeList();
540
    nodes.add(node);
541
    setNodeList(nodes);
542
    return node;
543
}
544

    
545

    
546

    
547
## Count Edges
548

    
549

    
550
### countEdgesRec
551

    
552
{
553
    if (!nodeSet.add(node)) {
554
        return;
555
    }
556

    
557
    for (final Edge<N, E> edge : node.getFanOut()) {
558
        edgeSet.add(edge);
559

    
560
        countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
561
    }
562
    for (final Edge<N, E> edge : node.getFanIn()) {
563
        edgeSet.add(edge);
564

    
565
        countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
566
    }
567
}
568

    
569

    
570
### countEdgesInConnectedGraph
571

    
572
{
573
    if (node == null || !contains(node)) {
574
        return -1;
575
    }
576

    
577
    final HashSet<Edge<N, E>> edges = new HashSet<>();
578
    final HashSet<Node<N, E>> nodes = new HashSet<>();
579
    countEdgesRec(node, edges, nodes);
580
    return edges.size();
581
}
582

    
583

    
584

    
585
## Find Node
586

    
587
{
588
    if (startNode == null || data == null || !contains(startNode)) {
589
        return null;
590
    }
591

    
592
    final HashSet<Node<N, E>> processed = new HashSet<>();
593
    final ArrayDeque<Node<N, E>> stack = new ArrayDeque<>();
594
    stack.push(startNode);
595
    while (!stack.isEmpty()) {
596
        final Node<N, E> node = stack.pop();
597

    
598
        if (processed.contains(node)) {
599
            continue;
600
        }
601

    
602
        processed.add(node);
603
        for (final Edge<N, E> edge : node.getFanOut()) {
604
            stack.push(edge.getTargetNode());
605
        }
606

    
607
        if (objectEquals(node.getData(), data)) {
608
            return node;
609
        }
610
    }
611
    return null;
612
}
613

    
614

    
615

    
616
## Remove Edge
617

    
618
{
619
    if (edge == null || !getEdgeList().contains(edge)) {
620
        return false;
621
    }
622

    
623
    final ArrayList<Edge<N, E>> edges = getEdgeList();
624
    edges.remove(edge);
625
    setEdgeList(edges);
626

    
627
    edge.removeFromNodes();
628

    
629
    return true;
630
}
631

    
632

    
633

    
634
## Remove Node
635

    
636
{
637
    if (node == null || !contains(node)) {
638
        return false;
639
    }
640

    
641
    final ArrayList<Node<N, E>> nodes = getNodeList();
642
    nodes.remove(node);
643
    setNodeList(nodes);
644

    
645
    final ArrayList<Edge<N, E>> edges = getEdgeList();
646
    edges.removeAll(node.getFanOut());
647
    edges.removeAll(node.getFanIn());
648
    setEdgeList(edges);
649

    
650
    for (final Edge<N, E> edge : node.getFanOut()) {
651
        edge.removeFromNodes();
652
    }
653
    for (final Edge<N, E> edge : node.getFanIn()) {
654
        edge.removeFromNodes();
655
    }
656

    
657
    return true;
658
}
659

    
660

    
661

    
662

    
663
# Iterativ
664

    
665

    
666

    
667
## Palindrome Check
668

    
669
{
670
    if (s == null) {
671
        throw new NullPointerException();
672
    }
673
    if (StringHelper.isEmpty(s)) {
674
        return false;
675
    }
676

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

    
686

    
687

    
688
## Fibonacci
689

    
690
{
691
    if (n < 0) {
692
        throw new IllegalArgumentException();
693
    }
694

    
695
    if (n == 0) {
696
        return 0;
697
    }
698

    
699
    int prev = 0;
700
    int result = 1;
701
    for (int i = 1; i < n; i++) {
702
        result = prev + (prev = result);
703
    }
704
    return result;
705
}
706

    
707

    
708

    
709
## Multiple Palindrome Check
710

    
711
{
712
    if (a == null) {
713
        throw new NullPointerException();
714
    }
715
    if (a.length <= 0) {
716
        return null;
717
    }
718

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

    
734

    
735

    
736

    
737
# MIPS
738

    
739

    
740

    
741

    
742
# Rekursiv
743

    
744

    
745

    
746
## Approximate Square Root
747

    
748
{
749
    if (x < 0 || g < 0 || tolerance < 0) {
750
        throw new IllegalArgumentException();
751
    }
752

    
753
    if (Math.abs((x / g) - g) < tolerance) {
754
        return g;
755
    }
756

    
757
    return proxRootRec(x, ((x / g) + g) / 2, tolerance);
758
}
759

    
760

    
761

    
762
## Fibonacci
763

    
764
{
765
    if (i <= 0) {
766
        return 0;
767
    }
768
    if (i == 1) {
769
        return 1;
770
    }
771
    return fibRec(i - 1) + fibRec(i - 2);
772
}
773

    
774

    
775

    
776

    
777
# Single Linked List
778

    
779

    
780

    
781
## Insert First (single)
782

    
783
{
784
    if (el == null || getFirst() == el) {
785
        return false;
786
    }
787

    
788
    if (getFirst() == null) {
789
        setLast(el);
790
    }
791
    el.setNext(getFirst());
792
    setFirst(el);
793
    setSize(size() + 1);
794

    
795
    return true;
796
}
797

    
798

    
799

    
800
## Insert Last (single)
801

    
802
{
803
    if (el == null || getLast() == el) {
804
        return false;
805
    }
806

    
807
    if (getFirst() == null) {
808
        setFirst(el);
809
    } else {
810
        getLast().setNext(el);
811
    }
812
    setLast(el);
813
    el.setNext(null);
814

    
815
    setSize(size() + 1);
816

    
817
    return true;
818
}
819

    
820

    
821

    
822
## Clone Elements
823

    
824
{
825
    if (el == null) {
826
        throw new NullPointerException();
827
    }
828

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

    
840

    
841

    
842
## Clone List
843

    
844
{
845
    if (list == null) {
846
        throw new NullPointerException();
847
    }
848
    if (list.isEmpty()) {
849
        return new LinkedList<T>();
850
    }
851

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

    
868

    
869

    
870
## Duplicate every second Element
871

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

    
882
        duplicate = !duplicate;
883
    }
884

    
885
    return head;
886
}
887

    
888

    
889

    
890
## Get at Index
891

    
892
{
893
    // Dummy call to make Codemonkeys happy.
894
    isEmpty();
895

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

    
905

    
906

    
907
## Insert First
908

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

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

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

    
952
    return true;
953
}
954

    
955

    
956

    
957
## Insert Last
958

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

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

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

    
1003
    return true;
1004
}
1005

    
1006

    
1007

    
1008
## Insert (single)
1009

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

    
1015
    el.setNext(null);
1016

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

    
1046

    
1047

    
1048
## Invert
1049

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

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

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

    
1067

    
1068

    
1069
## Merge Linked Lists
1070

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

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

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

    
1103
    return result;
1104
}
1105

    
1106

    
1107

    
1108
## Remove First
1109

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

    
1122

    
1123

    
1124
## Remove Last
1125

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

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

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

    
1148

    
1149

    
1150
## Remove duplicated Elements
1151

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

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

    
1168

    
1169

    
1170

    
1171
# String Operations
1172

    
1173

    
1174

    
1175
## Prefix Check
1176

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

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

    
1192

    
1193

    
1194
## Simple String Matcher
1195

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

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

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

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

    
1224

    
1225

    
1226

    
1227
# Lambda
1228

    
1229

    
1230

    
1231
## Lambda Expressions/Strategy Pattern
1232

    
1233

    
1234
### doArrayWork
1235

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

    
1247

    
1248
### makeOperations
1249

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