-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
PrimitiveSortedArraySet.java
93 lines (91 loc) · 2.78 KB
/
PrimitiveSortedArraySet.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
* Copyright (c) 2002-2017 "Neo Technology,"
* Network Engine for Objects in Lund AB [http://neotechnology.com]
*
* This file is part of Neo4j.
*
* Neo4j is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package org.neo4j.collection.primitive;
import java.util.Arrays;
public class PrimitiveSortedArraySet
{
/**
* Merges two sets of integers represented as sorted arrays.
*
* @param lhs
* a set of integers, represented as a sorted array.
* @param rhs
* a set of integers, represented as a sorted array.
* @return a set of integers, represented as a sorted array.
*/
public static int[] mergeSortedSet( int[] lhs, int[] rhs )
{
if ( lhs.length < rhs.length )
{
return mergeSortedSet( rhs, lhs );
}
int[] merged = null;
int m = 0;
for ( int l = 0, r = 0; l < lhs.length && r < rhs.length; )
{
while ( l < lhs.length && lhs[l] < rhs[r] )
{
if ( merged != null )
{
merged[m++] = lhs[l];
}
l++;
}
if ( l == lhs.length )
{
if ( merged == null )
{
merged = Arrays.copyOf( lhs, lhs.length + rhs.length - r );
m = l;
}
System.arraycopy( rhs, r, merged, m, rhs.length - r );
m += rhs.length - r;
break;
}
if ( lhs[l] > rhs[r] )
{
if ( merged == null )
{
merged = Arrays.copyOf( lhs, lhs.length + rhs.length - r );
m = l;
}
merged[m++] = rhs[r++];
}
else // i.e. ( lhs[l] == rhs[r] )
{
if ( merged != null )
{
merged[m++] = lhs[l];
}
l++;
r++;
}
}
if ( merged == null )
{
return lhs;
}
if ( merged.length < m )
{
merged = Arrays.copyOf( merged, m );
}
return merged;
}
}