package test_jvm;

import java.util.ArrayList;
import java.util.List;

/**
 * Класс элемента дерева и, собственно, само дерево.
 * 
*/
public class Node<T> {
    private T data;
    private List<Node<T>> children = new ArrayList<>();
    private Node<T> parent;
    /*
     * Константы задающие тип иникальности
     */
    /**
     * Иерархия не контролирует иникальность добавленных записей
     */
    public static final int NO_UNIQUE = 0;
    /**
     * Дубли на одном уровне не допускаются
     */
    public static final int LEVEL_UNIQUE = 1;
    /**
     * Дубли на допускаются целиком по дерево (ниже лежащим уровням)
     */
    public static final int GLOBAL_UNIQUE = 2;
    
    /**
     * 
     */
    public int uniqueMode;
    /**
     * Создает новый КОРНЕВОЙ узел. Проставляет флаг уникальности. 
     * 
     * @param data Данные для нового узла
     * @param parent Ссылка на родителя данного узла
     * @aram uniqueMode режим уникальности
     * 
    */
    public Node(T data, Node<T> parent, int uniqueMode ) {
        this.data = data;
        this.parent = parent;
        this.uniqueMode = uniqueMode;
    }
    
    /**
     * Создает новый узел. Флаг уникальности копируется из предка. Что
     * обеспечивает, что все дерево будет иметь один и тот же режим
     * проверки уникальности 
    */
    public Node( T data, Node<T> parent ) {
    	if ( parent==null ) {
            this.data = data;
            this.parent = parent;
            this.uniqueMode = NO_UNIQUE;
    	} else {
            this.data = data;
            this.parent = parent;
            this.uniqueMode = this.parent.uniqueMode;
    	}
    }

    
    /**
     * Возвращает hashCode. Требуется для корректной работы стандартных коллекций
     */
    @Override
	public int hashCode() {
		return this.data.hashCode();
	}

    /**
     * Провеяем эквивалентность двух узлов по их содержимому.
     */
	@Override
	public boolean equals(Object obj) {
		return this.data.equals( ((Node<T>)obj).data );
	}

	/**
     *  Ищем, есть ли уже узел с такими данными.
     * 
     * @param obj Данные с которыми сверяемся.
     * @param global Если false, то поиск только в текущем узле, если true,
     * то по всему дереву
     */
    public boolean contains( Node<T> obj, boolean global ) {
    	/* Проверка на текущем уровне */
    	if ( this.children.contains(obj) ) {
    		return true;
    	}
    	/* Если требуется глобальная проверка, рекурсивно проверяем и у детей */
    	if ( global ) {
    		for ( Node<T> kind: this.children ) {
    			if ( kind.contains( obj, global ) ) {
    				return true;
    			}
    		}
    	}
    	return false;
    }

    /**
     * Ищет данные в дереве
     */
    public boolean contains( T obj, boolean global ) {
    	// Временный объект для поиска
    	Node<T> tmp = new Node<T>( obj, null );
    	// Ищем
    	return this.contains( tmp, global );
    }
    
    /**
     * Ищет данные в дереве глобально
    */
    public boolean contains( T obj ) {
    	return this.contains( obj, true );
    }
    
    public void addChild(Node<T> node) throws NotUniqueException {
    	/*
    	 *  Если требуется обеспечение уникальности, то проверяем, что
    	 * узла с такими данными еще не существует
    	 */
    	if ( uniqueMode!=Node.NO_UNIQUE ) {
    		if ( this.contains( node, uniqueMode==Node.GLOBAL_UNIQUE )) {
    			throw new NotUniqueException();
    		}
    	}
        children.add(node);
    }

    /**
     * Создает узел и добавляет его в иерархию на основе его данных.
     * 
     * @param nodeData Данные для нового узла
     * @return Возвращает вновь созданный узел
     * @throws NotUniqueException 
     */
    public Node<T> addChild(T nodeData) throws NotUniqueException {
    	// Создаваемый узел будет принадлежать нашему. Т.ч. его
    	// parent - это мы
    	Node<T> newNode = new Node<T>( nodeData, this ); 
        this.addChild( newNode );
        return newNode;
    }

