XOR linked list - wstawianie kilku elementów na raz

Piszę właśnie implementację 'XOR linked list' (na podstawie http://en.wikipedia.org/wiki/Xor_linked_list) i mam taki problem: chciałem dodać możliwość wstawienia do listy całego bloku na raz (by nie pieprzyć się ze wstawianiem po jednym - zawsze byłby to dodatkowy narzut ;)) O ile udało mi się to łatwo ze wstawianiem w środek listy, o tyle jak wstawiam na początek czy na koniec to mi się program wywala :/ Tak wygląda wyrwany z kontekstu, za to kompilowalny kod który mi nie działa:

#include <iostream>

typedef int pointer_type;
template<typename T>
inline T XOR(T a, T b) {return (T)((pointer_type)a^(pointer_type)b);}

class Node
{
 public:
    Node(Node* prev, Node* next, const int& v):
        ptr(XOR(prev, next)),
        val(v)
    {}
    
    Node* ptr;
    int val;

 protected:
    Node(Node* n, const int& v): ptr(n), val(v) {}
};

class BoundingNode : public Node
{
 public:
    BoundingNode(Node* nd, const int& vl): Node(nd, vl) {}
};

typedef long long int size_type;

class iterator
{
 public:
    iterator(Node* n1, Node* n2, bool rev = false): prev(n1), curr(n2), reverse(rev) {}
    
    int& operator*() {return curr->val;}
    int* operator->() {return &(curr->val);}
    
    // a^b = b^a
    // curr->getVal() = prev^next
    // next = curr->getVal()^prev
    iterator operator++()
    {
        Node* next = XOR(curr->ptr, prev);
        prev = curr;
        curr = next;
        return *this;
    }
    
    iterator operator++(int)
    {
        iterator toReturn = *this;
        
        Node* next = XOR(curr->ptr, prev);
        prev = curr;
        curr = next;
        
        return toReturn;
    }
    
    iterator operator--()
    {
        Node* pprev = XOR(prev->ptr, curr);
        curr = prev;
        prev = pprev;
    }
    
    iterator operator--(int)
    {
        iterator toReturn = *this;
        
        Node* pprev = XOR(prev->ptr, curr);
        curr = prev;
        prev = pprev;
        
        return toReturn;
    }

    iterator add(size_type i) const // not to be used in normal situations
    {
        iterator it = *this;
        for(; i>0; i--) ++it;
        return it;
    }
        
    bool operator==(const ::iterator& it) const {return (it.curr == curr) && (it.reverse == reverse);}
    bool operator!=(const ::iterator& it) const {return (it.curr != curr);}

    const bool reverse;
    Node* curr;
    Node* prev;
};
 
int main(int argc, char *argv[])
{
    Node* head = new BoundingNode(0, 0);
    Node* tail = new BoundingNode(0, 0);
    
    Node* one = new Node(0, 0, 666);
    Node* two = new Node(0, 0, 42);
    
    head->ptr = one;
    tail->ptr = two;
    
    one->ptr = XOR(head, two);
    two->ptr = XOR(one, tail);
    
    const int howMany = 3;
    Node** nodes = new Node*[howMany];
    
    nodes[0] = new Node(0, 0, 232);
    nodes[1] = new Node(0, 0, 58);
    nodes[2] = new Node(0, 0, 29);
    
    Node* where = head;
    
    for(size_type i = 1; i < (howMany-1); i++)
        nodes[i]->ptr = XOR(nodes[i-1], nodes[i+1]);
    
    Node* prev = where->ptr;
    Node* pprev = XOR(prev->ptr, where);
    
    nodes[0]->ptr = XOR(where, nodes[1]);
    nodes[howMany-1]->ptr = XOR(prev, nodes[howMany-2]);
    
    prev->ptr = XOR(pprev, nodes[howMany-1]);
    where->ptr = nodes[0];
    
    iterator it(head, one);
    std::cout << *(it++) << std::endl;
    std::cout << *(it++) << std::endl;
    std::cout << *(it++) << std::endl;
    std::cout << *(it++) << std::endl;
    std::cout << *(it++) << std::endl;
    
    delete head, one, two, tail;
    delete nodes[0], nodes[1], nodes[2];
    delete[] nodes;
    
    std::cout << std::endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

W programie funkcja do wstawiania wygląda tak (nodes musi być wstępnie wypełnione wskaźnikami na nody z danymi do wstawienia):

    void pushBlock(Node* where, size_type howMany, Node** nodes)
    {
        itsSize += howMany;
        for(size_type i = 1; i < (howMany-1); i++)
            nodes[i]->ptr = XOR(nodes[i-1], nodes[i+1]);
        
        Node* prev = where->ptr;
        Node* pprev = XOR(prev->ptr, where);
        
        nodes[0]->ptr = XOR(where, nodes[1]);
        nodes[howMany-1]->ptr = XOR(prev, nodes[howMany-2]);
        
        prev->ptr = XOR(pprev, nodes[howMany-1]);
        where->ptr = nodes[0];// BoundingNode przechowuje bezpośrednio wskaźniki
    }

Za to ta funkcja działa (wywoływana z tego samego kontekstu):

    void insertBlock(const iterator& pos, size_type howMany, Node** nodes)
    {
        itsSize += howMany;
        for(size_type i = 1; i < (howMany-1); i++)
            nodes[i]->ptr = XOR(nodes[i-1], nodes[i+1]);
        
        Node* prev = pos.curr;
        Node* next = (pos.add(1)).curr;
        
        Node* nnext = XOR(next->ptr, prev);
        Node* pprev = XOR(prev->ptr, next);
        
        nodes[0]->ptr = XOR(prev, nodes[1]);
        nodes[howMany-1]->ptr = XOR(next, nodes[howMany-2]);
        
        prev->ptr = XOR(pprev, nodes[0]);
        next->ptr = XOR(nnext, nodes[howMany-1]);
    }

Jakby co, obie funkcje wywołuję tylko z tej (są to funkcje prywatne więc nie ma mowy by były wywołane w inny sposób):

    template<typename InputIterator>
    void insert(iterator pos, InputIterator start, InputIterator end)
    {
        --pos;
        IterLength<typename std::iterator_traits<InputIterator>::iterator_category> length;
        size_type num = length(start, end);
            
        Node** nodes = new Node*[num];
        
        for(size_type i = 0; start != end; start++, i++) nodes[i] = new Node(0, 0, *start);
        
        if(pos == rend()) pushBlock(tail, num, nodes);
        else if(pos == this->end()) pushBlock(head, num, nodes);
            else insertBlock(pos, num, nodes);
        
        delete[] nodes;
    }

Co robię źle? Rozrysowałem to sobie na kartce, i niby wszystko ok. Domyślam się, że to musi być jakiś głupi błąd, ale siedzę nad tym od jakiegoś czasu i nie mogę nic znaleźć :/

ot: jesli to co piszesz nie jest wymogiem odgórnym, to proponuje calosc potraktowac jako 'proof of concept', bo w rzeczywistosci zwykla podwojnie wiazana lista jest wygodniejsza :)

flabra napisał(a)

ot: jesli to co piszesz nie jest wymogiem odgórnym, to proponuje calosc potraktowac jako 'proof of concept', bo w rzeczywistosci zwykla podwojnie wiazana lista jest wygodniejsza :)

Piszę dla jaj bardziej ;), chociaż prawdę mówiąc jak sprawdziłem z zewnątrz operuje się równie łatwo jak na zwykłej liście, tylko wewnętrzna implementacja jest bardziej zakręcona. W dodatku, przez to że jak dla mnie głównym zastosowaniem wszelkiej maści kontenerów jest przechowywanie wskaźników na tworzone na stercie elementy, lista podwójnie wiązana zużywa dodatkowo 2x tyle pamięci niż przechowuje. A do list zwiniętych nie mam głowy, ze stałą wielkością 'komórek' to byłby horror przy wstawianiu elementów (przesuwanie wszystkich elementów listy, jak w tablicy :/) a przy zmiennej to byłby jeszcze większy horror przy iteracji ;)

EDIT: Ok, problem rozwiązany, błąd był jednak w publicznej metodzie insert ;) Wystarczyło zmienić końcówkę na:

        if(pos == begin()) {pushBlock(head, num, nodes); goto after;}
        else if(pos == end()) {pushBlock(head, num, nodes); goto after;}
        insertBlock(pos, num, nodes);
        
        after: