My tree should do like this table below. When you see new element in tree it prints out -1 and puts it on the begining, else count distinct steps when you seen your element last time and write its position. You can get more out of it by looking at the table:
i 0 1 2 3 4 5 6 7 8 9 -> index
ai A B B C A A C B D A -> input
LRU -1 -1 0 -1 2 0 1 2 -1 3 -> output needed
For now my tree does everything as needed perfectly, just as the table tells me, but my tree is not balanced which causes to be extremely slow and I need it to perform faster and to be balanced, I would like to achieve O(1) or O(logn) time, here is my code, hpp class :
--------------------------------------------------------------------------------------
/* $Id: nutri.hpp,v 1.3 2006/04/15 09:33:03 adnanm Exp adnanm $ */
#ifndef __HEADER_FILE_INCLUDED__nutri_hpp__
#define __HEADER_FILE_INCLUDED__nutri_hpp__
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include "interface_LRU.hpp"
class nutri
{
public:
struct tree_node
{
tree_node * mom_ptr;
tree_node * left_child;
tree_node * right_child;
unsigned int nodes_in_left_subtree;
};
tree_node * root;
typedef tree_node * key;
void clear()
{
kill();
reset();
};
void insert_leftmost(tree_node * & moving_node,
tree_node * & local_root)
{
if (local_root == NULL)
{
local_root = moving_node;
local_root->left_child = NULL;
local_root->right_child = NULL;
local_root->nodes_in_left_subtree = 0;
}
else
{
insert_leftmost(moving_node,
local_root->left_child);
local_root->left_child->mom_ptr = local_root;
local_root->nodes_in_left_subtree++;
};
};
key new_item()
{
tree_node * result = new tree_node;
insert_leftmost(result, root);
root->mom_ptr = NULL;
return result;
};
unsigned int position(key & item)
{
unsigned int result = 0;
result = item->nodes_in_left_subtree;
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->right_child == item)
{
result += current->nodes_in_left_subtree + 1;
};
item = current;
};
return result;
};
tree_node * & moms_ptr_to_me(tree_node * me)
{
if (me->mom_ptr == NULL)
{
return root;
}
else if (me->mom_ptr->left_child == me)
{
return me->mom_ptr->left_child;
}
else
{
return me->mom_ptr->right_child;
};
};
tree_node * & rightmost(tree_node * & subtree)
{
if (subtree->right_child == NULL)
{
return subtree;
}
else
{
return rightmost(subtree->right_child);
};
};
void nodeswap(tree_node * & A, tree_node * & B)
{
std::swap(moms_ptr_to_me(A->mom_ptr),
moms_ptr_to_me(B->mom_ptr));
std::swap(A->mom_ptr, B->mom_ptr);
std::swap(A->left_child, B->left_child);
std::swap(A->right_child, B->right_child);
std::swap(A->nodes_in_left_subtree,
B->nodes_in_left_subtree);
};
void update_count(tree_node * item)
{
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->left_child == item)
{
current->nodes_in_left_subtree--;
};
item = current;
};
};
void remove_from_tree(tree_node * item)
{
if (item->left_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->right_child;
}
else if (item->right_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->left_child;
}
else
{
nodeswap(item, rightmost(item->left_child));
remove_from_tree(item);
};
};
void move_to_front(key & item)
{
remove_from_tree(item);
insert_leftmost(item, root);
root->mom_ptr = NULL;
};
private:
void reset()
{
root = NULL;
};
void copy(const nutri & other)
{
throw std::string("Bad idea dude!");
};
void kill_tree_node(tree_node * & condemned_root)
{
if (condemned_root != NULL)
{
kill_tree_node(condemned_root->left_child);
kill_tree_node(condemned_root->right_child);
delete condemned_root;
};
};
void kill()
{
kill_tree_node(root);
};
public:
nutri()
{
reset();
};
nutri(const nutri & other)
{
reset();
copy(other);
};
nutri & operator=(const nutri & other)
{
if (this != &other)
{
kill();
reset();
copy(other);
};
return *this;
};
~nutri()
{
kill();
};
private:
void dump_tree_node(std:
stream & fout, const tree_node * root, int depth) const
{
if (root != NULL)
{
dump_tree_node(fout, root->left_child, depth + 1);
indent(fout, depth);
fout << "@" << root->nodes_in_left_subtree << std::endl;
dump_tree_node(fout, root->right_child, depth + 1);
};
};
public:
void dump(std:
stream & fout) const
{
dump_tree_node(fout, root, 0);
};
static void indent(std:
stream & fout, int n)
{
for (int i = 0; i < n; i++)
{
fout << " ";
};
};
};
inline
std:
stream & operator<<(std:
stream & fout, const nutri & X)
{
X.dump(fout);
return fout;
};
#endif // __HEADER_FILE_INCLUDED__nutri_hpp__
--------------------------------------------------------------------------
/* Interface: interface_LRU.hpp */
#ifndef __HEADER_FILE_INCLUDED__interface_LRU_hpp
#define __HEADER_FILE_INCLUDED__interface_LRU_hpp
class interface_LRU
{
public:
virtual const char * identifier() const = 0;
virtual void clear () = 0;
virtual int touch(long long int item) = 0;
virtual ~interface_LRU() {};
};
#endif //__HEADER_FILE_INCLUDED__interface_LRU_hpp
-----------------------------------------------
/* Test program:nutri_tester.cpp */
#include "nutri.hpp"
#include <iostream>
#include <map>
using namespace std;
#define SInt64 long long int
int main ()
{
/*
* Ovo pod komentarima ispisuje elemente u arrayu,
* ne sortiranim redosljedom
*/
nutri shisko;
map<SInt64, nutri::key> finder;
cout << "Which number you want to find" << endl;
SInt64 num;
while (cin >> num)
{
if (finder.find(num) == finder.end())
{
finder[num] = shisko.new_item();
cout << -1 << endl;
cout << shisko << endl;
}
else
{
cout << shisko.position(finder[num]) << endl;
shisko.move_to_front(finder[num]);
cout << shisko << endl;
};
};
return 0;
}
---------------------------------------------