src/com/owncloud/android/files/services/IndexedForest.java

   1 /* ownCloud Android client application
   2  *   Copyright (C) 2015 ownCloud Inc.
   3  *
   4  *   This program is free software: you can redistribute it and/or modify
   5  *   it under the terms of the GNU General Public License version 2,
   6  *   as published by the Free Software Foundation.
   7  *
   8  *   This program is distributed in the hope that it will be useful,
   9  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  *   GNU General Public License for more details.
  12  *
  13  *   You should have received a copy of the GNU General Public License
  14  *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  15  *
  16  */
  17
  18 package com.owncloud.android.files.services;
  19
  20 import android.accounts.Account;
  21 import android.util.Pair;
  22
  23 import com.owncloud.android.datamodel.OCFile;
  24
  25 import java.io.File;
  26 import java.util.HashSet;
  27 import java.util.Iterator;
  28 import java.util.Set;
  29 import java.util.concurrent.ConcurrentHashMap;
  30 import java.util.concurrent.ConcurrentMap;
  31
  32 /**
  33  *  Helper structure to keep the trees of folders containing any file downloading or synchronizing.
  34  *
  35  *  A map provides the indexation based in hashing.
  36  *
  37  *  A tree is created per account.
  38  *
  39  * @author David A. Velasco
  40  */
  41 public class IndexedForest<V> {
  42
  43     private ConcurrentMap<String, Node<V>> mMap = new ConcurrentHashMap<String, Node<V>>();
  44
  45     private class Node<V> {
  46         String mKey = null;
  47         Node<V> mParent = null;
  48         Set<Node<V>> mChildren = new HashSet<Node<V>>();    // TODO be careful with hash()
  49         V mPayload = null;
  50
  51         // payload is optional
  52         public Node(String key, V payload) {
  53             if (key == null) {
  54                 throw new IllegalArgumentException("Argument key MUST NOT be null");
  55             }
  56             mKey = key;
  57             mPayload = payload;
  58         }
  59
  60         public Node<V> getParent() {
  61             return mParent;
  62         };
  63
  64         public Set<Node<V>> getChildren() {
  65             return mChildren;
  66         }
  67
  68         public String getKey() {
  69             return mKey;
  70         }
  71
  72         public V getPayload() {
  73             return mPayload;
  74         }
  75
  76         public void addChild(Node<V> child) {
  77             mChildren.add(child);
  78             child.setParent(this);
  79         }
  80
  81         private void setParent(Node<V> parent) {
  82             mParent = parent;
  83         }
  84
  85         public boolean hasChildren() {
  86             return mChildren.size() > 0;
  87         }
  88
  89         public void removeChild(Node<V> removed) {
  90             mChildren.remove(removed);
  91         }
  92
  93         public void clearPayload() {
  94             mPayload = null;
  95         }
  96     }
  97
  98
  99     public /* synchronized */ Pair<String, String> putIfAbsent(Account account, String remotePath, V value) {
 100         String targetKey = buildKey(account, remotePath);
 101         Node<V> valuedNode = new Node(targetKey, value);
 102         mMap.putIfAbsent(
 103                 targetKey,
 104                 valuedNode
 105         );
 106
 107         String currentPath = remotePath, parentPath = null, parentKey = null;
 108         Node<V> currentNode = valuedNode, parentNode = null;
 109         boolean linked = false;
 110         while (!OCFile.ROOT_PATH.equals(currentPath) && !linked) {
 111             parentPath = new File(currentPath).getParent();
 112             if (!parentPath.endsWith(OCFile.PATH_SEPARATOR)) {
 113                 parentPath += OCFile.PATH_SEPARATOR;
 114             }
 115             parentKey = buildKey(account, parentPath);
 116             parentNode = mMap.get(parentKey);
 117             if (parentNode == null) {
 118                 parentNode = new Node(parentKey, null);
 119                 parentNode.addChild(currentNode);
 120                 mMap.put(parentKey, parentNode);
 121             } else {
 122                 parentNode.addChild(currentNode);
 123                 linked = true;
 124             }
 125             currentPath = parentPath;
 126             currentNode = parentNode;
 127         }
 128
 129         String linkedTo = OCFile.ROOT_PATH;
 130         if (linked) {
 131             linkedTo = parentNode.getKey().substring(account.name.length());
 132         }
 133         return new Pair<String, String>(targetKey, linkedTo);
 134     };
 135
 136
 137     public Pair<V, String> removePayload(Account account, String remotePath) {
 138         String targetKey = buildKey(account, remotePath);
 139         Node<V> target = mMap.get(targetKey);
 140         if (target != null) {
 141             target.clearPayload();
 142             if (!target.hasChildren()) {
 143                 return remove(account, remotePath);
 144             }
 145         }
 146         return new Pair<V, String>(null, null);
 147     }
 148
 149
 150     public /* synchronized */ Pair<V, String> remove(Account account, String remotePath) {
 151         String targetKey = buildKey(account, remotePath);
 152         Node<V> firstRemoved = mMap.remove(targetKey);
 153         String unlinkedFrom = null;
 154
 155         if (firstRemoved != null) {
 156             /// remove children
 157             removeDescendants(firstRemoved);
 158
 159             /// remove ancestors if only here due to firstRemoved
 160             Node<V> removed = firstRemoved;
 161             Node<V> parent = removed.getParent();
 162             boolean unlinked = false;
 163             while (parent != null) {
 164                 parent.removeChild(removed);
 165                 if (!parent.hasChildren()) {
 166                     removed = mMap.remove(parent.getKey());
 167                     parent = removed.getParent();
 168                 } else {
 169                     break;
 170                 }
 171             }
 172
 173             if (parent != null) {
 174                 unlinkedFrom = parent.getKey().substring(account.name.length());
 175             }
 176
 177             return new Pair<V, String>(firstRemoved.getPayload(), unlinkedFrom);
 178         }
 179
 180         return new Pair<V, String>(null, null);
 181     }
 182
 183     private void removeDescendants(Node<V> removed) {
 184         Iterator<Node<V>> childrenIt = removed.getChildren().iterator();
 185         Node<V> child = null;
 186         while (childrenIt.hasNext()) {
 187             child = childrenIt.next();
 188             mMap.remove(child.getKey());
 189             removeDescendants(child);
 190         }
 191     }
 192
 193     public boolean contains(Account account, String remotePath) {
 194         String targetKey = buildKey(account, remotePath);
 195         return mMap.containsKey(targetKey);
 196     }
 197
 198     public /* synchronized */ V get(String key) {
 199         Node<V> node = mMap.get(key);
 200         if (node != null) {
 201             return node.getPayload();
 202         } else {
 203             return null;
 204         }
 205     }
 206
 207     public V get(Account account, String remotePath) {
 208         String key = buildKey(account, remotePath);
 209         return get(key);
 210     }
 211
 212
 213     /**
 214      * Builds a key to index files
 215      *
 216      * @param account       Account where the file to download is stored
 217      * @param remotePath    Path of the file in the server
 218      */
 219     private String buildKey(Account account, String remotePath) {
 220         return account.name + remotePath;
 221     }
 222
 223
 224
 225 }