From 222265e0c884d06158426e7d0ca033127cecb22f Mon Sep 17 00:00:00 2001
From: Anton Tananaev <anton.tananaev@gmail.com>
Date: Thu, 10 Mar 2016 15:29:26 +1300
Subject: Implement group tree structure

---
 src/org/traccar/database/GroupTree.java      | 106 +++++++++++++++++++++++++++
 test/org/traccar/database/GroupTreeTest.java |  37 ++++++++++
 2 files changed, 143 insertions(+)
 create mode 100644 src/org/traccar/database/GroupTree.java
 create mode 100644 test/org/traccar/database/GroupTreeTest.java

diff --git a/src/org/traccar/database/GroupTree.java b/src/org/traccar/database/GroupTree.java
new file mode 100644
index 000000000..7263a6331
--- /dev/null
+++ b/src/org/traccar/database/GroupTree.java
@@ -0,0 +1,106 @@
+/*
+ * Copyright 2016 Anton Tananaev (anton.tananaev@gmail.com)
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.traccar.database;
+
+import org.traccar.model.Group;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+public class GroupTree {
+
+    private static class GroupNode {
+
+        private Group group;
+        private GroupNode parent;
+        private Collection<GroupNode> children = new HashSet<>();
+
+        public GroupNode(Group group) {
+            this.group = group;
+        }
+
+        @Override
+        public int hashCode() {
+            return (int) group.getId();
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (!(obj instanceof GroupNode)) {
+                return false;
+            }
+            return obj == this || group.getId() == ((GroupNode) obj).group.getId();
+        }
+
+        public Group getGroup() {
+            return group;
+        }
+
+        public void setParent(GroupNode parent) {
+            this.parent = parent;
+            if (parent != null) {
+                parent.children.add(this);
+            }
+        }
+
+        public GroupNode getParent() {
+            return parent;
+        }
+
+        public Collection<GroupNode> getChildren() {
+            return children;
+        }
+
+    }
+
+    private final Map<Long, GroupNode> groupMap = new HashMap<>();
+
+    public GroupTree(Collection<Group> groups) {
+
+        for (Group group : groups) {
+            groupMap.put(group.getId(), new GroupNode(group));
+        }
+
+        for (GroupNode node : groupMap.values()) {
+            if (node.getGroup().getGroupId() != 0) {
+                node.setParent(groupMap.get(node.getGroup().getGroupId()));
+            }
+        }
+
+    }
+
+    public Collection<Group> getDescendants(long groupId) {
+        Set<GroupNode> results = new HashSet<>();
+        getDescendants(results, groupMap.get(groupId));
+        Collection<Group> groups = new ArrayList<>();
+        for (GroupNode node : results) {
+            groups.add(node.getGroup());
+        }
+        return groups;
+    }
+
+    private void getDescendants(Set<GroupNode> results, GroupNode node) {
+        for (GroupNode child : node.getChildren()) {
+            results.add(child);
+            getDescendants(results, child);
+        }
+    }
+
+}
diff --git a/test/org/traccar/database/GroupTreeTest.java b/test/org/traccar/database/GroupTreeTest.java
new file mode 100644
index 000000000..26ac595f8
--- /dev/null
+++ b/test/org/traccar/database/GroupTreeTest.java
@@ -0,0 +1,37 @@
+package org.traccar.database;
+
+import org.junit.Assert;
+import org.junit.Test;
+import org.traccar.model.Group;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+public class GroupTreeTest {
+
+    private static Group createGroup(long id, String name, long parent) {
+        Group group = new Group();
+        group.setId(id);
+        group.setName(name);
+        group.setGroupId(parent);
+        return group;
+    }
+    
+    @Test
+    public void testGetDescendants() {
+        Collection<Group> groups = new ArrayList<>();
+        groups.add(createGroup(1, "First", 0));
+        groups.add(createGroup(2, "Second", 1));
+        groups.add(createGroup(3, "Third", 2));
+        groups.add(createGroup(4, "Fourth", 2));
+        groups.add(createGroup(5, "Fifth", 4));
+
+        GroupTree groupTree = new GroupTree(groups);
+
+        Assert.assertEquals(4, groupTree.getDescendants(1).size());
+        Assert.assertEquals(3, groupTree.getDescendants(2).size());
+        Assert.assertEquals(0, groupTree.getDescendants(3).size());
+        Assert.assertEquals(1, groupTree.getDescendants(4).size());
+    }
+
+}
-- 
cgit v1.2.3