old_classwork_cs445_algorithms/tape_merge.cpp at master · rcrocomb/old_classwork_cs445_algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <assert.h>

#include <vector>

/*!
    Tapes will be represented by vectors.

    Front of tape is back of vector

    So tape that holds "abcd" is like so:

    [0] [1] [2] [3]
     d   c   b   a
*/
typedef std::vector<int> tape_t;

/*!
    Write element 'data' to end of tape
*/

void
write(tape_t *d, unsigned int data)
{
    d->insert(d->begin(), 1, data);
}

unsigned int
read(tape_t *s)
{
    assert((!s->empty()) && "read: empty tape");
    unsigned int data = s->back();
    s->pop_back();
    return data;
}

bool
is_end(tape_t *t)
{
    return t->empty();
}

void
alice
(
    unsigned int x,
    unsigned int y,
    tape_t *s1,
    tape_t *t2,
    tape_t *s3,
    tape_t *d,
    tape_t *o
)
{
    while (!is_end(s3))
    {
        if (is_end(d))
            write(o, x);
        else
            write(d, x)
        x = read(s3);
    }
    sorty_thing(d, o, d, s1, s2);
}

/*!
    Return value is tape number 1..4 where sorted keys start: extra keys are on
    "tape + 1".  If value is 4, then I dunno.
*/

unsigned int
sorty_thing(tape_t *s1, tape_t *t2, tape_t *s3, tape_t *d, tape_t *o)
{
    static unsigned int x, y;
    x = read(s1);
    y = read(s2);
    if (x < y)
    {
        write(d, x);
        write(d, y);
        x = y;
    } else
    {
        write(d, y);
        write(d, x);
    }

    y = read(s3);
    if (is_end(s3))
    {
        if (y > x)
        {
            write();
        }
    } else
    {
        alice(x, y, s1, s2, s3, d, o);
    }
}

void
merge(tape_t *t1, tape_t *t2, tape_t *t3, tape_t *t4)
{
    unsigned int n = t1->size() + t2->size();

    switch (n)
    {
    case 0:
        // blank tapes!
        return;
    case 1:
        //  single element on tape 1.  Done!
        return;
    case 2:
    {
        // two possibilities: smallest on 1st tape, or smallest on 2nd
        assert((t1->size() == 1) && "t1 is screwed up");
        assert((t2->size() == 1) && "t2 is screwed up");

        unsigned int x = (*t1)[0];
        unsigned int y = (*t2)[0];
        if (x < y)
            return; // came in sorted order (smallest on 1st): done
        else
        {
            (*t1)[0] = y;   // reverse sorted (smallest on 2nd): fix
            (*t2)[0] = x;
            // done!
            return;
        }
    }
    break;

    default:
        // unknown number of elements
        sorty_thing(t1,t1,t2,t3,t4);
    }

}

/*!

*/

int
main(int argc, char *argv[])
{
    tape_t t1();
    tape_t t2();
    tape_t t3();
    tape_t t4();

    merge(&t1, &t2, &t3, &t4);

    return 0;
}