Electronic Document Security

The Tyrell corporation uses a state-of-the-art electronic document system that controls all aspects of document creation, viewing, editing, and distribution. Document security is handled via access control lists (ACLs). An ACL defines a set of entities that have access to the document, and for each entity defines the set of rights that it has. Entities are denoted by uppercase letters; an entity might be a single individual or an entire division. Rights are denoted by lowercase letters; examples of rights are a for append, d for delete, e for edit, and r for read.

The ACL for a document is stored along with that document, but there is also a separate ACL log stored on a separate log server. All documents start with an empty ACL, which grants no rights to anyone. Every time the ACL for a document is changed, a new entry is written to the log. An entry is of the form ExR, where E is a nonempty set of entities, R is a nonempty set of rights, and x is either "+", "–", or "=". Entry E+R says to grant all the rights in R to all the entities in E, entry E–R says to remove all the rights in R from all the entities in E, and entry E=R says that all the entities in E have exactly the rights in R and no others. An entry might be redundant in the sense that it grants an entity a right it already has and/or denies an entity a right that it doesn't have. A log is simply a list of entries separated by commas, ordered chronologically from oldest to most recent. Entries are cumulative, with newer entries taking precedence over older entries if there is a conflict.

Periodically the Tyrell corporation will run a security check by using the logs to compute the current ACL for each document and then comparing it with the ACL actually stored with the document. A mismatch indicates a security breach. Your job is to write a program that, given an ACL log, computes the current ACL.

Input: The input consists of one or more ACL logs, each 3–79 characters long and on a line by itself, followed by a line containing only "#" that signals the end of the input. Logs will be in the format defined above and will not contain any whitespace.

Output: For each log, output a single line containing the log number (logs are numbered sequentially starting with one), then a colon, then the current ACL in the format shown below. Note that (1) spaces do not appear in the output; (2) entities are listed in alphabetical order; (3) the rights for an entity are listed in alphabetical order; (4) entities with no current rights are not listed (even if they appeared in a log entry), so it's possible that an ACL will be empty; and (5) if two or more consecutive entities have exactly the same rights, those rights are only output once, after the list of entities.

Example input:	Example output:
MC-p,SC+c YB=rde,B-dq,AYM+e GQ+tju,GH-ju,AQ-z,Q=t,QG-t JBL=fwa,H+wf,LD-fz,BJ-a,P=aw #	1:CSc 2:AeBerMeYder 3: 4:BHJfwLPaw

Solucion: eds.java



import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;

public class eds {

private BufferedReader bf = null;

public eds() {
}

public static void main(String arg[]) {
eds e = new eds();
try {
File f = new File("eds.in");
e.bf = new BufferedReader(new FileReader(f));
String linea = e.bf.readLine();
int numeroLinea = 0;
while (linea != null && !linea.equals("#")) {
Map<String, String> permisos = new LinkedHashMap<String, String>();
String[] sp = linea.split(",");
for (int i = 0; i < sp.length; i++) {
if (sp[i].indexOf("-") >= 0) {
String[] prs = sp[i].split("-");
for (int j = 0; j < prs[0].length(); j++) {
permisos.put(String.valueOf(prs[0].charAt(j)), e.retirarPermisos((String) permisos.get(String.valueOf(prs[0].charAt(j))), prs[1]));
}
}
if (sp[i].indexOf("+") >= 0) {
String[] prs = new String[2];
prs[0] = sp[i].substring(0, sp[i].indexOf("+"));
prs[1] = sp[i].substring(sp[i].indexOf("+") + 1);
for (int j = 0; j < prs[0].length(); j++) {
permisos.put(String.valueOf(prs[0].charAt(j)), e.agregarPermisos((String) permisos.get(String.valueOf(prs[0].charAt(j))), prs[1]));
}
}
if (sp[i].indexOf("=") >= 0) {
String[] prs = sp[i].split("=");
for (int j = 0; j < prs[0].length(); j++) {
permisos.put(String.valueOf(prs[0].charAt(j)), prs[1]);
}
}
}
System.out.println((numeroLinea++ + 1) + ":" + e.listadoEntidadesPermisos(permisos).replace("null", ""));
linea = e.bf.readLine();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}

public String getOrdenada(String cadena) {
String res = "";
char[] sb = cadena.toCharArray();
for (int k = 0; k < sb.length; k++) {
for (int i = 0; i < sb.length - 1; i++) {
if (sb[i] > sb[i + 1]) {
char tmp = sb[i];
sb[i] = sb[i + 1];
sb[i + 1] = tmp;
}
}
}
for (int i = 0; i < sb.length; i++) {
res += sb[i];
}
return res;
}

public String retirarPermisos(String cadena, String permisos) {
String cadenaRetorno = cadena;
if (cadena != null) {
for (int i = 0; i < permisos.length(); i++) {
cadenaRetorno = cadenaRetorno.replace(String.valueOf(permisos.charAt(i)), "");
}
} else {
cadenaRetorno = "";
}
return cadenaRetorno;
}

public String agregarPermisos(String cadena, String permisos) {
String cadenaRetorno = cadena;
if (cadena != null) {
for (int i = 0; i < permisos.length(); i++) {
if (!cadenaRetorno.contains(String.valueOf(permisos.charAt(i)))) {
cadenaRetorno += String.valueOf(permisos.charAt(i));
}
}
} else {
cadenaRetorno = permisos;
}
return cadenaRetorno;
}

public String listadoEntidadesPermisos(Map<String, String> permisos) {
String permisosRetorno = "";
String[] prm = new String[permisos.keySet().size()];
permisos.keySet().toArray(prm);
ordenarArray(prm);
String permisoAnterior = "";
ArrayList<Mapeo> maps = new ArrayList<Mapeo>();
for (int i = 0; i < prm.length; i++) {
if (!permisos.get(prm[i]).equals("")) {
if (getOrdenada(permisoAnterior).equals(getOrdenada(permisos.get(prm[i])))) {
Mapeo mp = maps.get(maps.size() - 1);
mp.setEntidades(mp.getEntidades().append(prm[i]));
} else {
Mapeo mp = new Mapeo();
mp.setPermisos(permisos.get(prm[i]));
mp.setEntidades(new StringBuffer(prm[i]));
maps.add(mp);
permisoAnterior = permisos.get(prm[i]);
}
}
}
for (Mapeo aux : maps) {
permisosRetorno += aux.getEntidades().toString() + getOrdenada(aux.getPermisos());
}
return permisosRetorno;
}

public void ordenarArray(String[] prm) {
String tmp;
for (int k = 0; k < prm.length; k++) {
for (int i = 0; i < prm.length - 1; i++) {
if (prm[i].compareTo(prm[i + 1]) > 0) {
tmp = prm[i];
prm[i] = prm[i + 1];
prm[i + 1] = tmp;
}
}
}

}
}

class Mapeo {

private StringBuffer entidades;
private String permisos;

public Mapeo() {
}

public Mapeo(StringBuffer entidades, String permisos) {
this.entidades = entidades;
this.permisos = permisos;
}

public StringBuffer getEntidades() {
return entidades;
}

public void setEntidades(StringBuffer entidades) {
this.entidades = entidades;
}

public String getPermisos() {
return permisos;
}

public void setPermisos(String permisos) {
this.permisos = permisos;
}
}