/* Directory tree browser for the Midnight Commander
   Copyright (C) 1994, 1995, 1996, 1997 The Free Software Foundation

   Written: 1994, 1996 Janne Kukonlehto
            1997 Norbert Warmuth
            1996 Miguel de Icaza

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

   This module has been converted to be a widget.

   The program load and saves the tree each time the tree widget is
   created and destroyed.  This is required for the future vfs layer,
   it will be possible to have tree views over virtual file systems.

   */
#include <config.h>
#include <sys/types.h>
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif
#include <fcntl.h>
#include <sys/param.h>
#include <sys/stat.h>
#include <errno.h>
#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>	/* For free() and atoi() */
#include <string.h>
#include "tty.h"
#include "mad.h"
#include "global.h"
#include "util.h"
#include "color.h"
#include "dialog.h"
#include "dir.h"
#include "dlg.h"
#include "widget.h"
#include "panel.h"
#include "mouse.h"
#include "main.h"
#include "file.h"	/* For copy_dir_dir(), move_dir_dir(), erase_dir() */
#include "help.h"
#include "key.h"	/* For mi_getch() */
#include "tree.h"
#include "cmd.h"
#include "../vfs/vfs.h"
#ifdef OS2_NT
#   include <io.h>
#endif

extern int command_prompt;

#define TREE_NORMALC HOT_FOCUSC

/* Specifies the display mode: 1d or 2d */
int tree_navigation_flag;

/* If this is true, then when browsing the tree the other window will
 * automatically reload it's directory with the contents of the currently
 * selected directory.
 */
int xtree_mode = 0;

/* Forwards */
static int tree_callback (Dlg_head *h, WTree *tree, int msg, int par);
#define tcallback (callback_fn) tree_callback

/* "$Id: tree.c 15091 2005-05-07 21:24:31Z sedwards $" */

/* Returns number of common characters */
static inline int str_common (char *s1, char *s2)
{
    int result = 0;

    while (*s1++ == *s2++)
	result++;
    return result;
}

static tree_entry *back_ptr (tree_entry *ptr, int *count)
{
    int i = 0;

    while (ptr && ptr->prev && i < *count){
	ptr = ptr->prev;
	i ++;
    }
    *count = i;
    return ptr;
}

static tree_entry *forw_ptr (tree_entry *ptr, int *count)
{
    int i = 0;

    while (ptr && ptr->next && i < *count){
	ptr = ptr->next;
	i ++;
    }
    *count = i;
    return ptr;
}

/* The directory names are arranged in a single linked list in the same
   order as they are displayed. When the tree is displayed the expected
   order is like this:
        /
        /bin
        /etc
        /etc/X11
        /etc/rc.d
        /etc.old/X11
        /etc.old/rc.d
        /usr

   i.e. the required collating sequence when comparing two directory names is
        '\0' < PATH_SEP < all-other-characters-in-encoding-order

    Since strcmp doesn't fulfil this requirement we use pathcmp when
    inserting directory names into the list. The meaning of the return value
    of pathcmp and strcmp are the same (an integer less than, equal to, or
    greater than zero if p1 is found to be less than, to match, or be greater
    than p2.
 */
int
pathcmp (const char *p1, const char *p2)
{
    for ( ;*p1 == *p2; p1++, p2++)
        if (*p1 == '\0' )
    	    return 0;

    if (*p1 == '\0')
        return -1;
    if (*p2 == '\0')
        return 1;
    if (*p1 == PATH_SEP)
        return -1;
    if (*p2 == PATH_SEP)
        return 1;
    return (*p1 - *p2);
}

/* Searches for specified directory */
static tree_entry *whereis (WTree *tree, char *name)
{
    tree_entry *current = tree->tree_first;
    int flag = -1;

#if 0
    if (tree->tree_last){
	flag = strcmp (tree->tree_last->name, name);
	if (flag <= 0){
	    current = tree->tree_last;
	} else if (tree->selected_ptr){
	    flag = strcmp (tree->selected_ptr->name, name);
	    if (flag <= 0){
		current = tree->selected_ptr;
	    }
	}
    }
#endif
    while (current && (flag = pathcmp (current->name, name)) < 0)
	current = current->next;

    if (flag == 0)
	return current;
    else
	return NULL;
}

