pramodraob/directorymanager

Repo for the DSA Mini-project Directory Manager

Directory Manager

A simple commandline sandbox directory manager which showcases several data-structure and algorithms such as hashing using the djb2 hash function, N-ary trees and tries for fast prefix matching.

Installation and Setup

To setup the program on your desktop, do the following.

git clone https://github.com/PramodRaoB/directoryManager

In the directory of your choice. This includes all files required for the program and the report + code documentation.

Running the program

In the local repository, just type the following into the console

make

This runs the Makefile which contains the instructions to compile and run the program.

Note: The Makefile assumes the compiler to be gcc

For clang users, use

`make clang`

Usage

The user can type help after running the program to see a full list of commands available to the user. In short,

To add a file/folder to the directory use the command where type can be "file" or "folder"

add <name> <type>

To move to a different directory. Here the path cannot contain spaces, and be in the format "root/".

move <path>

To alias a path to a string, use the following command. Path should follow the same rules as above.

alias <path>

To teleport to the alias use this command. The alias should be created first using alias before teleporting.

teleport <alias>

To quit the program, type

quit

Features

1. Add a file in the current directory using the add function
2. Move to any directory using move.
3. Save path to directory using alias.
4. Move to any directory using teleportby providing alias of the path.
5. findallows you to search through the current directory with a specified prefix
6. Exit the program using quit
7. Display contents of current directory using ls.
8. Use cd to move to directory of choice from the current directory.
9. Use help to learn more about the usage.

Repository Contents

├── DirectoryManager.c
├── DirectoryManager.h
├── Directree
│   ├── NodeElement.h
│   ├── hashChild.c
│   ├── hashChild.h
│   ├── tree.c
│   ├── tree.h
│   ├── trie.c
│   └── trie.h
├── Hash(Alias)
│   ├── hash.c
│   └── hash.h
├── Makefile
├── README.md
├── a.out
├── changelog.md
├── design.sh
├── documentation.md
├── include.h
├── main.c
├── main.out
└── utils
    ├── colors.c
    ├── colors.h
    ├── design.sh
    ├── stack.c
    ├── stack.h
    ├── string_parser.c
    ├── string_parser.h
    ├── utils.c
    └── utils.h

directorymanager's Issues

Make a new README file

Edit the README.md file of the repo and add To-dos for better management of tasks

Util function for finding prime number greater than twice a given number

For effective rehashing, we will need to increase the current table size (which is a prime number) into a prime number that is more than double the current size.
Implement a util function that achieves this.

Implement Find path from alias hashtable

Rehashing functionality for the alias hashtable

Implement rehashing functionality for the alias hashtable using the prime finder util.

Final TELEPORT function

Implement a function named TELEPORT

• Change the current directory to any directory by taking input the alias of that directory.
• Error handling should be done for non-existing aliases.

Implementing hashtable for the children nodes

Currently, we have a linked list that stores the list of children to a given node.
Finding in the linked list would take us O(n) time where 'n' is the number of children to a given node.
This not only makes finding slow but it delays traversal.

So, implement a hashtable that:

• Uses the path-name of the child node as the input to the hash function to come up with a hash value
• Implement finding a child node to current node in O(1)
  • If found, return a pointer to the node.
  • If not, return NULL
• Implement rehashing using the prime finder util

Final FIND function

Implement a function named FIND

• Implement searching all the files/directories with given prefix inside the current directory.
• Take a prefix-string input for search.
• Output all the files/directories with the given prefix.

Final ALIAS function

Implement a function named ALIAS

• Implement saving a directory with an alias.
• Take input the complete path to that directory and the alias.
• Error handling should be done for incorrect path and for already-existing aliases.

Need to implement a string parser

• Implement a string parser that takes in a string with alphanumeric characters and '/'.
• Separate the string into groups of characters using '/' as the delimiter
• Make sure to append the null character '\0' to every word of the final list of words
• Both array and linked list-based implementation would be valid for the final list of words

Tree traversal given a path

• Given a list of nodes, traverse the tree and return the pointer to the final destination node.
• Return NULL if the path is invalid

Restructure "TreeNode"

• To remove char name[NAME_SIZE] and bool isFile into a separate struct from struct treenode to make it easier to work with when changing to an array implementation of children.
• This would require changing the fundamental functions written for linked lists as well.

Remove hashtables for nodes of type: "file"

Currently, all nodes have a hashtable linked for the child nodes.
Since nodes of type file do not contain child nodes, make the program memory efficient by removing the corresponding linked hashtable.

Final ADD function

Implement a function named ADD

• Implement the addition of a file/directory inside the current directory.
• Take user input for type (file/directory) and name.

Dynamic length of node name

Instead of the current static allocation of node name, implement dynamic memory allocation (using heap memory).

1. Accept a string of a predefined maximum length
2. Pass the value of the length of the input as an argument to init_node
3. Dynamically allocate memory on the heap and copy contents of a given input string onto the node
4. Make sure to free this chunk of memory as well before the end of the program

Final MOVE function

Implement a function named MOVE

• Change the current directory to any directory by taking input the complete path to that directory.
• Error handling should be done for incorrect paths.

Foundation tree structure

Create the functionality of a basic tree structure which will represent the directories

• Each file/folder will be a node
• Each node has a boolean to denote if it is a file or a folder
• Should have a linked list of children
• Store pointers to all children
• Optional: Add useful metadata
• Insertion of node, finding a child, traversing the tree should be implemented

Hashtable for Alias

We'll need a hashtable to maintain the Aliases for O(1) finding.

• Should take in two strings, an alias and a string that denotes the path. Use the Alias as the key to store the path.
• Add insertion and finding features
• Error handling when an alias is already used
• Add rehashing feature (assume the size to rehash to, to be available)
• Preferably use quadratic probing