Programming Assignment

CSC 2

1

2 Programming Assignment
Developing a Photo Management Application

College of Computer and Information Sciences
King Saud University

Fall 2020

1 Introduction
The role of a photo management application is to organize photographs so that they can
be easily accessed. In order to help organize photos, the user can provide tags to describe
the content of the photos. A tag is a keyword associated with a photo. For example, we
can associate the tag ”vacation” to any photo taken during a vacation. In Table 1, you
may find some examples of photos and the tags that are used to describe them.

Table 1: Example of photos with associated tags.

hedgehog
animal, hedgehog,
apple, grass, green

bear
animal, bear, cub,
grass, wind

butterfly1
insect, butterfly,
flower, color

butterfly2
insect, butterfly,
black, flower

fox
animal, fox, tree,
forest, grass

panda
animal, bear,
panda, grass

wolf
animal, wolf,
mountain, sky,
snow, cloud

raccoon
animal, raccoon,
log, snow

1

The photo manager organizes the photos into albums created by the user. An album
is identified by a unique name and regroups photos that satisfy certain conditions. For
the purpose of this assignment, the conditions used to create albums consist in a sequence
of tags separated by ”AND”:

Tag1 AND Tag2 AND Tag3

Photos that contain all specified tags will appear in the album. An empty tag list matches
all photos.

Example 1. Using the photos of Table 1, the album with the condition bear, will con-
tain two photos (that of the panda and the grizzly bear). The album with the condition
animal AND grass will contain four photos (hedgehog, grizzly bear, fox and panda). The
albbum with no tags will contain all eight photos.

2 Inverted index
In order to accelerate the search for photos, it is possible to store the tags in an inverted
index. The idea is that instead of having the photos point to the tags, the inverted index
will store all the tags, and each tag will point to all the photos that contain it.

The following is an example showing a partial inverted index for the photos shown
above:

animal → hedgehog , bear , fox , panda , wolf , racoon
apple → hedgehog
bear → bear , panda
black → butterfly2
butterfly → butterfly1 , butterfly2
…

You are required to:

1. Represent the photos-tags association using an inverted index stored in the class
PhotoManager.

2. Use a data structure that allows O(log n) in average to search for a tag.

3 Requirements
You are required to implement the following specification:

public class Photo {
// Constructor
public Photo(String path, LinkedList tags);
// Return the path (full file name) of the photo. A photo is uniquely identified

by its path.
public String getPath();
// Return all tags associated with the photo
public LinkedList getTags();

}

public class Album {
// Constructor
public Album(String name, String condition, PhotoManager manager);
// Return the name of the album
public String getName();
// Return the condition associated with the album
public String getCondition();
// Return the manager
public PhotoManager getManager();
// Return all photos that satisfy the album condition
public LinkedList getPhotos();
// Return the number of tag comparisons used to find all photos of the album
public int getNbComps();

}

public class PhotoManager {
// Constructor
public Photomanager();
// Add a photo
public void addPhoto(Photo p);
// Delete a photo
public void deletePhoto(String path);
// Return the inverted index of all managed photos
public BST> getPhotos();

}

Remark 1. The list of photos that belong to the album is determined at the time when
the method getPhotos is called, not when the album is created.

4 Deliverables and rules
You must deliver:

1. Source code submission to Web-CAT.

The submission deadline is: 06/12/2020.
You have to read and follow the following rules:

1. The specification given in the assignment (class and interface names, and
method signatures) must not be modified. Any change to the specification results
in compilation errors and consequently the mark zero.

2. All data structures used in this assignment must be implemented by the student.
The use of Java collections or any other data structures library is strictly forbidden.

3. This assignment is an individual assignment. Sharing code with other students will
result in harsh penalties.

4. Posting the code of the assignment or a link to it on public servers, social platforms
or any communication media including but not limited to Facebook, Twitter or
WhatsApp will result in disciplinary measures against any involved parties.

5. The submitted software will be evaluated automatically using Web-Cat.

6. All submitted code will be automatically checked for similarity, and if plagiarism
is confirmed penalties will apply.

