NOTES.txt

push_swap Log

/*------------------BINARY_SEARCH----------------*/
int	get_index(int number, int *n, int size, int len)
/*Binary search
int len very stupid idea
Not working at all times*/
{
	i = size / 2;
	// if (i <= 0)
	// 	return (0);
	if (i >= len)
		return (len - 1);
	if (number != n[i])
	{
		if (number == n[i + 1])
			return (i + 1);
		else if (number == n[i - 1])
			return (i - 1);
		else if (number < n[i])
			return (get_index(number, n, i, len));
		else
			return (get_index(number, n, size + (i + 1), len));
	}
	return (i);
}
/*-------------NOT_WORKING_PROPERLY_THOUGH-------------*/

if (a->size > SHORT_LST && a.neg) <----- Attributing indexes only in case there's negatives ........
	Not to execute if no negatives on list; CREATE NEG FLAG ON T_STACK

/*-------USEFUL_FOR_VISUALIZING-----------*/
#include <stdio.h>

printf("stack a:\n");
printlst(&a, 0);
printlst(&a, 'i');

void	printlst(t_stack *s, char arg)
{
	t_dlist	*tmp;

	if (arg == 'r')
	{
		tmp = s->last;
		printf("REVERSE\n");
	}
	else
		tmp = s->head;
	printf("--------\n");
	if (!tmp)
	{
		printf("Empty!\n");
		return ;
	}
	while (tmp)
	{
		if (arg == 'i')
			printf("(index)%d\n", tmp->index);
		else
			printf("%d\n", tmp->n);
		if (arg == 'r')
			tmp = tmp->prev;
		else
			tmp = tmp->next;
	}
	printf("--------\n");
}
/*------------------------------------------------*/


pa = push(b, a) pb = push(a, b)
push -> if no src abort <------------------------------
rotate -> if no src abort <------------------------------



/*DEREFERENCE elements using *(int *)a.head->content */
*(int *)ft_lstlast(a->head)->content WORKS!!

Doubly Linked Lists w/ int n -> need remake lstlast lstnew lstadd_front lstclear lstdelone

--------------------------------------------------------------------------------
SEE 2nd_impl/ for implementation w/ doubly-linked-list and double-stack-struct (w/ int as value)
set doubly linked lists on libft.h and push_swap.h without thinking...still
using libft functions as well........................
	lstiter might actually be useful

--------------------------------------------------------------------------------------------

ARG=`ruby -e "puts (0..99).to_a.shuffle.join(' ')"`
----------------->(need create an sh tester script)<-----------------------

ARRAY IMPLEMENTATION OF STACKS:
typedef struct	s_stack
{
	int	stack[CAPACITY];
	int	top;
}		t_stack;

LINKED LIST IMPLEMENTATION OF STACK:
typedef struct	s_stack
{
	t_list	*head;
	ssize_t	size;
}		t_stack;

GETTING ARGUMENTS INTO A LINKED LIST USING LIBFT(original):
int	main(int argc, char **argv)
{
	int		n;
	t_list	*a;
	t_list	*new;
	int		i;

	a = ft_lstnew(argv[1]);
	i = 1;
	while (++i < argc)
		ft_lstadd_back(&a, ft_lstnew(argv[i]));
	new = a;
	while (new->next)							//prints list contents
	{
		n = ft_atoi((char *)new->content);		//casts to str and converts to int
		ft_putnbr_fd(n, 1);
		ft_putchar_fd('\n', 1);
		new = new->next;
	}
	n = ft_atoi((char *)new->content);
	ft_putnbr_fd(n, 1);
	ft_putchar_fd('\n', 1);
	ft_putnbr_fd(ft_lstsize(a), 1);
//	ft_lstclear(&a, (free)(void *)); <----------- Not sure yet how to do this
	return (0);
}

	^ Maybe not the best idea (?)^

POP:
t_list  pop(t_stack *s)
/*
 * Deletes 1st node on stack pointed to by s->head
 * Returns same node*/
{
        t_list  *node;

        node = &(s->head);      /*node points to 1st element of stack*/
        node->next = NULL;      /*isolates element*/
        s->head = s->head->next;        /*stack head points to next element*/
        s->size--;      /*size "decrement"*/
        return (*node); /*return element pointed to by "node"*/
}

PUSH:
void    push(t_list *node, t_stack *s)
/*
 *Add node to list pointed by stack's head
 increment stack size
 does not pop from previous t_list, ...*/
{
        ft_lstadd_back(&(s->head), ft_lstnew(node));
        s->size++;
}


/*------UNUSED FUNCTIONS BECAUSE I RAN OUT OF TIME--------*/

#include "inc/push_swap.h"

static int ft_rotate(t_stack *a, int rot, char *dir)
/*rotates a rot times in dir direction
	does nothing and returns 1 if rot is -1
only working for stack a atm; not very versatile*/
{
	if (rot == -1)
		return (1);
	while (rot--)
		exec(dir, a, 0);
	return (0);
}