    /**
     * Специальный метод, что бы всех разбирающихся в структурах
     * данных доводить до иступления.
     * Все знаю, что метод iterate должен возвращать интератор, а
     * не коллекцию. Если итератора нет, то и нафиг такой метод.
     * 
     * НО ! Если его не будет, тогда у всех будет душевное спокойствие,
     * что не интересно. Поэтому данный метод необходим, как увеличивающий
     * продажи психотропных и успокоительных лекарств, соответственно
     * стимулирующий рост экономики в сфере фарм-индустрии и соответственно
     * увеличивающий рост ВВП России. Слава Путину !!!
    */
    public List<Node<T>> iterate() {
        return children;
    }

    public void remove(Node<T> node) {
        children.remove(node);
    }

    public List<Node<T>> getChildren() {
        return children;
    }

    public Node getParent() {
        return parent;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

package test_jvm;

import java.io.PrintStream;
import java.util.List;

/**
 * Дерево с возможность его печати
 */
public class Tree<T> {
	private Node<T> rootNode;

	public Tree( T data ) {
		/* Корневой узел владельца не имеет */
		rootNode = new Node<T>( data, null, Node.NO_UNIQUE );
	}

	/**
	 * Создает дерево с заданным типом проверки уникальности
	 * @param data
	 */
	public Tree( T data, int uniqueMode ) {
		/* Корневой узел владельца не имеет, зато может иметь проверку уникальности */
		rootNode = new Node<T>( data, null, uniqueMode );
	}

	/**
	 * Возврашает корневой узел
	 * 
	 * @return Ссылка на корневой узел
	 */
	public Node<T> getRoot() {
		return rootNode;
	}
	
	/**
	 * Печатает дерево
	 * 
	 * @param writer Куда печатать
	 */
	public void printCatalog( PrintStream out ) {
		// Печатаем сами себя (мы главные, т.ч. без отступов)
        printNode( out, rootNode, 0, null );
        // Печатаем узлы в дереве (отступы наинаются с 1 уровня)
        List<Node<T>> kids = rootNode.getChildren();
        printChildren( out, kids, 1, null );
	}
	
	/**
	 * Печатает дерево на экран
	 */
	public void printCatalog( ) {
		printCatalog( System.out );
	}
	
	

	/**
	 * Печатает детей указанной Node (бывший printTree)
	 * 
	 * @param kids Дети для печати
	 * @param level Положение в иерархии, для генерации красивого отступа 
	 * @param isLastArr Массив, который для каждого уровня в иерархии, покащывает, печатаем
	 * ли мы последний элемент или не последний (для последнего элемента в каждом уровне не
	 * нужно печатать вертикальную черточку). Размер массива level-1 
	 */
    private static <T> void printChildren( PrintStream out, List<Node<T>> kids, int level, boolean isLastArr[] ) {
    	// Проверка на пустоту не нужна. Если пусто, то
    	// и for ничего делать не будет
        // if (kids.isEmpty()) {
        //     return;
        // }
    	// 
    	boolean curIsLastArr[];
    	curIsLastArr = new boolean[level];
    	// копируем переданные данные из isLastArr в curIsLastArr
    	// последний (текущей) будет не проинициализирован. Мы его будем
    	// заполнять, когда будем ходить по переданной коллекции
    	for ( int i=0; i<(level-1); i++ ) {
    		curIsLastArr[ i ] = isLastArr[ i ];
    	}
        // Цикл по всем узлам в переданном нам списке для печати
    	// Т.к. нам нужно знать, есть ли данные дальше, то используем 
    	// Iterator как более удобный
    	java.util.ListIterator<Node<T>> iterator;
    	iterator = kids.listIterator();
    	while ( iterator.hasNext() ) {
    		// Получаем следующий (текущей) узел
    		Node<T> kid = iterator.next();
    		// Если если есть еще данные, мы НЕ последние на данном
    		// уровне иерархии
    		// Node: т.к. индекс в массиве с 0, то последний элемент
    		// это level-1 
    		if ( iterator.hasNext() ) {
    			// НЕ последний
    			curIsLastArr[ level-1 ] = false; 
    		} else {
    			// последний 
    			curIsLastArr[ level-1 ] = true; 
    		}
        	// Печатаем текущей узел
            printNode( out, kid, level, curIsLastArr );
            // Печатаем всех детей данного узла, увеличиваем уровень
            // в иерархии, что бы увеличился отступ при печати
            printChildren( out, kid.getChildren(), level+1, curIsLastArr );
        }
    }

    /**
     * Печатает узел с отступом.
     * 
     * @param kid Узел, который нужно напечатать
     * @param level Положение в иерархии, для генерации красивого отступа
     * @param isLastArr Массив флагов, что на данном уровне иерархии печататется
     * последний элемент
     */
    private static <T> void printNode(PrintStream out, Node<T> kid, int level, boolean isLastArr[] ) {
    	// Печатаем отступы других уровней. Если на данном уровне мы последнии, то
    	// вертикальную черточку печатать не нужно
    	for ( int i=0; i<(level-1); i++ ) {
    		if ( isLastArr[i] ) {
        		out.print( "    " );  // 4 пробела
    		} else {
    		    out.print( "|   " );  // 3 пробела
    		}
    	}
        // Печатаем отступы для нашего уровня или для корня
		if ( level>0 ) {
			out.print( "+-- " );
		} else {
			// level = 0, корень, отступы не нужны
			;
		}
    	
        out.println(kid.getData());
    }
}

package test_jvm;

import java.io.IOException;
import java.io.LineNumberReader;
import java.io.StringReader;
import java.util.List;

/**
 * Специальный класс для иерархий из строк. Дополнительно позволяет считывать иерархию
 * из входного потока и разбирать отступы
 * 
 * Универсальный generic'ом сделать не получилось, т.к. требуется явная совметимость типа T со String
 *
 */
public class Tree4String extends Tree<String> {
	/**
	 * Константа, задает сколько пробелов должен быть отступ для одного
	 * уровня.
	 */
	public final static int spaceForOneLevel = 4;
	
	public Tree4String() {
    	super( "Default root" );
    }

	/**
	 * Возврашает последнию ноду на заданном уровне
	 * 
	 * @param level Уровень. Нумерация с 1
	 * @return Последнию ноду на заданном уровне (и последнию по всем
	 * предыдущим уровням)
	 */
	private Node<String> getNodeByLevel( int level ) {
		Node<String> cur;
		cur = this.getRoot();
		
		// Цикл пока не доберемся до заданного уровня
		// или не кончатся данные (ошибкой не считается)
		for ( int i=1; i<level; i++ ) {
			List<Node<String>> kinds;
			kinds = cur.getChildren();
			// Пееходим на следующий уровень и ищем
			// последний элемент. Для классических
			// списков это операция крайне не оптимальна. 
			int size = kinds.size();
			if ( size==0 ) {
				// Пустой список, ничего не делаем
				;
			} else {
				// Берем последний элемент с данного уровня
				cur = kinds.get( size-1 );
			}
		}
		return cur;
	}
	
	/**
	 * Добювляет узел на заданный уровень дерева в конец списка.
	 * 
	 * @param level Уровень. Нумерация с 1. 0 само дерево, тогда его переименовываем
	 * @return Добавленный узел или измененный корень
	 * @throws NotUniqueException 
	 * 
	*/
	public Node<String> addChildAtLevel( int level, String nodeData ) throws NotUniqueException {
		Node<String> nodeToInsert;
		if ( level==0 ) {
			this.getRoot().setData( nodeData );
			return this.getRoot();
		}
		nodeToInsert = this.getNodeByLevel( level );
		return nodeToInsert.addChild( nodeData );
	}
	
	/**
	 * Функция делит кол-во пробелов/символов в отступе на константу и
	 * возврашает получившийся номер уровня. Выделено в отдельную ф-цию,
	 * что бы проще управлять правилами округления 
	 */
	private int spaceToLevel( int spaceCount, int spaceForOneLevel ) {
		return (spaceCount + (spaceForOneLevel/2)) / spaceForOneLevel;
	}
	
	/**
	 * Подсчитывает кол-во пробелов/символов в отступе в конкретной строке.
	 * 
	 *  Примечание: спец. символы в начале строки так-же считаем пробелами.
	 *  
	 *  @return Позицию первого не пробельного (не отступного) символа.
	 */
	private int calculateSpaceAtString( String s ) {
		int i;
		for ( i = 0; i<s.length(); i++ ) {
			int c = s.charAt( i );
			if ( c==' ' || c=='+' || c=='-' || c=='|' ) {
				continue;
			} else {
				break;
			}
		}
		return i;
	}
	
	/**
	 * Разбирает строку с отступами и добавляет ее в дерево.
	 * @throws NotUniqueException 
	*/
	public Node<String> addStringWithIndent( String s ) throws NotUniqueException {
		int spaceCount = calculateSpaceAtString( s );
		String nodeData = s.substring( spaceCount );
		int level = this.spaceToLevel( spaceCount, spaceForOneLevel );
		// Trace
		// System.out.println( "s="+s+"  spaceCount="+spaceCount+" level="+level );
		return this.addChildAtLevel( level, nodeData );
	}

	/**
	 * Создает иерархию читая его из файла с отступами
	 * 
	 * @param reader Откуда читать
	 * @throws IOException
	 * @throws NotUniqueException 
	 */
	public void read( java.io.Reader reader ) throws IOException, NotUniqueException {
		java.io.LineNumberReader lnr = new LineNumberReader( reader);
		while ( true ) {
			String s = lnr.readLine();
			if ( s==null ) {
				// End of file
				return;
			}
			this.addStringWithIndent( s );
		}
	}
	
	/**
	 * Создает иерархию читая ее из строкового буфера. Текст должен быть разделен на
	 * строки через \n или \r\n
	 * 
	 * @param text Строка содержащая текст
	 * @throws IOException 
	 * @throws NotUniqueException 
	 */
	public void readText( String text ) throws IOException, NotUniqueException {
		// Читаем из входного потока
		java.io.StringReader reader = new StringReader( text );
        this.read( reader );
        reader.close();
	}
}

package test_jvm;

import java.io.IOException;
import java.io.StringReader;

/**
 * Главный класс приложения. Создает дерево и печатает его.
 * Проверяет работу метода contains и не возможность добавить дубли
 */
public class TreePrint3 {
	public static void test1() throws IOException, NotUniqueException {
        String s =
"root\n" +
"    Video\n"+
"        Terminator\n"+
"        Die Hard\n"+
"        Rocky\n"+
"    Music\n"+
"        Eminem\n"+
"    Picture\n"+
"        Picasso";

        Tree4String rootFolder = new Tree4String();
        rootFolder.readText( s );
        rootFolder.printCatalog();
        Node<String> rootNode = rootFolder.getRoot();

   	 	System.out.println( "" );
   	 	
        if ( rootNode.contains( "nastyaa" ) ) {
        	System.out.println( "There is nastyaa in tree" );
        } else {
       	 	System.out.println( "There is NOT nastyaa in tree" );
        }

        if ( rootNode.contains( "Video" ) ) {
       	 	System.out.println( "There is Video in tree" );
        } else {
      	 	System.out.println( "There is NOT Video in tree" );
        }

        if ( rootNode.contains( "Picasso" ) ) {
       	 	System.out.println( "There is Picasso in tree" );
        } else {
      	 	System.out.println( "There is NOT Picasso in tree" );
        }
	}
	

	public static void main(String[] args) throws IOException, NotUniqueException {
		System.out.println( "\n\n************ TEST 1 ************\n\n" );
    	test1();
    }
}

************ TEST 1 ************


root
+-- Video
|   +-- Terminator
|   +-- Die Hard
|   +-- Rocky
+-- Music
|   +-- Eminem
+-- Picture
    +-- Picasso

There is NOT nastyaa in tree
There is Video in tree
There is Picasso in tree