만화 알고리즘: 점프 표 가 무엇 입 니까?
9350 단어 코드 노트
// Copyright (C) 2017
// 。
//
// :SkipList
// :
// :zhaoguanghui
// :2017/9/1
// :V1.0.0
//----------------------------------------------------------------*/
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
///
///
///
///
///
public class SkipList : IDictionary where TKey : IComparable
{
private SkipListNode head;
private int count;
public int Count { get { return count; } }
public bool IsReadOnly { get { return false; } }
public TValue this[TKey key]
{
get
{
return Get(key);
}
set
{
Add(key, value);
}
}
public ICollection Keys
{
get
{
List keys = new List(count);
WalkEntries(n => keys.Add(n.key));
return keys;
}
}
public ICollection Values
{
get
{
List values = new List(count);
WalkEntries(n => values.Add(n.value));
return values;
}
}
private struct SkipListKVPair
{
private W key;
public W Key
{
get { return key; }
}
public X Value;
public SkipListKVPair(W key, X value)
{
this.key = key;
this.Value = value;
}
}
private class SkipListNode
{
public SkipListNode forward, back, up, down;
public SkipListKVPair keyValue;
public bool isFront = false;
public TNKey key
{
get { return keyValue.Key; }
}
public TNValue value
{
get { return keyValue.Value; }
set { keyValue.Value = value; }
}
public SkipListNode()
{
this.keyValue = new SkipListKVPair(default(TNKey), default(TNValue));
this.isFront = true;
}
public SkipListNode(SkipListKVPair keyValue)
{
this.keyValue = keyValue;
}
public SkipListNode(TNKey key, TNValue value)
{
this.keyValue = new SkipListKVPair(key, value);
}
}
public SkipList()
{
this.head = new SkipListNode();
count = 0;
}
public void Add(TKey key, TValue value)
{
SkipListNode position;
bool found = Search(key, out position);
if (found)
position.value = value;
else
{
SkipListNode newEntry = new SkipListNode((TKey)key, value);
count++;
//
newEntry.back = position;
if (position.forward != null)
{
newEntry.forward = position.forward;
position.forward.back = newEntry;
}
position.forward = newEntry;
Promote(newEntry);
}
}
public void Add(KeyValuePair keyValue)
{
Add(keyValue.Key, keyValue.Value);
}
public void Clear()
{
head = new SkipListNode();
count = 0;
}
public bool ContainsKey(TKey key)
{
SkipListNode notused;
return Search(key, out notused);
}
public bool Contains(KeyValuePair keyValue)
{
return ContainsKey(keyValue.Key);
}
public bool Remove(TKey key)
{
SkipListNode position;
bool found = Search(key, out position);
if (!found)
return false;
else
{
SkipListNode old = position;
do
{
old.back.forward = old.forward;
if (old.forward != null)
old.forward.back = old.back;
old = old.up;
} while (old != null);
count--;
while (head.forward == null)
{
head = head.down;
}
return true;
}
}
public bool Remove(KeyValuePair keyValue)
{
return Remove(keyValue.Key);
}
public bool TryGetValue(TKey key, out TValue value)
{
try
{
value = Get(key);
return true;
}
catch (KeyNotFoundException)
{
value = default(TValue);
return false;
}
}
public void CopyTo(KeyValuePair[] array, int index)
{
if (array == null)
throw new ArgumentNullException("array");
if (index < 0)
throw new ArgumentOutOfRangeException("index");
if (array.IsReadOnly)
throw new ArgumentException("The array argument is Read Only and new items cannot be added to it.");
if (array.IsFixedSize && array.Length < count + index)
throw new ArgumentException("The array argument does not have sufficient space for the SkipList entries.");
int i = index;
WalkEntries(n => array[i++] = new KeyValuePair(n.key, n.value));
}
public IEnumerator> GetEnumerator()
{
SkipListNode position = head;
while (position.down != null)
position = position.down;
while (position.forward != null)
{
position = position.forward;
yield return new KeyValuePair(position.key, position.value);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return (IEnumerator)GetEnumerator();
}
private TValue Get(TKey key)
{
SkipListNode position;
bool found = Search(key, out position);
if (!found)
throw new KeyNotFoundException("Unable to find entry with key \"" + key.ToString() + "\"");
return position.value;
}
private void WalkEntries(Action> lambda)
{
SkipListNode node = head;
while (node.down != null)
node = node.down;
while (node.forward != null)
{
node = node.forward;
lambda(node);
}
}
private bool Search(TKey key, out SkipListNode position)
{
if (key == null)
throw new ArgumentNullException("key");
SkipListNode current;
position = current = head;
int num = 0;
while ((current.isFront || key.CompareTo(current.key) >= 0) && (current.forward != null || current.down != null))
{
position = current;
if (key.CompareTo(current.key) == 0)
return true;
if (current.forward == null || key.CompareTo(current.forward.key) < 0)
{
if (current.down == null)
return false;
else
current = current.down;
}
else
{
current = current.forward;
}
num++;
}
Debug.Log(num);
position = current;
if (key.CompareTo(position.key) == 0)
return true;
else
return false;
}
private void Promote(SkipListNode node)
{
SkipListNode back = node.back;
SkipListNode last = node;
for (int levels = this.Levels(); levels > 0; levels--)
{
while (back.up == null && !back.isFront)
{
back = back.back;
}
if (back.isFront && back.up == null)
{
back.up = new SkipListNode();
head = back.up;
}
back = back.up;
SkipListNode newNode = new SkipListNode(node.keyValue);
//
newNode.forward = back.forward;
if (newNode.forward != null)
{
newNode.forward.back = newNode;
}
//
newNode.back = back;
back.forward = newNode;
//
newNode.down = last;
last.up = newNode;
last = newNode;
}
}
private int Levels()
{
int levels = 0;
while (UnityEngine.Random.Range(0, 1f) < 0.5)
levels++;
return levels;
}
}