/* Add a directory to the list of directories */
tree_entry *tree_add_entry (WTree *tree, char *name)
{
    int flag = -1;
    tree_entry *current = tree->tree_first;
    tree_entry *old = NULL;
    tree_entry *new;
    int i, len;
    int submask = 0;

    if (!tree)
	return 0;

    if (tree->tree_last && tree->tree_last->next)
	abort ();
#if 0
    if (tree->tree_last){
	flag = strcmp (tree->tree_last->name, name);
	if (flag <= 0){
	    current = tree->tree_last;
	    old = current->prev;
	} else if (tree->selected_ptr){
	    flag = strcmp (tree->selected_ptr->name, name);
	    if (flag <= 0){
		current = tree->selected_ptr;
		old = current->prev;
	    }
	}
    }
#endif
    /* Search for the correct place */
    while (current && (flag = pathcmp (current->name, name)) < 0){
	old = current;
	current = current->next;
    }

    if (flag == 0)
	return current; /* Already in the list */

    /* Not in the list -> add it */
    new = xmalloc (sizeof (tree_entry), "tree, tree_entry");
    if (!current){
	/* Append to the end of the list */
	if (!tree->tree_first){
	    /* Empty list */
	    tree->tree_first = new;
	    new->prev = NULL;
	} else {
	    old->next = new;
	    new->prev = old;
	}
	new->next = NULL;
	tree->tree_last = new;
    } else {
	/* Insert in to the middle of the list */
	new->prev = old;
	if (old){
	    /* Yes, in the middle */
	    new->next = old->next;
	    old->next = new;
	} else {
	    /* Nope, in the beginning of the list */
	    new->next = tree->tree_first;
	    tree->tree_first = new;
	}
	new->next->prev = new;
    }
    /* tree_count++; */

    /* Calculate attributes */
    new->name = strdup (name);
    len = strlen (new->name);
    new->sublevel = 0;
    for (i = 0; i < len; i++)
	if (new->name [i] == PATH_SEP){
	    new->sublevel++;
	    new->subname = new->name + i + 1;
	}
    if (new->next)
	submask = new->next->submask;
    else
	submask = 0;
    submask |= 1 << new->sublevel;
    submask &= (2 << new->sublevel) - 1;
    new->submask = submask;
    new->mark = 0;

    /* Correct the submasks of the previous entries */
    current = new->prev;
    while (current && current->sublevel > new->sublevel){
	current->submask |= 1 << new->sublevel;
	current = current->prev;
    }

    /* The entry has now been added */

    if (new->sublevel > 1){
	/* Let's check if the parent directory is in the tree */
	char *parent = strdup (new->name);
	int i;

	for (i = strlen (parent) - 1; i > 1; i--){
	    if (parent [i] == PATH_SEP){
		parent [i] = 0;
		tree_add_entry (tree, parent);
		break;
	    }
	}
	free (parent);
    }

    return new;
}

#if 0
/* Append a directory to the list of directories */
static tree_entry *tree_append_entry (WTree *tree, char *name)
{
    tree_entry *current, *new;
    int i, len;
    int submask = 0;

    /* We assume the directory is not yet in the list */

    new = xmalloc (sizeof (tree_entry), "tree, tree_entry");
    if (!tree->tree_first){
        /* Empty list */
        tree->tree_first = new;
        new->prev = NULL;
    } else {
        tree->tree_last->next = new;
        new->prev = tree->tree_last;
    }
    new->next = NULL;
    tree->tree_last = new;

    /* Calculate attributes */
    new->name = strdup (name);
    len = strlen (new->name);
    new->sublevel = 0;
    for (i = 0; i < len; i++)
	if (new->name [i] == PATH_SEP){
	    new->sublevel++;
	    new->subname = new->name + i + 1;
	}
    submask = 1 << new->sublevel;
    submask &= (2 << new->sublevel) - 1;
    new->submask = submask;
    new->mark = 0;

    /* Correct the submasks of the previous entries */
    current = new->prev;
    while (current && current->sublevel > new->sublevel){
	current->submask |= 1 << new->sublevel;
	current = current->prev;
    }

    /* The entry has now been appended */
    return new;
}
#endif

static void remove_entry (WTree *tree, tree_entry *entry)
{
    tree_entry *current = entry->prev;
    long submask = 0;

    if (tree->selected_ptr == entry){
	if (tree->selected_ptr->next)
	    tree->selected_ptr = tree->selected_ptr->next;
	else
	    tree->selected_ptr = tree->selected_ptr->prev;
    }

    /* Correct the submasks of the previous entries */
    if (entry->next)
	submask = entry->next->submask;
    while (current && current->sublevel > entry->sublevel){
	submask |= 1 << current->sublevel;
	submask &= (2 << current->sublevel) - 1;
	current->submask = submask;
	current = current->prev;
    }

    /* Unlink the entry from the list */
    if (entry->prev)
	entry->prev->next = entry->next;
    else
	tree->tree_first = entry->next;
    if (entry->next)
	entry->next->prev = entry->prev;
    else
	tree->tree_last = entry->prev;
    /* tree_count--; */

    /* Free the memory used by the entry */
    free (entry->name);
    free (entry);
}