static int	find_closest(t_stack *a, int i)
/*finds looked for element closest to extremes(top/bottom) and brings it to top
returns -1 if none found*/
{
	t_stack		top;
	t_stack		bottom;

	if (!a->size)
		return (0);
	top.head = a->head;
	top.size = 0;
	bottom.size = 0;
	while (top.head && top.size++ < (a->size / 2))
	{
		if (!((top.head->n >> i) & 1))
			break ;
		top.head = top.head->next;
	}
	bottom.head = lstlast(top.head);
	while (bottom.head && bottom.size <= (a->size / 2))
	{
		bottom.size++;
		if (!((bottom.head->n >> i) & 1) && bottom.size < top.size)
			return (ft_rotate(a, bottom.size, "rra"));
		bottom.head = bottom.head->prev;
	}
	if (top.size > (a->size / 2) && ((top.head->n >> i) & 1))
		top.size = 0;
	/*if tmp.size > i: tmp.size = i*/
//	printf("\ntop = %d\tbottom = %d\t", top.size, bottom.size);
	return (ft_rotate(a, --top.size, "ra"));
/*return (ft_rotate(a, top, bottom));*/
}

/* ^^^ ------------------------------------------------------------------------------ ^^^
		maybe pass a copy of a->head to save a line (t_dlist a, int condition)
		maybe return absolute index number instead of relative to top/bottom (0 - a.size)
		... or call a rotating function instead
		...or pass char rot == "ra" or "raa" depending on value returned
   ^^^ ------------------------------------------------------------------------------ ^^^	*/


t_dlist	pop(t_stack *s)
/*
 * Deletes 1st node on stack pointed to by s->head
 * Returns same node*/
{
	t_dlist	*node;

	node = s->head;	/*node points to 1st element of stack*/
	node->next = NULL;	/*isolates element*/
	s->head = s->head->next;	/*stack head points to next element*/
	s->size--;	/*size "decrement"*/
	return (*node); /*return element pointed to by "node"*/
}


static int	chunk_sort(t_stack *s, int *i, int *j, int min, int max)
/*NOT WORKING*/
{
	int	tmp;

	while ((*i)++ != (int)(s->size / 2) && s->head)
	{
		if (s->head->n >= min && s->head->n < max)
			break ;
		s->head = s->head->next;
	}
	tmp = *i;
	while (tmp++ != s->size)
		s->head = s->head->next;
	tmp = s->size / 2;
	*j = 0;
	while (s->head)
	{
		if (s->head->n >= min && s->head->n < max)
			*j = tmp;
		s->head = s->head->next;
		tmp++;
	}
	if (*i == (int)(s->size / 2) && *j == 0)
		return(0);
	else
		return (1);
}

void	quick_sort(t_stack *a, t_stack *b)
/*NOT WORKING*/
{
	int 	first;
	int		second;
	int		range;
	int		i;

	i = 0;
	range = a->size / 5;
	while (i++ < 5)
	{
		while (chunk_sort(a, &first, &second, range - (range * i), range * i))
		{
			if (first <= second)
			{
				while (first--)
					exec("ra", a, 0);
			}
			else
			{
				while (second--)
					exec("rra", a, 0);
			}
			exec("pb", a, b);
		}
	}
	printf("stack b:\n");
	printlst(b, 0);
	printf("stack b:\n");
	free(b);
}

static t_dlist	*get_middle(t_stack a)
/*finds midpoint in stack if odd or end of upper half if even
	not really useful atm*/
{
	t_dlist	*tmp;
	int		i;

	i = 0;
	tmp = a.head;
	while (i++ < (a.size / 2))
		tmp = tmp->next;
	return (tmp);
}



static void	merge(int *a, int l, int h, int m) //no actual need for m here
{
	int			left[(m - l)]; //not permitted
	int			right[(h - m)]; //not permitted
	t_indexes	id;

	id.llen = m - l;
	id.rlen = h - m;
	copy(a, left, right, &id);
	while (id.l < id.llen && id.r < id.rlen)
	{
		if (left[id.l] < right[id.r])
			a[l++] = left[id.l++];
		else
			a[l++] = right[id.r++];
	}
	while (id.l < id.llen)
		a[l++] = left[id.l++];
	while (id.r < id.rlen)
		a[l++] = right[id.r++];
}

void	merge_sort(int *a, int l, int h) //Not sure copy would work with recursion;
{
	int	m;

	m = h / 2; // middle
	if (h > 1) //base case
	{
		merge_sort(a, l, m); //DIVIDE LEFT SIDE
		merge_sort(a + m, m, h - 1); //DIVIDE RIGHT SIDE
		merge(a, l, h, m); //pass tmp[] instead of m maybe
	}
//	return (copy); //MERGE BOTH SIDES (malloc and return results or return a)
}

/*Dealing with $ARG (because zsh)*/
	if (argc == 2)
	{
		a->size = 0;
		arg = ft_split(argv[1], ' ');
		if (!arg)
			display_err();
		while (arg[a->size])
		{
			n[a->size] = _atoi(arg[a->size]);
			free(arg[a->size]);
			a->size++;
		}
		// ft_free_arr_str(arg);
		free(arg);
	}
	else