Skip to content

Instantly share code, notes, and snippets.

@supr

supr/list.cc

Last active December 7, 2018 05:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save supr/3d5a63c07d486512e5380124a658d8c3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save supr/3d5a63c07d486512e5380124a658d8c3 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. supr revised this gist Dec 7, 2018. 1 changed file with 3 additions and 0 deletions.
    3 changes: 3 additions & 0 deletions list.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -95,6 +95,9 @@ void mylist<T>::merge_sorted(mylist<T>&& l) {
    } else {
    new_tail->next = h1;
    }

    head = new_head;
    tail = new_tail;
    }

    template<typename T>
  2. supr created this gist Dec 7, 2018.
    156 changes: 156 additions & 0 deletions list.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,156 @@
    #include <iostream>
    #include <memory>
    #include <optional>

    template<typename T>
    class mylist;

    template<typename T>
    class mynode {
    private:
    T data;
    std::shared_ptr<mynode<T>> next = nullptr;

    public:
    mynode() = default;
    mynode(T data): data{data} {}
    mynode(const mynode<T>&) = delete;
    mynode<T>& operator=(const mynode<T>&) = delete;

    friend class mylist<T>;
    };

    template<typename T>
    class mylist {
    private:
    std::shared_ptr<mynode<T>> head = nullptr;
    std::shared_ptr<mynode<T>> tail = nullptr;

    public:
    mylist() = default;
    void append(std::shared_ptr<mynode<T>> n);
    void print();
    void merge_sorted(mylist<T>&& l);
    void remove(const std::shared_ptr<mynode<T>>& n);
    void remove(const T& data);
    std::optional<std::shared_ptr<mynode<T>>> find(const T& data);
    };

    template<typename T>
    void mylist<T>::append(std::shared_ptr<mynode<T>> n) {
    if(tail == nullptr) {
    tail = n;
    head = n;
    } else {
    tail->next = n;
    tail = n;
    }
    }

    template<typename T>
    void mylist<T>::print() {
    std::shared_ptr<mynode<T>> n(head);
    while(n) {
    std::cout << (*n).data << ",";
    n = n->next;
    }

    std::cout << '\b' << ' ' << std::endl;
    }

    template<typename T>
    void mylist<T>::merge_sorted(mylist<T>&& l) {
    auto h1 = head;
    auto h2 = l.head;
    std::shared_ptr<mynode<T>> new_tail = nullptr;
    std::shared_ptr<mynode<T>> new_head = nullptr;

    while(h1 && h2) {
    auto x = h1->data;
    auto y = h2->data;
    if (x <= y) {
    auto next = h1->next;
    if(!new_tail) {
    new_head = h1;
    } else {
    new_tail->next = h1;
    }
    new_tail = h1;
    h1->next = nullptr;
    h1 = next;
    } else {
    auto next = h2->next;
    if(!new_tail) {
    new_head = h2;
    } else {
    new_tail->next = h2;
    }
    new_tail = h2;
    h2->next = nullptr;
    h2 = next;
    }
    }
    if(!h1) {
    new_tail->next = h2;
    } else {
    new_tail->next = h1;
    }
    }

    template<typename T>
    void mylist<T>::remove(const std::shared_ptr<mynode<T>>& n) {
    std::shared_ptr<mynode<T>> v(head);
    std::shared_ptr<mynode<T>> prev = nullptr;
    while(v) {
    if(v == n) {
    if(prev) {
    prev->next = n->next;
    } else {
    head = n->next;
    }
    }
    prev = v;
    v = v->next;
    }
    }

    template<typename T>
    void mylist<T>::remove(const T& data) {
    auto idx = find(data);
    if(idx.has_value()) {
    auto node = idx.value();
    remove(node);
    }
    }

    template<typename T>
    std::optional<std::shared_ptr<mynode<T>>> mylist<T>::find(const T& data) {
    std::shared_ptr<mynode<T>> v(head);
    while(v) {
    if(v->data == data) {
    return v;
    }
    v = v->next;
    }
    return {};
    }

    int main(int argc, char** argv) {
    mylist<int> l1, l2;
    l1.append(std::make_shared<mynode<int>>(1));
    l1.append(std::make_shared<mynode<int>>(5));
    l1.append(std::make_shared<mynode<int>>(7));
    l2.append(std::make_shared<mynode<int>>(2));
    l2.append(std::make_shared<mynode<int>>(4));
    l2.append(std::make_shared<mynode<int>>(8));
    l2.append(std::make_shared<mynode<int>>(9));
    l2.append(std::make_shared<mynode<int>>(10));
    l1.print();
    l2.print();
    l2.remove(8);
    l2.print();
    l1.merge_sorted(std::move(l2));
    l1.print();

    return 0;
    }
    20 changes: 20 additions & 0 deletions meson.build
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,20 @@
    project(
    'two_numbers', 'cpp', 'c',
    version: '0.1',
    default_options : [
    'cpp_std=c++17',
    'buildtype=debug'
    ],
    )

    cpp_args = []
    cpp_link_args = []

    thread_dep = dependency('threads')

    progs = [ ['list', ['list.cc']],
    ]

    foreach p: progs
    exe = executable(p[0], p[1], dependencies: [thread_dep])
    endforeach