Skip to content

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Program logic

	The program implements a simplified file indexing system based on keywords.
	The files are stored in a doubly linked list.
	Each file has a unique id, a relevance score and a list of associated keywords.
	The keywords are stored in a trie.
	Each terminal node has a reference to the files associated with that keyword.
	The program reads commands one by one, parses them and processes them,
	modifying the system constantly.

#main.c

	Initializes the system.
	Reads the number of operations, then proccess each line, sending them one by
	one to the command proccessing functions.
	Frees the system at the end of the program.

#comenzi.h
#comenzi.c

	This is where all functions that procces commands are located.
	Each function handles one command.
	This file was created to free up the main, to be more organized by command
	type and to make the program logic clearly visible.

	- read_line -> reads dinamically a line and returns it

	Each function:
		- checks if it recognizes the command (returns 1 if yes, otherwise 0)
		- modifies the system if needed
		- prints the corresponding messages

	- proc_com_add -> adds a new file to the system along with its associated
									 keywords
	- proc_com_del -> removes the file and eliminates all its refrences from trie

	- proc_com_addkw -> adds a keyword to an existing file and inserts it into trie
	- proc_com_delkw -> removes a keyword from an existing file and eliminates the
										 the refrence from trie

	- proc_com_find -> searches for a word in the trie and prints the associated
										files in lexicographic order by id
	- proc_com_topk -> searches for a keyword in trie, build a max heap with the
										found files and extracts the top k by score
										if same score, in lexicographic order by id 
	
	- proc_com_print -> traverses the trie and prints all keywords in lexicographic
										 order, with the count and ids in lexicographic order

	- proc_com_prefix -> proceseaza comanda PREFIX

#sistem.h
#sistem.c

	Defines and manages the main structure of the program.

	Structures:
		-syst -> the central structure of the system
						 holds a pointer to the doubly linked list of files
						 holds a pointer to the keyword trie

	There is one function for each of the following:
		- creating and initializing the system
		- freeing the system
		- finding and returning a file by id, along with its position in the list
		daca nu e necesara pozitia, programul pune NULL si nu actualizeaza pozitia
		if position isn't necessary, pos = NULL and it isn't actualized 

#list.h
#list.c

	Implements the doubly linked list used for:
		- the system
		- each file's keyword list
		- the reference list stored in trie terminal nodes

	Structures:
		-node -> node of doubly linked list
						 hold a generic pointer to the data
						 holds a pointer to the previous and next node
		-linked_list -> holds pointer to the head and tail of the list
										holds the size of the list
		-file -> represents a file in the system
						 holds the id and score
						 holds a doubly linked list of associated keywords to the file
						 (the list stores copies of strings)

	There is one function for each of the following:
		- duplicating a string dynamically

		- creating an empty list
		- creating and initializing a file

		- inserting a node at the tail of the list
		- removing and returning the node at the nth position

		- finding and removing a file refrence from a list by pointer
		- checking if a file exists in a list by pointer
		- checking if keyword exists in a file's keywordlist and returning if found

		- sorting a file list lexicographically by id(swaps data pointers inside nodes)

		- freeing a file with its keyword list
		- freeing a node, with or withoud the data stored
		- freeing a list, with or withoud the data stored

#trie.h
#trie.c

	Implements the multiway retrieval tree (trie), used for keyword indexing. 
	Each node corresponds to a letter from the alphabet.
	The terminal nodes hold refrence

	Structures;
		-trie_node -> node of the trie
									holds a pointer to an array of ALPHAPET_SIZE children
									holds the number of children
									end_of_word = remembers if the node represents end of a keyword
									holds a doubly linkest list of pointers to associated files
									in terminal nodes
	
	trie -> holds a pointer to the root node
					holds the number of keywords and of nodes

	There is one function for each of the following:
	 - creating a trie node
	 - creating a trie

	 - inserting a keyword and adding a file reference to the terminal node
	 - searching for a keyword and returning its associated file list
	 - searching for a prefix and returning a list with all files associated

	 - removing a file reference from a terminal node (with a helper)
	 - printing the trie (with a helper)
	 - freeing the trie (with a helper)

#heap.h
#heap.c

	Implements a max heap of file pointers.
	Used for command TOPK.
	Priority is determined by a file's score and if it's the same, then
	lexicographically by id.

	Structures:
		-heap -> holds an array of pointers to files (only references, not the files)
						 holds the current size and capacity

		
	There is one function for each of the following:
		- creating a heap
		- comparing two files by score, if it's the same, then lexicographically by id

		- inserting a file into the heap (with a helper)
		- removing the root and restoring the heap (with a helper)

		- freeing the heap

#utils.h
	Defines the macro DIE.
	I used it for defensive programming throughout the entire program.

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages