Sign in to follow this  
  • entries
    149
  • comments
    510
  • views
    94511

I like trees

Sign in to follow this  

109 views

I spent a lot of time today developing a directory structure for the ResoPack library. I decided to use a tree structure since that will allow an unlimited amount of folders within a ResoPack. Each folder (node) contains a list of files, a reference to its parent, a name, and a list of references to its children.

What I've got so far...

I've created a tree class called DTree. It uses an STL vector to manage an N-ary tree. It includes functions to move around the directory from the current folder (move_up_one_level and move_into_folder). You can also move to a folder path string ("\folder_a\folder_b\"). This function uses a private member to tokenize the folder path into a list of folder strings. This list is then used to navigate from root to the desired folder. The parser function will also accept paths with filenames (I'll need that later).

There are functions to add and delete files, and folders. The delete folder function uses a postorder traversal to flag folders which are to be deleted. Then the master directory list is traversed to find the flagged folders and delete them. STL makes the deletion easy however at every deletion the list must be traversed once again to shift indices that are greater than the deleted folder's index.

The traversal functions are state based and call an operation function, such as print, search, or flag-delete, according to the current operation state. I've also added a function to return the current path as a string.

What's in a file..?

As I mentioned earlier, every node (folder) contains a list of files. Each file structure contains the name, starting point (in bytes) of the file data, and the size of the file's data. This will allow me to find a file within the ResoPack once the directory is loaded from the ResoPack's header which may actually be at the bottom of the file. [smile]
Sign in to follow this  


2 Comments


Recommended Comments

You ever thought about putting an index at the top of the file?

I can't say I know of this ResoPack library, but it sounds fairly similar to other archives??

For a small number of files it probably isn't a problem, but a developer I know implemented a binary searchable index in the header so as to identify the requested file as quick as possible. Retrievable speed was important.

I forget exactly how it worked to be honest, but it allowed a request to be identified in binary sort time (O(Log|n|) ?) based on as few characters as possible.

Just an idea [smile]
Jack

Share this comment


Link to comment
Thanks for the ideas! You wouldn't know about ResoPack because it's what I'm making. [smile]

Files in this archive need to be accessed fast too. I generally access non archived files using a path name "..//media//texture.jpg" or something. No searching involved. So I'm setting this system up to do the same. When you want a file you give it a path name and it locates the file in very few steps. A binary search tree would be good if the path was unknown but here it is required of the user. No searches available at run time. [edit] This was an error in my thinking. Locating a path is a search.

I will be implementing a search for the interface tool and your idea seems easy enough to implement. I suppose I could build the binary tree when the file is loaded or maybe the first time a search is needed. [edit] I was thinking about a general search here.

Something to think about... Thanks again!

[edit] This just occurred to me. Every node has a list of files. Folders can be accessed quickly enough but the list of files should be sorted for a quick binary search of the file. I suppose then I could just keep a sorted index of every sub folder index in every node for an even faster location of the individual folder. I'm really glad that you said something now. We'll see how it turns out tomorrow. O(logn) sounds good to me. [smile]

- Neil

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now