Login
1. Overview
2. Undo/Redo (Stack)
Ex 1: A Simple Editor
Ex 2: The undo() Method
Ex 3: redo()
3. Job Processing (Queue)
Ex 4: Parallel Workers
Ex 5: Saving Results
Ex 6: Dynamic Tasks
4. File System (Graph)
Ex 7: A Simple File System
Ex 8: Directory Search
Ex 9: Symbolic Links
1. Overview
1. Weekly quiz
available on eLearning (https://elearning.sydney.edu.au/)
2. Weekly task
due Monday at 6pm
Normal stream: Ex 2: The undo() Method
Advanced stream: Ex 3: redo()
Note
This tutorial is more of a collection of fun & interesting exercises than a complement of the lecture
content. For this reason, the applications covered in the lectures may not match the exercises
presented here.
Week 12 Tutorial
Applications of Data Structures1
Instead, we have tried to choose applications that present an interesting implementation in some
way. Since applications of data structures is a wide and far-reaching topic, it deserves separate
analyses from both theoretical and practical perspectives.
2. Undo/Redo (Stack)
One application of the stack data structure is as an undo/redo history. Undo and redo are two
operations available in many applications that can un-perform and re-perform previous commands.
For example, in a text editor, you may want to type the word "The". To do this, you press each key on the
keyboard – T, h, and e – and the letters appear on the screen to say "T", "Th" and "The" as expected.
However, if you change your mind after typing a letter, you can undo that keypress, which will take you
back to the state the editor was in before the key was pressed. For example, if you undo after typing the
"e", you go back to the previous state of "Th", like so:
The undo operation is no longer available once you have undone all available history (and you reach the
start state again).
The state history can be implemented using a stack, since we only need to keep track of the current state
at any given time (to display it on the screen). To undo the last operation, we just p o p ( ) it off the stack.
The r e d o ( ) operation re-performs the last undo. For example, if we called r e d o ( ) after the scenario
above, it would put our "e" back at the end of the word, producing "The" again.
2.1. Ex 1: A Simple Editor
We'll start by creating a basic editor, and slowly add more functionality as we go.
Start by creating a new project and class T e x t E d i t o r, with the following structure:a
b
c
d
2
1 . p u b l i c c l a s s T e x t E d i t o r {
2 . p u b l i c T e x t E d i t o r ( ) ;
3 .
4 . / / C a l l e d w h e n t h e g i v e n c h a r a c t e r i s t y p e d i n t o t h e e d i t o r
5 . p u b l i c v o i d t y p e C h a r a c t e r ( c h a r c ) ;
6 .
7 . / / C a l l e d w h e n t h e b a c k s p a c e k e y i s p r e s s e d ; h a s n o e f f e c t i f t h e d o c u m e n
t i s e m p t y
8 . p u b l i c v o i d d e l e t e L a s t C h a r a c t e r ( ) ;
9 .
1 0 . / / R e t u r n s t h e t e x t t h e e d i t o r s h o u l d d i s p l a y o n t h e s c r e e n
1 1 . p u b l i c S t r i n g r e a d T e x t ( ) ;
1 2 .
1 3 . / / U n d o e s t h e p r e v i o u s a c t i o n
1 4 . p u b l i c v o i d u n d o ( ) ;
1 5 . }
Also import your S t a c k project from the Week 4 Tutorial into your workspace, and add it to the
build path for T e x t E d i t o r (we'll need it later).
Warning
Remember to leave the C o p y p r o j e c t s i n t o w o r k s p a c e checkbox unchecked
when importing projects from other workspaces. This way, Eclipse only links to the
project (and doesn't duplicate any files).
We'll now implement each of the methods, leaving u n d o ( ) blank for now.
Member variables
We'll need an internal variable to keep track of the text in our document, so add the
string t e x t like so:
1 . p r i v a t e S t r i n g t e x t ;
Constructor
Fill in the constructor to initialise t e x t to an empty string.
t y p e C h a r a c t e r ( )
You can use the plus operator to add characters to a string, so add c to our document
like so:
1 . t e x t + = c
d e l e t e L a s t C h a r a c t e r ( )
To delete the last character, we can use the . s u b s t r i n g ( ) method on our document
text.e
a
b
c
3
. s u b s t r i n g ( ) takes two parameters: the index to start at (inclusive), and the index to
end at (exclusive). So, to take a substring of every character except the last one, we
want to call . s u b s t r i n g ( ) with 0 and n − 1 (where n is the length of the string), like
so:
1 . t e x t = t e x t . s u b s t r i n g ( 0 , t e x t . l e n g t h ( ) - 1 ) ;
r e a d T e x t ( )
Just return t e x t, the contents of our document.
Great! Time to add some tests to check the functionality of our T e x t E d i t o r.
t e s t C o n s t r u c t i o n ( )
Ensure that a new T e x t E d i t o r has r e a d T e x t ( ) returning an empty string.
t e s t T y p e C h a r a c t e r ( )
Create a new T e x t E d i t o r, then check that r e a d T e x t ( ) returns "T", "Th" and then
"The" respectively when t e s t T y p e C h a r a c t e r ( ) is called with 'T', 'h' and 'e'.
t e s t D e l e t e L a s t C h a r a c t e r ( )
Create a new T e x t E d i t o r and enter "T", "h" and "e", then ensure
d e l e t e L a s t C h a r a c t e r ( ) causes r e a d T e x t ( ) to return "Th", "T" and "" (empty
string) when called 3 times.
Now run your tests. Hopefully they all passed!
EXERCISE 1 COMPLETED
2.2. Ex 2: The undo() Method
Now that we have a working T e x t E d i t o r, we can implement the u n d o ( ) method and check we didn't
break any existing functionality.
You will need to make the following changes to your T e x t E d i t o r:
1. Replace t e x t with a B a s i c S t a c k object which will store each change in the document (as shown in
the diagram in the Undo/Redo Section)
2. Initialise the stack to an empty one in the constructor
3. Change r e a d T e x t ( ) to just return the string at the top of the stack (or an empty string if the stack is
empty)
4. After a character is added or deleted, add the resultant string to the top of the stack
5. When u n d o ( ) is called, remove the string at the top of the stack
Note
Since our B a s i c S t a c k can throw an E m p t y S t a c k E x c e p t i o n, use this to your advantage to
detect when the stack is empty.
✔For example, in the r e a d T e x t ( ) method, instead of writing:
1 . i f ( ! t e x t . i s E m p t y ( ) ) {
2 . r e t u r n t e x t . p e e k ( ) ;
3 . } e l s e {
4 . r e t u r n " " ;
5 . }
you can write:
1 . t r y {
2 . r e t u r n t e x t . p e e k ( ) ;
3 . } c a t c h ( E m p t y S t a c k E x c e p t i o n e ) {
4 . r e t u r n " " ;
5 . }
This way, you also don't need to change the signatures for any of the methods (to add a throw
clause).
Test your new u n d o ( ) method by adding a new test, t e s t U n d o ( ), which performs the following steps:
1. Creates a new T e x t E d i t o r and adds "T", "h" and "e" as before
2. Calls u n d o ( ) and checks that r e a d T e x t ( ) returns "Th"
3. Calls d e l e t e L a s t C h a r a c t e r ( ) then u n d o ( ) and checks that r e a d T e x t ( ) returns "Th"
EXERCISE 2 COMPLETED
2.3. Ex 3: redo()
Extend your T e x t E d i t o r with a r e d o ( ) method (which has the same signature as u n d o ( ), but a
different name).
r e d o ( ) works the same as u n d o ( ), but re-applies any previously un-done actions. For example, if you
enter "T", "h" and "e", then call u n d o ( ) to undo adding the "e", you can call r e d o ( ) to add the "e" back
(it re-does the last u n d o ( ) action).
Before u n d o ( ) is called the first time, r e d o ( ) will have no effect. Similarly, calling t y p e C h a r a c t e r ( )
or d e l e t e L a s t C h a r a c t e r ( ) will 'reset' the redo history (and calling r e d o ( ) without u n d o ( ) will have
no effect).
Implement r e d o ( ) by using another stack in a similar way to u n d o ( ).
To test your r e d o ( ) method, add a test t e s t R e d o ( ) which:
1. Creates a new T e x t E d i t o r and adds "T", "h" and "e" as before
2. Calls u n d o ( ) and then r e d o ( ), and checks that r e a d T e x t ( ) returns "The"
3. Calls r e d o ( ) again and checks that r e a d T e x t ( ) still returns "The"
4. Calls d e l e t e L a s t C h a r a c t e r ( ) and r e d o ( ), then checks r e a d T e x t ( ) returns "Th"
5. Calls u n d o ( ) twice and then r e d o ( ) twice, and checks that r e a d T e x t ( ) returns "The" and then
"Th"
✔EXERCISE 3 COMPLETED
3. Job Processing (Queue)
One common use of a queue data structure is for storing jobs entered by users.
Users (or clients), add jobs to the queue, whilst servers (or workers) remove jobs and perform them.
Usually, a set of servers await jobs from the queue, whilst users add those jobs, like so:
One problem with using a regular queue for this system is that a lot of memory is wasted as our queue fills
and empties. One improvement we can make is to use a circular buffer, allowing our system to use a
fixed amount of memory:
✔In this tutorial, we'll implement a basic queue without users, to give you an idea of what it's like to
implement a fully-functional dynamic job system.
3.1. Ex 4: Parallel Workers
Create a new project called J o b P r o c e s s o r. We'll start by implementing a basic job queue, filling it with
jobs, and then spawn (Creating a thread, so that it can start executing in parallel with the rest of the
program) some worker threads to fetch jobs out of the queue and run them. For now, we'll make each job
just take two numbers and add them.
Since this is quite a complex project, we're going to need to break it into a few separate class files which
each perform a simple task by themselves. Although there are many correct ways of implementing this,
breaking it down this way will help you understand how each of the pieces work, as well as how they fit
together.
Firstly, we'll need a J o b, which stores everything we need to know about the job in order to complete it,
so add the following structure to J o b . j a v a:
1 . p u b l i c c l a s s J o b {
2 . / / C r e a t e s a n e w j o b w i t h t h e g i v e n n u m b e r s
3 . p u b l i c J o b ( i n t f i r s t N u m b e r , i n t s e c o n d N u m b e r ) ;
4 .
5 . p u b l i c i n t g e t F i r s t N u m b e r ( ) ;
6 . p u b l i c i n t g e t S e c o n d N u m b e r ( ) ;
7 . }
Next, we'll need a J o b Q u e u e that can store these jobs, which is where our workers will be able to fetch the
jobs from. Add the following structure to J o b Q u e u e . j a v a, and implement it with a queue (or just an
ArrayList):
1 . p u b l i c c l a s s J o b Q u e u e {
2 . / / C r e a t e s a n e w e m p t y j o b q u e u e
3 . p u b l i c J o b Q u e u e ( ) ;
4 .
5 . / / A d d s t h e g i v e n j o b t o t h e q u e u e
6 . p u b l i c v o i d a d d J o b ( J o b j ) ;
7 .
8 . / / R e m o v e s t h e j o b a t t h e f r o n t o f t h e q u e u e a n d r e t u r n s i t .
9 . / / R e t u r n s n u l l i f t h e r e a r e n o j o b s l e f t i n t h e q u e u e .
1 0 . p u b l i c s y n c h r o n i z e d J o b t r y T a k e J o b ( ) ;
1 1 . }
Note
The s y n c h r o n i z e d keyword in t r y T a k e J o b prevents multiple threads from executing this
method at the same time. In this case, that means that only one worker can call t r y T a k e J o b at a
time (other workers that call it will have to wait for the first one to finish), meaning that we don't
have to worry about the race condition (When a parallel program can execute incorrectly as a
result of events occuring in a specific order) caused from two workers trying to take the same job
at the same time.Now that we have jobs and a queue to place them in, we'll need to create workers to perform the jobs.
Since our workers will be threads (Portions of a program that run at the same time), we'll need to extend
the T h r e a d parent class. The r u n ( ) method will be the body of the executing thread (so it will execute
the r u n ( ) method, and when the r u n ( ) method returns, it will die).
Create a new class W o r k e r with the following structure (the r u n ( ) method is filled in for you):
1 . p u b l i c c l a s s W o r k e r e x t e n d s T h r e a d {
2 . / / C r e a t e a n e w W o r k e r w i t h t h e g i v e n q u e u e
3 . p u b l i c W o r k e r ( J o b Q u e u e q u e u e ) ;
4 .
5 . / / W i l l r u n w h e n t h e t h r e a d i s s t a r t e d
6 . / / R u n s i n p a r a l l e l w i t h a l l o t h e r s t a r t e d t h r e a d s
7 . @ O v e r r i d e
8 . p u b l i c v o i d r u n ( ) {
9 . w h i l e ( t r u e ) {
1 0 . / / T r y a n d g e t a f r e e j o b
1 1 . J o b j = q u e u e . t r y T a k e J o b ( ) ;
1 2 . i f ( j = = n u l l )
1 3 . r e t u r n ;
1 4 .
1 5 . / / P e r f o r m t h e j o b
1 6 . i n t r e s u l t = j . g e t F i r s t N u m b e r ( ) + j . g e t S e c o n d N u m b e r ( ) ;
1 7 . / / F o r n o w , w e w o n ' t s a v e t h e r e s u l t a n y w h e r e
1 8 . }
1 9 . }
2 0 . }
Finally, we're ready to put it all together. Create one more class J o b P r o c e s s o r with the following
structure (the s t a r t W o r k e r s ( ) method is given for you):1 . p u b l i c c l a s s J o b P r o c e s s o r {
2 . p u b l i c J o b Q u e u e q u e u e ;
3 .
4 . / / C r e a t e s a n e w j o b p r o c e s s o r
5 . p u b l i c J o b P r o c e s s o r ( ) ;
6 .
7 . / / R e t u r n s t h e q u e u e f o r t h i s j o b p r o c e s s o r
8 . p u b l i c J o b Q u e u e g e t Q u e u e ( ) ;
9 .
1 0 . / / S t a r t s n w o r k e r t h r e a d s , w h i c h w i l l p e r f o r m a l l j o b s i n t h e q u e u e ,
1 1 . / / a n d w a i t s f o r t h e m t o c o m p l e t e
1 2 . p u b l i c v o i d s t a r t W o r k e r s ( i n t n ) {
1 3 . L i s t < W o r k e r > w o r k e r s = n e w A r r a y L i s t < W o r k e r > ( ) ;
1 4 .
1 5 . / / C r e a t e t h e w o r k e r s
1 6 . f o r ( i n t i = 0 ; i < n ; i + + ) {
1 7 . w o r k e r s . a d d ( n e w W o r k e r ( q u e u e ) ) ;
1 8 . }
1 9 .
2 0 . / / S t a r t t h e w o r k e r s
2 1 . f o r ( W o r k e r w : w o r k e r s ) {
2 2 . w . s t a r t ( ) ;
2 3 . }
2 4 .
2 5 . / / W a i t f o r t h e w o r k e r s t o c o m p l e t e
2 6 . f o r ( W o r k e r w : w o r k e r s ) {
2 7 . t r y {
2 8 . w . j o i n ( ) ;
2 9 . } c a t c h ( I n t e r r u p t e d E x c e p t i o n e ) {
3 0 . / / T h i s o c c u r s w h e n a t h r e a d r e c e i v e s a n i n t e r r u p t w h i l e w e w e r e w a i t i
n g f o r i t
3 1 . / / N o n e e d t o d o a n y t h i n g : t h e t h r e a d h a s a l r e a d y q u i t
3 2 . }
3 3 . }
3 4 . }
3 5 . }
You'll need to fill in the other methods, as well as implement the J o b Q u e u e.
To test your system, create two tests in J o b P r o c e s s o r T e s t that just create a J o b P r o c e s s o r and start
some workers (since we can't test whether the jobs actually complete yet). Call the first test
t e s t S p a w n S i n g l e W o r k e r ( ) (which passes 1 to s t a r t W o r k e r s ( )) and call the second test
t e s t S p a w n M u l t i p l e W o r k e r s ( ) (which passes something larger than 1, such as 3).
You can create a job processor and spawn workers like so:1 . J o b P r o c e s s o r j = n e w J o b P r o c e s s o r ( ) ;
2 . j . g e t Q u e u e ( ) . a d d J o b ( n e w J o b ( 5 , 7 ) ) ;
3 . j . g e t Q u e u e ( ) . a d d J o b ( n e w J o b ( 1 , 4 ) ) ;
4 . j . g e t Q u e u e ( ) . a d d J o b ( n e w J o b ( 2 , - 1 ) ) ;
5 .
6 . j . s t a r t W o r k e r s ( 3 ) ;
EXERCISE 4 COMPLETED
3.2. Ex 5: Saving Results
So far, our job processing system is fairly interesting, but we can't actually see any of the results. To do
this, we will need to create a second queue (or just a list, in fact) which just stores the results, and have a
synchronous method on it that adds a result (which will allow threads to call it safely in parallel).
To implement saving results in our system, you will need to make the following changes to our current job
processor:
1. Create a new class, R e s u l t s Q u e u e, which is very similar to a J o b Q u e u e but has the add method
synchronized (since this is the method the worker threads will be calling). Give your new class the
following structure:
1 . p u b l i c c l a s s R e s u l t s Q u e u e {
2 . / / C r e a t e s a n e w e m p t y r e s u l t s q u e u e
3 . p u b l i c R e s u l t s Q u e u e ( ) ;
4 .
5 . / / A d d t h e g i v e n r e s u l t t o t h e q u e u e
6 . p u b l i c s y n c h r o n i z e d v o i d a d d R e s u l t ( I n t e g e r j ) ;
7 .
8 . / / R e t u r n s a l l r e s u l t s i n t h e q u e u e
9 . p u b l i c L i s t < I n t e g e r > g e t A l l R e s u l t s ( ) ;
1 0 . }
Note
It might feel like we could just use an A r r a y L i s t here, rather than having to make our own
R e s u l t s Q u e u e. However, the A r r a y L i s t class is not thread-safe (The data structure does
not expect to be called by multiple threads at the same time, so it may have race conditions),
so it could result in unexpected behaviour.
2. Add a new R e s u l t s Q u e u e to the J o b P r o c e s s o r class (and initialise it in the constructor)
3. Add a method with the following signature to the J o b P r o c e s s o r, which returns the contents of
R e s u l t s Q u e u e:
1 . p u b l i c L i s t < I n t e g e r > g e t R e s u l t s ( ) ;
4. Modify the constructor for a W o r k e r to take a R e s u l t s Q u e u e and save it (so it knows where to put
the results)
5. Modify the r u n ( ) method for a W o r k e r to save the result to its R e s u l t s Q u e u e after the job is
✔complete
6. Update the s t a r t W o r k e r s ( ) method in J o b P r o c e s s o r to pass its R e s u l t s Q u e u e to the new
W o r k e r constructor
To test your changes, you can update your tests from before to call . g e t R e s u l t s ( ) on the
J o b P r o c e s s o r and check the contents are the correct results for the tasks.
Note
Since the threads execute in parallel, they can complete in an unpredictable order. So, instead of
using a s s e r t E q u a l s ( ) to check the results are correct, check the results list contains all the
correct values and has the correct size.
EXERCISE 5 COMPLETED
3.3. Ex 6: Dynamic Tasks
Extend your job processing system to allow all kinds of jobs, not just addition. To start with, you could
support addition, subtraction, division and multiplication.
Note
You can implement the various types of jobs however you'd like. Some ways might include using
an e n u m to determine the job's type, or making various subclasses of J o b (or implementations,
by turning J o b into an interface) for each of the different types of jobs you would like to support.
When you're done, add appropriate tests for each of your new types of jobs.
EXERCISE 6 COMPLETED
4. File System (Graph)
File systems organise and give structure to the way we store files on disk. Although some people think a
filesystem can be implemented using a Tree, file systems actually support linking (The ability to reference
one file from another file in a file system) (such as Windows shortcuts or symbolic links), meaning they are
actually implemented using a directed graph.
For example, suppose we had the following directory structure in our file system:
1. A root directory (the outermost folder)
2. A file form.pdf in the root directory
3. A folder work/ in the root directory
4. A file notes.txt in the work directory
5. A file form.pdf in the work directory
In this case, our file system might look like this:
✔
✔Suppose the form.pdf file in the root directory is actually not a file, but a link to the form.pdf file in the work
directory. Now our file system contains a link, which looks like:As you can see, these links create non-tree edges in the structure, making it a graph.
4.1. Ex 7: A Simple File System
You'll want to start by importing your W e i g h t e d G r a p h project from the Week 9 Tutorial.
Now create a project and class F i l e S y s t e m, with G r a p h on the build path. Give your new class the
following structure:
1 . p u b l i c c l a s s F i l e S y s t e m {
2 . p u b l i c F i l e S y s t e m ( ) ;
3 .
4 . / / C r e a t e s a f o l d e r a t t h e g i v e n p a t h w i t h t h e g i v e n n a m e
5 . / / I f a n y f o l d e r s o n t h i s p a t h d o n o t e x i s t , d o n o t h i n g
6 . p u b l i c v o i d c r e a t e F o l d e r ( S t r i n g p a t h , S t r i n g n a m e ) ;
7 .
8 . / / C r e a t e s a f i l e a t t h e g i v e n p a t h w i t h t h e g i v e n n a m e
9 . / / I f a n y f o l d e r s o n t h i s p a t h d o n o t e x i s t , d o n o t h i n g
1 0 . p u b l i c v o i d c r e a t e F i l e ( S t r i n g p a t h , S t r i n g n a m e ) ;
1 1 .
1 2 . / / R e t u r n s a l i s t o f f i l e n a m e s a t t h i s p a t h
1 3 . p u b l i c L i s t < S t r i n g > g e t F i l e L i s t ( S t r i n g p a t h ) ;
1 4 . }
For example, to build the example file system from before, we could do the following:
1 . / / C r e a t e t h e f i l e s y s t e m
2 . F i l e S y s t e m f = n e w F i l e S y s t e m ( ) ;
3 .
4 . / / C r e a t e t h e f i l e s a n d f o l d e r s , a s s u m i n g t h e / f o l d e r a l r e a d y e x i s t s
5 . f . c r e a t e F i l e ( " / " , " f o r m . p d f " ) ;
6 . f . c r e a t e F o l d e r ( " / " , " w o r k " ) ;
7 . f . c r e a t e F i l e ( " / w o r k " , " n o t e s . t x t " ) ;
8 . f . c r e a t e F i l e ( " / w o r k " , " f o r m . p d f " ) ;
9 .
1 0 . / / G e t a l i s t o f f o l d e r s i n / w o r k
1 1 . f . g e t F i l e L i s t ( " / w o r k " ) ; / / R e t u r n s [ " n o t e s . t x t " , " f o r m . p d f " ]
You can assume that filenames will always be correctly constructed in the following valid format:
1. Filenames will always begin with a forward slash
2. Filenames will never end with a forward slash
3. Folder and file names will never contain forward slashes
Hint
You can use a queue to help parse your path. After breaking the path into parts, dequeue each
part one-at-a-time and try to find it in your current location in the graph.
You are free to implement the file system however you want, but we recommend you use the
W e i g h t e d D i r e c t e d G r a p h class we have already implemented.Hint
To distinguish between different node types (files and folders), you will need to store different
objects at different places in the graph.
You can do this using polymorphism (An object of a child class behaves the same as an object of
the parent class). For example, you can create an abstract F i l e S y s t e m E n t r y class to store in
the graph:
1 . a b s t r a c t c l a s s F i l e S y s t e m E n t r y { }
And you can create a new class for each type of node you want to store – in this case, a F i l e
and F o l d e r:
1 . c l a s s F i l e e x t e n d s F i l e S y s t e m E n t r y { }
2 . c l a s s F o l d e r e x t e n d s F i l e S y s t e m E n t r y { }
Now you can use the i n s t a n c e o f operator to check whether a node is a F i l e or F o l d e r:
1 . F i l e S y s t e m E n t r y f = . . . ;
2 . i f ( f i n s t a n c e o f F i l e ) {
3 . / / . . . D o s o m e t h i n g s p e c i f i c t o f i l e s h e r e
4 . } e l s e i f ( f i n s t a n c e o f F o l d e r ) {
5 . / / . . . D o s o m e t h i n g s p e c i f i c t o f o l d e r s h e r e
6 . }
Rather than providing test cases, design your own tests that test your file system as thoroughly as you
can. Depending on your implementation, you may need a more thorough set of test cases for particular
areas of your code.
EXERCISE 7 COMPLETED
4.2. Ex 8: Directory Search
Add a new method to your file system with the following signature:
1 . / / R e t u r n s t r u e i f a f i l e w i t h t h e g i v e n n a m e e x i s t s i n
2 . / / t h e g i v e n p a t h o r a n y p a t h s b e n e a t h i t
3 . p u b l i c b o o l e a n f i n d F i l e ( S t r i n g p a t h , S t r i n g n a m e ) ;
Given a filename and a path, this method should recursively search all files within all folders in this path
looking for a file with the given name.
For example, f i n d F i l e ( " / " , " n o t e s . t x t " ) should return true (since notes.txt exists inside the root
directory), but f i n d F i l e ( " / w o r k " , " t e s t . t x t " ) should return false (since there is no file with this
name in that folder or any of its subfolders).
Test your method by adding the following tests:
1. Ensure that f i n d F i l e ( " / " , " n o t e s . t x t " ) returns false in an empty F i l e S y s t e m
✔2. Ensure that f i n d F i l e ( " / " , " n o t e s . t x t " ) returns true in the sample F i l e S y s t e m
3. Ensure that f i n d F i l e ( " / w o r k " , " d o e s N o t E x i s t . t x t " ) returns false in the sample F i l e S y s t e m
Hint
A previously implemented traversal method on W e i g h t e d D i r e c t e d G r a p h can help you here.
EXERCISE 8 COMPLETED
4.3. Ex 9: Symbolic Links
Finally, let's complete our file system by adding support for symbolic links.
Add a method with the following signature to F i l e S y s t e m:
1 . / / C r e a t e s a s y m b o l i c l i n k a t t h e g i v e n p a t h t o t h e g i v e n p a t h
2 . / / e . g . c r e a t e L i n k ( ' / f o r m . p d f ' , ' / w o r k / f o r m . p d f ' ) w i l l c r e a t e a l i n k ' / f o r m . p d f ' w h i c h
p o i n t s
3 . / / t o ' / w o r k / f o r m . p d f ' ( ' f o r m . p d f ' i n t h e r o o t d i r e c t o r y t h a t l i n k s t o ' / w o r k / f o r
m . p d f ' )
4 . / / e . g . c r e a t e L i n k ( ' / f o o ' , ' / w o r k ' ) w i l l c r e a t e a f o l d e r ' / f o o ' w h i c h i s a l i n k t o ' / w
o r k ' , a n d
5 . / / c o n t a i n s a l l t h e s a m e f i l e s a n d f o l d e r s a s ' / w o r k '
6 . p u b l i c v o i d c r e a t e L i n k ( S t r i n g p a t h , S t r i n g p a t h T o L i n k T o ) ;
You can tell whether the arguments are for files or folders as folders will not contain a dot (since they have
no file extension).
You may have to update some of your existing methods to ensure that they still work with symbolic links.
Test your new changes by adding the following tests:
1. Copy your test for g e t F i l e L i s t ( ) to instead create a symbolic link for f o r m . p d f in the root
directory (rather than a different file), and ensure the test still works correctly
2. Copy the above test, but rename the file '/work/form.pdf' to '/work/newform.pdf', and ensure that the
test still works correctly (but expects 'newform.pdf' where it previously expected 'form.pdf')
3. Create a link at '/work-link' which links to '/work', and ensure that g e t F i l e L i s t ( " / w o r k " ) and
g e t F i l e L i s t ( " / w o r k - l i n k " ) both work as expected. Then, create two files using
c r e a t e F i l e ( " / w o r k " , " a . p d f " ) and c r e a t e F i l e ( " / w o r k - l i n k " , " b . p d f " ) and ensure that
f i n d F i l e ( ) returns true for all 4 combinations of files at this location (work a, work b, work-link a and
work-link b).
4. Create a symbolic link to a folder that already contains a symbolic link to another folder. Add a file
inside the second folder and try and find it using all combinations of f i n d F i l e ( ).
5. Create a symbolic link '/cycle' that links back to the root. Ensure that g e t F i l e L i s t ( " / " ) and
g e t F i l e L i s t ( " / c y c l e " ) contain the same contents, but f i n d F i l e ( " / c y c l e " , " t e s t . t x t " )
returns false.
EXERCISE 9 COMPLETED
✔
✔Designed and built for INFO1105/INFO1905 Data Structures at Sydney University (http://sydney.edu.au/)
© 2013
