forward_list.hpp

Go to the documentation of this file.

/*
MIT License
 
Copyright (c) 2025 Build X  From  Scratch
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
#include <functional>
#include <iostream>
#include <initializer_list>
#include <type_traits>
#include <ranges>
#include <iterator>
#include <unordered_set>
#include <cstddef>
#include <limits>
#include <concepts>
#include <utility>
#ifndef __forwardList
#define __forwardList
template <typename It>
concept my_input_iterator = requires(It it){
    *it; //bisa di deferencing
    ++it; //bisa post increment
    it++; //bisa pre increment
};
template <typename T,typename Allocator = std::allocator<T>>
class forward_lists{
    private:
        struct Node{
            T data;
            Node* next;
        };
        //allocator khusus node
        using node_allocator_type = 
        typename std::allocator_traits<Allocator>::template rebind_alloc<Node>;
        using node_traits = std::allocator_traits<node_allocator_type>;
        node_allocator_type alloc; //instance allocator
        Node* head  = nullptr; //head pointer
        Node* tail; //tail pointer
        int size; //banyak element pada linked list
    private:
        Node* _create_node(const T& value){
            Node* n = node_traits::allocate(alloc,1); //alokasi memory mentah sebanyak 1 blok memory untuk node(allocate)
            try{
                node_traits::construct(alloc,std::addressof(n->data),value); //membangun object di memory(construct)
            }catch(...){ //catch all handler
                node_traits::deallocate(alloc,n,1); //dealokasi
            }
            //set next menjadi null
            n->next = nullptr;
            //kembalikan node
            return n;
        }
        void _destroy_node(Node* n)noexcept{
                node_traits::destroy(alloc,std::addressof(n->data));
                node_traits::deallocate(alloc,n,1);
        }
    public:
    //default constructor allocator 
        explicit forward_lists():
            alloc(node_allocator_type()),head(_create_node(T{})),tail(head),size(0){}
        //default constructor   
        forward_lists(const Allocator& a):
        alloc(a),head(_create_node(T{})),tail(head),size(0){}

        template <typename It>  
        requires my_input_iterator<It>
        forward_lists(It begin,It end){
            Node* new_node = _create_node(T{}); //create dummy node
            head = new_node;
            size = 0;
            tail = head;
            Node** curr = &head->next; //curr menunjuk head->next
            while(begin != end){
                Node* n_node = _create_node(*begin);
                *curr = n_node; //isi node dengan deferencing begin
                tail = *curr;
                curr = &((*curr)->next); //curr = curr->next
                ++size; //increment size
                ++begin; //increment iterator
            }
        }

        forward_lists(std::initializer_list<T> arr): head(nullptr){
            Node* new_node = _create_node(T{});
            head = new_node;
            tail = head;
            size = 0;
            Node** curr = &head->next; //store alamat memory head ke curr
            for(const T& it: arr){
                Node* n_node = _create_node(it);
                *curr = n_node; //curr menunjuk n_noed
                tail = *curr; //tail ikut menunjuk curr
                curr = &((*curr)->next); //store alamat curr->next
               //curr selalu menunjuk ke posisi kosong
               size++;
            }   
        }
        //copy constructor
        forward_lists(const forward_lists& others){
            if(others.head->next == nullptr){
                head = nullptr;
                return;
            }
            head = _create_node(T{}); //isi dummy 
            head->next = _create_node(others.head->next->data); //inialisasi data pertama
            Node* curr = head->next; //pointer penggerak
            Node* temp = others.head->next->next; //mulai dari node ke 2
            while(temp != nullptr){
                curr->next = _create_node(temp->data);
                curr = curr->next;
                temp = temp->next;
            }
        }
        //copy assignment
        forward_lists& operator=(const forward_lists& others){
            if(this == &others){
                return *this;
            }
            clear();
            if(!others.head->next){ //nullptr
                head = nullptr;
                return *this;
            }
            head = _create_node(T{}); //isi dummy 
            head->next = _create_node(others.head->next->data);//inialisasi data pertama
            Node* curr = head->next; //pointer penggerak
            Node* temp = others.head->next->next; //mulai dari node ke 2
            while(temp != nullptr){
                curr->next = _create_node(temp->data);
                curr = curr->next;
                temp = temp->next;
            }
            return *this;
        }

        forward_lists(forward_lists&& others) noexcept: head(_create_node(T{})),tail(head),size(0){
            head->next = others.head->next;
            tail = others.tail == head ? head: others.tail; //ternery operator,if you dont understand please read documentation 
            size = others.size;
 
            //kosongkan object lama
            others.head->next = nullptr; 
            others.tail = others.head;
            others.size = 0;
        }

        forward_lists& operator=(forward_lists&& others)noexcept{
            if(this != &others){
                clear();
                head->next = others.head->next;
                tail = others.tail == head ? head: others.tail; //ternery operator,if you dont understand please read documentation 
                size = others.size;
 
                //kosongkan object lama
                others.head->next = nullptr; 
                others.tail = others.head;
                others.size = 0;
            }
            return *this;
        }

        ~forward_lists(){
            clear(); //panggil method clear
        }
    private:
        class Iterator{
            private:
                Node* node;
            public:
                using iterator_category = std::forward_iterator_tag;
                using value_type        = T;
                using difference_type   = std::ptrdiff_t;
                using pointer           = T*;
                using reference         = T&;
                Iterator(Node* n){
                    this->node = n;
                }   
            friend std::ostream& operator<<(std::ostream& os,const Iterator& it){
                if(it.node){
                    os << it.node->data;
                }else{
                    os << "no output";
                }
                return os;
                }
                T& operator*(){
                    return node->data;
                }
                reference operator*()const{
                    return node->data;
                }
                pointer operator->()const{
                    return &(node->data);
                }
                Iterator& operator++(){ //harus mengembalikan reference ke object saat ini
                    if(node) node = node->next;
                    return *this;
                }
                Iterator& operator->(){
                    return node;
                }
                Iterator operator++(int){ //harus mengambalikan salin bukan referensi
                    Iterator temp = *this; //simpan keadaan sebelum di geser
                    ++(*this);//geser
                    return temp; //kembalikan keadaan sebelum di geser
                }
                bool operator!=(const Iterator& others)const{
                    return node != others.node;
                }
                bool operator==(const Iterator& others)const{
                    return node == others.node;
                }
                Node* get_raw()const{
                    return node;
                }
        };
    public: //inialisasi Iterator
        Iterator before_begin(){
            return Iterator(head);
        }

        Iterator begin(){
            return Iterator(head->next);
        }

        Iterator end(){
            return Iterator(nullptr);
        }
        Iterator cbegin()const{//constant iterator
            return Iterator(head->next);
        }
        Iterator cend()const{ //constant iterator
            return Iterator(nullptr);
        }
        Iterator cbefore_begin()const{ //constant iterator
            return Iterator(head);
        }
    public: //getter
        T front(){
            return head->next->data;
        }

        int get_size(){
            return this->size;
        }

        bool is_empty(){
            if(size == 0){
                return true;
            }
            return false;
        }

        std::size_t max_size()const noexcept{
            return std::numeric_limits<T>::max() / sizeof(Node);
        }   
        T back()const noexcept{
            return this->tail->data;
        }
        Allocator get_allocator()const noexcept{
            return alloc;
        }
        bool check_cycle()const noexcept{
            Node* slow = head->next;
            Node* fast = head->next;
            while(slow && fast && fast->next != nullptr){
                slow = slow->next;
                fast = fast->next->next;
                if(fast == slow){
                    return true;
                }
            }
            return false;
        }
        T get_middle()const noexcept{
            Node* slow = head->next;
            Node* fast = head->next;
            while(slow && fast && fast->next){
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow->data;
        }
    public:
        void push_front(T&& data){ //forwadding reference
            if(tail == head){
                Node* new_node = _create_node(data);
                head->next = tail = new_node;
                size++;
            }else{
                Node* new_node  = _create_node(data);
                new_node->next = head->next;
                head->next = new_node;
                size++;
            }
        }
        void push_front(const T& data){
            if(tail == head){
                Node* new_node = _create_node(data);
                head->next = tail = new_node;
                size++;
            }else{
                Node* new_node  = _create_node(data);
                new_node->next = head->next;
                head->next = new_node;
                size++;
            }
            
        }

        void pop_front(){   
            if(tail == head){
                return;
            }
            Node* temp = head->next;
            head->next = temp->next;
            if(temp == tail){
                tail = head;
            }
            _destroy_node(temp);
            size--;
            
        }
    public:
        void push_back(const T& value){
            if(!head->next){
                head->next = tail = _create_node(value);
                size++;
            }else{
                tail->next = _create_node(value);
                tail = tail->next;
                size++;
            }
        }
        void push_back(T&& value){
            if(!head->next){
                head->next = tail = _create_node(value);
                size++;
            }else{
                tail->next = _create_node(value);
                tail = tail->next;
                size++;
            }
        }

        void pop_back(){
            if(!head->next){//is_empty
                return;
            }else if(!head->next->next){
                Node* temp = tail;
                tail = head;
                tail->next = nullptr;
                size--;
                _destroy_node(temp);
            }else{
                Node* curr = head->next;
                while(curr->next->next != nullptr){
                    curr = curr->next;
                }
                Node* temp = curr->next;
                tail = curr;
                tail->next = nullptr;
                size--;
                _destroy_node(temp);
            }
        }
    public:
        void insert_after(Iterator iter_position,T&& val){
            Node* curr = iter_position.get_raw();
            Node* new_node = _create_node(val);
            new_node->next = curr->next;
            curr->next  = new_node;
            if(curr == tail){ //jika posisi curr sama dengan tail
                tail = new_node;
            }
            size++; //update size
        }
        void insert_after(Iterator iter_position,const T& val){
            Node* curr = iter_position.get_raw();
            Node* new_node = _create_node(val);
            new_node->next = curr->next;
            curr->next  = new_node;
            if(curr == tail){
                tail = new_node; //update tail
            }
            size++; //increment size
        }      
        void insert_after(Iterator Iterator_position,int n,T&& val){
            Node* curr = Iterator_position.get_raw();
            if(n < 1){
                return;
            }
            if(n == 1){
                Node* new_node = _create_node(val);
                new_node->next = curr->next;
                curr->next = new_node;
                if(curr == tail){
                    tail = new_node;
                }
            }else{
                Node* new_node = _create_node(val);
                Node* n_tail = new_node;
                for(int i = 0;i < n - 1;i++){
                    Node* baru = _create_node(val);
                    n_tail->next = baru;
                    n_tail = baru;
                }
                n_tail->next = curr->next; 
                curr->next = new_node;
                if(curr == tail){
                    tail = n_tail; //karena n_tail menunju node terakhir saat insertion
                }
            }
        }
        void insert_after(Iterator Iterator_position,int n,const T& val){
            Node* curr = Iterator_position.get_raw();
            if(n < 1){
                return;
            }
            if(n == 1){
                Node* new_node = _create_node(val);
                new_node->next = curr->next;
                curr->next = new_node;
                if(curr == tail){
                    tail = new_node;
                }
            }else{
                Node* new_node = _create_node(val);
                Node* n_tail = new_node;
                for(int i = 0;i < n - 1;i++){
                    Node* baru = _create_node(val);
                    n_tail->next = baru;
                    n_tail = baru;
                }
                n_tail->next = curr->next; 
                curr->next = new_node;
                if(curr == tail){
                    tail = n_tail;
                }
            }
        }
        template<std::input_iterator It>
        requires (!std::same_as<It,Iterator>)
        void insert_after(Iterator iter_position,It itr1,It itr2){
            Node* curr = iter_position.get_raw();
            Node* new_node = _create_node(*itr1);
            size++;
            Node* n_tail = new_node;
            ++itr1;
            while(itr1 != itr2){
                Node* n_node = _create_node(*itr1); //deferencing itr1
                ++itr1; //increment iterator itr1
                n_tail->next = n_node;
                n_tail = n_node;
                size++;
            }
            n_tail->next = curr->next;
            curr->next = new_node;
            if(curr == tail){
                tail = n_tail;
            }
        }
        void insert_after(const Iterator iter_position,Iterator listBegin,const Iterator listEnd){
            Node* curr = iter_position.get_raw();
            Node* new_head = listBegin.get_raw();
            Node* end = listEnd.get_raw();
            Node* new_node = _create_node(new_head->data);
            size++;
            Node* n_tail = new_node;
            new_head = new_head->next;   
            while(new_head != end){
                Node* n_node = _create_node(new_head->data);
                n_tail->next = n_node;
                n_tail = n_node;
                new_head = new_head->next; 
                size++;
            }
            n_tail->next = curr->next;
            curr->next = new_node;
            if(curr == tail){
                tail = new_node;
            }
        }
    public://overload erase after
        void erase_after(const Iterator iter_position){
            Node* curr = iter_position.get_raw();
            if(!curr->next){//tidak ada node setelah posisi iterator 
                return; //return
            }
            if(curr->next == tail){ //jika node selanjutnya tail
                Node* temp = curr->next;
                tail = curr; // tail sekarang curr 
                _destroy_node(temp);
                size--; 
            }else{ //
                Node* temp = curr->next;
                curr->next = temp->next;
                size--;
                _destroy_node(temp);
            }
        }
        void erase_after(const Iterator pos_begin,const Iterator pos_end){
            Node* first = pos_begin.get_raw();
            Node* fst = pos_begin.get_raw();
            Node* curr = first->next;
            Node* last = pos_end.get_raw();
         //   curr = curr->next;
            while(curr != last){
                if(curr == tail){
                    Node* temp = curr;
                    tail = fst;
                    curr = curr->next;
                    _destroy_node(temp);
                    size--;
                }else{
                    Node* temp = curr;
                    curr = curr->next;
                    _destroy_node(temp);
                    size--;
                }
            }
            first->next = last;
            if(last == nullptr){
                tail = first;
            }
        }
 
    public: //reverse method
        void reverse(){
            Node* prev = nullptr;
            Node* curr = head->next;    
            while(curr != nullptr){
                Node* next = curr->next;
                curr->next = next;
                prev = curr;
                curr = next;
            }
            head->next = prev;
        }
    public:
        void assign(std::size_t n,const T& value){
            clear();
            Node* curr = head;
            for(std::size_t i = 0;i < n;i++){
                curr->next = _create_node(value);
                curr = curr->next;
                size++;
            }
        }
        void assign(std::size_t n,T&& value){
            clear();
            Node* curr = head;
            for(std::size_t i = 0;i < n;i++){
                curr->next = _create_node(value);
                curr = curr->next;
                size++;
            }
        }
        void assign(std::initializer_list<T> arr){
            clear();
            head = _create_node(T{});
            head->next = nullptr;
            Node** curr = &head->next;
            //size++;
            for(const T& value: arr){
                *curr = _create_node(value); //curr = new Node
                curr = &((*curr)->next); //curr = curr->next
                size++;
            }   
        }   
        template<typename It>
        requires my_input_iterator<It>
        void assign(It itr1,It itr2){
            clear();
            Node* curr = head;
            while(itr1 != itr2){
                curr->next = _create_node(*itr1);//deferencing itr1
                curr = curr->next;
                size++;
                ++itr1;
            }
        }
    public:  //slice after
        void splice_after(const Iterator pos,forward_lists& others,const Iterator It){
            Node* src = It.get_raw();
            Node* moved = src->next;
            src->next = moved->next; //src->next = src->next->next
            
            Node* dest = pos.get_raw();
            moved->next = dest->next; //hubungkan ke list tujuan
            dest->next = moved;
            others.size--;
            size++;
        }
        void splice_after(const Iterator pos,forward_lists&& others,const Iterator It){
            Node* src = It.get_raw();
            Node* moved = src->next;
            src->next = moved->next; //src->next = src->next->next
            
            Node* dest = pos.get_raw();
            moved->next = dest->next; //hubungkan ke list tujuan
            dest->next = moved;
            others.size--;
            size++;
        }
        void splice_after(const Iterator pos,forward_lists& others){
            if(this == &others){
                return;
            }
            Node* src = pos.get_raw();//pos object saat ini
            Node* begin = others.head->next ; //begin object lain
            Node* end = others.tail; //end object lain
 
            end->next = src->next;
            src->next = begin;
            //update tail
            if(src == tail){
                tail = end;
            }
            //update size
            size += others.size;
            //kosong object lain
            others.head->next = nullptr; //harus menunjuk nullptr
            others.tail = others.head;//reset tail,tail menunjuk head(dummy node)
            others.size = 0;
        }
        void splice_after(const Iterator pos,forward_lists&& others){ //global reference
            if(this == &others){
                return;
            }
            Node* src = pos.get_raw();//pos object saat ini
            Node* begin = others.head->next ; //begin object lain
            Node* end = others.tail; //end object lain
            end->next = src->next;
            src->next = begin;
            //update tail
            if(src == tail){
                tail = end;
            }
            //update size
            size += others.size;
            //kosong object lain
            others.head->next = nullptr; //harus menunjuk nullptr
            others.tail = others.head;//reset tail,tail menunjuk head(dummy node)
            others.size = 0;
        }
        void splice_after(const Iterator pos,forward_lists& others,const Iterator first,const Iterator last){
            //relingking dari range (first,last)
            Node* curr = pos.get_raw();
            Node* other_begin = first.get_raw()->next;
            Node* other_end = last.get_raw();
            Node* after_node = curr->next; //simpan first this
            if(other_begin == other_end){
                return; //nullptr   
            }
            //update size,update size sebelum di linking
            auto moved = (std::distance(first, last)) - 1;
            size += moved;
            others.size -= moved;
            //simpan last_node
            Node* last_node = other_begin;
            //cari node sebelum lasr
            while(last_node->next != other_end){
                last_node = last_node->next;
                //loop sampai last_node tepat menunjuk sebelum pos last
            }
            //sembungkan ke list tujuan
            last_node->next = curr->next;
            curr->next = other_begin;
            //lingking curr->next with to others_begin  
 
            //update tail
            if(after_node == tail || other_end == nullptr){
                tail = last_node;
            }
            //relingking object lain
            first.get_raw()->next = other_end;
            if(other_end == nullptr){
                others.tail = first.get_raw();
            }
 
        }
        void splice_after(const Iterator pos,forward_lists&& others,const Iterator first,const Iterator last){
            //relingking dari range (first,last)
            Node* curr = pos.get_raw();
            Node* other_begin = first.get_raw()->next;
            Node* other_end = last.get_raw();
            Node* after_node = curr->next;
            if(other_begin == other_end){
                return; //nullptr   
            }
            //update size,update size sebelum di linking
            auto moved = std::distance(std::next(first),(last));
            size += moved;
            Node* last_node = other_begin;
            others.size -= moved;
            //cari node sebelum lasr
            while(last_node->next != other_end){
                last_node = last_node->next;
                //loop sampai last_node tepat menunjuk sebelum pos last
            }
            //sembungkan ke list tujuan
            last_node->next = curr->next;
            curr->next = other_begin;
            //lingking curr->next with to others_begin  
 
            //update tail
            Node* new_begin = first.get_raw();
            if(after_node == tail){
                tail = last_node;
            }
            //relingking object lain
            first.get_raw()->next = other_end;
            if(other_end == nullptr){
                others.tail = first.get_raw();
            }
 
        }
    public:
        void swap(forward_lists& others)noexcept{
            if(this == &others){//jika this sama dengan object lain
                return;
            }
            //swap head;
            Node* tempHead = head;
            head = others.head;
            others.head = tempHead; 
            //swap tail
            Node* tempTail = tail;
            tail = others.tail;
            others.tail = tempTail;
            //swap size
            int tempSize = size;
            size = others.size;
            others.size = tempSize;
        }
        void swap(forward_lists&& others)noexcept{
            if(this == &others){//jika this sama dengan object lain
                return;
            }
            //swap head;
            Node* tempHead = head;
            head = others.head;
            others.head = tempHead;
            //swap tail
            Node* tempTail = tail;
            tail = others.tail;
            others.tail = tempTail;
            //swap size
            int tempSize = size;
            size = others.size;
            others.size = tempSize;
        }
    private: //helper sort
        Node* merge(Node* left, Node* right) {
            if (!left) return right;
            if (!right) return left;
 
            if (left->data <= right->data) {
                left->next = merge(left->next, right);
                return left;
            } else {
                right->next = merge(left, right->next);
                return right;
            }
        }
        // overload with parameter
        template<typename compare = std::less<T>>
        Node* merge(Node* left, Node* right,compare comp) {
            if (!left) return right;
            if (!right) return left;
 
            if (comp(left->data, right->data)) {
                left->next = merge(left->next, right,comp);
                return left;
            } else {
                right->next = merge(left, right->next,comp);
                return right;
            }
        }
        Node* getMiddle(Node* head){
            //mulai dari note pertama
            Node* slow = head;
            Node* fast = head->next;
            while(fast && fast->next){
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
        Node* helper(Node* head){
            if(!head || !head->next){
                return head;
            }
            Node* middle = getMiddle(head);
            Node* nextMiddle = middle->next;
            //putushkan hubungan list
            middle->next = nullptr;
            Node* left = helper(head);
            Node* right = helper(nextMiddle);
            return merge(left,right);
        }
        template <typename compare>
        Node* helper(Node* head,compare comp){
            if(!head || !head->next){
                return head;
            }
            Node* middle = getMiddle(head);
            Node* nextMiddle = middle->next;
            //putushkan hubungan list
            middle->next = nullptr;
            Node* left = helper(head,comp);
            Node* right = helper(nextMiddle,comp);
            return merge(left,right,comp);
        }
    public:
        void sort(){
            head->next = helper(head->next);
            Node* curr = head;
            while(curr && curr->next){
                curr = curr->next;
            }
            tail = curr;
        }
        template <typename Compare = std::less<T>>
        void sort(Compare comp = Compare{}) {
            head->next = helper(head->next, comp);
 
            // update tail sekali
            Node* curr = head;
            while (curr && curr->next) {
                curr = curr->next;
            }
            tail = curr;
        }
    public:
        void merge(forward_lists& others){
            if(this == &others){
                return;
            }
            Node dummy(T{});
            Node* temp = &dummy;
            temp->next = nullptr;
            Node* curr = head->next;
            Node* pos = others.head->next;
            while(curr && pos){
                if(curr->data <= pos->data){
                    temp->next = curr;
                    curr = curr->next;
                }else{
                    temp->next = pos;
                    pos = pos->next;
                    // temp = temp->next;
                }
                temp = temp->next;
            }
            //update tail
            if(curr != nullptr){
                temp->next = curr;
                // tail = this->tail;
            }else if(pos != nullptr){
                temp->next = pos;
                tail = others.tail;
            }else{
                tail = temp;
            }
            //update size
            size += others.size;
            others.size = 0;
            //kosongkan lama
            others.head->next = nullptr;
            others.tail = head;
            //update head
            head->next = dummy.next;
        }
        void merge(forward_lists&& others){
            if(this == &others){
                return;
            }
            Node dummy(T{});
            Node* temp = &dummy;
            temp->next = nullptr;
            Node* curr = head->next;
            Node* pos = others.head->next;
            while(curr && pos){
                if(curr->data <= pos->data){
                    temp->next = curr;
                    curr = curr->next;
                }else{
                    temp->next = pos;
                    pos = pos->next;
                    // temp = temp->next;
                }
                temp = temp->next;
            }
            //update tail
            if(curr != nullptr){
                temp->next = curr;
                // tail = this->tail;
            }else if(pos != nullptr){
                temp->next = pos;
                tail = others.tail;
            }else{
                tail = temp;
            }
            //update size
            size += others.size;
            others.size = 0;
            //kosongkan lama
            others.head->next = nullptr;
            others.tail = head;
            //update head
            head->next = dummy.next;
        }    
        template <typename compare = std::less<T>>
        void merge(forward_lists& others,compare comp = compare{}){
            if(this == &others){
                return;
            }
            Node dummy(T{});
            Node* temp = &dummy;
            temp->next = nullptr;
            Node* curr = head->next;
            Node* pos = others.head->next;
            while(curr && pos){
                if(comp(curr->data, pos->data)){
                    temp->next = curr;
                    curr = curr->next;
                }else{
                    temp->next = pos;
                    pos = pos->next;
                    // temp = temp->next;
                }
                temp = temp->next;
            }
            //update tail
            if(curr != nullptr){
                temp->next = curr;
                // tail = this->tail;
            }else if(pos != nullptr){
                temp->next = pos;
                tail = others.tail;
            }else{
                tail = temp;
            }
            //update size
            size += others.size;
            others.size = 0;
            //kosongkan lama
            others.head->next = nullptr;
            others.tail = head;
            //update head
            head->next = dummy.next;
        }
        template <typename compare = std::less<T>>
        void merge(forward_lists&& others,compare comp = compare{}){
            if(this == &others){
                return;
            }
            Node dummy(T{});
            Node* temp = &dummy;
            temp->next = nullptr;
            Node* curr = head->next;
            Node* pos = others.head->next;
            while(curr && pos){
                if(comp(curr->data, pos->data)){
                    temp->next = curr;
                    curr = curr->next;
                }else{
                    temp->next = pos;
                    pos = pos->next;
                    // temp = temp->next;
                }
                temp = temp->next;
            }
            //update tail
            if(curr != nullptr){
                temp->next = curr;
                // tail = this->tail;
            }else if(pos != nullptr){
                temp->next = pos;
                tail = others.tail;
            }else{
                tail = temp;
            }
            //update size
            size += others.size;
            others.size = 0;
            //kosongkan lama
            others.head->next = nullptr;
            others.tail = head;
            //update head
            head->next = dummy.next;
        }
    public:
        void merge_sort(forward_lists& others){
            if(this == &others){ 
                return;
            }
            if(head->next->data <= others.head->next->data){
                //sambung mulai tail dengan head.tail
                tail->next = others.head->next;
                //update tail
                tail = others.tail;
                //update size
                size += others.size;
                others.head->next = nullptr;
                others.tail = others.head;
            }else{
                others.tail->next = head->next;
                //update head pada this
                head->next = others.head->next;
                //update size
                size += others.size;
            }
 
        }
        void merge_sort(forward_lists&& others){
            if(this == &others){
                return;
            }
            if(head->next->data <= others.head->next->data){
                //sambung tail
                tail->next = others->head->next;
                //update tail
                tail = others.tail;
                //update size
                size += others.size;
            }else{
                //sambung others tail ke node setelah dummy
                others.tail->next = head->next;
                //sambung node setelah du
                head->next = others.head->next;
                //update size
                size += others.size;
            }
        }
    public:
        void resize(std::size_t count){
            if(count == size){
                return;
            }else if(count > size){
                while(size < count){
                    push_back(0);
                    size++;
                }
            }else{
                while(size > count){
                    pop_back();
                    size--;
                }
            }   
        }
        void resize(std::size_t count,const T& value){
            if(count == size){
                return;
            }else if(count > size){
                while(size < count){
                    push_back(value);
                    size++;
                }
            }else{
                while(size > count){
                    pop_back();
                    size--;
                }
            }
 
        }
    public:
    //time complexity O(n),Space Complexity O(n)
        void uniqe_all(){
            std::unordered_set<T>seen;
            Node* curr = head;
            Node* fast = head->next;
            if(!fast){
                return;//jika list kosong
            }
            while(fast != nullptr){
                if(seen.find(fast->data) != seen.end()){
                    Node* temp = fast;
                    Node* _next = fast->next;
                    //relinking curr dengan fast->next
                    curr->next =  _next;
                    _destroy_node(temp);
                    if(_next != nullptr){
                        fast = _next;
                        // curr = curr->next;//melompat 2 kali
                    }else{
                        fast = nullptr;
                    }
                }else{
                    seen.insert(fast->data);
                    curr = curr->next; //maju sekali jika tidak ada di set
                    fast = fast->next;
                }
            }
        }
        void uniqe(){
            Node* curr = head;
            Node* fast = head->next;
            if(fast == nullptr){
                return; 
            }
            while(fast && fast->next){
                if(fast->data == fast->next->data){
                    Node* temp = fast;
                    Node* _next = fast->next;
                    curr->next = _next;
                    _destroy_node(temp);
                    fast = _next;
                }else{
                    curr = curr->next;
                    fast = fast->next;
                }
            }
        }
    public:
        template<std::ranges::input_range R>
        void assign_range(R&& rg){
            clear();
            size = 0;
            Node* curr = head;
            for(auto&& elem: rg){
                if(!curr){
                    size++;
                    curr->next = tail = _create_node(elem);
                }else{
                    Node* new_node = _create_node(elem);
                    curr->next = new_node;
                    curr = curr->next; //majukan curr
                    tail = curr; //tail menunjuk currr
                    size++;
                }
            }
        }
        // template<typename T>
        void assign_range(std::initializer_list<T> arr){
            clear();
            size = 0;
            Node* curr = head;
            for(const T& x: arr){
                if(!curr){
                    curr->next = tail = _create_node(x);
                    size++;
                }else{
                    curr->next = _create_node(x);
                    curr = curr->next;
                    tail = curr;
                    size++;
                }
            }
        }
    public:
        void remove(const T& value){
            if(!head->next){ //list is empty
                return;
            }
            Node* curr = head;
            while(curr->next != nullptr){
                if(curr->next->data == value){
                    Node* _next = curr->next;
                    if(_next == tail){
                        curr->next = nullptr;
                        tail = curr;
                        tail->next = nullptr;
                    }else{
                        curr->next = _next->next;
                    }
                    size--;
                    _destroy_node(_next);
                }else{
                    curr = curr->next;
                }
            }
            if(!head->next){
                tail = head;    
                size = 0;
            }
        }
    
        void remove(const std::size_t pos){
            if(!head->next){
                return;
            }
            if(pos >= static_cast<std::size_t>(size)){
                return;
            }
 
            //- 1 1 1 2 2 
            Node* prev = head;
            Node* curr = head->next;
            static_assert(std::is_same_v<decltype(curr), Node*>);
            static_assert(std::is_same_v<decltype(tail), Node*>);
 
            for(std::size_t i = 0;i < pos;i++){
                prev = curr;
                curr = curr->next;
            }
            //sekarang curr menunjuk pos
            if(curr == tail){
                head->next = nullptr;
                curr = nullptr;
                tail = head;
            }else{  
                prev->next = curr->next;
            }
            size--;
            _destroy_node(curr);
            if(!head->next){
                tail = head;
                size = 0;
            }
        }  
        std::size_t remove_count(const T& value){
            if(!head->next){ //list is empty
                return 0;
            }
            int cnt = 0;
            Node* curr = head;
            while(curr->next != nullptr){
                if(curr->next->data == value){
                    Node* _next = curr->next;
                    if(_next == tail){
                        curr->next = nullptr;
                        tail = curr;
                        tail->next = nullptr;
                    }else{
                        curr->next = _next->next;
                    }
                    size--;
                    cnt++;
                    _destroy_node(_next);
                }else{
                    curr = curr->next;
                }
            }
            if(!head->next){
                tail = head;    
                size = 0;
            }
            return cnt;
        } 
        template <class UnaryPred>
        requires(std::predicate<UnaryPred&, const T&>)
        void remove_if(UnaryPred p){
            if(!head->next){
                return;
            }
            Node* curr = head->next;
            Node* prev = head;
            while(curr != nullptr){
                if(p(curr->data)){
                    Node* _next = curr->next;
                    // Node* temp = curr;
                    //relink pada next
                    prev->next = _next;
                    if(_next == nullptr){//curr == tail
                        tail = prev;
                    }
                    //majukan curr
                    _destroy_node(curr);
                    size--;
                    curr = _next;
                }else{
                    prev = curr;
                    curr = curr->next;
                }
            }
            if(!head->next){ //jika terhapus semua
                tail = head;
                head->next = nullptr;
                size = 0;
            }
        }
        template <class UnaryPred>
        requires(std::predicate<UnaryPred&,const T&>)
        std::size_t remove_if_count(UnaryPred p){
            if(!head->next){
                return 0;
            }
            std::size_t count = 0;
            Node* curr = head->next;
            Node* prev = head;
            while(curr != nullptr){
                if(p(curr->data)){
                    Node* _next = curr->next;
                    //linking prev
                    prev->next = _next;
                    //check _next;
                    if(_next == nullptr){
                        tail = prev;
                        
                    }
                    _destroy_node(curr);
                    size--;
                    curr = _next;
                    count++;//increment count
                }else{
                    prev = curr;
                    curr = curr->next;
                }
            }
            return count;
        }
    public:
        void print_all(Iterator begin,Iterator end){
            while(begin != end){
                std::cout << *begin << " ";
                ++begin;
            }
            std::cout << std::endl;
        }

    public:
        template <std::ranges::input_range R>
        void insert_range_after(const Iterator& pos,R&& r){
            Node* curr = pos.get_raw();
            if(is_empty()){
                Node* _next = curr->next; //nullptr
                   for(auto&& x: r){
                    curr->next = _create_node(x);
                    curr = curr->next;
                    size++;
                }
                //linking node terakhir r ke _next
                curr->next = _next;
                tail = curr;
            }else{
                Node* _next = curr->next;
                for(auto&& x: r){
                    curr->next = _create_node(x);
                    curr = curr->next;
                    size++;
                }
                //linking node terakhir r ke _next
                curr->next = _next;
            }
        }
    public:
        template<std::ranges::input_range R>
        void prepend_range(R&& r){
            if(is_empty()){
                Node* curr = head;
                Node* _next = head->next; //nullptr
                for(auto&& x: r){
                    curr->next = _create_node(x);
                    curr = curr->next;
                    size++;
                } 
                curr->next = _next;
                tail = curr; 
            }else{
                Node* curr = head;
                Node* _next = head->next;
                for(auto&& x: r){
                    curr->next = _create_node(x);
                    curr = curr->next;
                    size++;
                }
                curr->next = _next; 
            }
        }
    public:
        template <class ... Args>
        void emplace_front(Args&&... args){
            Node* new_node = _create_node(std::forward<Args>(args)...);
            //linking head baru ke head lama
            if(!head->next){
                tail = new_node;
            }
            new_node->next = head->next;
            //update head;
            head->next = new_node;
            //update size;
            size++;
        }
        template <class  ... Args>
        void emplace_after(Iterator pos,Args&&... args){
            Node* curr = pos.get_raw();
            if(!curr){
                return;
            }
            Node* _next = curr->next;
            Node* new_node = _create_node(std::forward<Args>(args)...);
 
            //linking
            new_node->next = _next;
            curr->next = new_node;
            //emplace pada saat list kosong
            if(curr == tail){
                tail = new_node;
            }
            size++;
        }
        template<class... Args>
        void emplace_back(Args&&... args){
            Node* new_node = _create_node(std::forward<Args>(args)...);
            tail->next = new_node;
            tail = new_node;
            //update size
            size++;
        }
    public:
        void clear(){
            Node* curr = head->next;   // mulai dari setelah dummy
            while(curr != nullptr){
                Node* next = curr->next; //simpan curr->next
                _destroy_node(curr);  //hancurkan curr
                curr = next;//curr menunjuk next
            }
            head->next = nullptr;  // dummy menunjuk ke kosong
            tail = head;           // tail kembali ke dummy
            size = 0;
        }
};
#endif