void tree_remove_entry (WTree *tree, char *name)
{
    tree_entry *current, *base, *old;
    int len, base_sublevel;

    /* Miguel Ugly hack */
    if (name [0] == PATH_SEP && name [1] == 0)
	return;
    /* Miguel Ugly hack end */

    base = whereis (tree, name);
    if (!base)
	return;	/* Doesn't exist */
    if (tree->check_name [0] == PATH_SEP && tree->check_name [1] == 0)
	base_sublevel = base->sublevel;
    else
	base_sublevel = base->sublevel + 1;
    len = strlen (base->name);
    current = base->next;
    while (current
	   && strncmp (current->name, base->name, len) == 0
	   && (current->name[len] == '\0' || current->name[len] == PATH_SEP)){
	old = current;
	current = current->next;
	remove_entry (tree, old);
    }
    remove_entry (tree, base);
}

void tree_destroy (WTree *tree)
{
    tree_entry *current, *old;

    save_tree (tree);
    current = tree->tree_first;
    while (current){
	old = current;
	current = current->next;
	free (old->name);
	free (old);
    }
    if (tree->tree_shown){
	free (tree->tree_shown);
	tree->tree_shown = 0;
    }
    tree->selected_ptr = tree->tree_first = tree->tree_last = NULL;
}

/* Mark the subdirectories of the current directory for delete */
void start_tree_check (WTree *tree)
{
    tree_entry *current;
    int len;

    if (!tree)
	tree = (WTree *) find_widget_type (current_dlg, tcallback);
    if (!tree)
	return;

    /* Search for the start of subdirectories */
    mc_get_current_wd (tree->check_name, MC_MAXPATHLEN);
    tree->check_start = NULL;
    current = whereis (tree, tree->check_name);
    if (!current){
	/* Cwd doesn't exist -> add it */
	current = tree_add_entry (tree, tree->check_name);
	return;
    }

    /* Mark old subdirectories for delete */
    tree->check_start = current->next;
    len = strlen (tree->check_name);

    current = tree->check_start;
    while (current
	   && strncmp (current->name, tree->check_name, len) == 0
	   && (current->name[len] == '\0' || current->name[len] == PATH_SEP || len == 1)){
	current->mark = 1;
	current = current->next;
    }
}

/* This subdirectory exists -> clear deletion mark */
void do_tree_check (WTree *tree, const char *subname)
{
    char *name;
    tree_entry *current, *base;
    int flag = 1, len;

    /* Calculate the full name of the subdirectory */
    if (subname [0] == '.' &&
	(subname [1] == 0 || (subname [1] == '.' && subname [2] == 0)))
	return;
    if (tree->check_name [0] == PATH_SEP && tree->check_name [1] == 0)
	name = copy_strings (PATH_SEP_STR, subname, 0);
    else
	name = concat_dir_and_file (tree->check_name, subname);

    /* Search for the subdirectory */
    current = tree->check_start;
    while (current && (flag = pathcmp (current->name, name)) < 0)
	current = current->next;

    if (flag != 0)
	/* Doesn't exist -> add it */
	current = tree_add_entry (tree, name);
    free (name);

    /* Clear the deletion mark from the subdirectory and its children */
    base = current;
    if (base){
	len = strlen (base->name);
	base->mark = 0;
	current = base->next;
	while (current
	       && strncmp (current->name, base->name, len) == 0
	       && (current->name[len] == '\0' || current->name[len] == PATH_SEP || len == 1)){
	    current->mark = 0;
	    current = current->next;
	}
    }
}

/* Tree check searchs a tree widget in the current dialog and
 * if it finds it, it calls do_tree_check on the subname
 */
void tree_check (const char *subname)
{
    WTree *tree;

    tree = (WTree *) find_widget_type (current_dlg, tcallback);
    if (!tree)
	return;
    do_tree_check (tree, subname);
}


/* Delete subdirectories which still have the deletion mark */
void end_tree_check (WTree *tree)
{
    tree_entry *current, *old;
    int len;

    if (!tree)
	tree = (WTree *) find_widget_type (current_dlg, tcallback);
    if (!tree)
	return;

    /* Check delete marks and delete if found */