7. You may be selected for discussing your code with an examiner at the discretion of
the teaching team. If the examiner concludes plagiarism has taken place, penalties
will apply.

class Node {
public T data;
public Node next;
public Node (T val) {
data = val;
next = null;
}
}
public class LinkedList {
private Node head;
private Node current;
public LinkedList () {
head = current = null;
}
public boolean empty () {
return head == null;
}
public boolean last () {
return current.next == null;
}
public boolean full () {
return false;
}
public void findFirst () {
current = head;
}
public void findNext () {
current = current.next;
}
public T retrieve () {
return current.data;
}
public void update (T val) {
current.data = val;
}
public void insert (T val) {
Node tmp;
if (empty()) {
current = head = new Node (val);
}
else {
tmp = current.next;
current.next = new Node (val);
current = current.next;
current.next = tmp;
}
}
public void remove () {
if (current == head) {
head = head.next;
}
else {
Node tmp = head;
while (tmp.next != current)
tmp = tmp.next;
tmp.next = current.next;
}
if (current.next == null)
current = head;
else
current = current.next;
}
}

public class Album {
// Constructor
public Album(String name, String condition, PhotoManager manager);
// Return the name of the album
public String getName();
// Return the condition associated with the album
public String getCondition();
// Return the manager
public PhotoManager getManager();
// Return all photos that satisfy the album condition
public LinkedList getPhotos();
// Return the number of tag comparisons used to find all photos of the album
public int getNbComps();
}

public class Photo {
// Constructor
public Photo(String path, LinkedList tags);
// Return the path (full file name) of the photo. A photo is uniquely identified by its path.
public String getPath();
// Return all tags associated with the photo
public LinkedList getTags();
}

public class PhotoManager {
// Constructor
public Photomanager();
// Add a photo
public void addPhoto(Photo p);
// Delete a photo
public void deletePhoto(String path);
// Return the inverted index of all managed photos
public BST> getPhotos();
}

class BSTNode {
public String key;
public T data;
public BSTNode left, right;
public BSTNode(String key, T data) {
this.key = key;
this.data = data;
left = right = null;
}
}
public class BST {
private BSTNode root, current;
public BST() {
current = root = null;
}
public void clear() {
current = root = null;
}
public boolean empty() {
return root == null;
}
public boolean full() {
return false;
}
public T retrieve() {
return current.data;
}
public boolean findKey(String k) {
BSTNode p = root;
while (p != null) {
current = p;
if (k.compareTo(p.key) == 0) {
return true;
} else if (k.compareTo(p.key) < 0) { p = p.left; } else { p = p.right; } } return false; } public boolean insert(String k, T val) { if (root == null) { current = root = new BSTNode(k, val);
return true;
}
BSTNode p = current;
if (findKey(k)) {
current = p;
return false;
}
BSTNode tmp = new BSTNode(k, val);
if (k.compareTo(current.key) < 0) { current.left = tmp; } else { current.right = tmp; } current = tmp; return true; } public boolean removeKey(String k) { // Search for k String k1 = k; BSTNode p = root;
BSTNode q = null; // Parent of p
while (p != null) {
if (k1.compareTo(p.key) < 0) { q =p; p = p.left; } else if (k1.compareTo(p.key) > 0) {
q = p;
p = p.right;
} else { // Found the key
// Check the three cases
if ((p.left != null) && (p.right != null)) { // Case 3: two
// children
// Search for the min in the right subtree
BSTNode min = p.right;
q = p;
while (min.left != null) {
q = min;
min = min.left;
}
p.key = min.key;
p.data = min.data;
k1 = min.key;
p = min;
// Now fall back to either case 1 or 2
}
// The subtree rooted at p will change here
if (p.left != null) { // One child
p = p.left;
} else { // One or no children
p = p.right;
}
if (q == null) { // No parent for p, root must change
root = p;
} else {
if (k1.compareTo(q.key) < 0) { q.left = p; } else { q.right = p; } } current = root; return true; } } return false; // Not found } }