GetByRankRange returns nodes within specific rank range [start, end]. Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node If start is greater than end, the returned array is in reserved order If remove is true, the returned nodes are removed. Time complex
(start, end int, remove bool)
| 680 | // |
| 681 | // Time complexity of this method is : O(log(N)). |
| 682 | func (sl *SkipList) GetByRankRange(start, end int, remove bool) []*SkipListNode { |
| 683 | var ( |
| 684 | update [SkipListMaxLevel]*SkipListNode |
| 685 | nodes []*SkipListNode |
| 686 | traversed int |
| 687 | ) |
| 688 | |
| 689 | start, end = sl.sanitizeIndexes(start, end) |
| 690 | |
| 691 | reverse := start > end |
| 692 | if reverse { // swap start and end |
| 693 | start, end = end, start |
| 694 | } |
| 695 | |
| 696 | traversed = 0 |
| 697 | x := sl.header |
| 698 | for i := sl.level - 1; i >= 0; i-- { |
| 699 | for x.level[i].forward != nil && |
| 700 | traversed+int(x.level[i].span) < start { |
| 701 | traversed += int(x.level[i].span) |
| 702 | x = x.level[i].forward |
| 703 | } |
| 704 | if remove { |
| 705 | update[i] = x |
| 706 | } else { |
| 707 | if traversed+1 == start { |
| 708 | break |
| 709 | } |
| 710 | } |
| 711 | } |
| 712 | |
| 713 | traversed++ |
| 714 | x = x.level[0].forward |
| 715 | for x != nil && traversed <= end { |
| 716 | next := x.level[0].forward |
| 717 | |
| 718 | nodes = append(nodes, x) |
| 719 | |
| 720 | if remove { |
| 721 | sl.deleteNode(x, update) |
| 722 | } |
| 723 | |
| 724 | traversed++ |
| 725 | x = next |
| 726 | } |
| 727 | |
| 728 | if reverse { |
| 729 | for i, j := 0, len(nodes)-1; i < j; i, j = i+1, j-1 { |
| 730 | nodes[i], nodes[j] = nodes[j], nodes[i] |
| 731 | } |
| 732 | } |
| 733 | return nodes |
| 734 | } |
| 735 | |
| 736 | func (sl *SkipList) sanitizeIndexes(start, end int) (newStart, newEnd int) { |
| 737 | if start < 0 { |
no test coverage detected